csg.cpp

hl2 source code. Do not use it illegal.

#include "vbsp.h"

/*

tag all brushes with original contents
brushes may contain multiple contents
there will be no brush overlap after csg phase




each side has a count of the other sides it splits

the best split will be the one that minimizes the total split counts
of all remaining sides

precalc side on plane table

evaluate split side
{
cost = 0
for all sides
	for all sides
		get 
		if side splits side and splitside is on same child
			cost++;
}


  */

void SplitBrush2( bspbrush_t *brush, int planenum, bspbrush_t **front, bspbrush_t **back )
{
	SplitBrush( brush, planenum, front, back );
#if 0
	if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)
		(*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo;	// not -1
	if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)
		(*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo;	// not -1
#endif
}

/*
===============
SubtractBrush

Returns a list of brushes that remain after B is subtracted from A.
May by empty if A is contained inside B.

The originals are undisturbed.
===============
*/
bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
{	// a - b = out (list)
	int		i;
	bspbrush_t	*front, *back;
	bspbrush_t	*out, *in;

	in = a;
	out = NULL;
	for (i=0 ; i<b->numsides && in ; i++)
	{
		SplitBrush2 (in, b->sides[i].planenum, &front, &back);
		if (in != a)
			FreeBrush (in);
		if (front)
		{	// add to list
			front->next = out;
			out = front;
		}
		in = back;
	}
	if (in)
		FreeBrush (in);
	else
	{	// didn't really intersect
		FreeBrushList (out);
		return a;
	}
	return out;
}

/*
===============
IntersectBrush

Returns a single brush made up by the intersection of the
two provided brushes, or NULL if they are disjoint.

The originals are undisturbed.
===============
*/
bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)
{
	int		i;
	bspbrush_t	*front, *back;
	bspbrush_t	*in;

	in = a;
	for (i=0 ; i<b->numsides && in ; i++)
	{
		SplitBrush2 (in, b->sides[i].planenum, &front, &back);
		if (in != a)
			FreeBrush (in);
		if (front)
			FreeBrush (front);
		in = back;
	}

	if (in == a)
		return NULL;

	in->next = NULL;
	return in;
}


/*
===============
BrushesDisjoint

Returns true if the two brushes definately do not intersect.
There will be false negatives for some non-axial combinations.
===============
*/
qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)
{
	int		i, j;

	// check bounding boxes
	for (i=0 ; i<3 ; i++)
		if (a->mins[i] >= b->maxs[i]
		|| a->maxs[i] <= b->mins[i])
			return true;	// bounding boxes don't overlap

	// check for opposing planes
	for (i=0 ; i<a->numsides ; i++)
	{
		for (j=0 ; j<b->numsides ; j++)
		{
			if (a->sides[i].planenum ==
			(b->sides[j].planenum^1) )
				return true;	// opposite planes, so not touching
		}
	}

	return false;	// might intersect
}

/*
===============
IntersectionContents

Returns a content word for the intersection of two brushes.
Some combinations will generate a combination (water + clip),
but most will be the stronger of the two contents.
===============
*/
int	IntersectionContents (int c1, int c2)
{
	int		out;

	out = c1 | c2;

	if (out & CONTENTS_SOLID)
		out = CONTENTS_SOLID;

	return out;
}


int		minplanenums[3];
int		maxplanenums[3];

/*
===============
ClipBrushToBox

Any planes shared with the box edge will be set to no texinfo
===============
*/
bspbrush_t	*ClipBrushToBox (bspbrush_t *brush, const Vector& clipmins, const Vector& clipmaxs)
{
	int		i, j;
	bspbrush_t	*front,	*back;
	int		p;

	for (j=0 ; j<2 ; j++)
	{
		if (brush->maxs[j] > clipmaxs[j])
		{
			SplitBrush (brush, maxplanenums[j], &front, &back);
			if (front)
				FreeBrush (front);
			brush = back;
			if (!brush)
				return NULL;
		}
		if (brush->mins[j] < clipmins[j])
		{
			SplitBrush (brush, minplanenums[j], &front, &back);
			if (back)
				FreeBrush (back);
			brush = front;
			if (!brush)
				return NULL;
		}
	}

	// remove any colinear faces

	for (i=0 ; i<brush->numsides ; i++)
	{
		p = brush->sides[i].planenum & ~1;
		if (p == maxplanenums[0] || p == maxplanenums[1] 
			|| p == minplanenums[0] || p == minplanenums[1])
		{
			brush->sides[i].texinfo = TEXINFO_NODE;
			brush->sides[i].visible = false;
		}
	}
	return brush;
}


//-----------------------------------------------------------------------------
// Creates a clipped brush from a map brush
//-----------------------------------------------------------------------------
static bspbrush_t *CreateClippedBrush( mapbrush_t *mb, const Vector& clipmins, const Vector& clipmaxs )
{
	int nNumSides = mb->numsides;
	if (!nNumSides)
		return NULL;

	// if the brush is outside the clip area, skip it
	for (int j=0 ; j<3 ; j++)
	{
		if (mb->mins[j] >= clipmaxs[j] || mb->maxs[j] <= clipmins[j])
		{
			return NULL;
		}
	}

	// make a copy of the brush
	bspbrush_t *newbrush = AllocBrush( nNumSides );
	newbrush->original = mb;
	newbrush->numsides = nNumSides;
	memcpy (newbrush->sides, mb->original_sides, nNumSides*sizeof(side_t));

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

		if (newbrush->sides[j].surf & SURF_HINT)
		{
			newbrush->sides[j].visible = true;	// hints are always visible
		}

        // keep a pointer to the original map brush side -- use to create the original face later!!
        //newbrush->sides[j].original = &mb->original_sides[j];
	}

	VectorCopy (mb->mins, newbrush->mins);
	VectorCopy (mb->maxs, newbrush->maxs);

	// carve off anything outside the clip box
	newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
	return newbrush;
}


//-----------------------------------------------------------------------------
// Creates a clipped brush from a map brush
//-----------------------------------------------------------------------------
static void ComputeBoundingPlanes( const Vector& clipmins, const Vector& clipmaxs )
{
	Vector normal;
	float dist;
	for (int i=0 ; i<2 ; i++)
	{
		VectorClear (normal);
		normal[i] = 1;
		dist = clipmaxs[i];
		maxplanenums[i] = FindFloatPlane (normal, dist);
		dist = clipmins[i];
		minplanenums[i] = FindFloatPlane (normal, dist);
	}
}


// This forces copies of texinfo data for matching sides of a brush
void CopyMatchingTexinfos( bspbrush_t *pDest, const bspbrush_t *pSource )
{
	for ( int i = 0; i < pDest->numsides; i++ )
	{
		side_t *pSide = &pDest->sides[i];
		plane_t *pPlane = &mapplanes[pSide->planenum];
		bool found = false;
		for ( int j = 0; j < pSource->numsides; j++ )
		{
			const side_t *pSourceSide = &pSource->sides[j];
			plane_t *pSourcePlane = &mapplanes[pSourceSide->planenum];

			float dot = DotProduct( pPlane->normal, pSourcePlane->normal );
			if ( dot == 1.0 || pSide->planenum == pSourceSide->planenum )
			{
				found = true;
				pSide->texinfo = pSourceSide->texinfo;
				if ( pSide->original )
				{
					pSide->original->texinfo = pSide->texinfo;
				}
				break;
			}
		}
		if ( !found )
		{
			texinfo_t *pTexInfo = &texinfo[pSide->texinfo];
			dtexdata_t *pTexData = GetTexData( pTexInfo->texdata );
			Msg("Found no matching plane for %s\n", TexDataStringTable_GetString( pTexData->nameStringTableID ) );
		}
	}
}

// This is a hack to allow areaportals to work in water
// It was done this way for ease of implementation.
// This searches a brush list to find intersecting areaportals and water
// If an areaportal is found inside water, then the water contents and 
// texture information is copied over to the areaportal so that the 
// resulting space has the same properties as the water (normal areaportals assume "empty" surroundings)
void FixupAreaportalWaterBrushes( bspbrush_t *pList )
{
	for ( bspbrush_t *pAreaportal = pList; pAreaportal; pAreaportal = pAreaportal->next )
	{
		if ( !(pAreaportal->original->contents & CONTENTS_AREAPORTAL) )
			continue;

		for ( bspbrush_t *pWater = pList; pWater; pWater = pWater->next )
		{
			if ( !(pWater->original->contents & CONTENTS_WATER) )
				continue;
			if ( BrushesDisjoint( pAreaportal, pWater ) )
				continue;

			bspbrush_t *pIntersect = IntersectBrush( pAreaportal, pWater );
			if ( !pIntersect )
				continue;
			FreeBrush( pIntersect );
			pAreaportal->original->contents |= pWater->original->contents;
			CopyMatchingTexinfos( pAreaportal, pWater );
		}
	}
}

//-----------------------------------------------------------------------------
// MakeBspBrushList 
//-----------------------------------------------------------------------------
// UNDONE: Put detail brushes in a separate brush array and pass that instead of "onlyDetail" ?
bspbrush_t *MakeBspBrushList (int startbrush, int endbrush, const Vector& clipmins, const Vector& clipmaxs, int detailScreen)
{
	ComputeBoundingPlanes( clipmins, clipmaxs );

	bspbrush_t	*pBrushList = NULL;

	int i;
	for (i=startbrush ; i<endbrush ; i++)
	{
		mapbrush_t *mb = &mapbrushes[i];

		if ( detailScreen != FULL_DETAIL )
		{
			bool onlyDetail = (detailScreen == ONLY_DETAIL);
			bool detail = (mb->contents & CONTENTS_DETAIL) != 0;
			if ( onlyDetail ^ detail )
			{
				// both of these must have the same value or we're not interested in this brush
				continue;
			}
		}

		bspbrush_t *pNewBrush = CreateClippedBrush( mb, clipmins, clipmaxs );
		if ( pNewBrush )
		{
			pNewBrush->next = pBrushList;
			pBrushList = pNewBrush;
		}
	}

	return pBrushList;
}


//-----------------------------------------------------------------------------
// A version which uses a passed-in list of brushes 
//-----------------------------------------------------------------------------
bspbrush_t *MakeBspBrushList (mapbrush_t **pBrushes, int nBrushCount, const Vector& clipmins, const Vector& clipmaxs)
{
	ComputeBoundingPlanes( clipmins, clipmaxs );

	bspbrush_t	*pBrushList = NULL;
	for ( int i=0; i < nBrushCount; ++i )
	{
		bspbrush_t *pNewBrush = CreateClippedBrush( pBrushes[i], clipmins, clipmaxs );
		if ( pNewBrush )
		{
			pNewBrush->next = pBrushList;
			pBrushList = pNewBrush;
		}
	}

	return pBrushList;