newlines fixed

git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea

1 files changed, 1005 insertions, 1005 deletions

diff --git a/code/bspc/csg.c b/code/bspc/csg.c
index c141075..fc7c327 100755
--- a/code/bspc/csg.c
+++ b/code/bspc/csg.c
@@ -1,1005 +1,1005 @@
-/*

-===========================================================================

-Copyright (C) 1999-2005 Id Software, Inc.

-

-This file is part of Quake III Arena source code.

-

-Quake III Arena 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 2 of the License,

-or (at your option) any later version.

-

-Quake III Arena 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 Foobar; if not, write to the Free Software

-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

-===========================================================================

-*/

-

-#include "qbsp.h"

-

-/*

-

-tag all brushes with original contents

-brushes may contain multiple contents

-there will be no brush overlap after csg phase

-

-*/

-

-int minplanenums[3];

-int maxplanenums[3];

-

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-void CheckBSPBrush(bspbrush_t *brush)

-{

-	int i, j;

-	plane_t *plane1, *plane2;

-

-	//check if the brush is convex... flipped planes make a brush non-convex

-	for (i = 0; i < brush->numsides; i++)

-	{

-		for (j = 0; j < brush->numsides; j++)

-		{

-			if (i == j) continue;

-			plane1 = &mapplanes[brush->sides[i].planenum];

-			plane2 = &mapplanes[brush->sides[j].planenum];

-			//

-			if (WindingsNonConvex(brush->sides[i].winding,

-									brush->sides[j].winding,

-									plane1->normal, plane2->normal,

-									plane1->dist, plane2->dist))

-			{

-				Log_Print("non convex brush");

-				break;

-			} //end if

-		} //end for

-	} //end for

-	BoundBrush(brush);

-	//check for out of bound brushes

-	for (i = 0; i < 3; i++)

-	{

-		if (brush->mins[i] < -MAX_MAP_BOUNDS || brush->maxs[i] > MAX_MAP_BOUNDS)

-		{

-			Log_Print("brush: bounds out of range\n");

-			Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);

-			break;

-		} //end if

-		if (brush->mins[i] > MAX_MAP_BOUNDS || brush->maxs[i] < -MAX_MAP_BOUNDS)

-		{

-			Log_Print("brush: no visible sides on brush\n");

-			Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);

-			break;

-		} //end if

-	} //end for

-} //end of the function CheckBSPBrush

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-void BSPBrushWindings(bspbrush_t *brush)

-{

-	int i, j;

-	winding_t *w;

-	plane_t *plane;

-

-	for (i = 0; i < brush->numsides; i++)

-	{

-		plane = &mapplanes[brush->sides[i].planenum];

-		w = BaseWindingForPlane(plane->normal, plane->dist);

-		for (j = 0; j < brush->numsides && w; j++)

-		{

-			if (i == j) continue;

-			plane = &mapplanes[brush->sides[j].planenum^1];

-			ChopWindingInPlace(&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);

-		} //end for

-		brush->sides[i].winding = w;

-	} //end for

-} //end of the function BSPBrushWindings

-//===========================================================================

-// NOTE: can't keep brush->original intact

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *TryMergeBrushes(bspbrush_t *brush1, bspbrush_t *brush2)

-{

-	int i, j, k, n, shared;

-	side_t *side1, *side2, *cs;

-	plane_t *plane1, *plane2;

-	bspbrush_t *newbrush;

-

-	//check for bounding box overlapp

-	for (i = 0; i < 3; i++)

-	{

-		if (brush1->mins[i] > brush2->maxs[i] + 2

-				|| brush1->maxs[i] < brush2->mins[i] - 2)

-		{

-			return NULL;

-		} //end if

-	} //end for

-	//

-	shared = 0;

-	//check if the brush is convex... flipped planes make a brush non-convex

-	for (i = 0; i < brush1->numsides; i++)

-	{

-		side1 = &brush1->sides[i];

-		//don't check the "shared" sides

-		for (k = 0; k < brush2->numsides; k++)

-		{

-			side2 = &brush2->sides[k];

-			if (side1->planenum == (side2->planenum^1))

-			{

-				shared++;

-				//there may only be ONE shared side

-				if (shared > 1) return NULL;

-				break;

-			} //end if

-		} //end for

-		if (k < brush2->numsides) continue;

-		//

-		for (j = 0; j < brush2->numsides; j++)

-		{

-			side2 = &brush2->sides[j];

-			//don't check the "shared" sides

-			for (n = 0; n < brush1->numsides; n++)

-			{

-				side1 = &brush1->sides[n];

-				if (side1->planenum == (side2->planenum^1)) break;

-			} //end for

-			if (n < brush1->numsides) continue;

-			//

-			side1 = &brush1->sides[i];

-			//if the side is in the same plane

-			//*

-			if (side1->planenum == side2->planenum)

-			{

-				if (side1->texinfo != TEXINFO_NODE &&

-					side2->texinfo != TEXINFO_NODE &&

-					side1->texinfo != side2->texinfo) return NULL;

-				continue;

-			} //end if

-			//

-			plane1 = &mapplanes[side1->planenum];

-			plane2 = &mapplanes[side2->planenum];

-			//

-			if (WindingsNonConvex(side1->winding, side2->winding,

-									plane1->normal, plane2->normal,

-									plane1->dist, plane2->dist))

-			{

-				return NULL;

-			} //end if

-		} //end for

-	} //end for

-	newbrush = AllocBrush(brush1->numsides + brush2->numsides);

-	newbrush->original = brush1->original;

-	newbrush->numsides = 0;

-	//newbrush->side = brush1->side;	//brush contents

-	//fix texinfos for sides lying in the same plane

-	for (i = 0; i < brush1->numsides; i++)

-	{

-		side1 = &brush1->sides[i];

-		//

-		for (n = 0; n < brush2->numsides; n++)

-		{

-			side2 = &brush2->sides[n];

-			//if both sides are in the same plane get the texinfo right

-			if (side1->planenum == side2->planenum)

-			{

-				if (side1->texinfo == TEXINFO_NODE) side1->texinfo = side2->texinfo;

-				if (side2->texinfo == TEXINFO_NODE) side2->texinfo = side1->texinfo;

-			} //end if

-		} //end for

-	} //end for

-	//

-	for (i = 0; i < brush1->numsides; i++)

-	{

-		side1 = &brush1->sides[i];

-		//don't add the "shared" sides

-		for (n = 0; n < brush2->numsides; n++)

-		{

-			side2 = &brush2->sides[n];

-			if (side1->planenum == (side2->planenum ^ 1)) break;

-		} //end for

-		if (n < brush2->numsides) continue;

-		//

-		for (n = 0; n < newbrush->numsides; n++)

-		{

-			cs = &newbrush->sides[n];

-			if (cs->planenum == side1->planenum)

-			{

-				Log_Print("brush duplicate plane\n");

-				break;

-			} //end if

-		} //end if

-		if (n < newbrush->numsides) continue;

-		//add this side

-		cs = &newbrush->sides[newbrush->numsides];

-		newbrush->numsides++;

-		*cs = *side1;

-	} //end for

-	for (j = 0; j < brush2->numsides; j++)

-	{

-		side2 = &brush2->sides[j];

-		for (n = 0; n < brush1->numsides; n++)

-		{

-			side1 = &brush1->sides[n];

-			//if the side is in the same plane

-			if (side2->planenum == side1->planenum) break;

-			//don't add the "shared" sides

-			if (side2->planenum == (side1->planenum ^ 1)) break;

-		} //end for

-		if (n < brush1->numsides) continue;

-		//

-		for (n = 0; n < newbrush->numsides; n++)

-		{

-			cs = &newbrush->sides[n];

-			if (cs->planenum == side2->planenum)

-			{

-				Log_Print("brush duplicate plane\n");

-				break;

-			} //end if

-		} //end if

-		if (n < newbrush->numsides) continue;

-		//add this side

-		cs = &newbrush->sides[newbrush->numsides];

-		newbrush->numsides++;

-		*cs = *side2;

-	} //end for

-	BSPBrushWindings(newbrush);

-	BoundBrush(newbrush);

-	CheckBSPBrush(newbrush);

-	return newbrush;

-} //end of the function TryMergeBrushes

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *MergeBrushes(bspbrush_t *brushlist)

-{

-	int nummerges, merged;

-	bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;

-	bspbrush_t *lastb2;

-

-	if (!brushlist) return NULL;

-

-	qprintf("%5d brushes merged", nummerges = 0);

-	do

-	{

-		for (tail = brushlist; tail; tail = tail->next)

-		{

-			if (!tail->next) break;

-		} //end for

-		merged = 0;

-		newbrushlist = NULL;

-		for (b1 = brushlist; b1; b1 = brushlist)

-		{

-			lastb2 = b1;

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

-			{

-				//if the brushes don't have the same contents

-				if (b1->original->contents != b2->original->contents ||

-					b1->original->expansionbbox != b2->original->expansionbbox) newbrush = NULL;

-				else newbrush = TryMergeBrushes(b1, b2);

-				if (newbrush)

-				{

-					tail->next = newbrush;

-					lastb2->next = b2->next;

-					brushlist = brushlist->next;

-					FreeBrush(b1);

-					FreeBrush(b2);

-					for (tail = brushlist; tail; tail = tail->next)

-					{

-						if (!tail->next) break;

-					} //end for

-					merged++;

-					qprintf("\r%5d", nummerges++);

-					break;

-				} //end if

-				lastb2 = b2;

-			} //end for

-			//if b1 can't be merged with any of the other brushes

-			if (!b2)

-			{

-				brushlist = brushlist->next;

-				//keep b1

-				b1->next = newbrushlist;

-				newbrushlist = b1;

-			} //end else

-		} //end for

-		brushlist = newbrushlist;

-	} while(merged);

-	qprintf("\n");

-	return newbrushlist;

-} //end of the function MergeBrushes

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-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

-} //end of the function SplitBrush2

-//===========================================================================

-// 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.

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-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;

-		} //end if

-		in = back;

-	} //end for

-	if (in)

-	{

-		FreeBrush (in);

-	} //end if

-	else

-	{	// didn't really intersect

-		FreeBrushList (out);

-		return a;

-	} //end else

-	return out;

-} //end of the function SubtractBrush

-//===========================================================================

-// Returns a single brush made up by the intersection of the

-// two provided brushes, or NULL if they are disjoint.

-//

-// The originals are undisturbed.

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-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;

-	} //end for

-

-	if (in == a) return NULL;

-

-	in->next = NULL;

-	return in;

-} //end of the function IntersectBrush

-//===========================================================================

-// Returns true if the two brushes definately do not intersect.

-// There will be false negatives for some non-axial combinations.

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-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

-} //end of the function BrushesDisjoint

-//===========================================================================

-// 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.

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-int IntersectionContents (int c1, int c2)

-{

-	int out;

-

-	out = c1 | c2;

-

-	if (out & CONTENTS_SOLID) out = CONTENTS_SOLID;

-

-	return out;

-} //end of the function IntersectionContents

-//===========================================================================

-// Any planes shared with the box edge will be set to no texinfo

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *ClipBrushToBox(bspbrush_t *brush, vec3_t clipmins, vec3_t 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].flags &= ~SFL_VISIBLE;

-		}

-	}

-	return brush;

-} //end of the function ClipBrushToBox

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *MakeBspBrushList(int startbrush, int endbrush,

-											vec3_t clipmins, vec3_t clipmaxs)

-{

-	mapbrush_t	*mb;

-	bspbrush_t	*brushlist, *newbrush;

-	int			i, j;

-	int			c_faces;

-	int			c_brushes;

-	int			numsides;

-	int			vis;

-	vec3_t		normal;

-	float		dist;

-

-	for (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);

-	}

-

-	brushlist = NULL;

-	c_faces = 0;

-	c_brushes = 0;

-

-	for (i=startbrush ; i<endbrush ; i++)

-	{

-		mb = &mapbrushes[i];

-

-		numsides = mb->numsides;

-		if (!numsides)

-			continue;

-

-		// make sure the brush has at least one face showing

-		vis = 0;

-		for (j=0 ; j<numsides ; j++)

-			if ((mb->original_sides[j].flags & SFL_VISIBLE) && mb->original_sides[j].winding)

-				vis++;

-#if 0

-		if (!vis)

-			continue;	// no faces at all

-#endif

-		// if the brush is outside the clip area, skip it

-		for (j=0 ; j<3 ; j++)

-			if (mb->mins[j] >= clipmaxs[j]

-			|| mb->maxs[j] <= clipmins[j])

-			break;

-		if (j != 3)

-			continue;

-

-		//

-		// make a copy of the brush

-		//

-		newbrush = AllocBrush (mb->numsides);

-		newbrush->original = mb;

-		newbrush->numsides = mb->numsides;

-		memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));

-		for (j=0 ; j<numsides ; 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].flags |= SFL_VISIBLE;	// hints are always visible

-		}

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

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

-

-		//

-		// carve off anything outside the clip box

-		//

-		newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);

-		if (!newbrush)

-			continue;

-

-		c_faces += vis;

-		c_brushes++;

-

-		newbrush->next = brushlist;

-		brushlist = newbrush;

-	}

-

-	return brushlist;

-} //end of the function MakeBspBrushList

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)

-{

-	bspbrush_t	*walk, *next;

-

-	for (walk=list ; walk ; walk=next)

-	{	// add to end of list

-		next = walk->next;

-		walk->next = NULL;

-		tail->next = walk;

-		tail = walk;

-	} //end for

-	return tail;

-} //end of the function AddBrushListToTail

-//===========================================================================

-// Builds a new list that doesn't hold the given brush

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *CullList(bspbrush_t *list, bspbrush_t *skip1)

-{

-	bspbrush_t	*newlist;

-	bspbrush_t	*next;

-

-	newlist = NULL;

-

-	for ( ; list ; list = next)

-	{

-		next = list->next;

-		if (list == skip1)

-		{

-			FreeBrush (list);

-			continue;

-		}

-		list->next = newlist;

-		newlist = list;

-	}

-	return newlist;

-} //end of the function CullList

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-/*

-void WriteBrushMap(char *name, bspbrush_t *list)

-{

-	FILE	*f;

-	side_t	*s;

-	int		i;

-	winding_t	*w;

-

-	Log_Print("writing %s\n", name);

-	f = fopen (name, "wb");

-	if (!f)

-		Error ("Can't write %s\b", name);

-

-	fprintf (f, "{\n\"classname\" \"worldspawn\"\n");

-

-	for ( ; list ; list=list->next )

-	{

-		fprintf (f, "{\n");

-		for (i=0,s=list->sides ; i<list->numsides ; i++,s++)

-		{

-			w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);

-

-			fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);

-			fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);

-			fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);

-

-			fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);

-			FreeWinding (w);

-		}

-		fprintf (f, "}\n");

-	}

-	fprintf (f, "}\n");

-

-	fclose (f);

-} //end of the function WriteBrushMap

-*/

-//===========================================================================

-// Returns true if b1 is allowed to bite b2

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)

-{

-#ifdef ME

-	if (create_aas)

-	{

-		if (b1->original->expansionbbox != b2->original->expansionbbox)

-		{

-			return false;

-		} //end if

-		//never have something else bite a ladder brush

-		//never have a ladder brush bite something else

-		if ( (b1->original->contents & CONTENTS_LADDER)

-			&& !(b2->original->contents & CONTENTS_LADDER))

-		{ 

-			return false;

-		} //end if

-	} //end if

-#endif //ME

-	// detail brushes never bite structural brushes

-	if ( (b1->original->contents & CONTENTS_DETAIL) 

-		&& !(b2->original->contents & CONTENTS_DETAIL) )

-	{

-		return false;

-	} //end if

-	if (b1->original->contents & CONTENTS_SOLID)

-	{

-		return true;

-	} //end if

-	return false;

-} //end of the function BrushGE

-//===========================================================================

-// Carves any intersecting solid brushes into the minimum number

-// of non-intersecting brushes.

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *ChopBrushes (bspbrush_t *head)

-{

-	bspbrush_t	*b1, *b2, *next;

-	bspbrush_t	*tail;

-	bspbrush_t	*keep;

-	bspbrush_t	*sub, *sub2;

-	int			c1, c2;

-	int num_csg_iterations;

-

-	Log_Print("-------- Brush CSG ---------\n");

-	Log_Print("%6d original brushes\n", CountBrushList (head));

-

-	num_csg_iterations = 0;

-	qprintf("%6d output brushes", num_csg_iterations);

-

-#if 0

-	if (startbrush == 0)

-		WriteBrushList ("before.gl", head, false);

-#endif

-	keep = NULL;

-

-newlist:

-	// find tail

-	if (!head) return NULL;

-

-	for (tail = head; tail->next; tail = tail->next)

-		;

-

-	for (b1=head ; b1 ; b1=next)

-	{

-		next = b1->next;

-

-		//if the conversion is cancelled

-		if (cancelconversion)

-		{

-			b1->next = keep;

-			keep = b1;

-			continue;

-		} //end if

-		

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

-		{

-			if (BrushesDisjoint (b1, b2))

-				continue;

-

-			sub = NULL;

-			sub2 = NULL;

-			c1 = 999999;

-			c2 = 999999;

-

-			if (BrushGE (b2, b1))

-			{

-				sub = SubtractBrush (b1, b2);

-				if (sub == b1)

-				{

-					continue;		// didn't really intersect

-				} //end if

-				if (!sub)

-				{	// b1 is swallowed by b2

-					head = CullList (b1, b1);

-					goto newlist;

-				}

-				c1 = CountBrushList (sub);

-			}

-

-			if ( BrushGE (b1, b2) )

-			{

-				sub2 = SubtractBrush (b2, b1);

-				if (sub2 == b2)

-					continue;		// didn't really intersect

-				if (!sub2)

-				{	// b2 is swallowed by b1

-					FreeBrushList (sub);

-					head = CullList (b1, b2);

-					goto newlist;

-				}

-				c2 = CountBrushList (sub2);

-			}

-

-			if (!sub && !sub2)

-				continue;		// neither one can bite

-

-			// only accept if it didn't fragment

-			// (commenting this out allows full fragmentation)

-			if (c1 > 1 && c2 > 1)

-			{

-				if (sub2)

-					FreeBrushList (sub2);

-				if (sub)

-					FreeBrushList (sub);

-				continue;

-			}

-

-			if (c1 < c2)

-			{

-				if (sub2) FreeBrushList (sub2);

-				tail = AddBrushListToTail (sub, tail);

-				head = CullList (b1, b1);

-				goto newlist;

-			} //end if

-			else

-			{

-				if (sub) FreeBrushList (sub);

-				tail = AddBrushListToTail (sub2, tail);

-				head = CullList (b1, b2);

-				goto newlist;

-			} //end else

-		} //end for

-

-		if (!b2)

-		{	// b1 is no longer intersecting anything, so keep it

-			b1->next = keep;

-			keep = b1;

-		} //end if

-		num_csg_iterations++;

-		qprintf("\r%6d", num_csg_iterations);

-	} //end for

-

-	if (cancelconversion) return keep;

-	//

-	qprintf("\n");

-	Log_Write("%6d output brushes\r\n", num_csg_iterations);

-

-#if 0

-	{

-		WriteBrushList ("after.gl", keep, false);

-		WriteBrushMap ("after.map", keep);

-	}

-#endif

-

-	return keep;

-} //end of the function ChopBrushes

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *InitialBrushList (bspbrush_t *list)

-{

-	bspbrush_t *b;

-	bspbrush_t	*out, *newb;

-	int			i;

-

-	// only return brushes that have visible faces

-	out = NULL;

-	for (b=list ; b ; b=b->next)

-	{

-#if 0

-		for (i=0 ; i<b->numsides ; i++)

-			if (b->sides[i].flags & SFL_VISIBLE)

-				break;

-		if (i == b->numsides)

-			continue;

-#endif

-		newb = CopyBrush (b);

-		newb->next = out;

-		out = newb;

-

-		// clear visible, so it must be set by MarkVisibleFaces_r

-		// to be used in the optimized list

-		for (i=0 ; i<b->numsides ; i++)

-		{

-			newb->sides[i].original = &b->sides[i];

-//			newb->sides[i].visible = true;

-			b->sides[i].flags &= ~SFL_VISIBLE;

-		}

-	}

-

-	return out;

-} //end of the function InitialBrushList

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-bspbrush_t *OptimizedBrushList (bspbrush_t *list)

-{

-	bspbrush_t *b;

-	bspbrush_t	*out, *newb;

-	int			i;

-

-	// only return brushes that have visible faces

-	out = NULL;

-	for (b=list ; b ; b=b->next)

-	{

-		for (i=0 ; i<b->numsides ; i++)

-			if (b->sides[i].flags & SFL_VISIBLE)

-				break;

-		if (i == b->numsides)

-			continue;

-		newb = CopyBrush (b);

-		newb->next = out;

-		out = newb;

-	} //end for

-

-//	WriteBrushList ("vis.gl", out, true);

-	return out;

-} //end of the function OptimizeBrushList

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-tree_t *ProcessWorldBrushes(int brush_start, int brush_end)

-{

-	bspbrush_t *brushes;

-	tree_t *tree;

-	node_t *node;

-	vec3_t mins, maxs;

-

-	//take the whole world

-	mins[0] = map_mins[0] - 8;

-	mins[1] = map_mins[1] - 8;

-	mins[2] = map_mins[2] - 8;

-

-	maxs[0] = map_maxs[0] + 8;

-	maxs[1] = map_maxs[1] + 8;

-	maxs[2] = map_maxs[2] + 8;

-

-	//reset the brush bsp

-	ResetBrushBSP();

-

-	// the makelist and chopbrushes could be cached between the passes...

-

-	//create a list with brushes that are within the given mins/maxs

-	//some brushes will be cut and only the part that falls within the

-	//mins/maxs will be in the bush list

-	brushes = MakeBspBrushList(brush_start, brush_end, mins, maxs);

-	//

-

-	if (!brushes)

-	{

-		node = AllocNode ();

-		node->planenum = PLANENUM_LEAF;

-		node->contents = CONTENTS_SOLID;

-

-		tree = Tree_Alloc();

-		tree->headnode = node;

-		VectorCopy(mins, tree->mins);

-		VectorCopy(maxs, tree->maxs);

-	} //end if

-	else

-	{

-		//Carves any intersecting solid brushes into the minimum number

-		//of non-intersecting brushes. 

-		if (!nocsg)

-		{

-			brushes = ChopBrushes(brushes);

-			/*

-			if (create_aas)

-			{

-				brushes = MergeBrushes(brushes);

-			} //end if*/

-		} //end if

-		//if the conversion is cancelled

-		if (cancelconversion)

-		{

-			FreeBrushList(brushes);

-			return NULL;

-		} //end if

-		//create the actual bsp tree

-		tree = BrushBSP(brushes, mins, maxs);

-	} //end else

-	//return the tree

-	return tree;

-} //end of the function ProcessWorldBrushes

+/*
+===========================================================================
+Copyright (C) 1999-2005 Id Software, Inc.
+
+This file is part of Quake III Arena source code.
+
+Quake III Arena 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 2 of the License,
+or (at your option) any later version.
+
+Quake III Arena 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 Foobar; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+===========================================================================
+*/
+
+#include "qbsp.h"
+
+/*
+
+tag all brushes with original contents
+brushes may contain multiple contents
+there will be no brush overlap after csg phase
+
+*/
+
+int minplanenums[3];
+int maxplanenums[3];
+
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+void CheckBSPBrush(bspbrush_t *brush)
+{
+	int i, j;
+	plane_t *plane1, *plane2;
+
+	//check if the brush is convex... flipped planes make a brush non-convex
+	for (i = 0; i < brush->numsides; i++)
+	{
+		for (j = 0; j < brush->numsides; j++)
+		{
+			if (i == j) continue;
+			plane1 = &mapplanes[brush->sides[i].planenum];
+			plane2 = &mapplanes[brush->sides[j].planenum];
+			//
+			if (WindingsNonConvex(brush->sides[i].winding,
+									brush->sides[j].winding,
+									plane1->normal, plane2->normal,
+									plane1->dist, plane2->dist))
+			{
+				Log_Print("non convex brush");
+				break;
+			} //end if
+		} //end for
+	} //end for
+	BoundBrush(brush);
+	//check for out of bound brushes
+	for (i = 0; i < 3; i++)
+	{
+		if (brush->mins[i] < -MAX_MAP_BOUNDS || brush->maxs[i] > MAX_MAP_BOUNDS)
+		{
+			Log_Print("brush: bounds out of range\n");
+			Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
+			break;
+		} //end if
+		if (brush->mins[i] > MAX_MAP_BOUNDS || brush->maxs[i] < -MAX_MAP_BOUNDS)
+		{
+			Log_Print("brush: no visible sides on brush\n");
+			Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
+			break;
+		} //end if
+	} //end for
+} //end of the function CheckBSPBrush
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+void BSPBrushWindings(bspbrush_t *brush)
+{
+	int i, j;
+	winding_t *w;
+	plane_t *plane;
+
+	for (i = 0; i < brush->numsides; i++)
+	{
+		plane = &mapplanes[brush->sides[i].planenum];
+		w = BaseWindingForPlane(plane->normal, plane->dist);
+		for (j = 0; j < brush->numsides && w; j++)
+		{
+			if (i == j) continue;
+			plane = &mapplanes[brush->sides[j].planenum^1];
+			ChopWindingInPlace(&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
+		} //end for
+		brush->sides[i].winding = w;
+	} //end for
+} //end of the function BSPBrushWindings
+//===========================================================================
+// NOTE: can't keep brush->original intact
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *TryMergeBrushes(bspbrush_t *brush1, bspbrush_t *brush2)
+{
+	int i, j, k, n, shared;
+	side_t *side1, *side2, *cs;
+	plane_t *plane1, *plane2;
+	bspbrush_t *newbrush;
+
+	//check for bounding box overlapp
+	for (i = 0; i < 3; i++)
+	{
+		if (brush1->mins[i] > brush2->maxs[i] + 2
+				|| brush1->maxs[i] < brush2->mins[i] - 2)
+		{
+			return NULL;
+		} //end if
+	} //end for
+	//
+	shared = 0;
+	//check if the brush is convex... flipped planes make a brush non-convex
+	for (i = 0; i < brush1->numsides; i++)
+	{
+		side1 = &brush1->sides[i];
+		//don't check the "shared" sides
+		for (k = 0; k < brush2->numsides; k++)
+		{
+			side2 = &brush2->sides[k];
+			if (side1->planenum == (side2->planenum^1))
+			{
+				shared++;
+				//there may only be ONE shared side
+				if (shared > 1) return NULL;
+				break;
+			} //end if
+		} //end for
+		if (k < brush2->numsides) continue;
+		//
+		for (j = 0; j < brush2->numsides; j++)
+		{
+			side2 = &brush2->sides[j];
+			//don't check the "shared" sides
+			for (n = 0; n < brush1->numsides; n++)
+			{
+				side1 = &brush1->sides[n];
+				if (side1->planenum == (side2->planenum^1)) break;
+			} //end for
+			if (n < brush1->numsides) continue;
+			//
+			side1 = &brush1->sides[i];
+			//if the side is in the same plane
+			//*
+			if (side1->planenum == side2->planenum)
+			{
+				if (side1->texinfo != TEXINFO_NODE &&
+					side2->texinfo != TEXINFO_NODE &&
+					side1->texinfo != side2->texinfo) return NULL;
+				continue;
+			} //end if
+			//
+			plane1 = &mapplanes[side1->planenum];
+			plane2 = &mapplanes[side2->planenum];
+			//
+			if (WindingsNonConvex(side1->winding, side2->winding,
+									plane1->normal, plane2->normal,
+									plane1->dist, plane2->dist))
+			{
+				return NULL;
+			} //end if
+		} //end for
+	} //end for
+	newbrush = AllocBrush(brush1->numsides + brush2->numsides);
+	newbrush->original = brush1->original;
+	newbrush->numsides = 0;
+	//newbrush->side = brush1->side;	//brush contents
+	//fix texinfos for sides lying in the same plane
+	for (i = 0; i < brush1->numsides; i++)
+	{
+		side1 = &brush1->sides[i];
+		//
+		for (n = 0; n < brush2->numsides; n++)
+		{
+			side2 = &brush2->sides[n];
+			//if both sides are in the same plane get the texinfo right
+			if (side1->planenum == side2->planenum)
+			{
+				if (side1->texinfo == TEXINFO_NODE) side1->texinfo = side2->texinfo;
+				if (side2->texinfo == TEXINFO_NODE) side2->texinfo = side1->texinfo;
+			} //end if
+		} //end for
+	} //end for
+	//
+	for (i = 0; i < brush1->numsides; i++)
+	{
+		side1 = &brush1->sides[i];
+		//don't add the "shared" sides
+		for (n = 0; n < brush2->numsides; n++)
+		{
+			side2 = &brush2->sides[n];
+			if (side1->planenum == (side2->planenum ^ 1)) break;
+		} //end for
+		if (n < brush2->numsides) continue;
+		//
+		for (n = 0; n < newbrush->numsides; n++)
+		{
+			cs = &newbrush->sides[n];
+			if (cs->planenum == side1->planenum)
+			{
+				Log_Print("brush duplicate plane\n");
+				break;
+			} //end if
+		} //end if
+		if (n < newbrush->numsides) continue;
+		//add this side
+		cs = &newbrush->sides[newbrush->numsides];
+		newbrush->numsides++;
+		*cs = *side1;
+	} //end for
+	for (j = 0; j < brush2->numsides; j++)
+	{
+		side2 = &brush2->sides[j];
+		for (n = 0; n < brush1->numsides; n++)
+		{
+			side1 = &brush1->sides[n];
+			//if the side is in the same plane
+			if (side2->planenum == side1->planenum) break;
+			//don't add the "shared" sides
+			if (side2->planenum == (side1->planenum ^ 1)) break;
+		} //end for
+		if (n < brush1->numsides) continue;
+		//
+		for (n = 0; n < newbrush->numsides; n++)
+		{
+			cs = &newbrush->sides[n];
+			if (cs->planenum == side2->planenum)
+			{
+				Log_Print("brush duplicate plane\n");
+				break;
+			} //end if
+		} //end if
+		if (n < newbrush->numsides) continue;
+		//add this side
+		cs = &newbrush->sides[newbrush->numsides];
+		newbrush->numsides++;
+		*cs = *side2;
+	} //end for
+	BSPBrushWindings(newbrush);
+	BoundBrush(newbrush);
+	CheckBSPBrush(newbrush);
+	return newbrush;
+} //end of the function TryMergeBrushes
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *MergeBrushes(bspbrush_t *brushlist)
+{
+	int nummerges, merged;
+	bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
+	bspbrush_t *lastb2;
+
+	if (!brushlist) return NULL;
+
+	qprintf("%5d brushes merged", nummerges = 0);
+	do
+	{
+		for (tail = brushlist; tail; tail = tail->next)
+		{
+			if (!tail->next) break;
+		} //end for
+		merged = 0;
+		newbrushlist = NULL;
+		for (b1 = brushlist; b1; b1 = brushlist)
+		{
+			lastb2 = b1;
+			for (b2 = b1->next; b2; b2 = b2->next)
+			{
+				//if the brushes don't have the same contents
+				if (b1->original->contents != b2->original->contents ||
+					b1->original->expansionbbox != b2->original->expansionbbox) newbrush = NULL;
+				else newbrush = TryMergeBrushes(b1, b2);
+				if (newbrush)
+				{
+					tail->next = newbrush;
+					lastb2->next = b2->next;
+					brushlist = brushlist->next;
+					FreeBrush(b1);
+					FreeBrush(b2);
+					for (tail = brushlist; tail; tail = tail->next)
+					{
+						if (!tail->next) break;
+					} //end for
+					merged++;
+					qprintf("\r%5d", nummerges++);
+					break;
+				} //end if
+				lastb2 = b2;
+			} //end for
+			//if b1 can't be merged with any of the other brushes
+			if (!b2)
+			{
+				brushlist = brushlist->next;
+				//keep b1
+				b1->next = newbrushlist;
+				newbrushlist = b1;
+			} //end else
+		} //end for
+		brushlist = newbrushlist;
+	} while(merged);
+	qprintf("\n");
+	return newbrushlist;
+} //end of the function MergeBrushes
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+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
+} //end of the function SplitBrush2
+//===========================================================================
+// 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.
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+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;
+		} //end if
+		in = back;
+	} //end for
+	if (in)
+	{
+		FreeBrush (in);
+	} //end if
+	else
+	{	// didn't really intersect
+		FreeBrushList (out);
+		return a;
+	} //end else
+	return out;
+} //end of the function SubtractBrush
+//===========================================================================
+// Returns a single brush made up by the intersection of the
+// two provided brushes, or NULL if they are disjoint.
+//
+// The originals are undisturbed.
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+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;
+	} //end for
+
+	if (in == a) return NULL;
+
+	in->next = NULL;
+	return in;
+} //end of the function IntersectBrush
+//===========================================================================
+// Returns true if the two brushes definately do not intersect.
+// There will be false negatives for some non-axial combinations.
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+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
+} //end of the function BrushesDisjoint
+//===========================================================================
+// 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.
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+int IntersectionContents (int c1, int c2)
+{
+	int out;
+
+	out = c1 | c2;
+
+	if (out & CONTENTS_SOLID) out = CONTENTS_SOLID;
+
+	return out;
+} //end of the function IntersectionContents
+//===========================================================================
+// Any planes shared with the box edge will be set to no texinfo
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *ClipBrushToBox(bspbrush_t *brush, vec3_t clipmins, vec3_t 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].flags &= ~SFL_VISIBLE;
+		}
+	}
+	return brush;
+} //end of the function ClipBrushToBox
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *MakeBspBrushList(int startbrush, int endbrush,
+											vec3_t clipmins, vec3_t clipmaxs)
+{
+	mapbrush_t	*mb;
+	bspbrush_t	*brushlist, *newbrush;
+	int			i, j;
+	int			c_faces;
+	int			c_brushes;
+	int			numsides;
+	int			vis;
+	vec3_t		normal;
+	float		dist;
+
+	for (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);
+	}
+
+	brushlist = NULL;
+	c_faces = 0;
+	c_brushes = 0;
+
+	for (i=startbrush ; i<endbrush ; i++)
+	{
+		mb = &mapbrushes[i];
+
+		numsides = mb->numsides;
+		if (!numsides)
+			continue;
+
+		// make sure the brush has at least one face showing
+		vis = 0;
+		for (j=0 ; j<numsides ; j++)
+			if ((mb->original_sides[j].flags & SFL_VISIBLE) && mb->original_sides[j].winding)
+				vis++;
+#if 0
+		if (!vis)
+			continue;	// no faces at all
+#endif
+		// if the brush is outside the clip area, skip it
+		for (j=0 ; j<3 ; j++)
+			if (mb->mins[j] >= clipmaxs[j]
+			|| mb->maxs[j] <= clipmins[j])
+			break;
+		if (j != 3)
+			continue;
+
+		//
+		// make a copy of the brush
+		//
+		newbrush = AllocBrush (mb->numsides);
+		newbrush->original = mb;
+		newbrush->numsides = mb->numsides;
+		memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));
+		for (j=0 ; j<numsides ; 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].flags |= SFL_VISIBLE;	// hints are always visible
+		}
+		VectorCopy (mb->mins, newbrush->mins);
+		VectorCopy (mb->maxs, newbrush->maxs);
+
+		//
+		// carve off anything outside the clip box
+		//
+		newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
+		if (!newbrush)
+			continue;
+
+		c_faces += vis;
+		c_brushes++;
+
+		newbrush->next = brushlist;
+		brushlist = newbrush;
+	}
+
+	return brushlist;
+} //end of the function MakeBspBrushList
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)
+{
+	bspbrush_t	*walk, *next;
+
+	for (walk=list ; walk ; walk=next)
+	{	// add to end of list
+		next = walk->next;
+		walk->next = NULL;
+		tail->next = walk;
+		tail = walk;
+	} //end for
+	return tail;
+} //end of the function AddBrushListToTail
+//===========================================================================
+// Builds a new list that doesn't hold the given brush
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *CullList(bspbrush_t *list, bspbrush_t *skip1)
+{
+	bspbrush_t	*newlist;
+	bspbrush_t	*next;
+
+	newlist = NULL;
+
+	for ( ; list ; list = next)
+	{
+		next = list->next;
+		if (list == skip1)
+		{
+			FreeBrush (list);
+			continue;
+		}
+		list->next = newlist;
+		newlist = list;
+	}
+	return newlist;
+} //end of the function CullList
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+/*
+void WriteBrushMap(char *name, bspbrush_t *list)
+{
+	FILE	*f;
+	side_t	*s;
+	int		i;
+	winding_t	*w;
+
+	Log_Print("writing %s\n", name);
+	f = fopen (name, "wb");
+	if (!f)
+		Error ("Can't write %s\b", name);
+
+	fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
+
+	for ( ; list ; list=list->next )
+	{
+		fprintf (f, "{\n");
+		for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
+		{
+			w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
+
+			fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
+			fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
+			fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
+
+			fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
+			FreeWinding (w);
+		}
+		fprintf (f, "}\n");
+	}
+	fprintf (f, "}\n");
+
+	fclose (f);
+} //end of the function WriteBrushMap
+*/
+//===========================================================================
+// Returns true if b1 is allowed to bite b2
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
+{
+#ifdef ME
+	if (create_aas)
+	{
+		if (b1->original->expansionbbox != b2->original->expansionbbox)
+		{
+			return false;
+		} //end if
+		//never have something else bite a ladder brush
+		//never have a ladder brush bite something else
+		if ( (b1->original->contents & CONTENTS_LADDER)
+			&& !(b2->original->contents & CONTENTS_LADDER))
+		{ 
+			return false;
+		} //end if
+	} //end if
+#endif //ME
+	// detail brushes never bite structural brushes
+	if ( (b1->original->contents & CONTENTS_DETAIL) 
+		&& !(b2->original->contents & CONTENTS_DETAIL) )
+	{
+		return false;
+	} //end if
+	if (b1->original->contents & CONTENTS_SOLID)
+	{
+		return true;
+	} //end if
+	return false;
+} //end of the function BrushGE
+//===========================================================================
+// Carves any intersecting solid brushes into the minimum number
+// of non-intersecting brushes.
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *ChopBrushes (bspbrush_t *head)
+{
+	bspbrush_t	*b1, *b2, *next;
+	bspbrush_t	*tail;
+	bspbrush_t	*keep;
+	bspbrush_t	*sub, *sub2;
+	int			c1, c2;
+	int num_csg_iterations;
+
+	Log_Print("-------- Brush CSG ---------\n");
+	Log_Print("%6d original brushes\n", CountBrushList (head));
+
+	num_csg_iterations = 0;
+	qprintf("%6d output brushes", num_csg_iterations);
+
+#if 0
+	if (startbrush == 0)
+		WriteBrushList ("before.gl", head, false);
+#endif
+	keep = NULL;
+
+newlist:
+	// find tail
+	if (!head) return NULL;
+
+	for (tail = head; tail->next; tail = tail->next)
+		;
+
+	for (b1=head ; b1 ; b1=next)
+	{
+		next = b1->next;
+
+		//if the conversion is cancelled
+		if (cancelconversion)
+		{
+			b1->next = keep;
+			keep = b1;
+			continue;
+		} //end if
+		
+		for (b2 = b1->next; b2; b2 = b2->next)
+		{
+			if (BrushesDisjoint (b1, b2))
+				continue;
+
+			sub = NULL;
+			sub2 = NULL;
+			c1 = 999999;
+			c2 = 999999;
+
+			if (BrushGE (b2, b1))
+			{
+				sub = SubtractBrush (b1, b2);
+				if (sub == b1)
+				{
+					continue;		// didn't really intersect
+				} //end if
+				if (!sub)
+				{	// b1 is swallowed by b2
+					head = CullList (b1, b1);
+					goto newlist;
+				}
+				c1 = CountBrushList (sub);
+			}
+
+			if ( BrushGE (b1, b2) )
+			{
+				sub2 = SubtractBrush (b2, b1);
+				if (sub2 == b2)
+					continue;		// didn't really intersect
+				if (!sub2)
+				{	// b2 is swallowed by b1
+					FreeBrushList (sub);
+					head = CullList (b1, b2);
+					goto newlist;
+				}
+				c2 = CountBrushList (sub2);
+			}
+
+			if (!sub && !sub2)
+				continue;		// neither one can bite
+
+			// only accept if it didn't fragment
+			// (commenting this out allows full fragmentation)
+			if (c1 > 1 && c2 > 1)
+			{
+				if (sub2)
+					FreeBrushList (sub2);
+				if (sub)
+					FreeBrushList (sub);
+				continue;
+			}
+
+			if (c1 < c2)
+			{
+				if (sub2) FreeBrushList (sub2);
+				tail = AddBrushListToTail (sub, tail);
+				head = CullList (b1, b1);
+				goto newlist;
+			} //end if
+			else
+			{
+				if (sub) FreeBrushList (sub);
+				tail = AddBrushListToTail (sub2, tail);
+				head = CullList (b1, b2);
+				goto newlist;
+			} //end else
+		} //end for
+
+		if (!b2)
+		{	// b1 is no longer intersecting anything, so keep it
+			b1->next = keep;
+			keep = b1;
+		} //end if
+		num_csg_iterations++;
+		qprintf("\r%6d", num_csg_iterations);
+	} //end for
+
+	if (cancelconversion) return keep;
+	//
+	qprintf("\n");
+	Log_Write("%6d output brushes\r\n", num_csg_iterations);
+
+#if 0
+	{
+		WriteBrushList ("after.gl", keep, false);
+		WriteBrushMap ("after.map", keep);
+	}
+#endif
+
+	return keep;
+} //end of the function ChopBrushes
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *InitialBrushList (bspbrush_t *list)
+{
+	bspbrush_t *b;
+	bspbrush_t	*out, *newb;
+	int			i;
+
+	// only return brushes that have visible faces
+	out = NULL;
+	for (b=list ; b ; b=b->next)
+	{
+#if 0
+		for (i=0 ; i<b->numsides ; i++)
+			if (b->sides[i].flags & SFL_VISIBLE)
+				break;
+		if (i == b->numsides)
+			continue;
+#endif
+		newb = CopyBrush (b);
+		newb->next = out;
+		out = newb;
+
+		// clear visible, so it must be set by MarkVisibleFaces_r
+		// to be used in the optimized list
+		for (i=0 ; i<b->numsides ; i++)
+		{
+			newb->sides[i].original = &b->sides[i];
+//			newb->sides[i].visible = true;
+			b->sides[i].flags &= ~SFL_VISIBLE;
+		}
+	}
+
+	return out;
+} //end of the function InitialBrushList
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+bspbrush_t *OptimizedBrushList (bspbrush_t *list)
+{
+	bspbrush_t *b;
+	bspbrush_t	*out, *newb;
+	int			i;
+
+	// only return brushes that have visible faces
+	out = NULL;
+	for (b=list ; b ; b=b->next)
+	{
+		for (i=0 ; i<b->numsides ; i++)
+			if (b->sides[i].flags & SFL_VISIBLE)
+				break;
+		if (i == b->numsides)
+			continue;
+		newb = CopyBrush (b);
+		newb->next = out;
+		out = newb;
+	} //end for
+
+//	WriteBrushList ("vis.gl", out, true);
+	return out;
+} //end of the function OptimizeBrushList
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+tree_t *ProcessWorldBrushes(int brush_start, int brush_end)
+{
+	bspbrush_t *brushes;
+	tree_t *tree;
+	node_t *node;
+	vec3_t mins, maxs;
+
+	//take the whole world
+	mins[0] = map_mins[0] - 8;
+	mins[1] = map_mins[1] - 8;
+	mins[2] = map_mins[2] - 8;
+
+	maxs[0] = map_maxs[0] + 8;
+	maxs[1] = map_maxs[1] + 8;
+	maxs[2] = map_maxs[2] + 8;
+
+	//reset the brush bsp
+	ResetBrushBSP();
+
+	// the makelist and chopbrushes could be cached between the passes...
+
+	//create a list with brushes that are within the given mins/maxs
+	//some brushes will be cut and only the part that falls within the
+	//mins/maxs will be in the bush list
+	brushes = MakeBspBrushList(brush_start, brush_end, mins, maxs);
+	//
+
+	if (!brushes)
+	{
+		node = AllocNode ();
+		node->planenum = PLANENUM_LEAF;
+		node->contents = CONTENTS_SOLID;
+
+		tree = Tree_Alloc();
+		tree->headnode = node;
+		VectorCopy(mins, tree->mins);
+		VectorCopy(maxs, tree->maxs);
+	} //end if
+	else
+	{
+		//Carves any intersecting solid brushes into the minimum number
+		//of non-intersecting brushes. 
+		if (!nocsg)
+		{
+			brushes = ChopBrushes(brushes);
+			/*
+			if (create_aas)
+			{
+				brushes = MergeBrushes(brushes);
+			} //end if*/
+		} //end if
+		//if the conversion is cancelled
+		if (cancelconversion)
+		{
+			FreeBrushList(brushes);
+			return NULL;
+		} //end if
+		//create the actual bsp tree
+		tree = BrushBSP(brushes, mins, maxs);
+	} //end else
+	//return the tree
+	return tree;
+} //end of the function ProcessWorldBrushes