qc/tools/compilers/aas/Brush.cpp

/*
===========================================================================

Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company. 

This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).  

Doom 3 Source Code is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Doom 3 Source Code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.

In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.

If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.

===========================================================================
*/

#include "../../../idlib/precompiled.h"
#pragma hdrstop

#include "Brush.h"

#define BRUSH_EPSILON					0.1f
#define BRUSH_PLANE_NORMAL_EPSILON		0.00001f
#define BRUSH_PLANE_DIST_EPSILON		0.01f

#define OUTPUT_UPDATE_TIME				500		// update every 500 msec

//#define OUTPUT_CHOP_STATS

/*
============
DisplayRealTimeString
============
*/
void DisplayRealTimeString( char *string, ... ) {
	va_list argPtr;
	char buf[MAX_STRING_CHARS];
	static int lastUpdateTime;
	int time;

	time = Sys_Milliseconds();
	if ( time > lastUpdateTime + OUTPUT_UPDATE_TIME ) {
		va_start( argPtr, string );
		vsprintf( buf, string, argPtr );
		va_end( argPtr );
		common->Printf( buf );
		lastUpdateTime = time;
	}
}


//===============================================================
//
//	idBrushSide
//
//===============================================================

/*
============
idBrushSide::idBrushSide
============
*/
idBrushSide::idBrushSide( void ) {
	flags = 0;
	planeNum = -1;
	winding = NULL;
}

/*
============
idBrushSide::idBrushSide
============
*/
idBrushSide::idBrushSide( const idPlane &plane, int planeNum ) {
	this->flags = 0;
	this->plane = plane;
	this->planeNum = planeNum;
	this->winding = NULL;
}

/*
============
idBrushSide::~idBrushSide
============
*/
idBrushSide::~idBrushSide( void ) {
	if ( winding ) {
		delete winding;
	}
}

/*
============
idBrushSide::Copy
============
*/
idBrushSide *idBrushSide::Copy( void ) const {
	idBrushSide *side;

	side = new idBrushSide( plane, planeNum );
	side->flags = flags;
	if ( winding ) {
		side->winding = winding->Copy();
	}
	else {
		side->winding = NULL;
	}
	return side;
}

/*
============
idBrushSide::Split
============
*/
int idBrushSide::Split( const idPlane &splitPlane, idBrushSide **front, idBrushSide **back ) const {
	idWinding *frontWinding, *backWinding;

	assert( winding );

	*front = *back = NULL;

	winding->Split( splitPlane, 0.0f, &frontWinding, &backWinding );

	if ( frontWinding ) {
		(*front) = new idBrushSide( plane, planeNum );
		(*front)->winding = frontWinding;
		(*front)->flags = flags;
	}

	if ( backWinding ) {
		(*back) = new idBrushSide( plane, planeNum );
		(*back)->winding = backWinding;
		(*back)->flags = flags;
	}

	if ( frontWinding && backWinding ) {
		return PLANESIDE_CROSS;
	}
	else if ( frontWinding ) {
		return PLANESIDE_FRONT;
	}
	else {
		return PLANESIDE_BACK;
	}
}


//===============================================================
//
//	idBrushSide
//
//===============================================================

/*
============
idBrush::idBrush
============
*/
idBrush::idBrush( void ) {
	contents = flags = 0;
	bounds.Clear();
	sides.Clear();
	windingsValid = false;
}


/*
============
idBrush::~idBrush
============
*/
idBrush::~idBrush( void ) {
	for ( int i = 0; i < sides.Num(); i++ ) {
		delete sides[i];
	}
}

/*
============
idBrush::RemoveSidesWithoutWinding
============
*/
bool idBrush::RemoveSidesWithoutWinding( void ) {
	int i;

	for ( i = 0; i < sides.Num(); i++ ) {

		if ( sides[i]->winding ) {
			continue;
		}

		sides.RemoveIndex( i );
		i--;
	}

	return ( sides.Num() >= 4 );
}

/*
============
idBrush::CreateWindings
============
*/
bool idBrush::CreateWindings( void ) {
	int i, j;
	idBrushSide *side;

	bounds.Clear();
	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];

		if ( side->winding ) {
			delete side->winding;
		}

		side->winding = new idWinding( side->plane.Normal(), side->plane.Dist() );

		for ( j = 0; j < sides.Num() && side->winding; j++ ) {
			if ( i == j ) {
				continue;
			}
			// keep the winding if on the clip plane
			side->winding = side->winding->Clip( -sides[j]->plane, BRUSH_EPSILON, true );
		}

		if ( side->winding ) {
			for ( j = 0; j < side->winding->GetNumPoints(); j++ ) {
				bounds.AddPoint( (*side->winding)[j].ToVec3() );
			}
		}
	}

	if ( bounds[0][0] > bounds[1][0] ) {
		return false;
	}
	for ( i = 0; i < 3; i++ ) {
		if ( bounds[0][i] < MIN_WORLD_COORD || bounds[1][i] > MAX_WORLD_COORD ) {
			return false;
		}
	}

	windingsValid = true;

	return true;
}

/*
============
idBrush::BoundBrush
============
*/
void idBrush::BoundBrush( const idBrush *original ) {
	int i, j;
	idBrushSide *side;
	idWinding *w;

	assert( windingsValid );

	bounds.Clear();
	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];

		w = side->winding;

		if ( !w ) {
			continue;
		}

		for ( j = 0; j < w->GetNumPoints(); j++ ) {
			bounds.AddPoint( (*w)[j].ToVec3() );
		}
	}

	if ( bounds[0][0] > bounds[1][0] ) {
		if ( original ) {
			idBrushMap *bm = new idBrushMap( "error_brush", "_original" );
			bm->WriteBrush( original );
			delete bm;
		}
		common->Error( "idBrush::BoundBrush: brush %d on entity %d without windings", primitiveNum, entityNum );
	}

	for ( i = 0; i < 3; i++ ) {
		if ( bounds[0][i] < MIN_WORLD_COORD || bounds[1][i] > MAX_WORLD_COORD ) {
			if ( original ) {
				idBrushMap *bm = new idBrushMap( "error_brush", "_original" );
				bm->WriteBrush( original );
				delete bm;
			}
			common->Error( "idBrush::BoundBrush: brush %d on entity %d is unbounded", primitiveNum, entityNum );
		}
	}
}

/*
============
idBrush::FromSides
============
*/
bool idBrush::FromSides( idList<idBrushSide *> &sideList ) {
	int i;

	for ( i = 0; i < sideList.Num(); i++ ) {
		sides.Append( sideList[i] );
	}

	sideList.Clear();

	return CreateWindings();
}

/*
============
idBrush::FromWinding
============
*/
bool idBrush::FromWinding( const idWinding &w, const idPlane &windingPlane ) {
	int i, j, bestAxis;
	idPlane plane;
	idVec3 normal, axialNormal;

	sides.Append( new idBrushSide( windingPlane, -1 ) );
	sides.Append( new idBrushSide( -windingPlane, -1 ) );

	bestAxis = 0;
	for ( i = 1; i < 3; i++ ) {
		if ( idMath::Fabs( windingPlane.Normal()[i] ) > idMath::Fabs( windingPlane.Normal()[bestAxis] ) ) {
			bestAxis = i;
		}
	}
	axialNormal = vec3_origin;
	if ( windingPlane.Normal()[bestAxis] > 0.0f ) {
		axialNormal[bestAxis] = 1.0f;
	}
	else {
		axialNormal[bestAxis] = -1.0f;
	}

	for ( i = 0; i < w.GetNumPoints(); i++ ) {
		j = (i+1) % w.GetNumPoints();
		normal = ( w[j].ToVec3() - w[i].ToVec3() ).Cross( axialNormal );
		if ( normal.Normalize() < 0.5f ) {
			continue;
		}
		plane.SetNormal( normal );
		plane.FitThroughPoint( w[j].ToVec3() );
		sides.Append( new idBrushSide( plane, -1 ) );
	}

	if ( sides.Num() < 4 ) {
		for ( i = 0; i < sides.Num(); i++ ) {
			delete sides[i];
		}
		sides.Clear();
		return false;
	}

	sides[0]->winding = w.Copy();
	windingsValid = true;
	BoundBrush();

	return true;
}

/*
============
idBrush::FromBounds
============
*/
bool idBrush::FromBounds( const idBounds &bounds ) {
	int axis, dir;
	idVec3 normal;
	idPlane plane;

	for ( axis = 0; axis < 3; axis++ ) {
		for ( dir = -1; dir <= 1; dir += 2 ) {
			normal = vec3_origin;
			normal[axis] = dir;
			plane.SetNormal( normal );
			plane.SetDist( dir * bounds[(dir == 1)][axis] );
			sides.Append( new idBrushSide( plane, -1 ) );
		}
	}

	return CreateWindings();
}

/*
============
idBrush::Transform
============
*/
void idBrush::Transform( const idVec3 &origin, const idMat3 &axis ) {
	int i;
	bool transformed = false;

	if ( axis.IsRotated() ) {
		for ( i = 0; i < sides.Num(); i++ ) {
			sides[i]->plane.RotateSelf( vec3_origin, axis );
		}
		transformed = true;
	}
	if ( origin != vec3_origin ) {
		for ( i = 0; i < sides.Num(); i++ ) {
			sides[i]->plane.TranslateSelf( origin );
		}
		transformed = true;
	}
	if ( transformed ) {
		CreateWindings();
	}
}

/*
============
idBrush::GetVolume
============
*/
float idBrush::GetVolume( void ) const {
	int i;
	idWinding *w;
	idVec3 corner;
	float d, area, volume;

	// grab the first valid point as a corner
	w = NULL;
	for ( i = 0; i < sides.Num(); i++ ) {
		w = sides[i]->winding;
		if ( w ) {
			break;
		}
	}
	if ( !w ) {
		return 0.0f;
	}
	corner = (*w)[0].ToVec3();

	// create tetrahedrons to all other sides
	volume = 0.0f;
	for ( ; i < sides.Num(); i++) {
		w = sides[i]->winding;
		if ( !w ) {
			continue;
		}
		d = -( corner * sides[i]->plane.Normal() - sides[i]->plane.Dist() );
		area = w->GetArea();
		volume += d * area;
	}

	return ( volume * ( 1.0f / 3.0f ) );
}

/*
============
idBrush::Subtract
============
*/
bool idBrush::Subtract( const idBrush *b, idBrushList &list ) const {
	int i;
	idBrush *front, *back;
	const idBrush *in;

	list.Clear();
	in = this;
	for ( i = 0; i < b->sides.Num() && in; i++ ) {

		in->Split( b->sides[i]->plane, b->sides[i]->planeNum, &front, &back );

		if ( in != this ) {
			delete in;
		}
		if ( front ) {
			list.AddToTail( front );
		}
		in = back;
	}
	// if didn't really intersect
	if ( !in ) {
		list.Free();
		return false;
	}

	delete in;
	return true;
}

/*
============
idBrush::TryMerge
============
*/
bool idBrush::TryMerge( const idBrush *brush, const idPlaneSet &planeList ) {
	int i, j, k, l, m, seperatingPlane;
	const idBrush *brushes[2];
	const idWinding *w;
	const idPlane *plane;

	// brush bounds should overlap
	for ( i = 0; i < 3; i++ ) {
		if ( bounds[0][i] > brush->bounds[1][i] + 0.1f ) {
			return false;
		}
		if ( bounds[1][i] < brush->bounds[0][i] - 0.1f ) {
			return false;
		}
	}

	// the brushes should share an opposite plane
	seperatingPlane = -1;
	for ( i = 0; i < GetNumSides(); i++ ) {
		for ( j = 0; j < brush->GetNumSides(); j++ ) {
			if ( GetSide(i)->GetPlaneNum() == (brush->GetSide(j)->GetPlaneNum() ^ 1) ) {
				// may only have one seperating plane
				if ( seperatingPlane != -1 ) {
					return false;
				}
				seperatingPlane = GetSide(i)->GetPlaneNum();
				break;
			}
		}
	}
	if ( seperatingPlane == -1 ) {
		return false;
	}

	brushes[0] = this;
	brushes[1] = brush;

	for ( i = 0; i < 2; i++ ) {

		j = !i;

		for ( k = 0; k < brushes[i]->GetNumSides(); k++ ) {

			// if the brush side plane is the seprating plane
			if ( !( ( brushes[i]->GetSide(k)->GetPlaneNum() ^ seperatingPlane ) >> 1 ) ) {
				continue;
			}

			plane = &brushes[i]->GetSide(k)->GetPlane();

			// all the non seperating brush sides of the other brush should be at the back or on the plane
			for ( l = 0; l < brushes[j]->GetNumSides(); l++ ) {

				w = brushes[j]->GetSide(l)->GetWinding();
				if ( !w ) {
					continue;
				}

				if ( !( ( brushes[j]->GetSide(l)->GetPlaneNum() ^ seperatingPlane ) >> 1 ) ) {
					continue;
				}

				for ( m = 0; m < w->GetNumPoints(); m++ ) {
					if ( plane->Distance( (*w)[m].ToVec3() ) > 0.1f ) {
						return false;
					}
				}
			}
		}
	}

	// add any sides from the other brush to this brush
	for ( i = 0; i < brush->GetNumSides(); i++ ) {
		for ( j = 0; j < GetNumSides(); j++ ) {
			if ( !( ( brush->GetSide(i)->GetPlaneNum() ^ GetSide(j)->GetPlaneNum() ) >> 1 ) ) {
				break;
			}
		}
		if ( j < GetNumSides() ) {
			sides[j]->flags &= brush->GetSide(i)->GetFlags();
			continue;
		}
		sides.Append( brush->GetSide(i)->Copy() );
	}

	// remove any side from this brush that is the opposite of a side of the other brush
	for ( i = 0; i < GetNumSides(); i++ ) {
		for ( j = 0; j < brush->GetNumSides(); j++ ) {
			if ( GetSide(i)->GetPlaneNum() == ( brush->GetSide(j)->GetPlaneNum() ^ 1 ) ) {
				break;
			}
		}
		if ( j < brush->GetNumSides() ) {
			delete sides[i];
			sides.RemoveIndex(i);
			i--;
			continue;
		}
	}

	contents |= brush->contents;

	CreateWindings();
	BoundBrush();

	return true;
}

/*
============
idBrush::Split
============
*/
int idBrush::Split( const idPlane &plane, int planeNum, idBrush **front, idBrush **back ) const {
	int res, i, j;
	idBrushSide *side, *frontSide, *backSide;
	float dist, maxBack, maxFront, *maxBackWinding, *maxFrontWinding;
	idWinding *w, *mid;

	assert( windingsValid );

	if ( front ) {
		*front = NULL;
	}
	if ( back ) {
		*back = NULL;
	}

	res = bounds.PlaneSide( plane, -BRUSH_EPSILON );
	if ( res == PLANESIDE_FRONT ) {
		if ( front ) {
			*front = Copy();
		}
		return res;
	}
	if ( res == PLANESIDE_BACK ) {
		if ( back ) {
			*back = Copy();
		}
		return res;
	}

	maxBackWinding = (float *) _alloca16( sides.Num() * sizeof(float) );
	maxFrontWinding = (float *) _alloca16( sides.Num() * sizeof(float) );

	maxFront = maxBack = 0.0f;
	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];

		w = side->winding;

		if ( !w ) {
			continue;
		}

		maxBackWinding[i] = 10.0f;
		maxFrontWinding[i] = -10.0f;

		for ( j = 0; j < w->GetNumPoints(); j++ ) {

			dist = plane.Distance( (*w)[j].ToVec3() );
			if ( dist > maxFrontWinding[i] ) {
				maxFrontWinding[i] = dist;
			}
			if ( dist < maxBackWinding[i] ) {
				maxBackWinding[i] = dist;
			}
		}

		if ( maxFrontWinding[i] > maxFront ) {
			maxFront = maxFrontWinding[i];
		}
		if ( maxBackWinding[i] < maxBack ) {
			maxBack = maxBackWinding[i];
		}
	}

	if ( maxFront < BRUSH_EPSILON ) {
		if ( back ) {
			*back = Copy();
		}
		return PLANESIDE_BACK;
	}

	if ( maxBack > -BRUSH_EPSILON ) {
		if ( front ) {
			*front = Copy();
		}
		return PLANESIDE_FRONT;
	}

	mid = new idWinding( plane.Normal(), plane.Dist() );

	for ( i = 0; i < sides.Num() && mid; i++ ) {
		mid = mid->Clip( -sides[i]->plane, BRUSH_EPSILON, false );
	}

	if ( mid ) {
		if ( mid->IsTiny() ) {
			delete mid;
			mid = NULL;
		}
		else if ( mid->IsHuge() ) {
			// if the winding is huge then the brush is unbounded
			common->Warning( "brush %d on entity %d is unbounded"
						"( %1.2f %1.2f %1.2f )-( %1.2f %1.2f %1.2f )-( %1.2f %1.2f %1.2f )", primitiveNum, entityNum,
							bounds[0][0], bounds[0][1], bounds[0][2], bounds[1][0], bounds[1][1], bounds[1][2],
							bounds[1][0]-bounds[0][0], bounds[1][1]-bounds[0][1], bounds[1][2]-bounds[0][2] );
			delete mid;
			mid = NULL;
		}
	}

	if ( !mid ) {
		if ( maxFront > - maxBack ) {
			if ( front ) {
				*front = Copy();
			}
			return PLANESIDE_FRONT;
		}
		else {
			if ( back ) {
				*back = Copy();
			}
			return PLANESIDE_BACK;
		}
	}

	if ( !front && !back ) {
		delete mid;
		return PLANESIDE_CROSS;
	}

	*front = new idBrush();
	(*front)->SetContents( contents );
	(*front)->SetEntityNum( entityNum );
	(*front)->SetPrimitiveNum( primitiveNum );
	*back = new idBrush();
	(*back)->SetContents( contents );
	(*back)->SetEntityNum( entityNum );
	(*back)->SetPrimitiveNum( primitiveNum );

	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];

		if ( !side->winding ) {
			continue;
		}

		// if completely at the front
		if ( maxBackWinding[i] >= BRUSH_EPSILON ) {
			(*front)->sides.Append( side->Copy() );
		}
		// if completely at the back
		else if ( maxFrontWinding[i] <= -BRUSH_EPSILON ) {
			(*back)->sides.Append( side->Copy() );
		}
		else {
			// split the side
			side->Split( plane, &frontSide, &backSide );
			if ( frontSide ) {
				(*front)->sides.Append( frontSide );
			}
			else if ( maxFrontWinding[i] > -BRUSH_EPSILON ) {
				// favor an overconstrained brush
				side = side->Copy();
				side->winding = side->winding->Clip( idPlane( plane.Normal(), (plane.Dist() - (BRUSH_EPSILON+0.02f)) ), 0.01f, true );
				assert( side->winding );
				(*front)->sides.Append( side );
			}
			if ( backSide ) {
				(*back)->sides.Append( backSide );
			}
			else if ( maxBackWinding[i] < BRUSH_EPSILON ) {
				// favor an overconstrained brush
				side = side->Copy();
				side->winding = side->winding->Clip( idPlane( -plane.Normal(), -(plane.Dist() + (BRUSH_EPSILON+0.02f)) ), 0.01f, true );
				assert( side->winding );
				(*back)->sides.Append( side );
			}
		}
	}

	side = new idBrushSide( -plane, planeNum^1 );
	side->winding = mid->Reverse();
	side->flags |= SFL_SPLIT;
	(*front)->sides.Append( side );
	(*front)->windingsValid = true;
	(*front)->BoundBrush( this );

	side = new idBrushSide( plane, planeNum );
	side->winding = mid;
	side->flags |= SFL_SPLIT;
	(*back)->sides.Append( side );
	(*back)->windingsValid = true;
	(*back)->BoundBrush( this );

	return PLANESIDE_CROSS;
}

/*
============
idBrush::AddBevelsForAxialBox
============
*/
#define BRUSH_BEVEL_EPSILON		0.1f

void idBrush::AddBevelsForAxialBox( void ) {
	int axis, dir, i, j, k, l, order;
	idBrushSide *side, *newSide;
	idPlane plane;
	idVec3 normal, vec;
	idWinding *w, *w2;
	float d, minBack;

	assert( windingsValid );

	// add the axial planes
	order = 0;
	for ( axis = 0; axis < 3; axis++ ) {

		for ( dir = -1; dir <= 1; dir += 2, order++ ) {

			// see if the plane is already present
			for ( i = 0; i < sides.Num(); i++ ) {
				if ( dir > 0 ) {
					if ( sides[i]->plane.Normal()[axis] >= 0.9999f ) {
						break;
					}
				}
				else {
					if ( sides[i]->plane.Normal()[axis] <= -0.9999f ) {
						break;
					}
				}
			}

			if ( i >= sides.Num() ) {
				normal = vec3_origin;
				normal[axis] = dir;
				plane.SetNormal( normal );
				plane.SetDist( dir * bounds[(dir == 1)][axis] );
				newSide = new idBrushSide( plane, -1 );
				newSide->SetFlag( SFL_BEVEL );
				sides.Append( newSide );
			}
		}
	}

	// if the brush is pure axial we're done
	if ( sides.Num() == 6 ) {
		return;
	}

	// test the non-axial plane edges
	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];
		w = side->winding;
		if ( !w ) {
			continue;
		}

		for ( j = 0; j < w->GetNumPoints(); j++) {
			k = (j+1) % w->GetNumPoints();
			vec = (*w)[j].ToVec3() - (*w)[k].ToVec3();
			if ( vec.Normalize() < 0.5f ) {
				continue;
			}
			for ( k = 0; k < 3; k++ ) {
				if ( vec[k] == 1.0f || vec[k] == -1.0f || (vec[k] == 0.0f && vec[(k+1)%3] == 0.0f) ) {
					break;	// axial
				}
			}
			if ( k < 3 ) {
				continue;	// only test non-axial edges
			}

			// try the six possible slanted axials from this edge
			for ( axis = 0; axis < 3; axis++ ) {

				for ( dir = -1; dir <= 1; dir += 2 ) {

					// construct a plane
					normal = vec3_origin;
					normal[axis] = dir;
					normal = vec.Cross( normal );
					if ( normal.Normalize() < 0.5f ) {
						continue;
					}
					plane.SetNormal( normal );
					plane.FitThroughPoint( (*w)[j].ToVec3() );

					// if all the points on all the sides are
					// behind this plane, it is a proper edge bevel
					for ( k = 0; k < sides.Num(); k++ ) {

						// if this plane has allready been used, skip it
						if ( plane.Compare( sides[k]->plane, 0.001f, 0.1f ) ) {
							break;
						}

						w2 = sides[k]->winding;
						if ( !w2 ) {
							continue;
						}
						minBack = 0.0f;
						for ( l = 0; l < w2->GetNumPoints(); l++ ) {
							d = plane.Distance( (*w2)[l].ToVec3() );
							if ( d > BRUSH_BEVEL_EPSILON ) {
								break;	// point at the front
							}
							if ( d < minBack ) {
								minBack = d;
							}
						}
						// if some point was at the front
						if ( l < w2->GetNumPoints() ) {
							break;
						}
						// if no points at the back then the winding is on the bevel plane
						if ( minBack > -BRUSH_BEVEL_EPSILON ) {
							break;
						}
					}

					if ( k < sides.Num() ) {
						continue;	// wasn't part of the outer hull
					}

					// add this plane
					newSide = new idBrushSide( plane, -1 );
					newSide->SetFlag( SFL_BEVEL );
					sides.Append( newSide );
				}
			}
		}
	}
}

/*
============
idBrush::ExpandForAxialBox
============
*/
void idBrush::ExpandForAxialBox( const idBounds &bounds ) {
	int i, j;
	idBrushSide *side;
	idVec3 v;

	AddBevelsForAxialBox();

	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];

		for ( j = 0; j < 3; j++ ) {
			if ( side->plane.Normal()[j] > 0.0f ) {
				v[j] = bounds[0][j];
			}
			else {
				v[j] = bounds[1][j];
			}
		}

		side->plane.SetDist( side->plane.Dist() + v * -side->plane.Normal() );
	}

	if ( !CreateWindings() ) {
		common->Error( "idBrush::ExpandForAxialBox: brush %d on entity %d imploded", primitiveNum, entityNum );
	}

	/*
	// after expansion at least all non bevel sides should have a winding
	for ( i = 0; i < sides.Num(); i++ ) {
		side = sides[i];
		if ( !side->winding ) {
			if ( !( side->flags & SFL_BEVEL ) ) {
				int shit = 1;
			}
		}
	}
	*/
}

/*
============
idBrush::Copy
============
*/
idBrush *idBrush::Copy( void ) const {
	int i;
	idBrush *b;

	b = new idBrush();
	b->entityNum = entityNum;
	b->primitiveNum = primitiveNum;
	b->contents = contents;
	b->windingsValid = windingsValid;
	b->bounds = bounds;
	for ( i = 0; i < sides.Num(); i++ ) {
		b->sides.Append( sides[i]->Copy() );
	}
	return b;
}


//===============================================================
//
//	idBrushList
//
//===============================================================

/*
============
idBrushList::idBrushList
============
*/
idBrushList::idBrushList( void ) {
	numBrushes = numBrushSides = 0;
	head = tail = NULL;
}

/*
============
idBrushList::~idBrushList
============
*/
idBrushList::~idBrushList( void ) {
}

/*
============
idBrushList::GetBounds
============
*/
idBounds idBrushList::GetBounds( void ) const {
	idBounds bounds;
	idBrush *b;

	bounds.Clear();
	for ( b = Head(); b; b = b->Next() ) {
		bounds += b->GetBounds();
	}
	return bounds;
}

/*
============
idBrushList::AddToTail
============
*/
void idBrushList::AddToTail( idBrush *brush ) {
	brush->next = NULL;
	if ( tail ) {
		tail->next = brush;
	}
	tail = brush;
	if ( !head ) {
		head = brush;
	}
	numBrushes++;
	numBrushSides += brush->sides.Num();
}

/*
============
idBrushList::AddToTail
============
*/
void idBrushList::AddToTail( idBrushList &list ) {
	idBrush *brush, *next;

	for ( brush = list.head; brush; brush = next ) {
		next = brush->next;
		brush->next = NULL;
		if ( tail ) {
			tail->next = brush;
		}
		tail = brush;
		if ( !head ) {
			head = brush;
		}
		numBrushes++;
		numBrushSides += brush->sides.Num();
	}
	list.head = list.tail = NULL;
	list.numBrushes = 0;
}

/*
============
idBrushList::AddToFront
============
*/
void idBrushList::AddToFront( idBrush *brush ) {
	brush->next = head;
	head = brush;
	if ( !tail ) {
		tail = brush;
	}
	numBrushes++;
	numBrushSides += brush->sides.Num();
}

/*
============
idBrushList::AddToFront
============
*/
void idBrushList::AddToFront( idBrushList &list ) {
	idBrush *brush, *next;

	for ( brush = list.head; brush; brush = next ) {
		next = brush->next;
		brush->next = head;
		head = brush;
		if ( !tail ) {
			tail = brush;
		}
		numBrushes++;
		numBrushSides += brush->sides.Num();
	}
	list.head = list.tail = NULL;
	list.numBrushes = 0;
}

/*
============
idBrushList::Remove
============
*/
void idBrushList::Remove( idBrush *brush ) {
	idBrush	*b, *last;

	last = NULL;
	for ( b = head; b; b = b->next ) {
		if ( b == brush ) {
			if ( last ) {
				last->next = b->next;
			}
			else {
				head = b->next;
			}
			if ( b == tail ) {
				tail = last;
			}
			numBrushes--;
			numBrushSides -= brush->sides.Num();
			return;
		}
		last = b;
	}
}

/*
============
idBrushList::Delete
============
*/
void idBrushList::Delete( idBrush *brush ) {
	idBrush	*b, *last;

	last = NULL;
	for ( b = head; b; b = b->next ) {
		if ( b == brush ) {
			if ( last ) {
				last->next = b->next;
			}
			else {
				head = b->next;
			}
			if ( b == tail ) {
				tail = last;
			}
			numBrushes--;
			numBrushSides -= b->sides.Num();
			delete b;
			return;
		}
		last = b;
	}
}

/*
============
idBrushList::Copy
============
*/
idBrushList *idBrushList::Copy( void ) const {
	idBrush *brush;
	idBrushList *list;

	list = new idBrushList;

	for ( brush = head; brush; brush = brush->next ) {
		list->AddToTail( brush->Copy() );
	}
	return list;
}

/*
============
idBrushList::Free
============
*/
void idBrushList::Free( void ) {
	idBrush *brush, *next;

	for ( brush = head; brush; brush = next ) {
		next = brush->next;
		delete brush;
	}
	head = tail = NULL;
	numBrushes = numBrushSides = 0;
}

/*
============
idBrushList::Split
============
*/
void idBrushList::Split( const idPlane &plane, int planeNum, idBrushList &frontList, idBrushList &backList, bool useBrushSavedPlaneSide ) {
	idBrush *b, *front, *back;

	frontList.Clear();
	backList.Clear();

	if ( !useBrushSavedPlaneSide ) {
		for ( b = head; b; b = b->next ) {
			b->Split( plane, planeNum, &front, &back );
			if ( front ) {
				frontList.AddToTail( front );
			}
			if ( back ) {
				backList.AddToTail( back );
			}
		}
		return;
	}

	for ( b = head; b; b = b->next ) {
		if ( b->savedPlaneSide & BRUSH_PLANESIDE_BOTH ) {
			b->Split( plane, planeNum, &front, &back );
			if ( front ) {
				frontList.AddToTail( front );
			}
			if ( back ) {
				backList.AddToTail( back );
			}
		}
		else if ( b->savedPlaneSide & BRUSH_PLANESIDE_FRONT ) {
			frontList.AddToTail( b->Copy() );
		}
		else {
			backList.AddToTail( b->Copy() );
		}
	}
}

/*
============
idBrushList::Chop
============
*/
void idBrushList::Chop( bool (*ChopAllowed)( idBrush *b1, idBrush *b2 ) ) {
	idBrush	*b1, *b2, *next;
	idBrushList sub1, sub2, keep;
	int i, j, c1, c2;
	idPlaneSet planeList;

#ifdef OUTPUT_CHOP_STATS
	common->Printf( "[Brush CSG]\n");
	common->Printf( "%6d original brushes\n", this->Num() );
#endif

	CreatePlaneList( planeList );

	for ( b1 = this->Head(); b1; b1 = this->Head() ) {

		for ( b2 = b1->next; b2; b2 = next ) {

			next = b2->next;

			for ( i = 0; i < 3; i++ ) {
				if ( b1->bounds[0][i] >= b2->bounds[1][i] ) {
					break;
				}
				if ( b1->bounds[1][i] <= b2->bounds[0][i] ) {
					break;
				}
			}
			if ( i < 3 ) {
				continue;
			}

			for ( i = 0; i < b1->GetNumSides(); i++ ) {
				for ( j = 0; j < b2->GetNumSides(); j++ ) {
					if ( b1->GetSide(i)->GetPlaneNum() == ( b2->GetSide(j)->GetPlaneNum() ^ 1 ) ) {
						// opposite planes, so not touching
						break;
					}
				}
				if ( j < b2->GetNumSides() ) {
					break;
				}
			}
			if ( i < b1->GetNumSides() ) {
				continue;
			}

			sub1.Clear();
			sub2.Clear();

			c1 = 999999;
			c2 = 999999;

			// if b2 may chop up b1
			if ( !ChopAllowed || ChopAllowed( b2,  b1 ) ) {
				if ( !b1->Subtract( b2, sub1 ) ) {
					// didn't really intersect
					continue;
				}
				if ( sub1.IsEmpty() ) {
					// b1 is swallowed by b2
					this->Delete( b1 );
					break;
				}
				c1 = sub1.Num();
			}

			// if b1 may chop up b2
			if ( !ChopAllowed || ChopAllowed( b1,  b2 ) ) {
				if ( !b2->Subtract( b1, sub2 ) ) {
					// didn't really intersect
					continue;
				}
				if ( sub2.IsEmpty() ) {
					// b2 is swallowed by b1
					sub1.Free();
					this->Delete( b2 );
					continue;
				}
				c2 = sub2.Num();
			}

			if ( sub1.IsEmpty() && sub2.IsEmpty() ) {
				continue;
			}

			// don't allow too much fragmentation
			if ( c1 > 2 && c2 > 2 ) {
				sub1.Free();
				sub2.Free();
				continue;
			}

			if ( c1 < c2 ) {
				sub2.Free();
				this->AddToTail( sub1 );
				this->Delete( b1 );
				break;
			}
			else {
				sub1.Free();
				this->AddToTail( sub2 );
				this->Delete( b2 );
				continue;
			}
		}

		if ( !b2 ) {
			// b1 is no longer intersecting anything, so keep it
			this->Remove( b1 );
			keep.AddToTail( b1 );
#ifdef OUTPUT_CHOP_STATS
			DisplayRealTimeString( "\r%6d", keep.numBrushes );
#endif
		}
	}

	*this = keep;

#ifdef OUTPUT_CHOP_STATS
	common->Printf( "\r%6d output brushes\n", Num() );
#endif
}


/*
============
idBrushList::Merge
============
*/
void idBrushList::Merge( bool (*MergeAllowed)( idBrush *b1, idBrush *b2 ) ) {
	idPlaneSet planeList;
	idBrush *b1, *b2, *nextb2;
	int numMerges;

	common->Printf( "[Brush Merge]\n");
	common->Printf( "%6d original brushes\n", Num() );

	CreatePlaneList( planeList );

	numMerges = 0;
	for ( b1 = Head(); b1; b1 = b1->next ) {

		for ( b2 = Head(); b2; b2 = nextb2 ) {
			nextb2 = b2->Next();

			if ( b2 == b1 ) {
				continue;
			}

			if ( MergeAllowed && !MergeAllowed( b1, b2 ) ) {
				continue;
			}

			if ( b1->TryMerge( b2, planeList ) ) {
				Delete( b2 );
				DisplayRealTimeString( "\r%6d", ++numMerges );
				nextb2 = Head();
			}
		}
	}

	common->Printf( "\r%6d brushes merged\n", numMerges );
}

/*
============
idBrushList::SetFlagOnFacingBrushSides
============
*/
void idBrushList::SetFlagOnFacingBrushSides( const idPlane &plane, int flag ) {
	int i;
	idBrush *b;
	const idWinding *w;

	for ( b = head; b; b = b->next ) {
		if ( idMath::Fabs( b->GetBounds().PlaneDistance( plane ) ) > 0.1f ) {
			continue;
		}
		for ( i = 0; i < b->GetNumSides(); i++ ) {
			w = b->GetSide(i)->GetWinding();
			if ( !w ) {
				if ( b->GetSide(i)->GetPlane().Compare( plane, BRUSH_PLANE_NORMAL_EPSILON, BRUSH_PLANE_DIST_EPSILON ) ) {
					b->GetSide(i)->SetFlag( flag );
				}
				continue;
			}
			if ( w->PlaneSide( plane ) == SIDE_ON ) {
				b->GetSide(i)->SetFlag( flag );
			}
		}
	}
}

/*
============
idBrushList::CreatePlaneList
============
*/
void idBrushList::CreatePlaneList( idPlaneSet &planeList ) const {
	int i;
	idBrush *b;
	idBrushSide *side;

	planeList.Resize( 512, 128 );
	for ( b = Head(); b; b = b->Next() ) {
		for ( i = 0; i < b->GetNumSides(); i++ ) {
			side = b->GetSide( i );
			side->SetPlaneNum( planeList.FindPlane( side->GetPlane(), BRUSH_PLANE_NORMAL_EPSILON, BRUSH_PLANE_DIST_EPSILON ) );
		}
	}
}

/*
============
idBrushList::CreatePlaneList
============
*/
void idBrushList::WriteBrushMap( const idStr &fileName, const idStr &ext ) const {
	idBrushMap *map;

	map = new idBrushMap( fileName, ext );
	map->WriteBrushList( *this );
	delete map;
}


//===============================================================
//
//	idBrushMap
//
//===============================================================

/*
============
idBrushMap::idBrushMap
============
*/
idBrushMap::idBrushMap( const idStr &fileName, const idStr &ext ) {
	idStr qpath;

	qpath = fileName;
	qpath.StripFileExtension();
	qpath += ext;
	qpath.SetFileExtension( "map" );

	common->Printf( "writing %s...\n", qpath.c_str() );

	fp = fileSystem->OpenFileWrite( qpath, "fs_devpath" );
	if ( !fp ) {
		common->Error( "Couldn't open %s\n", qpath.c_str() );
		return;
	}

	texture = "textures/washroom/btile01";

	fp->WriteFloatString( "Version %1.2f\n", (float) CURRENT_MAP_VERSION );
	fp->WriteFloatString( "{\n" );
	fp->WriteFloatString( "\"classname\" \"worldspawn\"\n" );

	brushCount = 0;
}

/*
============
idBrushMap::~idBrushMap
============
*/
idBrushMap::~idBrushMap( void ) {
	if ( !fp ) {
		return;
	}
	fp->WriteFloatString( "}\n" );
	fileSystem->CloseFile( fp );
}

/*
============
idBrushMap::WriteBrush
============
*/
void idBrushMap::WriteBrush( const idBrush *brush ) {
	int i;
	idBrushSide *side;

	if ( !fp ) {
		return;
	}

	fp->WriteFloatString( "// primitive %d\n{\nbrushDef3\n{\n", brushCount++ );

	for ( i = 0; i < brush->GetNumSides(); i++ ) {
		side = brush->GetSide( i );
		fp->WriteFloatString( " ( %f %f %f %f ) ", side->GetPlane()[0], side->GetPlane()[1], side->GetPlane()[2], -side->GetPlane().Dist() );
		fp->WriteFloatString( "( ( 0.031250 0 0 ) ( 0 0.031250 0 ) ) %s 0 0 0\n", texture.c_str() );

	}
	fp->WriteFloatString( "}\n}\n" );
}

/*
============
idBrushMap::WriteBrushList
============
*/
void idBrushMap::WriteBrushList( const idBrushList &brushList ) {
	idBrush *b;

	if ( !fp ) {
		return;
	}

	for ( b = brushList.Head(); b; b = b->Next() ) {
		WriteBrush( b );
	}
}