tools/quake3/q3map2/facebsp.c

   1 /*\r
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 \r
  21 ----------------------------------------------------------------------------------\r
  22 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define FACEBSP_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 int                     c_faceLeafs;\r
  41 \r
  42 \r
  43 /*\r
  44 ================\r
  45 AllocBspFace\r
  46 ================\r
  47 */\r
  48 face_t  *AllocBspFace( void ) {\r
  49         face_t  *f;\r
  50 \r
  51         f = safe_malloc(sizeof(*f));\r
  52         memset( f, 0, sizeof(*f) );\r
  53 \r
  54         return f;\r
  55 }\r
  56 \r
  57 \r
  58 \r
  59 /*\r
  60 ================\r
  61 FreeBspFace\r
  62 ================\r
  63 */\r
  64 void    FreeBspFace( face_t *f ) {\r
  65         if ( f->w ) {\r
  66                 FreeWinding( f->w );\r
  67         }\r
  68         free( f );\r
  69 }\r
  70 \r
  71 \r
  72 \r
  73 /*\r
  74 SelectSplitPlaneNum()\r
  75 finds the best split plane for this node\r
  76 */\r
  77 \r
  78 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )\r
  79 {\r
  80         face_t          *split;\r
  81         face_t          *check;\r
  82         face_t          *bestSplit;\r
  83         int                     splits, facing, front, back;\r
  84         int                     side;\r
  85         plane_t         *plane;\r
  86         int                     value, bestValue;\r
  87         int                     i;\r
  88         vec3_t          normal;\r
  89         float           dist;\r
  90         int                     planenum;\r
  91         \r
  92         \r
  93         /* ydnar: set some defaults */\r
  94         *splitPlaneNum = -1; /* leaf */\r
  95         *compileFlags = 0;\r
  96         \r
  97         /* ydnar 2002-06-24: changed this to split on z-axis as well */\r
  98         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */\r
  99         \r
 100         /* if it is crossing a block boundary, force a split */\r
 101         for( i = 0; i < 3; i++ )\r
 102         {\r
 103                 if( blockSize[ i ] <= 0 )\r
 104                         continue;\r
 105                 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);\r
 106                 if( node->maxs[ i ] > dist )\r
 107                 {\r
 108                         VectorClear( normal );\r
 109                         normal[ i ] = 1;\r
 110                         planenum = FindFloatPlane( normal, dist, 0, NULL );\r
 111                         *splitPlaneNum = planenum;\r
 112                         return;\r
 113                 }\r
 114         }\r
 115         \r
 116         /* pick one of the face planes */\r
 117         bestValue = -99999;\r
 118         bestSplit = list;\r
 119         \r
 120         for( split = list; split; split = split->next )\r
 121                 split->checked = qfalse;\r
 122         \r
 123         for( split = list; split; split = split->next )\r
 124         {\r
 125                 if ( split->checked )\r
 126                         continue;\r
 127                 \r
 128                 plane = &mapplanes[ split->planenum ];\r
 129                 splits = 0;\r
 130                 facing = 0;\r
 131                 front = 0;\r
 132                 back = 0;\r
 133                 for ( check = list ; check ; check = check->next ) {\r
 134                         if ( check->planenum == split->planenum ) {\r
 135                                 facing++;\r
 136                                 check->checked = qtrue; // won't need to test this plane again\r
 137                                 continue;\r
 138                         }\r
 139                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );\r
 140                         if ( side == SIDE_CROSS ) {\r
 141                                 splits++;\r
 142                         } else if ( side == SIDE_FRONT ) {\r
 143                                 front++;\r
 144                         } else if ( side == SIDE_BACK ) {\r
 145                                 back++;\r
 146                         }\r
 147                 }\r
 148                 value =  5*facing - 5*splits; // - abs(front-back);\r
 149                 if ( plane->type < 3 ) {\r
 150                         value+=5;               // axial is better\r
 151                 }\r
 152                 value += split->priority;               // prioritize hints higher\r
 153 \r
 154                 if ( value > bestValue ) {\r
 155                         bestValue = value;\r
 156                         bestSplit = split;\r
 157                 }\r
 158         }\r
 159         \r
 160         /* nothing, we have a leaf */\r
 161         if( bestValue == -99999 )\r
 162                 return;\r
 163         \r
 164         /* set best split data */\r
 165         *splitPlaneNum = bestSplit->planenum;\r
 166         *compileFlags = bestSplit->compileFlags;\r
 167 }\r
 168 \r
 169 \r
 170 \r
 171 /*\r
 172 CountFaceList()\r
 173 counts bsp faces in the linked list\r
 174 */\r
 175 \r
 176 int     CountFaceList( face_t *list )\r
 177 {\r
 178         int             c;\r
 179         \r
 180 \r
 181         c = 0;\r
 182         for( list; list != NULL; list = list->next )\r
 183                 c++;\r
 184         return c;\r
 185 }\r
 186 \r
 187 \r
 188 \r
 189 /*\r
 190 BuildFaceTree_r()\r
 191 recursively builds the bsp, splitting on face planes\r
 192 */\r
 193 \r
 194 void BuildFaceTree_r( node_t *node, face_t *list )\r
 195 {\r
 196         face_t          *split;\r
 197         face_t          *next;\r
 198         int                     side;\r
 199         plane_t         *plane;\r
 200         face_t          *newFace;\r
 201         face_t          *childLists[2];\r
 202         winding_t       *frontWinding, *backWinding;\r
 203         int                     i;\r
 204         int                     splitPlaneNum, compileFlags;\r
 205         \r
 206         \r
 207         /* count faces left */\r
 208         i = CountFaceList( list );\r
 209         \r
 210         /* select the best split plane */\r
 211         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );\r
 212         \r
 213         /* if we don't have any more faces, this is a node */\r
 214         if ( splitPlaneNum == -1 )\r
 215         {\r
 216                 node->planenum = PLANENUM_LEAF;\r
 217                 c_faceLeafs++;\r
 218                 return;\r
 219         }\r
 220         \r
 221         /* partition the list */\r
 222         node->planenum = splitPlaneNum;\r
 223         node->compileFlags = compileFlags;\r
 224         plane = &mapplanes[ splitPlaneNum ];\r
 225         childLists[0] = NULL;\r
 226         childLists[1] = NULL;\r
 227         for( split = list; split; split = next )\r
 228         {\r
 229                 /* set next */\r
 230                 next = split->next;\r
 231                 \r
 232                 /* don't split by identical plane */\r
 233                 if( split->planenum == node->planenum )\r
 234                 {\r
 235                         FreeBspFace( split );\r
 236                         continue;\r
 237                 }\r
 238                 \r
 239                 /* determine which side the face falls on */\r
 240                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );\r
 241                 \r
 242                 /* switch on side */\r
 243                 if( side == SIDE_CROSS )\r
 244                 {\r
 245                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,\r
 246                                 &frontWinding, &backWinding );\r
 247                         if( frontWinding ) {\r
 248                                 newFace = AllocBspFace();\r
 249                                 newFace->w = frontWinding;\r
 250                                 newFace->next = childLists[0];\r
 251                                 newFace->planenum = split->planenum;\r
 252                                 newFace->priority = split->priority;\r
 253                                 newFace->compileFlags = split->compileFlags;\r
 254                                 childLists[0] = newFace;\r
 255                         }\r
 256                         if( backWinding ) {\r
 257                                 newFace = AllocBspFace();\r
 258                                 newFace->w = backWinding;\r
 259                                 newFace->next = childLists[1];\r
 260                                 newFace->planenum = split->planenum;\r
 261                                 newFace->priority = split->priority;\r
 262                                 newFace->compileFlags = split->compileFlags;\r
 263                                 childLists[1] = newFace;\r
 264                         }\r
 265                         FreeBspFace( split );\r
 266                 } else if ( side == SIDE_FRONT ) {\r
 267                         split->next = childLists[0];\r
 268                         childLists[0] = split;\r
 269                 } else if ( side == SIDE_BACK ) {\r
 270                         split->next = childLists[1];\r
 271                         childLists[1] = split;\r
 272                 }\r
 273         }\r
 274 \r
 275 \r
 276         // recursively process children\r
 277         for ( i = 0 ; i < 2 ; i++ ) {\r
 278                 node->children[i] = AllocNode();\r
 279                 node->children[i]->parent = node;\r
 280                 VectorCopy( node->mins, node->children[i]->mins );\r
 281                 VectorCopy( node->maxs, node->children[i]->maxs );\r
 282         }\r
 283 \r
 284         for ( i = 0 ; i < 3 ; i++ ) {\r
 285                 if ( plane->normal[i] == 1 ) {\r
 286                         node->children[0]->mins[i] = plane->dist;\r
 287                         node->children[1]->maxs[i] = plane->dist;\r
 288                         break;\r
 289                 }\r
 290         }\r
 291 \r
 292         for ( i = 0 ; i < 2 ; i++ ) {\r
 293                 BuildFaceTree_r ( node->children[i], childLists[i]);\r
 294         }\r
 295 }\r
 296 \r
 297 \r
 298 /*\r
 299 ================\r
 300 FaceBSP\r
 301 \r
 302 List will be freed before returning\r
 303 ================\r
 304 */\r
 305 tree_t *FaceBSP( face_t *list ) {\r
 306         tree_t          *tree;\r
 307         face_t  *face;\r
 308         int                     i;\r
 309         int                     count;\r
 310 \r
 311         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );\r
 312 \r
 313         tree = AllocTree ();\r
 314 \r
 315         count = 0;\r
 316         for( face = list; face != NULL; face = face->next )\r
 317         {\r
 318                 count++;\r
 319                 for( i = 0; i < face->w->numpoints; i++ )\r
 320                 {\r
 321                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );\r
 322                 }\r
 323         }\r
 324         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );\r
 325 \r
 326         tree->headnode = AllocNode();\r
 327         VectorCopy( tree->mins, tree->headnode->mins );\r
 328         VectorCopy( tree->maxs, tree->headnode->maxs );\r
 329         c_faceLeafs = 0;\r
 330 \r
 331         BuildFaceTree_r ( tree->headnode, list );\r
 332 \r
 333         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );\r
 334 \r
 335         return tree;\r
 336 }\r
 337 \r
 338 \r
 339 \r
 340 /*\r
 341 MakeStructuralBSPFaceList()\r
 342 get structural brush faces\r
 343 */\r
 344 \r
 345 face_t *MakeStructuralBSPFaceList( brush_t *list )\r
 346 {\r
 347         brush_t         *b;\r
 348         int                     i;\r
 349         side_t          *s;\r
 350         winding_t       *w;\r
 351         face_t          *f, *flist;\r
 352         \r
 353         \r
 354         flist = NULL;\r
 355         for( b = list; b != NULL; b = b->next )\r
 356         {\r
 357                 if( b->detail )\r
 358                         continue;\r
 359                 \r
 360                 for( i = 0; i < b->numsides; i++ )\r
 361                 {\r
 362                         /* get side and winding */\r
 363                         s = &b->sides[ i ];\r
 364                         w = s->winding;\r
 365                         if( w == NULL )\r
 366                                 continue;\r
 367                         \r
 368                         /* ydnar: skip certain faces */\r
 369                         if( s->compileFlags & C_SKIP )\r
 370                                 continue;\r
 371                         \r
 372                         /* allocate a face */\r
 373                         f = AllocBspFace();\r
 374                         f->w = CopyWinding( w );\r
 375                         f->planenum = s->planenum & ~1;\r
 376                         f->compileFlags = s->compileFlags;      /* ydnar */\r
 377                         \r
 378                         /* ydnar: set priority */\r
 379                         f->priority = 0;\r
 380                         if( f->compileFlags & C_HINT )\r
 381                                 f->priority += HINT_PRIORITY;\r
 382                         if( f->compileFlags & C_ANTIPORTAL )\r
 383                                 f->priority += ANTIPORTAL_PRIORITY;\r
 384                         if( f->compileFlags & C_AREAPORTAL )\r
 385                                 f->priority += AREAPORTAL_PRIORITY;\r
 386                         \r
 387                         /* get next face */\r
 388                         f->next = flist;\r
 389                         flist = f;\r
 390                 }\r
 391         }\r
 392         \r
 393         return flist;\r
 394 }\r
 395 \r
 396 \r
 397 \r
 398 /*\r
 399 MakeVisibleBSPFaceList()\r
 400 get visible brush faces\r
 401 */\r
 402 \r
 403 face_t *MakeVisibleBSPFaceList( brush_t *list )\r
 404 {\r
 405         brush_t         *b;\r
 406         int                     i;\r
 407         side_t          *s;\r
 408         winding_t       *w;\r
 409         face_t          *f, *flist;\r
 410         \r
 411         \r
 412         flist = NULL;\r
 413         for( b = list; b != NULL; b = b->next )\r
 414         {\r
 415                 if( b->detail )\r
 416                         continue;\r
 417                 \r
 418                 for( i = 0; i < b->numsides; i++ )\r
 419                 {\r
 420                         /* get side and winding */\r
 421                         s = &b->sides[ i ];\r
 422                         w = s->visibleHull;\r
 423                         if( w == NULL )\r
 424                                 continue;\r
 425                         \r
 426                         /* ydnar: skip certain faces */\r
 427                         if( s->compileFlags & C_SKIP )\r
 428                                 continue;\r
 429                         \r
 430                         /* allocate a face */\r
 431                         f = AllocBspFace();\r
 432                         f->w = CopyWinding( w );\r
 433                         f->planenum = s->planenum & ~1;\r
 434                         f->compileFlags = s->compileFlags;      /* ydnar */\r
 435                         \r
 436                         /* ydnar: set priority */\r
 437                         f->priority = 0;\r
 438                         if( f->compileFlags & C_HINT )\r
 439                                 f->priority += HINT_PRIORITY;\r
 440                         if( f->compileFlags & C_ANTIPORTAL )\r
 441                                 f->priority += ANTIPORTAL_PRIORITY;\r
 442                         if( f->compileFlags & C_AREAPORTAL )\r
 443                                 f->priority += AREAPORTAL_PRIORITY;\r
 444                         \r
 445                         /* get next face */\r
 446                         f->next = flist;\r
 447                         flist = f;\r
 448                 }\r
 449         }\r
 450         \r
 451         return flist;\r
 452 }\r
 453 \r