brushbsp.c

quakeIII源码这个不用我多说吧

//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
{
	bspbrush_t	*front, *back;
	qboolean	good;

	SplitBrush (node->volume, pnum, &front, &back);

	good = (front && back);

	if (front) FreeBrush (front);
	if (back) FreeBrush (back);

	return good;
} //end of the function CheckPlaneAgaintsVolume
//===========================================================================
// Using a hueristic, choses one of the sides out of the brushlist
// to partition the brushes with.
// Returns NULL if there are no valid planes to split with..
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
{
	int			value, bestvalue;
	bspbrush_t	*brush, *test;
	side_t		*side, *bestside;
	int			i, pass, numpasses;
	int			pnum;
	int			s;
	int			front, back, both, facing, splits;
	int			bsplits;
	int			bestsplits;
	int			epsilonbrush;
	qboolean	hintsplit = false;

	bestside = NULL;
	bestvalue = -99999;
	bestsplits = 0;

	// the search order goes: visible-structural, visible-detail,
	// nonvisible-structural, nonvisible-detail.
	// If any valid plane is available in a pass, no further
	// passes will be tried.
	numpasses = 2;
	for (pass = 0; pass < numpasses; pass++)
	{
		for (brush = brushes; brush; brush = brush->next)
		{
			// only check detail the second pass
//			if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
//				continue;
//			if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
//				continue;
			for (i = 0; i < brush->numsides; i++)
			{
				side = brush->sides + i;
//				if (side->flags & SFL_BEVEL)
//					continue;	// never use a bevel as a spliter
				if (!side->winding)
					continue;	// nothing visible, so it can't split
				if (side->texinfo == TEXINFO_NODE)
					continue;	// allready a node splitter
				if (side->flags & SFL_TESTED)
					continue;	// we allready have metrics for this plane
//				if (side->surf & SURF_SKIP)
//					continue;	// skip surfaces are never chosen

//				if (!(side->flags & SFL_VISIBLE) && (pass < 2))
//					continue;	// only check visible faces on first pass

				if ((side->flags & SFL_CURVE) && (pass < 1))
					continue;	// only check curves the second pass

				pnum = side->planenum;
				pnum &= ~1;	// allways use positive facing plane

				CheckPlaneAgainstParents (pnum, node);

				if (!CheckPlaneAgainstVolume (pnum, node))
					continue;	// would produce a tiny volume

				front = 0;
				back = 0;
				both = 0;
				facing = 0;
				splits = 0;
				epsilonbrush = 0;

				 //inner loop: optimize
				for (test = brushes; test; test = test->next)
				{
					s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);

					splits += bsplits;
//					if (bsplits && (s&PSIDE_FACING) )
//						Error ("PSIDE_FACING with splits");

					test->testside = s;
					//
					if (s & PSIDE_FACING) facing++;
					if (s & PSIDE_FRONT) front++;
					if (s & PSIDE_BACK) back++;
					if (s == PSIDE_BOTH) both++;
				} //end for

				// give a value estimate for using this plane
				value =  5*facing - 5*splits - abs(front-back);
//					value =  -5*splits;
//					value =  5*facing - 5*splits;
				if (mapplanes[pnum].type < 3)
					value+=5;		// axial is better

				value -= epsilonbrush * 1000;	// avoid!

				// never split a hint side except with another hint
				if (hintsplit && !(side->surf & SURF_HINT) )
					value = -9999999;

				// save off the side test so we don't need
				// to recalculate it when we actually seperate
				// the brushes
				if (value > bestvalue)
				{
					bestvalue = value;
					bestside = side;
					bestsplits = splits;
					for (test = brushes; test ; test = test->next)
						test->side = test->testside;
				} //end if
			} //end for
		} //end for (brush = brushes;

		// if we found a good plane, don't bother trying any
		// other passes
		if (bestside)
		{
			if (pass > 1)
			{
				if (numthreads == 1) c_nonvis++;
			}
			if (pass > 0) node->detail_seperator = true;	// not needed for vis
			break;
		} //end if
	} //end for (pass = 0;

	//
	// clear all the tested flags we set
	//
	for (brush = brushes ; brush ; brush=brush->next)
	{
		for (i = 0; i < brush->numsides; i++)
		{
			brush->sides[i].flags &= ~SFL_TESTED;
		} //end for
	} //end for

	return bestside;
} //end of the function SelectSplitSide
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
{
	int			i, j;
	winding_t	*w;
	vec_t		d, max;
	int			side;

	max = 0;
	side = PSIDE_FRONT;
	for (i=0 ; i<brush->numsides ; i++)
	{
		w = brush->sides[i].winding;
		if (!w)
			continue;
		for (j=0 ; j<w->numpoints ; j++)
		{
			d = DotProduct (w->p[j], plane->normal) - plane->dist;
			if (d > max)
			{
				max = d;
				side = PSIDE_FRONT;
			}
			if (-d > max)
			{
				max = -d;
				side = PSIDE_BACK;
			}
		}
	}
	return side;
} //end of the function BrushMostlyOnSide
//===========================================================================
// Generates two new brushes, leaving the original
// unchanged
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void SplitBrush (bspbrush_t *brush, int planenum,
	bspbrush_t **front, bspbrush_t **back)
{
	bspbrush_t	*b[2];
	int			i, j;
	winding_t	*w, *cw[2], *midwinding;
	plane_t		*plane, *plane2;
	side_t		*s, *cs;
	float d, d_front, d_back;

	*front = *back = NULL;
	plane = &mapplanes[planenum];

	// check all points
	d_front = d_back = 0;
	for (i=0 ; i<brush->numsides ; i++)
	{
		w = brush->sides[i].winding;
		if (!w)
			continue;
		for (j=0 ; j<w->numpoints ; j++)
		{
			d = DotProduct (w->p[j], plane->normal) - plane->dist;
			if (d > 0 && d > d_front)
				d_front = d;
			if (d < 0 && d < d_back)
				d_back = d;
		}
	}

	if (d_front < 0.2) // PLANESIDE_EPSILON)
	{	// only on back
		*back = CopyBrush (brush);
		return;
	}
	if (d_back > -0.2) // PLANESIDE_EPSILON)
	{	// only on front
		*front = CopyBrush (brush);
		return;
	}

	// create a new winding from the split plane

	w = BaseWindingForPlane (plane->normal, plane->dist);
	for (i=0 ; i<brush->numsides && w ; i++)
	{
		plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
		ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
	}

	if (!w || WindingIsTiny(w))
	{	// the brush isn't really split
		int		side;

		side = BrushMostlyOnSide (brush, plane);
		if (side == PSIDE_FRONT)
			*front = CopyBrush (brush);
		if (side == PSIDE_BACK)
			*back = CopyBrush (brush);
		//free a possible winding
		if (w) FreeWinding(w);
		return;
	}

	if (WindingIsHuge (w))
	{
		Log_Write("WARNING: huge winding\n");
	}

	midwinding = w;

	// split it for real

	for (i=0 ; i<2 ; i++)
	{
		b[i] = AllocBrush (brush->numsides+1);
		b[i]->original = brush->original;
	}

	// split all the current windings

	for (i=0 ; i<brush->numsides ; i++)
	{
		s = &brush->sides[i];
		w = s->winding;
		if (!w)
			continue;
		ClipWindingEpsilon (w, plane->normal, plane->dist,
			0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
		for (j=0 ; j<2 ; j++)
		{
			if (!cw[j])
				continue;
#if 0
			if (WindingIsTiny (cw[j]))
			{
				FreeWinding (cw[j]);
				continue;
			}
#endif
			cs = &b[j]->sides[b[j]->numsides];
			b[j]->numsides++;
			*cs = *s;
//			cs->planenum = s->planenum;
//			cs->texinfo = s->texinfo;
//			cs->original = s->original;
			cs->winding = cw[j];
			cs->flags &= ~SFL_TESTED;
		}
	}


	// see if we have valid polygons on both sides

	for (i=0 ; i<2 ; i++)
	{
		BoundBrush (b[i]);
		for (j=0 ; j<3 ; j++)
		{
			if (b[i]->mins[j] < -MAX_MAP_BOUNDS || b[i]->maxs[j] > MAX_MAP_BOUNDS)
			{
				Log_Write("bogus brush after clip");
				break;
			}
		}

		if (b[i]->numsides < 3 || j < 3)
		{
			FreeBrush (b[i]);
			b[i] = NULL;
		}
	}

	if ( !(b[0] && b[1]) )
	{
		if (!b[0] && !b[1])
			Log_Write("split removed brush\r\n");
		else
			Log_Write("split not on both sides\r\n");
		if (b[0])
		{
			FreeBrush (b[0]);
			*front = CopyBrush (brush);
		}
		if (b[1])
		{
			FreeBrush (b[1]);
			*back = CopyBrush (brush);
		}
		return;
	}

	// add the midwinding to both sides
	for (i=0 ; i<2 ; i++)
	{
		cs = &b[i]->sides[b[i]->numsides];
		b[i]->numsides++;

		cs->planenum = planenum^i^1;
		cs->texinfo = TEXINFO_NODE; //never use these sides as splitters
		cs->flags &= ~SFL_VISIBLE;
		cs->flags &= ~SFL_TESTED;
		if (i==0)
			cs->winding = CopyWinding (midwinding);
		else
			cs->winding = midwinding;
	}

{
	vec_t	v1;
	int i;

	for (i = 0; i < 2; i++)
	{
		v1 = BrushVolume (b[i]);
		if (v1 < 1.0)
		{
			FreeBrush(b[i]);
			b[i] = NULL;
			//Log_Write("tiny volume after clip");
		}
	}
	if (!b[0] && !b[1])
	{
		Log_Write("two tiny brushes\r\n");
	} //end if
}

	*front = b[0];
	*back = b[1];
} //end of the function SplitBrush
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void SplitBrushList (bspbrush_t *brushes, 
	node_t *node, bspbrush_t **front, bspbrush_t **back)
{
	bspbrush_t	*brush, *newbrush, *newbrush2;
	side_t		*side;
	int			sides;
	int			i;

	*front = *back = NULL;

	for (brush = brushes; brush; brush = brush->next)
	{
		sides = brush->side;

		if (sides == PSIDE_BOTH)
		{	// split into two brushes
			SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
			if (newbrush)
			{
				newbrush->next = *front;
				*front = newbrush;
			} //end if
			if (newbrush2)
			{
				newbrush2->next = *back;
				*back = newbrush2;
			} //end if
			continue;
		} //end if

		newbrush = CopyBrush (brush);

		// if the planenum is actualy a part of the brush
		// find the plane and flag it as used so it won't be tried
		// as a splitter again
		if (sides & PSIDE_FACING)
		{
			for (i=0 ; i<newbrush->numsides ; i++)
			{
				side = newbrush->sides + i;
				if ( (side->planenum& ~1) == node->planenum)
					side->texinfo = TEXINFO_NODE;
			} //end for
		} //end if
		if (sides & PSIDE_FRONT)
		{
			newbrush->next = *front;
			*front = newbrush;
			continue;
		} //end if
		if (sides & PSIDE_BACK)
		{
			newbrush->next = *back;
			*back = newbrush;
			continue;
		} //end if
	} //end for
} //end of the function SplitBrushList
//===========================================================================
//
// Parameter:			-