brushbsp.c

quakeIII源码这个不用我多说吧

	for ( ; brushes; brushes = next)
	{
		next = brushes->next;

		FreeBrush(brushes);
	} //end for
} //end of the function FreeBrushList
//===========================================================================
// Duplicates the brush, the sides, and the windings
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
bspbrush_t *CopyBrush (bspbrush_t *brush)
{
	bspbrush_t *newbrush;
	int			size;
	int			i;
	
	size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);

	newbrush = AllocBrush (brush->numsides);
	memcpy (newbrush, brush, size);

	for (i=0 ; i<brush->numsides ; i++)
	{
		if (brush->sides[i].winding)
			newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);
	}

	return newbrush;
} //end of the function CopyBrush
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
node_t *PointInLeaf (node_t *node, vec3_t point)
{
	vec_t		d;
	plane_t		*plane;

	while (node->planenum != PLANENUM_LEAF)
	{
		plane = &mapplanes[node->planenum];
		d = DotProduct (point, plane->normal) - plane->dist;
		if (d > 0)
			node = node->children[0];
		else
			node = node->children[1];
	}

	return node;
} //end of the function PointInLeaf
//===========================================================================
// Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
#if 0
int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
{
	int		side;
	int		i;
	vec3_t	corners[2];
	vec_t	dist1, dist2;

	// axial planes are easy
	if (plane->type < 3)
	{
		side = 0;
		if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
			side |= PSIDE_FRONT;
		if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
			side |= PSIDE_BACK;
		return side;
	}

	// create the proper leading and trailing verts for the box

	for (i=0 ; i<3 ; i++)
	{
		if (plane->normal[i] < 0)
		{
			corners[0][i] = mins[i];
			corners[1][i] = maxs[i];
		}
		else
		{
			corners[1][i] = mins[i];
			corners[0][i] = maxs[i];
		}
	}

	dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
	dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
	side = 0;
	if (dist1 >= PLANESIDE_EPSILON)
		side = PSIDE_FRONT;
	if (dist2 < PLANESIDE_EPSILON)
		side |= PSIDE_BACK;

	return side;
}
#else
int BoxOnPlaneSide (vec3_t emins, vec3_t emaxs, plane_t *p)
{
	float	dist1, dist2;
	int sides;

	// axial planes are easy
	if (p->type < 3)
	{
		sides = 0;
		if (emaxs[p->type] > p->dist+PLANESIDE_EPSILON) sides |= PSIDE_FRONT;
		if (emins[p->type] < p->dist-PLANESIDE_EPSILON) sides |= PSIDE_BACK;
		return sides;
	} //end if
	
// general case
	switch (p->signbits)
	{
	case 0:
		dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
		dist2 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
		break;
	case 1:
		dist1 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
		dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
		break;
	case 2:
		dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
		dist2 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
		break;
	case 3:
		dist1 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
		dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
		break;
	case 4:
		dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
		dist2 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
		break;
	case 5:
		dist1 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
		dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
		break;
	case 6:
		dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
		dist2 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
		break;
	case 7:
		dist1 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
		dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
		break;
	default:
		dist1 = dist2 = 0;		// shut up compiler
//		assert( 0 );
		break;
	}

	sides = 0;
	if (dist1 - p->dist >= PLANESIDE_EPSILON) sides = PSIDE_FRONT;
	if (dist2 - p->dist < PLANESIDE_EPSILON) sides |= PSIDE_BACK;

//	assert(sides != 0);

	return sides;
}
#endif
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
{
	int i, num;
	plane_t *plane;
	int s;

	*numsplits = 0;

	plane = &mapplanes[planenum];

#ifdef ME
	//fast axial cases
	if (plane->type < 3)
	{
		if (plane->dist + PLANESIDE_EPSILON < brush->mins[plane->type])
			return PSIDE_FRONT;
		if (plane->dist - PLANESIDE_EPSILON > brush->maxs[plane->type])
			return PSIDE_BACK;
	} //end if
#endif //ME*/

	// if the brush actually uses the planenum,
	// we can tell the side for sure
	for (i = 0; i < brush->numsides; i++)
	{
		num = brush->sides[i].planenum;
		if (num >= MAX_MAPFILE_PLANES)
			Error ("bad planenum");
		if (num == planenum)
			return PSIDE_BACK|PSIDE_FACING;
		if (num == (planenum ^ 1) )
			return PSIDE_FRONT|PSIDE_FACING;

	}

	// box on plane side
	s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);

	// if both sides, count the visible faces split
	if (s == PSIDE_BOTH)
	{
		*numsplits += 3;
	}

	return s;
} //end of the function QuickTestBrushToPlanenum
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
						 int *numsplits, qboolean *hintsplit, int *epsilonbrush)
{
	int i, j, num;
	plane_t *plane;
	int s = 0;
	winding_t *w;
	vec_t d, d_front, d_back;
	int front, back;
	int type;
	float dist;

	*numsplits = 0;
	*hintsplit = false;

	plane = &mapplanes[planenum];

#ifdef ME
	//fast axial cases
	type = plane->type;
	if (type < 3)
	{
		dist = plane->dist;
		if (dist + PLANESIDE_EPSILON < brush->mins[type]) return PSIDE_FRONT;
		if (dist - PLANESIDE_EPSILON > brush->maxs[type]) return PSIDE_BACK;
		if (brush->mins[type] < dist - PLANESIDE_EPSILON &&
					brush->maxs[type] > dist + PLANESIDE_EPSILON) s = PSIDE_BOTH;
	} //end if

	if (s != PSIDE_BOTH)
#endif //ME
	{
		// if the brush actually uses the planenum,
		// we can tell the side for sure
		for (i = 0; i < brush->numsides; i++)
		{
			num = brush->sides[i].planenum;
			if (num >= MAX_MAPFILE_PLANES) Error ("bad planenum");
			if (num == planenum)
			{
				//we don't need to test this side plane again
				brush->sides[i].flags |= SFL_TESTED;
				return PSIDE_BACK|PSIDE_FACING;
			} //end if
			if (num == (planenum ^ 1) )
			{
				//we don't need to test this side plane again
				brush->sides[i].flags |= SFL_TESTED;
				return PSIDE_FRONT|PSIDE_FACING;
			} //end if
		} //end for

		// box on plane side
		s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);

		if (s != PSIDE_BOTH) return s;
	} //end if

	// if both sides, count the visible faces split
	d_front = d_back = 0;

	for (i = 0; i < brush->numsides; i++)
	{
		if (brush->sides[i].texinfo == TEXINFO_NODE)
			continue;		// on node, don't worry about splits
		if (!(brush->sides[i].flags & SFL_VISIBLE))
			continue;		// we don't care about non-visible
		w = brush->sides[i].winding;
		if (!w) continue;
		front = back = 0;
		for (j = 0; j < w->numpoints; j++)
		{
			d = DotProduct(w->p[j], plane->normal) - plane->dist;
			if (d > d_front) d_front = d;
			if (d < d_back) d_back = d;
			if (d > 0.1) // PLANESIDE_EPSILON)
				front = 1;
			if (d < -0.1) // PLANESIDE_EPSILON)
				back = 1;
		} //end for
		if (front && back)
		{
			if ( !(brush->sides[i].surf & SURF_SKIP) )
			{
				(*numsplits)++;
				if (brush->sides[i].surf & SURF_HINT)
				{
					*hintsplit = true;
				} //end if
			} //end if
		} //end if
	} //end for

	if ( (d_front > 0.0 && d_front < 1.0)
		|| (d_back < 0.0 && d_back > -1.0) )
		(*epsilonbrush)++;

#if 0
	if (*numsplits == 0)
	{	//	didn't really need to be split
		if (front) s = PSIDE_FRONT;
		else if (back) s = PSIDE_BACK;
		else s = 0;
	}
#endif

	return s;
} //end of the function TestBrushToPlanenum
//===========================================================================
// Returns true if the winding would be crunched out of
// existance by the vertex snapping.
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
#define	EDGE_LENGTH	0.2
qboolean WindingIsTiny (winding_t *w)
{
#if 0
	if (WindingArea (w) < 1)
		return true;
	return false;
#else
	int		i, j;
	vec_t	len;
	vec3_t	delta;
	int		edges;

	edges = 0;
	for (i=0 ; i<w->numpoints ; i++)
	{
		j = i == w->numpoints - 1 ? 0 : i+1;
		VectorSubtract (w->p[j], w->p[i], delta);
		len = VectorLength (delta);
		if (len > EDGE_LENGTH)
		{
			if (++edges == 3)
				return false;
		}
	}
	return true;
#endif
} //end of the function WindingIsTiny
//===========================================================================
// Returns true if the winding still has one of the points
// from basewinding for plane
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
qboolean WindingIsHuge (winding_t *w)
{
	int		i, j;

	for (i=0 ; i<w->numpoints ; i++)
	{
		for (j=0 ; j<3 ; j++)
			if (w->p[i][j] < -BOGUS_RANGE+1 || w->p[i][j] > BOGUS_RANGE-1)
				return true;
	}
	return false;
} //end of the function WindingIsHuge
//===========================================================================
// creates a leaf out of the given nodes with the given brushes
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void LeafNode(node_t *node, bspbrush_t *brushes)
{
	bspbrush_t *b;
	int i;

	node->side = NULL;
	node->planenum = PLANENUM_LEAF;
	node->contents = 0;

	for (b = brushes; b; b = b->next)
	{
		// if the brush is solid and all of its sides are on nodes,
		// it eats everything
		if (b->original->contents & CONTENTS_SOLID)
		{
			for (i=0 ; i<b->numsides ; i++)
				if (b->sides[i].texinfo != TEXINFO_NODE)
					break;
			if (i == b->numsides)
			{
				node->contents = CONTENTS_SOLID;
				break;
			} //end if
		} //end if
		node->contents |= b->original->contents;
	} //end for

	if (create_aas)
	{
		node->expansionbboxes = 0;
		node->contents = 0;
		for (b = brushes; b; b = b->next)
		{
			node->expansionbboxes |= b->original->expansionbbox;
			node->contents |= b->original->contents;
			if (b->original->modelnum)
				node->modelnum = b->original->modelnum;
		} //end for
		if (node->contents & CONTENTS_SOLID)
		{
			if (node->expansionbboxes != cfg.allpresencetypes)
			{
				node->contents &= ~CONTENTS_SOLID;
			} //end if
		} //end if
	} //end if

	node->brushlist = brushes;
} //end of the function LeafNode
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void CheckPlaneAgainstParents (int pnum, node_t *node)
{
	node_t	*p;

	for (p = node->parent; p; p = p->parent)
	{
		if (p->planenum == pnum) Error("Tried parent");
	} //end for
} //end of the function CheckPlaneAgainstParants
//===========================================================================