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