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 ){
83 int splits, facing, front, back;
93 /* ydnar: set some defaults */
94 *splitPlaneNum = -1; /* leaf */
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 */
100 /* if it is crossing a block boundary, force a split */
101 for ( i = 0; i < 3; i++ )
103 if ( blockSize[ i ] <= 0 ) {
106 dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
107 if ( node->maxs[ i ] > dist ) {
108 VectorClear( normal );
110 planenum = FindFloatPlane( normal, dist, 0, NULL );
111 *splitPlaneNum = planenum;
116 /* pick one of the face planes */
120 for ( split = list; split; split = split->next )
121 split->checked = qfalse;
123 for ( split = list; split; split = split->next )
125 if ( split->checked ) {
129 plane = &mapplanes[ split->planenum ];
134 for ( check = list ; check ; check = check->next ) {
135 if ( check->planenum == split->planenum ) {
137 check->checked = qtrue; // won't need to test this plane again
140 side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
141 if ( side == SIDE_CROSS ) {
144 else if ( side == SIDE_FRONT ) {
147 else if ( side == SIDE_BACK ) {
151 value = 5 * facing - 5 * splits; // - abs(front-back);
152 if ( plane->type < 3 ) {
153 value += 5; // axial is better
155 value += split->priority; // prioritize hints higher
157 if ( value > bestValue ) {
163 /* nothing, we have a leaf */
164 if ( bestValue == -99999 ) {
168 /* set best split data */
169 *splitPlaneNum = bestSplit->planenum;
170 *compileFlags = bestSplit->compileFlags;
177 counts bsp faces in the linked list
180 int CountFaceList( face_t *list ){
185 for ( ; list != NULL; list = list->next )
194 recursively builds the bsp, splitting on face planes
197 void BuildFaceTree_r( node_t *node, face_t *list ){
203 face_t *childLists[2];
204 winding_t *frontWinding, *backWinding;
206 int splitPlaneNum, compileFlags;
209 /* count faces left */
210 i = CountFaceList( list );
212 /* select the best split plane */
213 SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
215 /* if we don't have any more faces, this is a node */
216 if ( splitPlaneNum == -1 ) {
217 node->planenum = PLANENUM_LEAF;
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 )
233 /* don't split by identical plane */
234 if ( split->planenum == node->planenum ) {
235 FreeBspFace( split );
239 /* determine which side the face falls on */
240 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
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;
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;
264 FreeBspFace( split );
266 else if ( side == SIDE_FRONT ) {
267 split->next = childLists[0];
268 childLists[0] = split;
270 else if ( side == SIDE_BACK ) {
271 split->next = childLists[1];
272 childLists[1] = split;
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 );
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;
293 for ( i = 0 ; i < 2 ; i++ ) {
294 BuildFaceTree_r( node->children[i], childLists[i] );
303 List will be freed before returning
306 tree_t *FaceBSP( face_t *list ) {
312 Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
317 for ( face = list; face != NULL; face = face->next )
320 for ( i = 0; i < face->w->numpoints; i++ )
322 AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
325 Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
327 tree->headnode = AllocNode();
328 VectorCopy( tree->mins, tree->headnode->mins );
329 VectorCopy( tree->maxs, tree->headnode->maxs );
332 BuildFaceTree_r( tree->headnode, list );
334 Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
342 MakeStructuralBSPFaceList()
343 get structural brush faces
346 face_t *MakeStructuralBSPFaceList( brush_t *list ){
355 for ( b = list; b != NULL; b = b->next )
361 for ( i = 0; i < b->numsides; i++ )
363 /* get side and winding */
370 /* ydnar: skip certain faces */
371 if ( s->compileFlags & C_SKIP ) {
375 /* allocate a face */
377 f->w = CopyWinding( w );
378 f->planenum = s->planenum & ~1;
379 f->compileFlags = s->compileFlags; /* ydnar */
381 /* ydnar: set priority */
383 if ( f->compileFlags & C_HINT ) {
384 f->priority += HINT_PRIORITY;
386 if ( f->compileFlags & C_ANTIPORTAL ) {
387 f->priority += ANTIPORTAL_PRIORITY;
389 if ( f->compileFlags & C_AREAPORTAL ) {
390 f->priority += AREAPORTAL_PRIORITY;
405 MakeVisibleBSPFaceList()
406 get visible brush faces
409 face_t *MakeVisibleBSPFaceList( brush_t *list ){
418 for ( b = list; b != NULL; b = b->next )
424 for ( i = 0; i < b->numsides; i++ )
426 /* get side and winding */
433 /* ydnar: skip certain faces */
434 if ( s->compileFlags & C_SKIP ) {
438 /* allocate a face */
440 f->w = CopyWinding( w );
441 f->planenum = s->planenum & ~1;
442 f->compileFlags = s->compileFlags; /* ydnar */
444 /* ydnar: set priority */
446 if ( f->compileFlags & C_HINT ) {
447 f->priority += HINT_PRIORITY;
449 if ( f->compileFlags & C_ANTIPORTAL ) {
450 f->priority += ANTIPORTAL_PRIORITY;
452 if ( f->compileFlags & C_AREAPORTAL ) {
453 f->priority += AREAPORTAL_PRIORITY;