tools/quake3/q3map2/facebsp.c

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