]> git.xonotic.org Git - xonotic/netradiant.git/blobdiff - tools/quake3/q3map2/brush.c
eol style
[xonotic/netradiant.git] / tools / quake3 / q3map2 / brush.c
index eebc097ff32b8fbde9025640d19c8ca290581e00..28ade081bb46e0fcd05bf9e3625827464ba7099e 100644 (file)
-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
-\r
-----------------------------------------------------------------------------------\r
-\r
-This code has been altered significantly from its original form, to support\r
-several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
-\r
-------------------------------------------------------------------------------- */\r
-\r
-\r
-\r
-/* marker */\r
-#define BRUSH_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-/* -------------------------------------------------------------------------------\r
-\r
-functions\r
-\r
-------------------------------------------------------------------------------- */\r
-\r
-/*\r
-AllocSideRef() - ydnar\r
-allocates and assigns a brush side reference\r
-*/\r
-\r
-sideRef_t *AllocSideRef( side_t *side, sideRef_t *next )\r
-{\r
-       sideRef_t *sideRef;\r
-       \r
-       \r
-       /* dummy check */\r
-       if( side == NULL )\r
-               return next;\r
-       \r
-       /* allocate and return */\r
-       sideRef = safe_malloc( sizeof( *sideRef ) );\r
-       sideRef->side = side;\r
-       sideRef->next = next;\r
-       return sideRef;\r
-}\r
-\r
-\r
-\r
-/*\r
-CountBrushList()\r
-counts the number of brushes in a brush linked list\r
-*/\r
-\r
-int    CountBrushList( brush_t *brushes )\r
-{\r
-       int     c = 0;\r
-       \r
-       \r
-       /* count brushes */\r
-       for( brushes; brushes != NULL; brushes = brushes->next )\r
-               c++;\r
-       return c;\r
-}\r
-\r
-\r
-\r
-/*\r
-AllocBrush()\r
-allocates a new brush\r
-*/\r
-\r
-brush_t *AllocBrush( int numSides )\r
-{\r
-       brush_t         *bb;\r
-       int                     c;\r
-       \r
-       \r
-       /* allocate and clear */\r
-       if( numSides <= 0 )\r
-               Error( "AllocBrush called with numsides = %d", numSides );\r
-       c = (int) &(((brush_t*) 0)->sides[ numSides ]);\r
-       bb = safe_malloc( c );\r
-       memset( bb, 0, c );\r
-       if( numthreads == 1 )\r
-               numActiveBrushes++;\r
-       \r
-       /* return it */\r
-       return bb;\r
-}\r
-\r
-\r
-\r
-/*\r
-FreeBrush()\r
-frees a single brush and all sides/windings\r
-*/\r
-\r
-void FreeBrush( brush_t *b )\r
-{\r
-       int                     i;\r
-       \r
-       \r
-       /* error check */\r
-       if( *((int*) b) == 0xFEFEFEFE )\r
-       {\r
-               Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );\r
-               return;\r
-       }\r
-       \r
-       /* free brush sides */\r
-       for( i = 0; i < b->numsides; i++ )\r
-               if( b->sides[i].winding != NULL )\r
-                       FreeWinding( b->sides[ i ].winding );\r
-       \r
-       /* ydnar: overwrite it */\r
-       memset( b, 0xFE, (int) &(((brush_t*) 0)->sides[ b->numsides ]) );\r
-       *((int*) b) = 0xFEFEFEFE;\r
-       \r
-       /* free it */\r
-       free( b );\r
-       if( numthreads == 1 )\r
-               numActiveBrushes--;\r
-}\r
-\r
-\r
-\r
-/*\r
-FreeBrushList()\r
-frees a linked list of brushes\r
-*/\r
-\r
-void FreeBrushList( brush_t *brushes )\r
-{\r
-       brush_t         *next;\r
-       \r
-       \r
-       /* walk brush list */\r
-       for( brushes; brushes != NULL; brushes = next )\r
-       {\r
-               next = brushes->next;\r
-               FreeBrush( brushes );\r
-       }               \r
-}\r
-\r
-\r
-\r
-/*\r
-CopyBrush()\r
-duplicates the brush, sides, and windings\r
-*/\r
-\r
-brush_t *CopyBrush( brush_t *brush )\r
-{\r
-       brush_t         *newBrush;\r
-       int                     size;\r
-       int                     i;\r
-       \r
-       \r
-       /* copy brush */\r
-       size = (int) &(((brush_t*) 0)->sides[ brush->numsides ]);\r
-       newBrush = AllocBrush( brush->numsides );\r
-       memcpy( newBrush, brush, size );\r
-       \r
-       /* ydnar: nuke linked list */\r
-       newBrush->next = NULL;\r
-       \r
-       /* copy sides */\r
-       for( i = 0; i < brush->numsides; i++ )\r
-       {\r
-               if( brush->sides[ i ].winding != NULL )\r
-                       newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );\r
-       }\r
-       \r
-       /* return it */\r
-       return newBrush;\r
-}\r
-\r
-\r
-\r
-\r
-/*\r
-BoundBrush()\r
-sets the mins/maxs based on the windings\r
-returns false if the brush doesn't enclose a valid volume\r
-*/\r
-\r
-qboolean BoundBrush( brush_t *brush )\r
-{\r
-       int                     i, j;\r
-       winding_t       *w;\r
-       \r
-       \r
-       ClearBounds( brush->mins, brush->maxs );\r
-       for( i = 0; i < brush->numsides; i++ )\r
-       {\r
-               w = brush->sides[ i ].winding;\r
-               if( w == NULL )\r
-                       continue;\r
-               for( j = 0; j < w->numpoints; j++ )\r
-                       AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );\r
-       }\r
-       \r
-       for( i = 0; i < 3; i++ )\r
-       {\r
-               if( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] )\r
-                       return qfalse;\r
-       }\r
-       \r
-       return qtrue;\r
-}\r
-\r
-\r
-\r
-\r
-/*\r
-SnapWeldVector() - ydnar\r
-welds two vec3_t's into a third, taking into account nearest-to-integer\r
-instead of averaging\r
-*/\r
-\r
-#define SNAP_EPSILON   0.01\r
-\r
-void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out )\r
-{\r
-       int             i;\r
-       vec_t   ai, bi, outi;\r
-       \r
-       \r
-       /* dummy check */\r
-       if( a == NULL || b == NULL || out == NULL )\r
-               return;\r
-       \r
-       /* do each element */\r
-       for( i = 0; i < 3; i++ )\r
-       {\r
-               /* round to integer */\r
-               ai = Q_rint( a[ i ] );\r
-               bi = Q_rint( a[ i ] );\r
-               \r
-               /* prefer exact integer */\r
-               if( ai == a[ i ] )\r
-                       out[ i ] = a[ i ];\r
-               else if( bi == b[ i ] )\r
-                       out[ i ] = b[ i ];\r
-\r
-               /* use nearest */\r
-               else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )\r
-                       out[ i ] = a[ i ];\r
-               else\r
-                       out[ i ] = b[ i ];\r
-               \r
-               /* snap */\r
-               outi = Q_rint( out[ i ] );\r
-               if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )\r
-                       out[ i ] = outi;\r
-       }\r
-}\r
-\r
-\r
-\r
-/*\r
-FixWinding() - ydnar\r
-removes degenerate edges from a winding\r
-returns qtrue if the winding is valid\r
-*/\r
-\r
-#define DEGENERATE_EPSILON     0.1\r
-\r
-qboolean FixWinding( winding_t *w )\r
-{\r
-       qboolean        valid = qtrue;\r
-       int                     i, j, k;\r
-       vec3_t          vec;\r
-       float           dist;\r
-       \r
-       \r
-       /* dummy check */\r
-       if( !w )\r
-               return qfalse;\r
-       \r
-       /* check all verts */\r
-       for( i = 0; i < w->numpoints; i++ )\r
-       {\r
-               /* don't remove points if winding is a triangle */\r
-               if( w->numpoints == 3 )\r
-                       return valid;\r
-               \r
-               /* get second point index */\r
-               j = (i + 1) % w->numpoints;\r
-               \r
-               /* degenerate edge? */\r
-               VectorSubtract( w->p[ i ], w->p[ j ], vec );\r
-               dist = VectorLength( vec );\r
-               if( dist < DEGENERATE_EPSILON )\r
-               {\r
-                       valid = qfalse;\r
-                       //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );\r
-                       \r
-                       /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */\r
-                       SnapWeldVector( w->p[ i ], w->p[ j ], vec );\r
-                       VectorCopy( vec, w->p[ i ] );\r
-                       //VectorAdd( w->p[ i ], w->p[ j ], vec );\r
-                       //VectorScale( vec, 0.5, w->p[ i ] );\r
-                       \r
-                       /* move the remaining verts */\r
-                       for( k = i + 2; k < w->numpoints; k++ )\r
-                       {\r
-                               VectorCopy( w->p[ k ], w->p[ k - 1 ] );\r
-                       }\r
-                       w->numpoints--;\r
-               }\r
-       }\r
-       \r
-       /* one last check and return */\r
-       if( w->numpoints < 3 )\r
-               valid = qfalse;\r
-       return valid;\r
-}\r
-\r
-\r
-\r
-\r
-\r
-\r
-\r
-/*\r
-CreateBrushWindings()\r
-makes basewindigs for sides and mins/maxs for the brush\r
-returns false if the brush doesn't enclose a valid volume\r
-*/\r
-\r
-qboolean CreateBrushWindings( brush_t *brush )\r
-{\r
-       int                     i, j;\r
-       winding_t       *w;\r
-       side_t          *side;\r
-       plane_t         *plane;\r
-       \r
-       \r
-       /* walk the list of brush sides */\r
-       for( i = 0; i < brush->numsides; i++ )\r
-       {\r
-               /* get side and plane */\r
-               side = &brush->sides[ i ];\r
-               plane = &mapplanes[ side->planenum ];\r
-               \r
-               /* make huge winding */\r
-               w = BaseWindingForPlane( plane->normal, plane->dist );\r
-               \r
-               /* walk the list of brush sides */\r
-               for( j = 0; j < brush->numsides && w != NULL; j++ )\r
-               {\r
-                       if( i == j )\r
-                               continue;\r
-                       if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )\r
-                               continue;               /* back side clipaway */\r
-                       if( brush->sides[ j ].bevel )\r
-                               continue;\r
-                       if( brush->sides[ j ].backSide )\r
-                               continue;\r
-                       plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];\r
-                       ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );\r
-                       \r
-                       /* ydnar: fix broken windings that would generate trifans */\r
-                       FixWinding( w );\r
-               }\r
-               \r
-               /* set side winding */\r
-               side->winding = w;\r
-       }\r
-       \r
-       /* find brush bounds */\r
-       return BoundBrush( brush );\r
-}\r
-\r
-\r
-\r
-\r
-/*\r
-==================\r
-BrushFromBounds\r
-\r
-Creates a new axial brush\r
-==================\r
-*/\r
-brush_t        *BrushFromBounds (vec3_t mins, vec3_t maxs)\r
-{\r
-       brush_t         *b;\r
-       int                     i;\r
-       vec3_t          normal;\r
-       vec_t           dist;\r
-\r
-       b = AllocBrush (6);\r
-       b->numsides = 6;\r
-       for (i=0 ; i<3 ; i++)\r
-       {\r
-               VectorClear (normal);\r
-               normal[i] = 1;\r
-               dist = maxs[i];\r
-               b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );\r
-\r
-               normal[i] = -1;\r
-               dist = -mins[i];\r
-               b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );\r
-       }\r
-\r
-       CreateBrushWindings (b);\r
-\r
-       return b;\r
-}\r
-\r
-/*\r
-==================\r
-BrushVolume\r
-\r
-==================\r
-*/\r
-vec_t BrushVolume (brush_t *brush)\r
-{\r
-       int                     i;\r
-       winding_t       *w;\r
-       vec3_t          corner;\r
-       vec_t           d, area, volume;\r
-       plane_t         *plane;\r
-\r
-       if (!brush)\r
-               return 0;\r
-\r
-       // grab the first valid point as the corner\r
-\r
-       w = NULL;\r
-       for (i=0 ; i<brush->numsides ; i++)\r
-       {\r
-               w = brush->sides[i].winding;\r
-               if (w)\r
-                       break;\r
-       }\r
-       if (!w)\r
-               return 0;\r
-       VectorCopy (w->p[0], corner);\r
-\r
-       // make tetrahedrons to all other faces\r
-\r
-       volume = 0;\r
-       for ( ; i<brush->numsides ; i++)\r
-       {\r
-               w = brush->sides[i].winding;\r
-               if (!w)\r
-                       continue;\r
-               plane = &mapplanes[brush->sides[i].planenum];\r
-               d = -(DotProduct (corner, plane->normal) - plane->dist);\r
-               area = WindingArea (w);\r
-               volume += d*area;\r
-       }\r
-\r
-       volume /= 3;\r
-       return volume;\r
-}\r
-\r
-\r
-\r
-/*\r
-WriteBSPBrushMap()\r
-writes a map with the split bsp brushes\r
-*/\r
-\r
-void WriteBSPBrushMap( char *name, brush_t *list )\r
-{\r
-       FILE            *f;\r
-       side_t          *s;\r
-       int                     i;\r
-       winding_t       *w;\r
-       \r
-       \r
-       /* note it */\r
-       Sys_Printf( "Writing %s\n", name );\r
-       \r
-       /* open the map file */\r
-       f = fopen( name, "wb" );\r
-       if( f == NULL )\r
-               Error( "Can't write %s\b", name );\r
-\r
-       fprintf (f, "{\n\"classname\" \"worldspawn\"\n");\r
-\r
-       for ( ; list ; list=list->next )\r
-       {\r
-               fprintf (f, "{\n");\r
-               for (i=0,s=list->sides ; i<list->numsides ; i++,s++)\r
-               {\r
-                       w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);\r
-\r
-                       fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);\r
-                       fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);\r
-                       fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);\r
-\r
-                       fprintf (f, "notexture 0 0 0 1 1\n" );\r
-                       FreeWinding (w);\r
-               }\r
-               fprintf (f, "}\n");\r
-       }\r
-       fprintf (f, "}\n");\r
-\r
-       fclose (f);\r
-\r
-}\r
-\r
-\r
-\r
-/*\r
-FilterBrushIntoTree_r()\r
-adds brush reference to any intersecting bsp leafnode\r
-*/\r
-\r
-int FilterBrushIntoTree_r( brush_t *b, node_t *node )\r
-{\r
-       brush_t         *front, *back;\r
-       int                     c;\r
-       \r
-       \r
-       /* dummy check */\r
-       if( b == NULL )\r
-               return 0;\r
-       \r
-       /* add it to the leaf list */\r
-       if( node->planenum == PLANENUM_LEAF )\r
-       {\r
-               /* something somewhere is hammering brushlist */\r
-               b->next = node->brushlist;\r
-               node->brushlist = b;\r
-               \r
-               /* classify the leaf by the structural brush */\r
-               if( !b->detail )\r
-               {\r
-                       if( b->opaque )\r
-                       {\r
-                               node->opaque = qtrue;\r
-                               node->areaportal = qfalse;\r
-                       }\r
-                       else if( b->compileFlags & C_AREAPORTAL )\r
-                       {\r
-                               if( !node->opaque )\r
-                                       node->areaportal = qtrue;\r
-                       }\r
-               }\r
-               \r
-               return 1;\r
-       }\r
-       \r
-       /* split it by the node plane */\r
-       c = b->numsides;\r
-       SplitBrush( b, node->planenum, &front, &back );\r
-       FreeBrush( b );\r
-       \r
-       c = 0;\r
-       c += FilterBrushIntoTree_r( front, node->children[ 0 ] );\r
-       c += FilterBrushIntoTree_r( back, node->children[ 1 ] );\r
-       \r
-       return c;\r
-}\r
-\r
-\r
-\r
-/*\r
-FilterDetailBrushesIntoTree\r
-fragment all the detail brushes into the structural leafs\r
-*/\r
-\r
-void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )\r
-{\r
-       brush_t                         *b, *newb;\r
-       int                                     r;\r
-       int                                     c_unique, c_clusters;\r
-       int                                     i;\r
-       \r
-       \r
-       /* note it */\r
-       Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );\r
-       \r
-       /* walk the list of brushes */\r
-       c_unique = 0;\r
-       c_clusters = 0;\r
-       for( b = e->brushes; b; b = b->next )\r
-       {\r
-               if( !b->detail )\r
-                       continue;\r
-               c_unique++;\r
-               newb = CopyBrush( b );\r
-               r = FilterBrushIntoTree_r( newb, tree->headnode );\r
-               c_clusters += r;\r
-               \r
-               /* mark all sides as visible so drawsurfs are created */\r
-               if( r )\r
-               {\r
-                       for( i = 0; i < b->numsides; i++ )\r
-                       {\r
-                               if( b->sides[ i ].winding )\r
-                                       b->sides[ i ].visible = qtrue;\r
-                       }\r
-               }\r
-       }\r
-       \r
-       /* emit some statistics */\r
-       Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );\r
-       Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );\r
-}\r
-\r
-/*\r
-=====================\r
-FilterStructuralBrushesIntoTree\r
-\r
-Mark the leafs as opaque and areaportals\r
-=====================\r
-*/\r
-void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {\r
-       brush_t                 *b, *newb;\r
-       int                                     r;\r
-       int                                     c_unique, c_clusters;\r
-       int                                     i;\r
-\r
-       Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");\r
-\r
-       c_unique = 0;\r
-       c_clusters = 0;\r
-       for ( b = e->brushes ; b ; b = b->next ) {\r
-               if ( b->detail ) {\r
-                       continue;\r
-               }\r
-               c_unique++;\r
-               newb = CopyBrush( b );\r
-               r = FilterBrushIntoTree_r( newb, tree->headnode );\r
-               c_clusters += r;\r
-\r
-               // mark all sides as visible so drawsurfs are created\r
-               if ( r ) {\r
-                       for ( i = 0 ; i < b->numsides ; i++ ) {\r
-                               if ( b->sides[i].winding ) {\r
-                                       b->sides[i].visible = qtrue;\r
-                               }\r
-                       }\r
-               }\r
-       }\r
-       \r
-       /* emit some statistics */\r
-       Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );\r
-       Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );\r
-}\r
-\r
-\r
-\r
-/*\r
-================\r
-AllocTree\r
-================\r
-*/\r
-tree_t *AllocTree (void)\r
-{\r
-       tree_t  *tree;\r
-\r
-       tree = safe_malloc(sizeof(*tree));\r
-       memset (tree, 0, sizeof(*tree));\r
-       ClearBounds (tree->mins, tree->maxs);\r
-\r
-       return tree;\r
-}\r
-\r
-/*\r
-================\r
-AllocNode\r
-================\r
-*/\r
-node_t *AllocNode (void)\r
-{\r
-       node_t  *node;\r
-\r
-       node = safe_malloc(sizeof(*node));\r
-       memset (node, 0, sizeof(*node));\r
-\r
-       return node;\r
-}\r
-\r
-\r
-/*\r
-================\r
-WindingIsTiny\r
-\r
-Returns true if the winding would be crunched out of\r
-existance by the vertex snapping.\r
-================\r
-*/\r
-#define        EDGE_LENGTH     0.2\r
-qboolean WindingIsTiny (winding_t *w)\r
-{\r
-/*\r
-       if (WindingArea (w) < 1)\r
-               return qtrue;\r
-       return qfalse;\r
-*/\r
-       int             i, j;\r
-       vec_t   len;\r
-       vec3_t  delta;\r
-       int             edges;\r
-\r
-       edges = 0;\r
-       for (i=0 ; i<w->numpoints ; i++)\r
-       {\r
-               j = i == w->numpoints - 1 ? 0 : i+1;\r
-               VectorSubtract (w->p[j], w->p[i], delta);\r
-               len = VectorLength (delta);\r
-               if (len > EDGE_LENGTH)\r
-               {\r
-                       if (++edges == 3)\r
-                               return qfalse;\r
-               }\r
-       }\r
-       return qtrue;\r
-}\r
-\r
-/*\r
-================\r
-WindingIsHuge\r
-\r
-Returns true if the winding still has one of the points\r
-from basewinding for plane\r
-================\r
-*/\r
-qboolean WindingIsHuge (winding_t *w)\r
-{\r
-       int             i, j;\r
-\r
-       for (i=0 ; i<w->numpoints ; i++)\r
-       {\r
-               for (j=0 ; j<3 ; j++)\r
-                       if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)\r
-                               return qtrue;\r
-       }\r
-       return qfalse;\r
-}\r
-\r
-//============================================================\r
-\r
-/*\r
-==================\r
-BrushMostlyOnSide\r
-\r
-==================\r
-*/\r
-int BrushMostlyOnSide (brush_t *brush, plane_t *plane)\r
-{\r
-       int                     i, j;\r
-       winding_t       *w;\r
-       vec_t           d, max;\r
-       int                     side;\r
-\r
-       max = 0;\r
-       side = PSIDE_FRONT;\r
-       for (i=0 ; i<brush->numsides ; i++)\r
-       {\r
-               w = brush->sides[i].winding;\r
-               if (!w)\r
-                       continue;\r
-               for (j=0 ; j<w->numpoints ; j++)\r
-               {\r
-                       d = DotProduct (w->p[j], plane->normal) - plane->dist;\r
-                       if (d > max)\r
-                       {\r
-                               max = d;\r
-                               side = PSIDE_FRONT;\r
-                       }\r
-                       if (-d > max)\r
-                       {\r
-                               max = -d;\r
-                               side = PSIDE_BACK;\r
-                       }\r
-               }\r
-       }\r
-       return side;\r
-}\r
-\r
-\r
-\r
-/*\r
-SplitBrush()\r
-generates two new brushes, leaving the original unchanged\r
-*/\r
-\r
-void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )\r
-{\r
-       brush_t         *b[2];\r
-       int                     i, j;\r
-       winding_t       *w, *cw[2], *midwinding;\r
-       plane_t         *plane, *plane2;\r
-       side_t          *s, *cs;\r
-       float           d, d_front, d_back;\r
-       \r
-       \r
-       *front = NULL;\r
-       *back = NULL;\r
-       plane = &mapplanes[planenum];\r
-       \r
-       // check all points\r
-       d_front = d_back = 0;\r
-       for (i=0 ; i<brush->numsides ; i++)\r
-       {\r
-               w = brush->sides[i].winding;\r
-               if (!w)\r
-                       continue;\r
-               for (j=0 ; j<w->numpoints ; j++)\r
-               {\r
-                       d = DotProduct (w->p[j], plane->normal) - plane->dist;\r
-                       if (d > 0 && d > d_front)\r
-                               d_front = d;\r
-                       if (d < 0 && d < d_back)\r
-                               d_back = d;\r
-               }\r
-       }\r
-       \r
-       if (d_front < 0.1) // PLANESIDE_EPSILON)\r
-       {       // only on back\r
-               *back = CopyBrush( brush );\r
-               return;\r
-       }\r
-       \r
-       if (d_back > -0.1) // PLANESIDE_EPSILON)\r
-       {       // only on front\r
-               *front = CopyBrush( brush );\r
-               return;\r
-       }\r
-       \r
-       // create a new winding from the split plane\r
-       w = BaseWindingForPlane (plane->normal, plane->dist);\r
-       for (i=0 ; i<brush->numsides && w ; i++)\r
-       {\r
-               if ( brush->sides[i].backSide ) {\r
-                       continue;       // fake back-sided polygons never split\r
-               }\r
-               plane2 = &mapplanes[brush->sides[i].planenum ^ 1];\r
-               ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);\r
-       }\r
-\r
-       if (!w || WindingIsTiny (w) )\r
-       {       // the brush isn't really split\r
-               int             side;\r
-\r
-               side = BrushMostlyOnSide (brush, plane);\r
-               if (side == PSIDE_FRONT)\r
-                       *front = CopyBrush (brush);\r
-               if (side == PSIDE_BACK)\r
-                       *back = CopyBrush (brush);\r
-               return;\r
-       }\r
-       \r
-       if( WindingIsHuge( w ) )\r
-               Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );\r
-\r
-       midwinding = w;\r
-\r
-       // split it for real\r
-\r
-       for (i=0 ; i<2 ; i++)\r
-       {\r
-               b[i] = AllocBrush (brush->numsides+1);\r
-               memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );\r
-               b[i]->numsides = 0;\r
-               b[i]->next = NULL;\r
-               b[i]->original = brush->original;\r
-       }\r
-\r
-       // split all the current windings\r
-\r
-       for (i=0 ; i<brush->numsides ; i++)\r
-       {\r
-               s = &brush->sides[i];\r
-               w = s->winding;\r
-               if (!w)\r
-                       continue;\r
-               ClipWindingEpsilon (w, plane->normal, plane->dist,\r
-                       0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);\r
-               for (j=0 ; j<2 ; j++)\r
-               {\r
-                       if (!cw[j])\r
-                               continue;\r
-                       cs = &b[j]->sides[b[j]->numsides];\r
-                       b[j]->numsides++;\r
-                       *cs = *s;\r
-                       cs->winding = cw[j];\r
-               }\r
-       }\r
-\r
-\r
-       // see if we have valid polygons on both sides\r
-       for (i=0 ; i<2 ; i++)\r
-       {\r
-               BoundBrush (b[i]);\r
-               for (j=0 ; j<3 ; j++)\r
-               {\r
-                       if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD)\r
-                       {\r
-                               Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");\r
-                               break;\r
-                       }\r
-               }\r
-\r
-               if (b[i]->numsides < 3 || j < 3)\r
-               {\r
-                       FreeBrush (b[i]);\r
-                       b[i] = NULL;\r
-               }\r
-       }\r
-       \r
-       if ( !(b[0] && b[1]) )\r
-       {\r
-               if (!b[0] && !b[1])\r
-                       Sys_FPrintf (SYS_VRB,"split removed brush\n");\r
-               else\r
-                       Sys_FPrintf (SYS_VRB,"split not on both sides\n");\r
-               if (b[0])\r
-               {\r
-                       FreeBrush (b[0]);\r
-                       *front = CopyBrush (brush);\r
-               }\r
-               if (b[1])\r
-               {\r
-                       FreeBrush (b[1]);\r
-                       *back = CopyBrush (brush);\r
-               }\r
-               return;\r
-       }\r
-       \r
-       // add the midwinding to both sides\r
-       for (i=0 ; i<2 ; i++)\r
-       {\r
-               cs = &b[i]->sides[b[i]->numsides];\r
-               b[i]->numsides++;\r
-\r
-               cs->planenum = planenum^i^1;\r
-               cs->shaderInfo = NULL;\r
-               if (i==0)\r
-                       cs->winding = CopyWinding (midwinding);\r
-               else\r
-                       cs->winding = midwinding;\r
-       }\r
-       \r
-       {\r
-               vec_t   v1;\r
-               int             i;\r
-               \r
-               \r
-               for (i=0 ; i<2 ; i++)\r
-               {\r
-                       v1 = BrushVolume (b[i]);\r
-                       if (v1 < 1.0)\r
-                       {\r
-                               FreeBrush (b[i]);\r
-                               b[i] = NULL;\r
-       //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");\r
-                       }\r
-               }\r
-       }\r
-       \r
-       *front = b[0];\r
-       *back = b[1];\r
-}\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant 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.
+
+GtkRadiant 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 GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+----------------------------------------------------------------------------------
+
+This code has been altered significantly from its original form, to support
+several games based on the Quake III Arena engine, in the form of "Q3Map2."
+
+------------------------------------------------------------------------------- */
+
+
+
+/* marker */
+#define BRUSH_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+/* -------------------------------------------------------------------------------
+
+functions
+
+------------------------------------------------------------------------------- */
+
+/*
+AllocSideRef() - ydnar
+allocates and assigns a brush side reference
+*/
+
+sideRef_t *AllocSideRef( side_t *side, sideRef_t *next )
+{
+       sideRef_t *sideRef;
+       
+       
+       /* dummy check */
+       if( side == NULL )
+               return next;
+       
+       /* allocate and return */
+       sideRef = safe_malloc( sizeof( *sideRef ) );
+       sideRef->side = side;
+       sideRef->next = next;
+       return sideRef;
+}
+
+
+
+/*
+CountBrushList()
+counts the number of brushes in a brush linked list
+*/
+
+int    CountBrushList( brush_t *brushes )
+{
+       int     c = 0;
+       
+       
+       /* count brushes */
+       for( brushes; brushes != NULL; brushes = brushes->next )
+               c++;
+       return c;
+}
+
+
+
+/*
+AllocBrush()
+allocates a new brush
+*/
+
+brush_t *AllocBrush( int numSides )
+{
+       brush_t         *bb;
+       int                     c;
+       
+       
+       /* allocate and clear */
+       if( numSides <= 0 )
+               Error( "AllocBrush called with numsides = %d", numSides );
+       c = (int) &(((brush_t*) 0)->sides[ numSides ]);
+       bb = safe_malloc( c );
+       memset( bb, 0, c );
+       if( numthreads == 1 )
+               numActiveBrushes++;
+       
+       /* return it */
+       return bb;
+}
+
+
+
+/*
+FreeBrush()
+frees a single brush and all sides/windings
+*/
+
+void FreeBrush( brush_t *b )
+{
+       int                     i;
+       
+       
+       /* error check */
+       if( *((int*) b) == 0xFEFEFEFE )
+       {
+               Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
+               return;
+       }
+       
+       /* free brush sides */
+       for( i = 0; i < b->numsides; i++ )
+               if( b->sides[i].winding != NULL )
+                       FreeWinding( b->sides[ i ].winding );
+       
+       /* ydnar: overwrite it */
+       memset( b, 0xFE, (int) &(((brush_t*) 0)->sides[ b->numsides ]) );
+       *((int*) b) = 0xFEFEFEFE;
+       
+       /* free it */
+       free( b );
+       if( numthreads == 1 )
+               numActiveBrushes--;
+}
+
+
+
+/*
+FreeBrushList()
+frees a linked list of brushes
+*/
+
+void FreeBrushList( brush_t *brushes )
+{
+       brush_t         *next;
+       
+       
+       /* walk brush list */
+       for( brushes; brushes != NULL; brushes = next )
+       {
+               next = brushes->next;
+               FreeBrush( brushes );
+       }               
+}
+
+
+
+/*
+CopyBrush()
+duplicates the brush, sides, and windings
+*/
+
+brush_t *CopyBrush( brush_t *brush )
+{
+       brush_t         *newBrush;
+       int                     size;
+       int                     i;
+       
+       
+       /* copy brush */
+       size = (int) &(((brush_t*) 0)->sides[ brush->numsides ]);
+       newBrush = AllocBrush( brush->numsides );
+       memcpy( newBrush, brush, size );
+       
+       /* ydnar: nuke linked list */
+       newBrush->next = NULL;
+       
+       /* copy sides */
+       for( i = 0; i < brush->numsides; i++ )
+       {
+               if( brush->sides[ i ].winding != NULL )
+                       newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
+       }
+       
+       /* return it */
+       return newBrush;
+}
+
+
+
+
+/*
+BoundBrush()
+sets the mins/maxs based on the windings
+returns false if the brush doesn't enclose a valid volume
+*/
+
+qboolean BoundBrush( brush_t *brush )
+{
+       int                     i, j;
+       winding_t       *w;
+       
+       
+       ClearBounds( brush->mins, brush->maxs );
+       for( i = 0; i < brush->numsides; i++ )
+       {
+               w = brush->sides[ i ].winding;
+               if( w == NULL )
+                       continue;
+               for( j = 0; j < w->numpoints; j++ )
+                       AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
+       }
+       
+       for( i = 0; i < 3; i++ )
+       {
+               if( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] )
+                       return qfalse;
+       }
+       
+       return qtrue;
+}
+
+
+
+
+/*
+SnapWeldVector() - ydnar
+welds two vec3_t's into a third, taking into account nearest-to-integer
+instead of averaging
+*/
+
+#define SNAP_EPSILON   0.01
+
+void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out )
+{
+       int             i;
+       vec_t   ai, bi, outi;
+       
+       
+       /* dummy check */
+       if( a == NULL || b == NULL || out == NULL )
+               return;
+       
+       /* do each element */
+       for( i = 0; i < 3; i++ )
+       {
+               /* round to integer */
+               ai = Q_rint( a[ i ] );
+               bi = Q_rint( a[ i ] );
+               
+               /* prefer exact integer */
+               if( ai == a[ i ] )
+                       out[ i ] = a[ i ];
+               else if( bi == b[ i ] )
+                       out[ i ] = b[ i ];
+
+               /* use nearest */
+               else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )
+                       out[ i ] = a[ i ];
+               else
+                       out[ i ] = b[ i ];
+               
+               /* snap */
+               outi = Q_rint( out[ i ] );
+               if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )
+                       out[ i ] = outi;
+       }
+}
+
+
+
+/*
+FixWinding() - ydnar
+removes degenerate edges from a winding
+returns qtrue if the winding is valid
+*/
+
+#define DEGENERATE_EPSILON     0.1
+
+qboolean FixWinding( winding_t *w )
+{
+       qboolean        valid = qtrue;
+       int                     i, j, k;
+       vec3_t          vec;
+       float           dist;
+       
+       
+       /* dummy check */
+       if( !w )
+               return qfalse;
+       
+       /* check all verts */
+       for( i = 0; i < w->numpoints; i++ )
+       {
+               /* don't remove points if winding is a triangle */
+               if( w->numpoints == 3 )
+                       return valid;
+               
+               /* get second point index */
+               j = (i + 1) % w->numpoints;
+               
+               /* degenerate edge? */
+               VectorSubtract( w->p[ i ], w->p[ j ], vec );
+               dist = VectorLength( vec );
+               if( dist < DEGENERATE_EPSILON )
+               {
+                       valid = qfalse;
+                       //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
+                       
+                       /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
+                       SnapWeldVector( w->p[ i ], w->p[ j ], vec );
+                       VectorCopy( vec, w->p[ i ] );
+                       //VectorAdd( w->p[ i ], w->p[ j ], vec );
+                       //VectorScale( vec, 0.5, w->p[ i ] );
+                       
+                       /* move the remaining verts */
+                       for( k = i + 2; k < w->numpoints; k++ )
+                       {
+                               VectorCopy( w->p[ k ], w->p[ k - 1 ] );
+                       }
+                       w->numpoints--;
+               }
+       }
+       
+       /* one last check and return */
+       if( w->numpoints < 3 )
+               valid = qfalse;
+       return valid;
+}
+
+
+
+
+
+
+
+/*
+CreateBrushWindings()
+makes basewindigs for sides and mins/maxs for the brush
+returns false if the brush doesn't enclose a valid volume
+*/
+
+qboolean CreateBrushWindings( brush_t *brush )
+{
+       int                     i, j;
+       winding_t       *w;
+       side_t          *side;
+       plane_t         *plane;
+       
+       
+       /* walk the list of brush sides */
+       for( i = 0; i < brush->numsides; i++ )
+       {
+               /* get side and plane */
+               side = &brush->sides[ i ];
+               plane = &mapplanes[ side->planenum ];
+               
+               /* make huge winding */
+               w = BaseWindingForPlane( plane->normal, plane->dist );
+               
+               /* walk the list of brush sides */
+               for( j = 0; j < brush->numsides && w != NULL; j++ )
+               {
+                       if( i == j )
+                               continue;
+                       if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
+                               continue;               /* back side clipaway */
+                       if( brush->sides[ j ].bevel )
+                               continue;
+                       if( brush->sides[ j ].backSide )
+                               continue;
+                       plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
+                       ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
+                       
+                       /* ydnar: fix broken windings that would generate trifans */
+                       FixWinding( w );
+               }
+               
+               /* set side winding */
+               side->winding = w;
+       }
+       
+       /* find brush bounds */
+       return BoundBrush( brush );
+}
+
+
+
+
+/*
+==================
+BrushFromBounds
+
+Creates a new axial brush
+==================
+*/
+brush_t        *BrushFromBounds (vec3_t mins, vec3_t maxs)
+{
+       brush_t         *b;
+       int                     i;
+       vec3_t          normal;
+       vec_t           dist;
+
+       b = AllocBrush (6);
+       b->numsides = 6;
+       for (i=0 ; i<3 ; i++)
+       {
+               VectorClear (normal);
+               normal[i] = 1;
+               dist = maxs[i];
+               b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
+
+               normal[i] = -1;
+               dist = -mins[i];
+               b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
+       }
+
+       CreateBrushWindings (b);
+
+       return b;
+}
+
+/*
+==================
+BrushVolume
+
+==================
+*/
+vec_t BrushVolume (brush_t *brush)
+{
+       int                     i;
+       winding_t       *w;
+       vec3_t          corner;
+       vec_t           d, area, volume;
+       plane_t         *plane;
+
+       if (!brush)
+               return 0;
+
+       // grab the first valid point as the corner
+
+       w = NULL;
+       for (i=0 ; i<brush->numsides ; i++)
+       {
+               w = brush->sides[i].winding;
+               if (w)
+                       break;
+       }
+       if (!w)
+               return 0;
+       VectorCopy (w->p[0], corner);
+
+       // make tetrahedrons to all other faces
+
+       volume = 0;
+       for ( ; i<brush->numsides ; i++)
+       {
+               w = brush->sides[i].winding;
+               if (!w)
+                       continue;
+               plane = &mapplanes[brush->sides[i].planenum];
+               d = -(DotProduct (corner, plane->normal) - plane->dist);
+               area = WindingArea (w);
+               volume += d*area;
+       }
+
+       volume /= 3;
+       return volume;
+}
+
+
+
+/*
+WriteBSPBrushMap()
+writes a map with the split bsp brushes
+*/
+
+void WriteBSPBrushMap( char *name, brush_t *list )
+{
+       FILE            *f;
+       side_t          *s;
+       int                     i;
+       winding_t       *w;
+       
+       
+       /* note it */
+       Sys_Printf( "Writing %s\n", name );
+       
+       /* open the map file */
+       f = fopen( name, "wb" );
+       if( f == NULL )
+               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, "notexture 0 0 0 1 1\n" );
+                       FreeWinding (w);
+               }
+               fprintf (f, "}\n");
+       }
+       fprintf (f, "}\n");
+
+       fclose (f);
+
+}
+
+
+
+/*
+FilterBrushIntoTree_r()
+adds brush reference to any intersecting bsp leafnode
+*/
+
+int FilterBrushIntoTree_r( brush_t *b, node_t *node )
+{
+       brush_t         *front, *back;
+       int                     c;
+       
+       
+       /* dummy check */
+       if( b == NULL )
+               return 0;
+       
+       /* add it to the leaf list */
+       if( node->planenum == PLANENUM_LEAF )
+       {
+               /* something somewhere is hammering brushlist */
+               b->next = node->brushlist;
+               node->brushlist = b;
+               
+               /* classify the leaf by the structural brush */
+               if( !b->detail )
+               {
+                       if( b->opaque )
+                       {
+                               node->opaque = qtrue;
+                               node->areaportal = qfalse;
+                       }
+                       else if( b->compileFlags & C_AREAPORTAL )
+                       {
+                               if( !node->opaque )
+                                       node->areaportal = qtrue;
+                       }
+               }
+               
+               return 1;
+       }
+       
+       /* split it by the node plane */
+       c = b->numsides;
+       SplitBrush( b, node->planenum, &front, &back );
+       FreeBrush( b );
+       
+       c = 0;
+       c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
+       c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
+       
+       return c;
+}
+
+
+
+/*
+FilterDetailBrushesIntoTree
+fragment all the detail brushes into the structural leafs
+*/
+
+void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
+{
+       brush_t                         *b, *newb;
+       int                                     r;
+       int                                     c_unique, c_clusters;
+       int                                     i;
+       
+       
+       /* note it */
+       Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
+       
+       /* walk the list of brushes */
+       c_unique = 0;
+       c_clusters = 0;
+       for( b = e->brushes; b; b = b->next )
+       {
+               if( !b->detail )
+                       continue;
+               c_unique++;
+               newb = CopyBrush( b );
+               r = FilterBrushIntoTree_r( newb, tree->headnode );
+               c_clusters += r;
+               
+               /* mark all sides as visible so drawsurfs are created */
+               if( r )
+               {
+                       for( i = 0; i < b->numsides; i++ )
+                       {
+                               if( b->sides[ i ].winding )
+                                       b->sides[ i ].visible = qtrue;
+                       }
+               }
+       }
+       
+       /* emit some statistics */
+       Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
+       Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
+}
+
+/*
+=====================
+FilterStructuralBrushesIntoTree
+
+Mark the leafs as opaque and areaportals
+=====================
+*/
+void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
+       brush_t                 *b, *newb;
+       int                                     r;
+       int                                     c_unique, c_clusters;
+       int                                     i;
+
+       Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
+
+       c_unique = 0;
+       c_clusters = 0;
+       for ( b = e->brushes ; b ; b = b->next ) {
+               if ( b->detail ) {
+                       continue;
+               }
+               c_unique++;
+               newb = CopyBrush( b );
+               r = FilterBrushIntoTree_r( newb, tree->headnode );
+               c_clusters += r;
+
+               // mark all sides as visible so drawsurfs are created
+               if ( r ) {
+                       for ( i = 0 ; i < b->numsides ; i++ ) {
+                               if ( b->sides[i].winding ) {
+                                       b->sides[i].visible = qtrue;
+                               }
+                       }
+               }
+       }
+       
+       /* emit some statistics */
+       Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
+       Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
+}
+
+
+
+/*
+================
+AllocTree
+================
+*/
+tree_t *AllocTree (void)
+{
+       tree_t  *tree;
+
+       tree = safe_malloc(sizeof(*tree));
+       memset (tree, 0, sizeof(*tree));
+       ClearBounds (tree->mins, tree->maxs);
+
+       return tree;
+}
+
+/*
+================
+AllocNode
+================
+*/
+node_t *AllocNode (void)
+{
+       node_t  *node;
+
+       node = safe_malloc(sizeof(*node));
+       memset (node, 0, sizeof(*node));
+
+       return node;
+}
+
+
+/*
+================
+WindingIsTiny
+
+Returns true if the winding would be crunched out of
+existance by the vertex snapping.
+================
+*/
+#define        EDGE_LENGTH     0.2
+qboolean WindingIsTiny (winding_t *w)
+{
+/*
+       if (WindingArea (w) < 1)
+               return qtrue;
+       return qfalse;
+*/
+       int             i, j;
+       vec_t   len;
+       vec3_t  delta;
+       int             edges;
+
+       edges = 0;
+       for (i=0 ; i<w->numpoints ; i++)
+       {
+               j = i == w->numpoints - 1 ? 0 : i+1;
+               VectorSubtract (w->p[j], w->p[i], delta);
+               len = VectorLength (delta);
+               if (len > EDGE_LENGTH)
+               {
+                       if (++edges == 3)
+                               return qfalse;
+               }
+       }
+       return qtrue;
+}
+
+/*
+================
+WindingIsHuge
+
+Returns true if the winding still has one of the points
+from basewinding for plane
+================
+*/
+qboolean WindingIsHuge (winding_t *w)
+{
+       int             i, j;
+
+       for (i=0 ; i<w->numpoints ; i++)
+       {
+               for (j=0 ; j<3 ; j++)
+                       if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
+                               return qtrue;
+       }
+       return qfalse;
+}
+
+//============================================================
+
+/*
+==================
+BrushMostlyOnSide
+
+==================
+*/
+int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
+{
+       int                     i, j;
+       winding_t       *w;
+       vec_t           d, max;
+       int                     side;
+
+       max = 0;
+       side = PSIDE_FRONT;
+       for (i=0 ; i<brush->numsides ; i++)
+       {
+               w = brush->sides[i].winding;
+               if (!w)
+                       continue;
+               for (j=0 ; j<w->numpoints ; j++)
+               {
+                       d = DotProduct (w->p[j], plane->normal) - plane->dist;
+                       if (d > max)
+                       {
+                               max = d;
+                               side = PSIDE_FRONT;
+                       }
+                       if (-d > max)
+                       {
+                               max = -d;
+                               side = PSIDE_BACK;
+                       }
+               }
+       }
+       return side;
+}
+
+
+
+/*
+SplitBrush()
+generates two new brushes, leaving the original unchanged
+*/
+
+void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
+{
+       brush_t         *b[2];
+       int                     i, j;
+       winding_t       *w, *cw[2], *midwinding;
+       plane_t         *plane, *plane2;
+       side_t          *s, *cs;
+       float           d, d_front, d_back;
+       
+       
+       *front = NULL;
+       *back = NULL;
+       plane = &mapplanes[planenum];
+       
+       // check all points
+       d_front = d_back = 0;
+       for (i=0 ; i<brush->numsides ; i++)
+       {
+               w = brush->sides[i].winding;
+               if (!w)
+                       continue;
+               for (j=0 ; j<w->numpoints ; j++)
+               {
+                       d = DotProduct (w->p[j], plane->normal) - plane->dist;
+                       if (d > 0 && d > d_front)
+                               d_front = d;
+                       if (d < 0 && d < d_back)
+                               d_back = d;
+               }
+       }
+       
+       if (d_front < 0.1) // PLANESIDE_EPSILON)
+       {       // only on back
+               *back = CopyBrush( brush );
+               return;
+       }
+       
+       if (d_back > -0.1) // PLANESIDE_EPSILON)
+       {       // only on front
+               *front = CopyBrush( brush );
+               return;
+       }
+       
+       // create a new winding from the split plane
+       w = BaseWindingForPlane (plane->normal, plane->dist);
+       for (i=0 ; i<brush->numsides && w ; i++)
+       {
+               if ( brush->sides[i].backSide ) {
+                       continue;       // fake back-sided polygons never split
+               }
+               plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
+               ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
+       }
+
+       if (!w || WindingIsTiny (w) )
+       {       // the brush isn't really split
+               int             side;
+
+               side = BrushMostlyOnSide (brush, plane);
+               if (side == PSIDE_FRONT)
+                       *front = CopyBrush (brush);
+               if (side == PSIDE_BACK)
+                       *back = CopyBrush (brush);
+               return;
+       }
+       
+       if( WindingIsHuge( w ) )
+               Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
+
+       midwinding = w;
+
+       // split it for real
+
+       for (i=0 ; i<2 ; i++)
+       {
+               b[i] = AllocBrush (brush->numsides+1);
+               memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
+               b[i]->numsides = 0;
+               b[i]->next = NULL;
+               b[i]->original = brush->original;
+       }
+
+       // split all the current windings
+
+       for (i=0 ; i<brush->numsides ; i++)
+       {
+               s = &brush->sides[i];
+               w = s->winding;
+               if (!w)
+                       continue;
+               ClipWindingEpsilon (w, plane->normal, plane->dist,
+                       0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
+               for (j=0 ; j<2 ; j++)
+               {
+                       if (!cw[j])
+                               continue;
+                       cs = &b[j]->sides[b[j]->numsides];
+                       b[j]->numsides++;
+                       *cs = *s;
+                       cs->winding = cw[j];
+               }
+       }
+
+
+       // see if we have valid polygons on both sides
+       for (i=0 ; i<2 ; i++)
+       {
+               BoundBrush (b[i]);
+               for (j=0 ; j<3 ; j++)
+               {
+                       if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD)
+                       {
+                               Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
+                               break;
+                       }
+               }
+
+               if (b[i]->numsides < 3 || j < 3)
+               {
+                       FreeBrush (b[i]);
+                       b[i] = NULL;
+               }
+       }
+       
+       if ( !(b[0] && b[1]) )
+       {
+               if (!b[0] && !b[1])
+                       Sys_FPrintf (SYS_VRB,"split removed brush\n");
+               else
+                       Sys_FPrintf (SYS_VRB,"split not on both sides\n");
+               if (b[0])
+               {
+                       FreeBrush (b[0]);
+                       *front = CopyBrush (brush);
+               }
+               if (b[1])
+               {
+                       FreeBrush (b[1]);
+                       *back = CopyBrush (brush);
+               }
+               return;
+       }
+       
+       // add the midwinding to both sides
+       for (i=0 ; i<2 ; i++)
+       {
+               cs = &b[i]->sides[b[i]->numsides];
+               b[i]->numsides++;
+
+               cs->planenum = planenum^i^1;
+               cs->shaderInfo = NULL;
+               if (i==0)
+                       cs->winding = CopyWinding (midwinding);
+               else
+                       cs->winding = midwinding;
+       }
+       
+       {
+               vec_t   v1;
+               int             i;
+               
+               
+               for (i=0 ; i<2 ; i++)
+               {
+                       v1 = BrushVolume (b[i]);
+                       if (v1 < 1.0)
+                       {
+                               FreeBrush (b[i]);
+                               b[i] = NULL;
+       //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
+                       }
+               }
+       }
+       
+       *front = b[0];
+       *back = b[1];
+}