1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 #include "sys/platform.h"
30
31 #include "tools/compilers/dmap/dmap.h"
32
33 int c_faceLeafs;
34
35
36 extern int c_nodes;
37
38 void RemovePortalFromNode( uPortal_t *portal, node_t *l );
39
NodeForPoint(node_t * node,idVec3 origin)40 node_t *NodeForPoint( node_t *node, idVec3 origin ) {
41 float d;
42
43 while( node->planenum != PLANENUM_LEAF ) {
44 idPlane &plane = dmapGlobals.mapPlanes[node->planenum];
45 d = plane.Distance( origin );
46 if ( d >= 0 ) {
47 node = node->children[0];
48 } else {
49 node = node->children[1];
50 }
51 }
52
53 return node;
54 }
55
56
57
58 /*
59 =============
60 FreeTreePortals_r
61 =============
62 */
FreeTreePortals_r(node_t * node)63 void FreeTreePortals_r (node_t *node)
64 {
65 uPortal_t *p, *nextp;
66 int s;
67
68 // free children
69 if (node->planenum != PLANENUM_LEAF)
70 {
71 FreeTreePortals_r (node->children[0]);
72 FreeTreePortals_r (node->children[1]);
73 }
74
75 // free portals
76 for (p=node->portals ; p ; p=nextp)
77 {
78 s = (p->nodes[1] == node);
79 nextp = p->next[s];
80
81 RemovePortalFromNode (p, p->nodes[!s]);
82 FreePortal (p);
83 }
84 node->portals = NULL;
85 }
86
87 /*
88 =============
89 FreeTree_r
90 =============
91 */
FreeTree_r(node_t * node)92 void FreeTree_r (node_t *node)
93 {
94 // free children
95 if (node->planenum != PLANENUM_LEAF)
96 {
97 FreeTree_r (node->children[0]);
98 FreeTree_r (node->children[1]);
99 }
100
101 // free brushes
102 FreeBrushList (node->brushlist);
103
104 // free the node
105 c_nodes--;
106 Mem_Free (node);
107 }
108
109
110 /*
111 =============
112 FreeTree
113 =============
114 */
FreeTree(tree_t * tree)115 void FreeTree( tree_t *tree ) {
116 if ( !tree ) {
117 return;
118 }
119 FreeTreePortals_r (tree->headnode);
120 FreeTree_r (tree->headnode);
121 Mem_Free (tree);
122 }
123
124 //===============================================================
125
PrintTree_r(node_t * node,int depth)126 void PrintTree_r (node_t *node, int depth)
127 {
128 int i;
129 uBrush_t *bb;
130
131 for (i=0 ; i<depth ; i++)
132 common->Printf(" ");
133 if (node->planenum == PLANENUM_LEAF)
134 {
135 if (!node->brushlist)
136 common->Printf("NULL\n");
137 else
138 {
139 for (bb=node->brushlist ; bb ; bb=bb->next)
140 common->Printf("%i ", bb->original->brushnum);
141 common->Printf("\n");
142 }
143 return;
144 }
145
146 idPlane &plane = dmapGlobals.mapPlanes[node->planenum];
147 common->Printf( "#%i (%5.2f %5.2f %5.2f %5.2f)\n", node->planenum,
148 plane[0], plane[1], plane[2], plane[3] );
149 PrintTree_r( node->children[0], depth+1 );
150 PrintTree_r( node->children[1], depth+1 );
151 }
152
153 /*
154 ================
155 AllocBspFace
156 ================
157 */
AllocBspFace(void)158 bspface_t *AllocBspFace( void ) {
159 bspface_t *f;
160
161 f = (bspface_t *)Mem_Alloc(sizeof(*f));
162 memset( f, 0, sizeof(*f) );
163
164 return f;
165 }
166
167 /*
168 ================
169 FreeBspFace
170 ================
171 */
FreeBspFace(bspface_t * f)172 void FreeBspFace( bspface_t *f ) {
173 if ( f->w ) {
174 delete f->w;
175 }
176 Mem_Free( f );
177 }
178
179
180 /*
181 ================
182 SelectSplitPlaneNum
183 ================
184 */
185 #define BLOCK_SIZE 1024
SelectSplitPlaneNum(node_t * node,bspface_t * list)186 int SelectSplitPlaneNum( node_t *node, bspface_t *list ) {
187 bspface_t *split;
188 bspface_t *check;
189 bspface_t *bestSplit;
190 int splits, facing, front, back;
191 int side;
192 idPlane *mapPlane;
193 int value, bestValue;
194 idPlane plane;
195 int planenum;
196 bool havePortals;
197 float dist;
198 idVec3 halfSize;
199
200 // if it is crossing a 1k block boundary, force a split
201 // this prevents epsilon problems from extending an
202 // arbitrary distance across the map
203
204 halfSize = ( node->bounds[1] - node->bounds[0] ) * 0.5f;
205 for ( int axis = 0; axis < 3; axis++ ) {
206 if ( halfSize[axis] > BLOCK_SIZE ) {
207 dist = BLOCK_SIZE * ( floor( ( node->bounds[0][axis] + halfSize[axis] ) / BLOCK_SIZE ) + 1.0f );
208 } else {
209 dist = BLOCK_SIZE * ( floor( node->bounds[0][axis] / BLOCK_SIZE ) + 1.0f );
210 }
211 if ( dist > node->bounds[0][axis] + 1.0f && dist < node->bounds[1][axis] - 1.0f ) {
212 plane[0] = plane[1] = plane[2] = 0.0f;
213 plane[axis] = 1.0f;
214 plane[3] = -dist;
215 planenum = FindFloatPlane( plane );
216 return planenum;
217 }
218 }
219
220 // pick one of the face planes
221 // if we have any portal faces at all, only
222 // select from them, otherwise select from
223 // all faces
224 bestValue = -999999;
225 bestSplit = list;
226
227 havePortals = false;
228 for ( split = list ; split ; split = split->next ) {
229 split->checked = false;
230 if ( split->portal ) {
231 havePortals = true;
232 }
233 }
234
235 for ( split = list ; split ; split = split->next ) {
236 if ( split->checked ) {
237 continue;
238 }
239 if ( havePortals != split->portal ) {
240 continue;
241 }
242 mapPlane = &dmapGlobals.mapPlanes[ split->planenum ];
243 splits = 0;
244 facing = 0;
245 front = 0;
246 back = 0;
247 for ( check = list ; check ; check = check->next ) {
248 if ( check->planenum == split->planenum ) {
249 facing++;
250 check->checked = true; // won't need to test this plane again
251 continue;
252 }
253 side = check->w->PlaneSide( *mapPlane );
254 if ( side == SIDE_CROSS ) {
255 splits++;
256 } else if ( side == SIDE_FRONT ) {
257 front++;
258 } else if ( side == SIDE_BACK ) {
259 back++;
260 }
261 }
262 value = 5*facing - 5*splits; // - abs(front-back);
263 if ( mapPlane->Type() < PLANETYPE_TRUEAXIAL ) {
264 value+=5; // axial is better
265 }
266
267 if ( value > bestValue ) {
268 bestValue = value;
269 bestSplit = split;
270 }
271 }
272
273 if ( bestValue == -999999 ) {
274 return -1;
275 }
276
277 return bestSplit->planenum;
278 }
279
280 /*
281 ================
282 BuildFaceTree_r
283 ================
284 */
BuildFaceTree_r(node_t * node,bspface_t * list)285 void BuildFaceTree_r( node_t *node, bspface_t *list ) {
286 bspface_t *split;
287 bspface_t *next;
288 int side;
289 bspface_t *newFace;
290 bspface_t *childLists[2];
291 idWinding *frontWinding, *backWinding;
292 int i;
293 int splitPlaneNum;
294
295 splitPlaneNum = SelectSplitPlaneNum( node, list );
296 // if we don't have any more faces, this is a node
297 if ( splitPlaneNum == -1 ) {
298 node->planenum = PLANENUM_LEAF;
299 c_faceLeafs++;
300 return;
301 }
302
303 // partition the list
304 node->planenum = splitPlaneNum;
305 idPlane &plane = dmapGlobals.mapPlanes[ splitPlaneNum ];
306 childLists[0] = NULL;
307 childLists[1] = NULL;
308 for ( split = list ; split ; split = next ) {
309 next = split->next;
310
311 if ( split->planenum == node->planenum ) {
312 FreeBspFace( split );
313 continue;
314 }
315
316 side = split->w->PlaneSide( plane );
317
318 if ( side == SIDE_CROSS ) {
319 split->w->Split( plane, CLIP_EPSILON * 2, &frontWinding, &backWinding );
320 if ( frontWinding ) {
321 newFace = AllocBspFace();
322 newFace->w = frontWinding;
323 newFace->next = childLists[0];
324 newFace->planenum = split->planenum;
325 childLists[0] = newFace;
326 }
327 if ( backWinding ) {
328 newFace = AllocBspFace();
329 newFace->w = backWinding;
330 newFace->next = childLists[1];
331 newFace->planenum = split->planenum;
332 childLists[1] = newFace;
333 }
334 FreeBspFace( split );
335 } else if ( side == SIDE_FRONT ) {
336 split->next = childLists[0];
337 childLists[0] = split;
338 } else if ( side == SIDE_BACK ) {
339 split->next = childLists[1];
340 childLists[1] = split;
341 }
342 }
343
344
345 // recursively process children
346 for ( i = 0 ; i < 2 ; i++ ) {
347 node->children[i] = AllocNode();
348 node->children[i]->parent = node;
349 node->children[i]->bounds = node->bounds;
350 }
351
352 // split the bounds if we have a nice axial plane
353 for ( i = 0 ; i < 3 ; i++ ) {
354 if ( idMath::Fabs( plane[i] - 1.0 ) < 0.001 ) {
355 node->children[0]->bounds[0][i] = plane.Dist();
356 node->children[1]->bounds[1][i] = plane.Dist();
357 break;
358 }
359 }
360
361 for ( i = 0 ; i < 2 ; i++ ) {
362 BuildFaceTree_r ( node->children[i], childLists[i]);
363 }
364 }
365
366
367 /*
368 ================
369 FaceBSP
370
371 List will be freed before returning
372 ================
373 */
FaceBSP(bspface_t * list)374 tree_t *FaceBSP( bspface_t *list ) {
375 tree_t *tree;
376 bspface_t *face;
377 int i;
378 int count;
379 int start, end;
380
381 start = Sys_Milliseconds();
382
383 common->Printf( "--- FaceBSP ---\n" );
384
385 tree = AllocTree ();
386
387 count = 0;
388 tree->bounds.Clear();
389 for ( face = list ; face ; face = face->next ) {
390 count++;
391 for ( i = 0 ; i < face->w->GetNumPoints() ; i++ ) {
392 tree->bounds.AddPoint( (*face->w)[i].ToVec3() );
393 }
394 }
395 common->Printf( "%5i faces\n", count );
396
397 tree->headnode = AllocNode();
398 tree->headnode->bounds = tree->bounds;
399 c_faceLeafs = 0;
400
401 BuildFaceTree_r ( tree->headnode, list );
402
403 common->Printf( "%5i leafs\n", c_faceLeafs );
404
405 end = Sys_Milliseconds();
406
407 common->Printf( "%5.1f seconds faceBsp\n", ( end - start ) / 1000.0 );
408
409 return tree;
410 }
411
412 //==========================================================================
413
414 /*
415 =================
416 MakeStructuralBspFaceList
417 =================
418 */
MakeStructuralBspFaceList(primitive_t * list)419 bspface_t *MakeStructuralBspFaceList( primitive_t *list ) {
420 uBrush_t *b;
421 int i;
422 side_t *s;
423 idWinding *w;
424 bspface_t *f, *flist;
425
426 flist = NULL;
427 for ( ; list ; list = list->next ) {
428 b = list->brush;
429 if ( !b ) {
430 continue;
431 }
432 if ( !b->opaque && !( b->contents & CONTENTS_AREAPORTAL ) ) {
433 continue;
434 }
435 for ( i = 0 ; i < b->numsides ; i++ ) {
436 s = &b->sides[i];
437 w = s->winding;
438 if ( !w ) {
439 continue;
440 }
441 if ( ( b->contents & CONTENTS_AREAPORTAL ) && ! ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
442 continue;
443 }
444 f = AllocBspFace();
445 if ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) {
446 f->portal = true;
447 }
448 f->w = w->Copy();
449 f->planenum = s->planenum & ~1;
450 f->next = flist;
451 flist = f;
452 }
453 }
454
455 return flist;
456 }
457
458 /*
459 =================
460 MakeVisibleBspFaceList
461 =================
462 */
MakeVisibleBspFaceList(primitive_t * list)463 bspface_t *MakeVisibleBspFaceList( primitive_t *list ) {
464 uBrush_t *b;
465 int i;
466 side_t *s;
467 idWinding *w;
468 bspface_t *f, *flist;
469
470 flist = NULL;
471 for ( ; list ; list = list->next ) {
472 b = list->brush;
473 if ( !b ) {
474 continue;
475 }
476 if ( !b->opaque && !( b->contents & CONTENTS_AREAPORTAL ) ) {
477 continue;
478 }
479 for ( i = 0 ; i < b->numsides ; i++ ) {
480 s = &b->sides[i];
481 w = s->visibleHull;
482 if ( !w ) {
483 continue;
484 }
485 f = AllocBspFace();
486 if ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) {
487 f->portal = true;
488 }
489 f->w = w->Copy();
490 f->planenum = s->planenum & ~1;
491 f->next = flist;
492 flist = f;
493 }
494 }
495
496 return flist;
497 }
498