tools/quake3/q3map2/facebsp.c

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