1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
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.
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.
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
22 ----------------------------------------------------------------------------------
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."
27 ------------------------------------------------------------------------------- */
49 face_t *AllocBspFace( void ) {
52 f = safe_malloc(sizeof(*f));
53 memset( f, 0, sizeof(*f) );
65 void FreeBspFace( face_t *f ) {
76 finds the best split plane for this node
79 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )
84 int splits, facing, front, back;
94 //int frontC,backC,splitsC,facingC;
97 /* ydnar: set some defaults */
98 *splitPlaneNum = -1; /* leaf */
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 */
104 /* if it is crossing a block boundary, force a split */
105 for( i = 0; i < 3; i++ )
107 if( blockSize[ i ] <= 0 )
109 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
110 if( node->maxs[ i ] > dist )
112 VectorClear( normal );
114 planenum = FindFloatPlane( normal, dist, 0, NULL );
115 *splitPlaneNum = planenum;
120 /* pick one of the face planes */
125 // div0: this check causes detail/structural mixes
126 //for( split = list; split; split = split->next )
127 // split->checked = qfalse;
129 for( split = list; split; split = split->next )
131 //if ( split->checked )
134 plane = &mapplanes[ split->planenum ];
139 for ( check = list ; check ; check = check->next ) {
140 if ( check->planenum == split->planenum ) {
142 //check->checked = qtrue; // won't need to test this plane again
145 side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
146 if ( side == SIDE_CROSS ) {
148 } else if ( side == SIDE_FRONT ) {
150 } else if ( side == SIDE_BACK ) {
155 if(bspAlternateSplitWeights)
160 sizeBias=WindingArea(split->w);
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
171 value = 5*facing - 5*splits; // - abs(front-back);
172 if ( plane->type < 3 ) {
173 value+=5; // axial is better
177 value += split->priority; // prioritize hints higher
179 if ( value > bestValue ) {
189 /* nothing, we have a leaf */
190 if( bestValue == -99999 )
193 //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
195 /* set best split data */
196 *splitPlaneNum = bestSplit->planenum;
197 *compileFlags = bestSplit->compileFlags;
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");
208 if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;
215 counts bsp faces in the linked list
218 int CountFaceList( face_t *list )
224 for( ; list != NULL; list = list->next )
233 recursively builds the bsp, splitting on face planes
236 void BuildFaceTree_r( node_t *node, face_t *list )
243 face_t *childLists[2];
244 winding_t *frontWinding, *backWinding;
246 int splitPlaneNum, compileFlags;
248 qboolean isstruct = qfalse;
252 /* count faces left */
253 i = CountFaceList( list );
255 /* select the best split plane */
256 SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
258 /* if we don't have any more faces, this is a node */
259 if ( splitPlaneNum == -1 )
261 node->planenum = PLANENUM_LEAF;
262 node->has_structural_children = qfalse;
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;
275 for( split = list; split; split = next )
280 /* don't split by identical plane */
281 if( split->planenum == node->planenum )
283 FreeBspFace( split );
288 if(!(split->compileFlags & C_DETAIL))
292 /* determine which side the face falls on */
293 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
296 if( side == SIDE_CROSS )
298 ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
299 &frontWinding, &backWinding ); /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
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;
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;
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;
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 );
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;
343 if ( plane->normal[i] == -1 ) {
344 node->children[0]->maxs[i] = -plane->dist;
345 node->children[1]->mins[i] = -plane->dist;
351 if((node->compileFlags & C_DETAIL) && isstruct)
352 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children);
355 for ( i = 0 ; i < 2 ; i++ ) {
356 BuildFaceTree_r ( node->children[i], childLists[i]);
357 node->has_structural_children |= node->children[i]->has_structural_children;
361 if((node->compileFlags & C_DETAIL) && !(node->children[0]->compileFlags & C_DETAIL) && node->children[0]->planenum != PLANENUM_LEAF)
362 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children);
363 if((node->compileFlags & C_DETAIL) && isstruct)
364 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children);
373 List will be freed before returning
376 tree_t *FaceBSP( face_t *list ) {
382 Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
387 for( face = list; face != NULL; face = face->next )
390 for( i = 0; i < face->w->numpoints; i++ )
392 AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
395 Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
397 for( i = 0; i < nummapplanes; i++)
399 mapplanes[ i ].counter=0;
402 tree->headnode = AllocNode();
403 VectorCopy( tree->mins, tree->headnode->mins );
404 VectorCopy( tree->maxs, tree->headnode->maxs );
407 BuildFaceTree_r ( tree->headnode, list );
409 Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
417 MakeStructuralBSPFaceList()
418 get structural brush faces
421 face_t *MakeStructuralBSPFaceList( brush_t *list )
431 for( b = list; b != NULL; b = b->next )
433 if( !deepBSP && b->detail )
436 for( i = 0; i < b->numsides; i++ )
438 /* get side and winding */
444 /* ydnar: skip certain faces */
445 if( s->compileFlags & C_SKIP )
448 /* allocate a face */
450 f->w = CopyWinding( w );
451 f->planenum = s->planenum & ~1;
452 f->compileFlags = s->compileFlags; /* ydnar */
454 f->compileFlags |= C_DETAIL;
456 /* ydnar: set priority */
458 if( f->compileFlags & C_HINT )
459 f->priority += HINT_PRIORITY;
460 if( f->compileFlags & C_ANTIPORTAL )
461 f->priority += ANTIPORTAL_PRIORITY;
462 if( f->compileFlags & C_AREAPORTAL )
463 f->priority += AREAPORTAL_PRIORITY;
464 if( f->compileFlags & C_DETAIL )
465 f->priority += DETAIL_PRIORITY;
479 MakeVisibleBSPFaceList()
480 get visible brush faces
483 face_t *MakeVisibleBSPFaceList( brush_t *list )
493 for( b = list; b != NULL; b = b->next )
495 if( !deepBSP && b->detail )
498 for( i = 0; i < b->numsides; i++ )
500 /* get side and winding */
506 /* ydnar: skip certain faces */
507 if( s->compileFlags & C_SKIP )
510 /* allocate a face */
512 f->w = CopyWinding( w );
513 f->planenum = s->planenum & ~1;
514 f->compileFlags = s->compileFlags; /* ydnar */
516 f->compileFlags |= C_DETAIL;
518 /* ydnar: set priority */
520 if( f->compileFlags & C_HINT )
521 f->priority += HINT_PRIORITY;
522 if( f->compileFlags & C_ANTIPORTAL )
523 f->priority += ANTIPORTAL_PRIORITY;
524 if( f->compileFlags & C_AREAPORTAL )
525 f->priority += AREAPORTAL_PRIORITY;
526 if( f->compileFlags & C_DETAIL )
527 f->priority += DETAIL_PRIORITY;