reduce more diff noise
[xonotic/netradiant.git] / tools / quake3 / q3map2 / facebsp.c
index b92facc..e5390ed 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 FACEBSP_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-int                    c_faceLeafs;\r
-\r
-\r
-/*\r
-================\r
-AllocBspFace\r
-================\r
-*/\r
-face_t *AllocBspFace( void ) {\r
-       face_t  *f;\r
-\r
-       f = safe_malloc(sizeof(*f));\r
-       memset( f, 0, sizeof(*f) );\r
-\r
-       return f;\r
-}\r
-\r
-\r
-\r
-/*\r
-================\r
-FreeBspFace\r
-================\r
-*/\r
-void   FreeBspFace( face_t *f ) {\r
-       if ( f->w ) {\r
-               FreeWinding( f->w );\r
-       }\r
-       free( f );\r
-}\r
-\r
-\r
-\r
-/*\r
-SelectSplitPlaneNum()\r
-finds the best split plane for this node\r
-*/\r
-\r
-static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )\r
-{\r
-       face_t          *split;\r
-       face_t          *check;\r
-       face_t          *bestSplit;\r
-       int                     splits, facing, front, back;\r
-       int                     side;\r
-       plane_t         *plane;\r
-       int                     value, bestValue;\r
-       int                     i;\r
-       vec3_t          normal;\r
-       float           dist;\r
-       int                     planenum;\r
-       \r
-       \r
-       /* ydnar: set some defaults */\r
-       *splitPlaneNum = -1; /* leaf */\r
-       *compileFlags = 0;\r
-       \r
-       /* ydnar 2002-06-24: changed this to split on z-axis as well */\r
-       /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */\r
-       \r
-       /* if it is crossing a block boundary, force a split */\r
-       for( i = 0; i < 3; i++ )\r
-       {\r
-               if( blockSize[ i ] <= 0 )\r
-                       continue;\r
-               dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);\r
-               if( node->maxs[ i ] > dist )\r
-               {\r
-                       VectorClear( normal );\r
-                       normal[ i ] = 1;\r
-                       planenum = FindFloatPlane( normal, dist, 0, NULL );\r
-                       *splitPlaneNum = planenum;\r
-                       return;\r
-               }\r
-       }\r
-       \r
-       /* pick one of the face planes */\r
-       bestValue = -99999;\r
-       bestSplit = list;\r
-       \r
-       for( split = list; split; split = split->next )\r
-               split->checked = qfalse;\r
-       \r
-       for( split = list; split; split = split->next )\r
-       {\r
-               if ( split->checked )\r
-                       continue;\r
-               \r
-               plane = &mapplanes[ split->planenum ];\r
-               splits = 0;\r
-               facing = 0;\r
-               front = 0;\r
-               back = 0;\r
-               for ( check = list ; check ; check = check->next ) {\r
-                       if ( check->planenum == split->planenum ) {\r
-                               facing++;\r
-                               check->checked = qtrue; // won't need to test this plane again\r
-                               continue;\r
-                       }\r
-                       side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );\r
-                       if ( side == SIDE_CROSS ) {\r
-                               splits++;\r
-                       } else if ( side == SIDE_FRONT ) {\r
-                               front++;\r
-                       } else if ( side == SIDE_BACK ) {\r
-                               back++;\r
-                       }\r
-               }\r
-               value =  5*facing - 5*splits; // - abs(front-back);\r
-               if ( plane->type < 3 ) {\r
-                       value+=5;               // axial is better\r
-               }\r
-               value += split->priority;               // prioritize hints higher\r
-\r
-               if ( value > bestValue ) {\r
-                       bestValue = value;\r
-                       bestSplit = split;\r
-               }\r
-       }\r
-       \r
-       /* nothing, we have a leaf */\r
-       if( bestValue == -99999 )\r
-               return;\r
-       \r
-       /* set best split data */\r
-       *splitPlaneNum = bestSplit->planenum;\r
-       *compileFlags = bestSplit->compileFlags;\r
-}\r
-\r
-\r
-\r
-/*\r
-CountFaceList()\r
-counts bsp faces in the linked list\r
-*/\r
-\r
-int    CountFaceList( face_t *list )\r
-{\r
-       int             c;\r
-       \r
-\r
-       c = 0;\r
-       for( list; list != NULL; list = list->next )\r
-               c++;\r
-       return c;\r
-}\r
-\r
-\r
-\r
-/*\r
-BuildFaceTree_r()\r
-recursively builds the bsp, splitting on face planes\r
-*/\r
-\r
-void BuildFaceTree_r( node_t *node, face_t *list )\r
-{\r
-       face_t          *split;\r
-       face_t          *next;\r
-       int                     side;\r
-       plane_t         *plane;\r
-       face_t          *newFace;\r
-       face_t          *childLists[2];\r
-       winding_t       *frontWinding, *backWinding;\r
-       int                     i;\r
-       int                     splitPlaneNum, compileFlags;\r
-       \r
-       \r
-       /* count faces left */\r
-       i = CountFaceList( list );\r
-       \r
-       /* select the best split plane */\r
-       SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );\r
-       \r
-       /* if we don't have any more faces, this is a node */\r
-       if ( splitPlaneNum == -1 )\r
-       {\r
-               node->planenum = PLANENUM_LEAF;\r
-               c_faceLeafs++;\r
-               return;\r
-       }\r
-       \r
-       /* partition the list */\r
-       node->planenum = splitPlaneNum;\r
-       node->compileFlags = compileFlags;\r
-       plane = &mapplanes[ splitPlaneNum ];\r
-       childLists[0] = NULL;\r
-       childLists[1] = NULL;\r
-       for( split = list; split; split = next )\r
-       {\r
-               /* set next */\r
-               next = split->next;\r
-               \r
-               /* don't split by identical plane */\r
-               if( split->planenum == node->planenum )\r
-               {\r
-                       FreeBspFace( split );\r
-                       continue;\r
-               }\r
-               \r
-               /* determine which side the face falls on */\r
-               side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );\r
-               \r
-               /* switch on side */\r
-               if( side == SIDE_CROSS )\r
-               {\r
-                       ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,\r
-                               &frontWinding, &backWinding );\r
-                       if( frontWinding ) {\r
-                               newFace = AllocBspFace();\r
-                               newFace->w = frontWinding;\r
-                               newFace->next = childLists[0];\r
-                               newFace->planenum = split->planenum;\r
-                               newFace->priority = split->priority;\r
-                               newFace->compileFlags = split->compileFlags;\r
-                               childLists[0] = newFace;\r
-                       }\r
-                       if( backWinding ) {\r
-                               newFace = AllocBspFace();\r
-                               newFace->w = backWinding;\r
-                               newFace->next = childLists[1];\r
-                               newFace->planenum = split->planenum;\r
-                               newFace->priority = split->priority;\r
-                               newFace->compileFlags = split->compileFlags;\r
-                               childLists[1] = newFace;\r
-                       }\r
-                       FreeBspFace( split );\r
-               } else if ( side == SIDE_FRONT ) {\r
-                       split->next = childLists[0];\r
-                       childLists[0] = split;\r
-               } else if ( side == SIDE_BACK ) {\r
-                       split->next = childLists[1];\r
-                       childLists[1] = split;\r
-               }\r
-       }\r
-\r
-\r
-       // recursively process children\r
-       for ( i = 0 ; i < 2 ; i++ ) {\r
-               node->children[i] = AllocNode();\r
-               node->children[i]->parent = node;\r
-               VectorCopy( node->mins, node->children[i]->mins );\r
-               VectorCopy( node->maxs, node->children[i]->maxs );\r
-       }\r
-\r
-       for ( i = 0 ; i < 3 ; i++ ) {\r
-               if ( plane->normal[i] == 1 ) {\r
-                       node->children[0]->mins[i] = plane->dist;\r
-                       node->children[1]->maxs[i] = plane->dist;\r
-                       break;\r
-               }\r
-       }\r
-\r
-       for ( i = 0 ; i < 2 ; i++ ) {\r
-               BuildFaceTree_r ( node->children[i], childLists[i]);\r
-       }\r
-}\r
-\r
-\r
-/*\r
-================\r
-FaceBSP\r
-\r
-List will be freed before returning\r
-================\r
-*/\r
-tree_t *FaceBSP( face_t *list ) {\r
-       tree_t          *tree;\r
-       face_t  *face;\r
-       int                     i;\r
-       int                     count;\r
-\r
-       Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );\r
-\r
-       tree = AllocTree ();\r
-\r
-       count = 0;\r
-       for( face = list; face != NULL; face = face->next )\r
-       {\r
-               count++;\r
-               for( i = 0; i < face->w->numpoints; i++ )\r
-               {\r
-                       AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );\r
-               }\r
-       }\r
-       Sys_FPrintf( SYS_VRB, "%9d faces\n", count );\r
-\r
-       tree->headnode = AllocNode();\r
-       VectorCopy( tree->mins, tree->headnode->mins );\r
-       VectorCopy( tree->maxs, tree->headnode->maxs );\r
-       c_faceLeafs = 0;\r
-\r
-       BuildFaceTree_r ( tree->headnode, list );\r
-\r
-       Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );\r
-\r
-       return tree;\r
-}\r
-\r
-\r
-\r
-/*\r
-MakeStructuralBSPFaceList()\r
-get structural brush faces\r
-*/\r
-\r
-face_t *MakeStructuralBSPFaceList( brush_t *list )\r
-{\r
-       brush_t         *b;\r
-       int                     i;\r
-       side_t          *s;\r
-       winding_t       *w;\r
-       face_t          *f, *flist;\r
-       \r
-       \r
-       flist = NULL;\r
-       for( b = list; b != NULL; b = b->next )\r
-       {\r
-               if( b->detail )\r
-                       continue;\r
-               \r
-               for( i = 0; i < b->numsides; i++ )\r
-               {\r
-                       /* get side and winding */\r
-                       s = &b->sides[ i ];\r
-                       w = s->winding;\r
-                       if( w == NULL )\r
-                               continue;\r
-                       \r
-                       /* ydnar: skip certain faces */\r
-                       if( s->compileFlags & C_SKIP )\r
-                               continue;\r
-                       \r
-                       /* allocate a face */\r
-                       f = AllocBspFace();\r
-                       f->w = CopyWinding( w );\r
-                       f->planenum = s->planenum & ~1;\r
-                       f->compileFlags = s->compileFlags;      /* ydnar */\r
-                       \r
-                       /* ydnar: set priority */\r
-                       f->priority = 0;\r
-                       if( f->compileFlags & C_HINT )\r
-                               f->priority += HINT_PRIORITY;\r
-                       if( f->compileFlags & C_ANTIPORTAL )\r
-                               f->priority += ANTIPORTAL_PRIORITY;\r
-                       if( f->compileFlags & C_AREAPORTAL )\r
-                               f->priority += AREAPORTAL_PRIORITY;\r
-                       \r
-                       /* get next face */\r
-                       f->next = flist;\r
-                       flist = f;\r
-               }\r
-       }\r
-       \r
-       return flist;\r
-}\r
-\r
-\r
-\r
-/*\r
-MakeVisibleBSPFaceList()\r
-get visible brush faces\r
-*/\r
-\r
-face_t *MakeVisibleBSPFaceList( brush_t *list )\r
-{\r
-       brush_t         *b;\r
-       int                     i;\r
-       side_t          *s;\r
-       winding_t       *w;\r
-       face_t          *f, *flist;\r
-       \r
-       \r
-       flist = NULL;\r
-       for( b = list; b != NULL; b = b->next )\r
-       {\r
-               if( b->detail )\r
-                       continue;\r
-               \r
-               for( i = 0; i < b->numsides; i++ )\r
-               {\r
-                       /* get side and winding */\r
-                       s = &b->sides[ i ];\r
-                       w = s->visibleHull;\r
-                       if( w == NULL )\r
-                               continue;\r
-                       \r
-                       /* ydnar: skip certain faces */\r
-                       if( s->compileFlags & C_SKIP )\r
-                               continue;\r
-                       \r
-                       /* allocate a face */\r
-                       f = AllocBspFace();\r
-                       f->w = CopyWinding( w );\r
-                       f->planenum = s->planenum & ~1;\r
-                       f->compileFlags = s->compileFlags;      /* ydnar */\r
-                       \r
-                       /* ydnar: set priority */\r
-                       f->priority = 0;\r
-                       if( f->compileFlags & C_HINT )\r
-                               f->priority += HINT_PRIORITY;\r
-                       if( f->compileFlags & C_ANTIPORTAL )\r
-                               f->priority += ANTIPORTAL_PRIORITY;\r
-                       if( f->compileFlags & C_AREAPORTAL )\r
-                               f->priority += AREAPORTAL_PRIORITY;\r
-                       \r
-                       /* get next face */\r
-                       f->next = flist;\r
-                       flist = f;\r
-               }\r
-       }\r
-       \r
-       return flist;\r
-}\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 FACEBSP_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+int c_faceLeafs;
+
+
+/*
+   ================
+   AllocBspFace
+   ================
+ */
+face_t  *AllocBspFace( void ) {
+       face_t  *f;
+
+       f = safe_malloc( sizeof( *f ) );
+       memset( f, 0, sizeof( *f ) );
+
+       return f;
+}
+
+
+
+/*
+   ================
+   FreeBspFace
+   ================
+ */
+void    FreeBspFace( face_t *f ) {
+       if ( f->w ) {
+               FreeWinding( f->w );
+       }
+       free( f );
+}
+
+
+
+/*
+   SelectSplitPlaneNum()
+   finds the best split plane for this node
+ */
+
+static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ){
+       face_t *split;
+       face_t *check;
+       face_t *bestSplit;
+       int splits, facing, front, back;
+       int side;
+       plane_t *plane;
+       int value, bestValue;
+       int i;
+       vec3_t normal;
+       float dist;
+       int planenum;
+       float sizeBias;
+
+       /* ydnar: set some defaults */
+       *splitPlaneNum = -1; /* leaf */
+       *compileFlags = 0;
+
+       /* ydnar 2002-06-24: changed this to split on z-axis as well */
+       /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
+
+       /* if it is crossing a block boundary, force a split */
+       for ( i = 0; i < 3; i++ )
+       {
+               if ( blockSize[ i ] <= 0 ) {
+                       continue;
+               }
+               dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
+               if ( node->maxs[ i ] > dist ) {
+                       VectorClear( normal );
+                       normal[ i ] = 1;
+                       planenum = FindFloatPlane( normal, dist, 0, NULL );
+                       *splitPlaneNum = planenum;
+                       return;
+               }
+       }
+
+       /* pick one of the face planes */
+       bestValue = -99999;
+       bestSplit = list;
+
+
+       // div0: this check causes detail/structural mixes
+       //for( split = list; split; split = split->next )
+       //      split->checked = qfalse;
+
+       for ( split = list; split; split = split->next )
+       {
+               //if ( split->checked )
+               //      continue;
+
+               plane = &mapplanes[ split->planenum ];
+               splits = 0;
+               facing = 0;
+               front = 0;
+               back = 0;
+               for ( check = list ; check ; check = check->next ) {
+                       if ( check->planenum == split->planenum ) {
+                               facing++;
+                               //check->checked = qtrue;       // won't need to test this plane again
+                               continue;
+                       }
+                       side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
+                       if ( side == SIDE_CROSS ) {
+                               splits++;
+                       }
+                       else if ( side == SIDE_FRONT ) {
+                               front++;
+                       }
+                       else if ( side == SIDE_BACK ) {
+                               back++;
+                       }
+               }
+
+               if ( bspAlternateSplitWeights ) {
+                       // from 27
+
+                       //Bigger is better
+                       sizeBias = WindingArea( split->w );
+
+                       //Base score = 20000 perfectly balanced
+                       value = 20000 - ( abs( front - back ) );
+                       value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again
+                       value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
+                       value -= splits * 5;        //more splits = bad
+                       value +=  sizeBias * 10; //We want a huge score bias based on plane size
+               }
+               else
+               {
+                       value =  5 * facing - 5 * splits; // - abs(front-back);
+                       if ( plane->type < 3 ) {
+                               value += 5;       // axial is better
+                       }
+               }
+
+               value += split->priority;       // prioritize hints higher
+
+               if ( value > bestValue ) {
+                       bestValue = value;
+                       bestSplit = split;
+               }
+       }
+
+       /* nothing, we have a leaf */
+       if ( bestValue == -99999 ) {
+               return;
+       }
+
+       /* set best split data */
+       *splitPlaneNum = bestSplit->planenum;
+       *compileFlags = bestSplit->compileFlags;
+
+       if ( *splitPlaneNum > -1 ) {
+               mapplanes[ *splitPlaneNum ].counter++;
+       }
+}
+
+
+
+/*
+   CountFaceList()
+   counts bsp faces in the linked list
+ */
+
+int CountFaceList( face_t *list ){
+       int c;
+
+
+       c = 0;
+       for ( ; list != NULL; list = list->next )
+               c++;
+       return c;
+}
+
+
+
+/*
+   BuildFaceTree_r()
+   recursively builds the bsp, splitting on face planes
+ */
+
+void BuildFaceTree_r( node_t *node, face_t *list ){
+       face_t      *split;
+       face_t      *next;
+       int side;
+       plane_t     *plane;
+       face_t      *newFace;
+       face_t      *childLists[2];
+       winding_t   *frontWinding, *backWinding;
+       int i;
+       int splitPlaneNum, compileFlags;
+
+
+       /* count faces left */
+       i = CountFaceList( list );
+
+       /* select the best split plane */
+       SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
+
+       /* if we don't have any more faces, this is a node */
+       if ( splitPlaneNum == -1 ) {
+               node->planenum = PLANENUM_LEAF;
+               node->has_structural_children = qfalse;
+               c_faceLeafs++;
+               return;
+       }
+
+       /* partition the list */
+       node->planenum = splitPlaneNum;
+       node->compileFlags = compileFlags;
+       node->has_structural_children = !( compileFlags & C_DETAIL ) && !node->opaque;
+       plane = &mapplanes[ splitPlaneNum ];
+       childLists[0] = NULL;
+       childLists[1] = NULL;
+
+       for ( split = list; split; split = next )
+       {
+               /* set next */
+               next = split->next;
+
+               /* don't split by identical plane */
+               if ( split->planenum == node->planenum ) {
+                       FreeBspFace( split );
+                       continue;
+               }
+
+               /* determine which side the face falls on */
+               side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
+
+               /* switch on side */
+               if ( side == SIDE_CROSS ) {
+                       /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
+                       ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
+                                                               &frontWinding, &backWinding );
+                       if ( frontWinding ) {
+                               newFace = AllocBspFace();
+                               newFace->w = frontWinding;
+                               newFace->next = childLists[0];
+                               newFace->planenum = split->planenum;
+                               newFace->priority = split->priority;
+                               newFace->compileFlags = split->compileFlags;
+                               childLists[0] = newFace;
+                       }
+                       if ( backWinding ) {
+                               newFace = AllocBspFace();
+                               newFace->w = backWinding;
+                               newFace->next = childLists[1];
+                               newFace->planenum = split->planenum;
+                               newFace->priority = split->priority;
+                               newFace->compileFlags = split->compileFlags;
+                               childLists[1] = newFace;
+                       }
+                       FreeBspFace( split );
+               }
+               else if ( side == SIDE_FRONT ) {
+                       split->next = childLists[0];
+                       childLists[0] = split;
+               }
+               else if ( side == SIDE_BACK ) {
+                       split->next = childLists[1];
+                       childLists[1] = split;
+               }
+       }
+
+
+       // recursively process children
+       for ( i = 0 ; i < 2 ; i++ ) {
+               node->children[i] = AllocNode();
+               node->children[i]->parent = node;
+               VectorCopy( node->mins, node->children[i]->mins );
+               VectorCopy( node->maxs, node->children[i]->maxs );
+       }
+
+       for ( i = 0 ; i < 3 ; i++ ) {
+               if ( plane->normal[i] == 1 ) {
+                       node->children[0]->mins[i] = plane->dist;
+                       node->children[1]->maxs[i] = plane->dist;
+                       break;
+               }
+               if ( plane->normal[i] == -1 ) {
+                       node->children[0]->maxs[i] = -plane->dist;
+                       node->children[1]->mins[i] = -plane->dist;
+                       break;
+               }
+       }
+
+       for ( i = 0 ; i < 2 ; i++ ) {
+               BuildFaceTree_r( node->children[i], childLists[i] );
+               node->has_structural_children |= node->children[i]->has_structural_children;
+       }
+}
+
+
+/*
+   ================
+   FaceBSP
+
+   List will be freed before returning
+   ================
+ */
+tree_t *FaceBSP( face_t *list ) {
+       tree_t      *tree;
+       face_t  *face;
+       int i;
+       int count;
+
+       Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
+
+       tree = AllocTree();
+
+       count = 0;
+       for ( face = list; face != NULL; face = face->next )
+       {
+               count++;
+               for ( i = 0; i < face->w->numpoints; i++ )
+               {
+                       AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
+               }
+       }
+       Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
+
+       for ( i = 0; i < nummapplanes; i++ )
+       {
+               mapplanes[ i ].counter = 0;
+       }
+
+       tree->headnode = AllocNode();
+       VectorCopy( tree->mins, tree->headnode->mins );
+       VectorCopy( tree->maxs, tree->headnode->maxs );
+       c_faceLeafs = 0;
+
+       BuildFaceTree_r( tree->headnode, list );
+
+       Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
+
+       return tree;
+}
+
+
+
+/*
+   MakeStructuralBSPFaceList()
+   get structural brush faces
+ */
+
+face_t *MakeStructuralBSPFaceList( brush_t *list ){
+       brush_t     *b;
+       int i;
+       side_t      *s;
+       winding_t   *w;
+       face_t      *f, *flist;
+
+
+       flist = NULL;
+       for ( b = list; b != NULL; b = b->next )
+       {
+               if ( !deepBSP && b->detail ) {
+                       continue;
+               }
+
+               for ( i = 0; i < b->numsides; i++ )
+               {
+                       /* get side and winding */
+                       s = &b->sides[ i ];
+                       w = s->winding;
+                       if ( w == NULL ) {
+                               continue;
+                       }
+
+                       /* ydnar: skip certain faces */
+                       if ( s->compileFlags & C_SKIP ) {
+                               continue;
+                       }
+
+                       /* allocate a face */
+                       f = AllocBspFace();
+                       f->w = CopyWinding( w );
+                       f->planenum = s->planenum & ~1;
+                       f->compileFlags = s->compileFlags;  /* ydnar */
+                       if ( b->detail ) {
+                               f->compileFlags |= C_DETAIL;
+                       }
+
+                       /* ydnar: set priority */
+                       f->priority = 0;
+                       if ( f->compileFlags & C_HINT ) {
+                               f->priority += HINT_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_ANTIPORTAL ) {
+                               f->priority += ANTIPORTAL_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_AREAPORTAL ) {
+                               f->priority += AREAPORTAL_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_DETAIL ) {
+                               f->priority += DETAIL_PRIORITY;
+                       }
+
+                       /* get next face */
+                       f->next = flist;
+                       flist = f;
+               }
+       }
+
+       return flist;
+}
+
+
+
+/*
+   MakeVisibleBSPFaceList()
+   get visible brush faces
+ */
+
+face_t *MakeVisibleBSPFaceList( brush_t *list ){
+       brush_t     *b;
+       int i;
+       side_t      *s;
+       winding_t   *w;
+       face_t      *f, *flist;
+
+
+       flist = NULL;
+       for ( b = list; b != NULL; b = b->next )
+       {
+               if ( !deepBSP && b->detail ) {
+                       continue;
+               }
+
+               for ( i = 0; i < b->numsides; i++ )
+               {
+                       /* get side and winding */
+                       s = &b->sides[ i ];
+                       w = s->visibleHull;
+                       if ( w == NULL ) {
+                               continue;
+                       }
+
+                       /* ydnar: skip certain faces */
+                       if ( s->compileFlags & C_SKIP ) {
+                               continue;
+                       }
+
+                       /* allocate a face */
+                       f = AllocBspFace();
+                       f->w = CopyWinding( w );
+                       f->planenum = s->planenum & ~1;
+                       f->compileFlags = s->compileFlags;  /* ydnar */
+                       if ( b->detail ) {
+                               f->compileFlags |= C_DETAIL;
+                       }
+
+                       /* ydnar: set priority */
+                       f->priority = 0;
+                       if ( f->compileFlags & C_HINT ) {
+                               f->priority += HINT_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_ANTIPORTAL ) {
+                               f->priority += ANTIPORTAL_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_AREAPORTAL ) {
+                               f->priority += AREAPORTAL_PRIORITY;
+                       }
+                       if ( f->compileFlags & C_DETAIL ) {
+                               f->priority += DETAIL_PRIORITY;
+                       }
+
+                       /* get next face */
+                       f->next = flist;
+                       flist = f;
+               }
+       }
+
+       return flist;
+}