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         float sizeBias;
  92
  93
  94         /* ydnar: set some defaults */
  95         *splitPlaneNum = -1; /* leaf */
  96         *compileFlags = 0;
  97
  98         /* ydnar 2002-06-24: changed this to split on z-axis as well */
  99         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
 100
 101         /* if it is crossing a block boundary, force a split */
 102         for ( i = 0; i < 3; i++ )
 103         {
 104                 if ( blockSize[ i ] <= 0 ) {
 105                         continue;
 106                 }
 107                 dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
 108                 if ( node->maxs[ i ] > dist ) {
 109                         VectorClear( normal );
 110                         normal[ i ] = 1;
 111                         planenum = FindFloatPlane( normal, dist, 0, NULL );
 112                         *splitPlaneNum = planenum;
 113                         return;
 114                 }
 115         }
 116
 117         /* pick one of the face planes */
 118         bestValue = -99999;
 119         bestSplit = list;
 120
 121
 122         // div0: this check causes detail/structural mixes
 123         //for( split = list; split; split = split->next )
 124         //      split->checked = qfalse;
 125
 126         for ( split = list; split; split = split->next )
 127         {
 128                 //if ( split->checked )
 129                 //      continue;
 130
 131                 plane = &mapplanes[ split->planenum ];
 132                 splits = 0;
 133                 facing = 0;
 134                 front = 0;
 135                 back = 0;
 136                 for ( check = list ; check ; check = check->next ) {
 137                         if ( check->planenum == split->planenum ) {
 138                                 facing++;
 139                                 //check->checked = qtrue;       // won't need to test this plane again
 140                                 continue;
 141                         }
 142                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
 143                         if ( side == SIDE_CROSS ) {
 144                                 splits++;
 145                         }
 146                         else if ( side == SIDE_FRONT ) {
 147                                 front++;
 148                         }
 149                         else if ( side == SIDE_BACK ) {
 150                                 back++;
 151                         }
 152                 }
 153
 154                 if ( bspAlternateSplitWeights ) {
 155                         // from 27
 156
 157                         //Bigger is better
 158                         sizeBias = WindingArea( split->w );
 159
 160                         //Base score = 20000 perfectly balanced
 161                         value = 20000 - ( abs( front - back ) );
 162                         value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again
 163                         value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
 164                         value -= splits * 5;        //more splits = bad
 165                         value +=  sizeBias * 10; //We want a huge score bias based on plane size
 166                 }
 167                 else
 168                 {
 169                         value =  5 * facing - 5 * splits; // - abs(front-back);
 170                         if ( plane->type < 3 ) {
 171                                 value += 5;       // axial is better
 172                         }
 173                 }
 174
 175                 value += split->priority;       // prioritize hints higher
 176
 177                 if ( value > bestValue ) {
 178                         bestValue = value;
 179                         bestSplit = split;
 180                 }
 181         }
 182
 183         /* nothing, we have a leaf */
 184         if ( bestValue == -99999 ) {
 185                 return;
 186         }
 187
 188         /* set best split data */
 189         *splitPlaneNum = bestSplit->planenum;
 190         *compileFlags = bestSplit->compileFlags;
 191
 192         if ( *splitPlaneNum > -1 ) {
 193                 mapplanes[ *splitPlaneNum ].counter++;
 194         }
 195 }
 196
 197
 198
 199 /*
 200    CountFaceList()
 201    counts bsp faces in the linked list
 202  */
 203
 204 int CountFaceList( face_t *list ){
 205         int c;
 206
 207
 208         c = 0;
 209         for ( ; list != NULL; list = list->next )
 210                 c++;
 211         return c;
 212 }
 213
 214
 215
 216 /*
 217    BuildFaceTree_r()
 218    recursively builds the bsp, splitting on face planes
 219  */
 220
 221 void BuildFaceTree_r( node_t *node, face_t *list ){
 222         face_t      *split;
 223         face_t      *next;
 224         int side;
 225         plane_t     *plane;
 226         face_t      *newFace;
 227         face_t      *childLists[2];
 228         winding_t   *frontWinding, *backWinding;
 229         int i;
 230         int splitPlaneNum, compileFlags;
 231
 232
 233         /* count faces left */
 234         i = CountFaceList( list );
 235
 236         /* select the best split plane */
 237         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
 238
 239         /* if we don't have any more faces, this is a node */
 240         if ( splitPlaneNum == -1 ) {
 241                 node->planenum = PLANENUM_LEAF;
 242                 node->has_structural_children = qfalse;
 243                 c_faceLeafs++;
 244                 return;
 245         }
 246
 247         /* partition the list */
 248         node->planenum = splitPlaneNum;
 249         node->compileFlags = compileFlags;
 250         node->has_structural_children = !( compileFlags & C_DETAIL ) && !node->opaque;
 251         plane = &mapplanes[ splitPlaneNum ];
 252         childLists[0] = NULL;
 253         childLists[1] = NULL;
 254
 255         for ( split = list; split; split = next )
 256         {
 257                 /* set next */
 258                 next = split->next;
 259
 260                 /* don't split by identical plane */
 261                 if ( split->planenum == node->planenum ) {
 262                         FreeBspFace( split );
 263                         continue;
 264                 }
 265
 266                 /* determine which side the face falls on */
 267                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
 268
 269                 /* switch on side */
 270                 if ( side == SIDE_CROSS ) {
 271                         /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
 272                         ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
 273                                                                 &frontWinding, &backWinding );
 274                         if ( frontWinding ) {
 275                                 newFace = AllocBspFace();
 276                                 newFace->w = frontWinding;
 277                                 newFace->next = childLists[0];
 278                                 newFace->planenum = split->planenum;
 279                                 newFace->priority = split->priority;
 280                                 newFace->compileFlags = split->compileFlags;
 281                                 childLists[0] = newFace;
 282                         }
 283                         if ( backWinding ) {
 284                                 newFace = AllocBspFace();
 285                                 newFace->w = backWinding;
 286                                 newFace->next = childLists[1];
 287                                 newFace->planenum = split->planenum;
 288                                 newFace->priority = split->priority;
 289                                 newFace->compileFlags = split->compileFlags;
 290                                 childLists[1] = newFace;
 291                         }
 292                         FreeBspFace( split );
 293                 }
 294                 else if ( side == SIDE_FRONT ) {
 295                         split->next = childLists[0];
 296                         childLists[0] = split;
 297                 }
 298                 else if ( side == SIDE_BACK ) {
 299                         split->next = childLists[1];
 300                         childLists[1] = split;
 301                 }
 302         }
 303
 304
 305         // recursively process children
 306         for ( i = 0 ; i < 2 ; i++ ) {
 307                 node->children[i] = AllocNode();
 308                 node->children[i]->parent = node;
 309                 VectorCopy( node->mins, node->children[i]->mins );
 310                 VectorCopy( node->maxs, node->children[i]->maxs );
 311         }
 312
 313         for ( i = 0 ; i < 3 ; i++ ) {
 314                 if ( plane->normal[i] == 1 ) {
 315                         node->children[0]->mins[i] = plane->dist;
 316                         node->children[1]->maxs[i] = plane->dist;
 317                         break;
 318                 }
 319                 if ( plane->normal[i] == -1 ) {
 320                         node->children[0]->maxs[i] = -plane->dist;
 321                         node->children[1]->mins[i] = -plane->dist;
 322                         break;
 323                 }
 324         }
 325
 326         for ( i = 0 ; i < 2 ; i++ ) {
 327                 BuildFaceTree_r( node->children[i], childLists[i] );
 328                 node->has_structural_children |= node->children[i]->has_structural_children;
 329         }
 330 }
 331
 332
 333 /*
 334    ================
 335    FaceBSP
 336
 337    List will be freed before returning
 338    ================
 339  */
 340 tree_t *FaceBSP( face_t *list ) {
 341         tree_t      *tree;
 342         face_t  *face;
 343         int i;
 344         int count;
 345
 346         Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
 347
 348         tree = AllocTree();
 349
 350         count = 0;
 351         for ( face = list; face != NULL; face = face->next )
 352         {
 353                 count++;
 354                 for ( i = 0; i < face->w->numpoints; i++ )
 355                 {
 356                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
 357                 }
 358         }
 359         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
 360
 361         for ( i = 0; i < nummapplanes; i++ )
 362         {
 363                 mapplanes[ i ].counter = 0;
 364         }
 365
 366         tree->headnode = AllocNode();
 367         VectorCopy( tree->mins, tree->headnode->mins );
 368         VectorCopy( tree->maxs, tree->headnode->maxs );
 369         c_faceLeafs = 0;
 370
 371         BuildFaceTree_r( tree->headnode, list );
 372
 373         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
 374
 375         return tree;
 376 }
 377
 378
 379
 380 /*
 381    MakeStructuralBSPFaceList()
 382    get structural brush faces
 383  */
 384
 385 face_t *MakeStructuralBSPFaceList( brush_t *list ){
 386         brush_t     *b;
 387         int i;
 388         side_t      *s;
 389         winding_t   *w;
 390         face_t      *f, *flist;
 391
 392
 393         flist = NULL;
 394         for ( b = list; b != NULL; b = b->next )
 395         {
 396                 if ( !deepBSP && b->detail ) {
 397                         continue;
 398                 }
 399
 400                 for ( i = 0; i < b->numsides; i++ )
 401                 {
 402                         /* get side and winding */
 403                         s = &b->sides[ i ];
 404                         w = s->winding;
 405                         if ( w == NULL ) {
 406                                 continue;
 407                         }
 408
 409                         /* ydnar: skip certain faces */
 410                         if ( s->compileFlags & C_SKIP ) {
 411                                 continue;
 412                         }
 413
 414                         /* allocate a face */
 415                         f = AllocBspFace();
 416                         f->w = CopyWinding( w );
 417                         f->planenum = s->planenum & ~1;
 418                         f->compileFlags = s->compileFlags;  /* ydnar */
 419                         if ( b->detail ) {
 420                                 f->compileFlags |= C_DETAIL;
 421                         }
 422
 423                         /* ydnar: set priority */
 424                         f->priority = 0;
 425                         if ( f->compileFlags & C_HINT ) {
 426                                 f->priority += HINT_PRIORITY;
 427                         }
 428                         if ( f->compileFlags & C_ANTIPORTAL ) {
 429                                 f->priority += ANTIPORTAL_PRIORITY;
 430                         }
 431                         if ( f->compileFlags & C_AREAPORTAL ) {
 432                                 f->priority += AREAPORTAL_PRIORITY;
 433                         }
 434                         if ( f->compileFlags & C_DETAIL ) {
 435                                 f->priority += DETAIL_PRIORITY;
 436                         }
 437
 438                         /* get next face */
 439                         f->next = flist;
 440                         flist = f;
 441                 }
 442         }
 443
 444         return flist;
 445 }
 446
 447
 448
 449 /*
 450    MakeVisibleBSPFaceList()
 451    get visible brush faces
 452  */
 453
 454 face_t *MakeVisibleBSPFaceList( brush_t *list ){
 455         brush_t     *b;
 456         int i;
 457         side_t      *s;
 458         winding_t   *w;
 459         face_t      *f, *flist;
 460
 461
 462         flist = NULL;
 463         for ( b = list; b != NULL; b = b->next )
 464         {
 465                 if ( !deepBSP && b->detail ) {
 466                         continue;
 467                 }
 468
 469                 for ( i = 0; i < b->numsides; i++ )
 470                 {
 471                         /* get side and winding */
 472                         s = &b->sides[ i ];
 473                         w = s->visibleHull;
 474                         if ( w == NULL ) {
 475                                 continue;
 476                         }
 477
 478                         /* ydnar: skip certain faces */
 479                         if ( s->compileFlags & C_SKIP ) {
 480                                 continue;
 481                         }
 482
 483                         /* allocate a face */
 484                         f = AllocBspFace();
 485                         f->w = CopyWinding( w );
 486                         f->planenum = s->planenum & ~1;
 487                         f->compileFlags = s->compileFlags;  /* ydnar */
 488                         if ( b->detail ) {
 489                                 f->compileFlags |= C_DETAIL;
 490                         }
 491
 492                         /* ydnar: set priority */
 493                         f->priority = 0;
 494                         if ( f->compileFlags & C_HINT ) {
 495                                 f->priority += HINT_PRIORITY;
 496                         }
 497                         if ( f->compileFlags & C_ANTIPORTAL ) {
 498                                 f->priority += ANTIPORTAL_PRIORITY;
 499                         }
 500                         if ( f->compileFlags & C_AREAPORTAL ) {
 501                                 f->priority += AREAPORTAL_PRIORITY;
 502                         }
 503                         if ( f->compileFlags & C_DETAIL ) {
 504                                 f->priority += DETAIL_PRIORITY;
 505                         }
 506
 507                         /* get next face */
 508                         f->next = flist;
 509                         flist = f;
 510                 }
 511         }
 512
 513         return flist;
 514 }