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 interAreaPortal_t interAreaPortals[MAX_INTER_AREA_PORTALS];
34 int numInterAreaPortals;
35
36
37 int c_active_portals;
38 int c_peak_portals;
39
40 /*
41 ===========
42 AllocPortal
43 ===========
44 */
AllocPortal(void)45 uPortal_t *AllocPortal (void)
46 {
47 uPortal_t *p;
48
49 c_active_portals++;
50 if (c_active_portals > c_peak_portals)
51 c_peak_portals = c_active_portals;
52
53 p = (uPortal_t *)Mem_Alloc (sizeof(uPortal_t ));
54 memset (p, 0, sizeof(uPortal_t ));
55
56 return p;
57 }
58
59
FreePortal(uPortal_t * p)60 void FreePortal (uPortal_t *p)
61 {
62 if (p->winding)
63 delete p->winding;
64 c_active_portals--;
65 Mem_Free (p);
66 }
67
68 //==============================================================
69
70 /*
71 =============
72 Portal_Passable
73
74 Returns true if the portal has non-opaque leafs on both sides
75 =============
76 */
Portal_Passable(uPortal_t * p)77 static bool Portal_Passable( uPortal_t *p ) {
78 if (!p->onnode) {
79 return false; // to global outsideleaf
80 }
81
82 if (p->nodes[0]->planenum != PLANENUM_LEAF
83 || p->nodes[1]->planenum != PLANENUM_LEAF) {
84 common->Error( "Portal_EntityFlood: not a leaf");
85 }
86
87 if ( !p->nodes[0]->opaque && !p->nodes[1]->opaque ) {
88 return true;
89 }
90
91 return false;
92 }
93
94
95 //=============================================================================
96
97 int c_tinyportals;
98
99 /*
100 =============
101 AddPortalToNodes
102 =============
103 */
AddPortalToNodes(uPortal_t * p,node_t * front,node_t * back)104 void AddPortalToNodes (uPortal_t *p, node_t *front, node_t *back) {
105 if (p->nodes[0] || p->nodes[1]) {
106 common->Error( "AddPortalToNode: already included");
107 }
108
109 p->nodes[0] = front;
110 p->next[0] = front->portals;
111 front->portals = p;
112
113 p->nodes[1] = back;
114 p->next[1] = back->portals;
115 back->portals = p;
116 }
117
118
119 /*
120 =============
121 RemovePortalFromNode
122 =============
123 */
RemovePortalFromNode(uPortal_t * portal,node_t * l)124 void RemovePortalFromNode (uPortal_t *portal, node_t *l)
125 {
126 uPortal_t **pp, *t;
127
128 // remove reference to the current portal
129 pp = &l->portals;
130 while (1)
131 {
132 t = *pp;
133 if (!t)
134 common->Error( "RemovePortalFromNode: portal not in leaf");
135
136 if ( t == portal )
137 break;
138
139 if (t->nodes[0] == l)
140 pp = &t->next[0];
141 else if (t->nodes[1] == l)
142 pp = &t->next[1];
143 else
144 common->Error( "RemovePortalFromNode: portal not bounding leaf");
145 }
146
147 if ( portal->nodes[0] == l ) {
148 *pp = portal->next[0];
149 portal->nodes[0] = NULL;
150 } else if ( portal->nodes[1] == l ) {
151 *pp = portal->next[1];
152 portal->nodes[1] = NULL;
153 } else {
154 common->Error( "RemovePortalFromNode: mislinked" );
155 }
156 }
157
158 //============================================================================
159
PrintPortal(uPortal_t * p)160 void PrintPortal (uPortal_t *p)
161 {
162 int i;
163 idWinding *w;
164
165 w = p->winding;
166 for ( i = 0; i < w->GetNumPoints(); i++ )
167 common->Printf("(%5.0f,%5.0f,%5.0f)\n",(*w)[i][0], (*w)[i][1], (*w)[i][2]);
168 }
169
170 /*
171 ================
172 MakeHeadnodePortals
173
174 The created portals will face the global outside_node
175 ================
176 */
177 #define SIDESPACE 8
MakeHeadnodePortals(tree_t * tree)178 static void MakeHeadnodePortals( tree_t *tree ) {
179 idBounds bounds;
180 int i, j, n;
181 uPortal_t *p, *portals[6];
182 idPlane bplanes[6], *pl;
183 node_t *node;
184
185 node = tree->headnode;
186
187 tree->outside_node.planenum = PLANENUM_LEAF;
188 tree->outside_node.brushlist = NULL;
189 tree->outside_node.portals = NULL;
190 tree->outside_node.opaque = false;
191
192 // if no nodes, don't go any farther
193 if ( node->planenum == PLANENUM_LEAF ) {
194 return;
195 }
196
197 // pad with some space so there will never be null volume leafs
198 for (i=0 ; i<3 ; i++) {
199 bounds[0][i] = tree->bounds[0][i] - SIDESPACE;
200 bounds[1][i] = tree->bounds[1][i] + SIDESPACE;
201 if ( bounds[0][i] >= bounds[1][i] ) {
202 common->Error( "Backwards tree volume" );
203 }
204 }
205
206 for (i=0 ; i<3 ; i++) {
207 for (j=0 ; j<2 ; j++) {
208 n = j*3 + i;
209
210 p = AllocPortal ();
211 portals[n] = p;
212
213 pl = &bplanes[n];
214 memset (pl, 0, sizeof(*pl));
215 if (j) {
216 (*pl)[i] = -1;
217 (*pl)[3] = bounds[j][i];
218 } else {
219 (*pl)[i] = 1;
220 (*pl)[3] = -bounds[j][i];
221 }
222 p->plane = *pl;
223 p->winding = new idWinding( *pl );
224 AddPortalToNodes (p, node, &tree->outside_node);
225 }
226 }
227
228 // clip the basewindings by all the other planes
229 for (i=0 ; i<6 ; i++) {
230 for (j=0 ; j<6 ; j++) {
231 if (j == i) {
232 continue;
233 }
234 portals[i]->winding = portals[i]->winding->Clip( bplanes[j], ON_EPSILON );
235 }
236 }
237 }
238
239 //===================================================
240
241
242 /*
243 ================
244 BaseWindingForNode
245 ================
246 */
247 #define BASE_WINDING_EPSILON 0.001f
248 #define SPLIT_WINDING_EPSILON 0.001f
249
BaseWindingForNode(node_t * node)250 idWinding *BaseWindingForNode (node_t *node) {
251 idWinding *w;
252 node_t *n;
253
254 w = new idWinding( dmapGlobals.mapPlanes[node->planenum] );
255
256 // clip by all the parents
257 for ( n = node->parent ; n && w ; ) {
258 idPlane &plane = dmapGlobals.mapPlanes[n->planenum];
259
260 if ( n->children[0] == node ) {
261 // take front
262 w = w->Clip( plane, BASE_WINDING_EPSILON );
263 } else {
264 // take back
265 idPlane back = -plane;
266 w = w->Clip( back, BASE_WINDING_EPSILON );
267 }
268 node = n;
269 n = n->parent;
270 }
271
272 return w;
273 }
274
275 //============================================================
276
277 /*
278 ==================
279 MakeNodePortal
280
281 create the new portal by taking the full plane winding for the cutting plane
282 and clipping it by all of parents of this node
283 ==================
284 */
MakeNodePortal(node_t * node)285 static void MakeNodePortal( node_t *node ) {
286 uPortal_t *new_portal, *p;
287 idWinding *w;
288 idVec3 normal;
289 int side;
290
291 w = BaseWindingForNode (node);
292
293 // clip the portal by all the other portals in the node
294 for (p = node->portals ; p && w; p = p->next[side])
295 {
296 idPlane plane;
297
298 if (p->nodes[0] == node)
299 {
300 side = 0;
301 plane = p->plane;
302 }
303 else if (p->nodes[1] == node)
304 {
305 side = 1;
306 plane = -p->plane;
307 }
308 else {
309 common->Error( "CutNodePortals_r: mislinked portal");
310 side = 0; // quiet a compiler warning
311 }
312
313 w = w->Clip( plane, CLIP_EPSILON );
314 }
315
316 if (!w)
317 {
318 return;
319 }
320
321 if ( w->IsTiny() )
322 {
323 c_tinyportals++;
324 delete w;
325 return;
326 }
327
328
329 new_portal = AllocPortal ();
330 new_portal->plane = dmapGlobals.mapPlanes[node->planenum];
331 new_portal->onnode = node;
332 new_portal->winding = w;
333 AddPortalToNodes (new_portal, node->children[0], node->children[1]);
334 }
335
336
337 /*
338 ==============
339 SplitNodePortals
340
341 Move or split the portals that bound node so that the node's
342 children have portals instead of node.
343 ==============
344 */
SplitNodePortals(node_t * node)345 static void SplitNodePortals( node_t *node ) {
346 uPortal_t *p, *next_portal, *new_portal;
347 node_t *f, *b, *other_node;
348 int side;
349 idPlane *plane;
350 idWinding *frontwinding, *backwinding;
351
352 plane = &dmapGlobals.mapPlanes[node->planenum];
353 f = node->children[0];
354 b = node->children[1];
355
356 for ( p = node->portals ; p ; p = next_portal ) {
357 if (p->nodes[0] == node ) {
358 side = 0;
359 } else if ( p->nodes[1] == node ) {
360 side = 1;
361 } else {
362 common->Error( "SplitNodePortals: mislinked portal" );
363 side = 0; // quiet a compiler warning
364 }
365 next_portal = p->next[side];
366
367 other_node = p->nodes[!side];
368 RemovePortalFromNode (p, p->nodes[0]);
369 RemovePortalFromNode (p, p->nodes[1]);
370
371 //
372 // cut the portal into two portals, one on each side of the cut plane
373 //
374 p->winding->Split( *plane, SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
375
376 if ( frontwinding && frontwinding->IsTiny() )
377 {
378 delete frontwinding;
379 frontwinding = NULL;
380 c_tinyportals++;
381 }
382
383 if ( backwinding && backwinding->IsTiny() )
384 {
385 delete backwinding;
386 backwinding = NULL;
387 c_tinyportals++;
388 }
389
390 if ( !frontwinding && !backwinding )
391 { // tiny windings on both sides
392 continue;
393 }
394
395 if (!frontwinding)
396 {
397 delete backwinding;
398 if (side == 0)
399 AddPortalToNodes (p, b, other_node);
400 else
401 AddPortalToNodes (p, other_node, b);
402 continue;
403 }
404 if (!backwinding)
405 {
406 delete frontwinding;
407 if (side == 0)
408 AddPortalToNodes (p, f, other_node);
409 else
410 AddPortalToNodes (p, other_node, f);
411 continue;
412 }
413
414 // the winding is split
415 new_portal = AllocPortal ();
416 *new_portal = *p;
417 new_portal->winding = backwinding;
418 delete p->winding;
419 p->winding = frontwinding;
420
421 if (side == 0)
422 {
423 AddPortalToNodes (p, f, other_node);
424 AddPortalToNodes (new_portal, b, other_node);
425 }
426 else
427 {
428 AddPortalToNodes (p, other_node, f);
429 AddPortalToNodes (new_portal, other_node, b);
430 }
431 }
432
433 node->portals = NULL;
434 }
435
436
437 /*
438 ================
439 CalcNodeBounds
440 ================
441 */
CalcNodeBounds(node_t * node)442 void CalcNodeBounds (node_t *node)
443 {
444 uPortal_t *p;
445 int s;
446 int i;
447
448 // calc mins/maxs for both leafs and nodes
449 node->bounds.Clear();
450 for (p = node->portals ; p ; p = p->next[s]) {
451 s = (p->nodes[1] == node);
452 for ( i = 0; i < p->winding->GetNumPoints(); i++ ) {
453 node->bounds.AddPoint( (*p->winding)[i].ToVec3() );
454 }
455 }
456 }
457
458
459 /*
460 ==================
461 MakeTreePortals_r
462 ==================
463 */
MakeTreePortals_r(node_t * node)464 void MakeTreePortals_r (node_t *node)
465 {
466 int i;
467
468 CalcNodeBounds( node );
469
470 if ( node->bounds[0][0] >= node->bounds[1][0]) {
471 common->Warning( "node without a volume" );
472 }
473
474 for ( i = 0; i < 3; i++ ) {
475 if ( node->bounds[0][i] < MIN_WORLD_COORD || node->bounds[1][i] > MAX_WORLD_COORD ) {
476 common->Warning( "node with unbounded volume");
477 break;
478 }
479 }
480 if ( node->planenum == PLANENUM_LEAF ) {
481 return;
482 }
483
484 MakeNodePortal (node);
485 SplitNodePortals (node);
486
487 MakeTreePortals_r (node->children[0]);
488 MakeTreePortals_r (node->children[1]);
489 }
490
491 /*
492 ==================
493 MakeTreePortals
494 ==================
495 */
MakeTreePortals(tree_t * tree)496 void MakeTreePortals (tree_t *tree)
497 {
498 common->Printf( "----- MakeTreePortals -----\n");
499 MakeHeadnodePortals (tree);
500 MakeTreePortals_r (tree->headnode);
501 }
502
503 /*
504 =========================================================
505
506 FLOOD ENTITIES
507
508 =========================================================
509 */
510
511 int c_floodedleafs;
512
513 /*
514 =============
515 FloodPortals_r
516 =============
517 */
FloodPortals_r(node_t * node,int dist)518 void FloodPortals_r (node_t *node, int dist) {
519 uPortal_t *p;
520 int s;
521
522 if ( node->occupied ) {
523 return;
524 }
525
526 if ( node->opaque ) {
527 return;
528 }
529
530 c_floodedleafs++;
531 node->occupied = dist;
532
533 for (p=node->portals ; p ; p = p->next[s]) {
534 s = (p->nodes[1] == node);
535 FloodPortals_r (p->nodes[!s], dist+1);
536 }
537 }
538
539 /*
540 =============
541 PlaceOccupant
542 =============
543 */
PlaceOccupant(node_t * headnode,idVec3 origin,uEntity_t * occupant)544 bool PlaceOccupant( node_t *headnode, idVec3 origin, uEntity_t *occupant ) {
545 node_t *node;
546 float d;
547 idPlane *plane;
548
549 // find the leaf to start in
550 node = headnode;
551 while ( node->planenum != PLANENUM_LEAF ) {
552 plane = &dmapGlobals.mapPlanes[node->planenum];
553 d = plane->Distance( origin );
554 if ( d >= 0.0f ) {
555 node = node->children[0];
556 } else {
557 node = node->children[1];
558 }
559 }
560
561 if ( node->opaque ) {
562 return false;
563 }
564 node->occupant = occupant;
565
566 FloodPortals_r (node, 1);
567
568 return true;
569 }
570
571 /*
572 =============
573 FloodEntities
574
575 Marks all nodes that can be reached by entites
576 =============
577 */
FloodEntities(tree_t * tree)578 bool FloodEntities( tree_t *tree ) {
579 int i;
580 idVec3 origin;
581 const char *cl;
582 bool inside;
583 node_t *headnode;
584
585 headnode = tree->headnode;
586 common->Printf ("--- FloodEntities ---\n");
587 inside = false;
588 tree->outside_node.occupied = 0;
589
590 c_floodedleafs = 0;
591 bool errorShown = false;
592 for (i=1 ; i<dmapGlobals.num_entities ; i++) {
593 idMapEntity *mapEnt;
594
595 mapEnt = dmapGlobals.uEntities[i].mapEntity;
596 if ( !mapEnt->epairs.GetVector( "origin", "", origin) ) {
597 continue;
598 }
599
600 // any entity can have "noFlood" set to skip it
601 if ( mapEnt->epairs.GetString( "noFlood", "", &cl ) ) {
602 continue;
603 }
604
605 mapEnt->epairs.GetString( "classname", "", &cl );
606
607 if ( !strcmp( cl, "light" ) ) {
608 const char *v;
609
610 // don't place lights that have a light_start field, because they can still
611 // be valid if their origin is outside the world
612 mapEnt->epairs.GetString( "light_start", "", &v);
613 if ( v[0] ) {
614 continue;
615 }
616
617 // don't place fog lights, because they often
618 // have origins outside the light
619 mapEnt->epairs.GetString( "texture", "", &v);
620 if ( v[0] ) {
621 const idMaterial *mat = declManager->FindMaterial( v );
622 if ( mat->IsFogLight() ) {
623 continue;
624 }
625 }
626 }
627
628 if (PlaceOccupant (headnode, origin, &dmapGlobals.uEntities[i])) {
629 inside = true;
630 }
631
632 if (tree->outside_node.occupied && !errorShown) {
633 errorShown = true;
634 common->Printf("Leak on entity # %d\n", i);
635 const char *p;
636
637 mapEnt->epairs.GetString( "classname", "", &p);
638 common->Printf("Entity classname was: %s\n", p);
639 mapEnt->epairs.GetString( "name", "", &p);
640 common->Printf("Entity name was: %s\n", p);
641 idVec3 origin;
642 if ( mapEnt->epairs.GetVector( "origin", "", origin)) {
643 common->Printf("Entity origin is: %f %f %f\n\n\n", origin.x, origin.y, origin.z);
644 }
645 }
646 }
647
648 common->Printf("%5i flooded leafs\n", c_floodedleafs );
649
650 if (!inside)
651 {
652 common->Printf ("no entities in open -- no filling\n");
653 }
654 else if (tree->outside_node.occupied)
655 {
656 common->Printf ("entity reached from outside -- no filling\n");
657 }
658
659 return (bool)(inside && !tree->outside_node.occupied);
660 }
661
662 /*
663 =========================================================
664
665 FLOOD AREAS
666
667 =========================================================
668 */
669
670 static int c_areas;
671 static int c_areaFloods;
672
673 /*
674 =================
675 FindSideForPortal
676 =================
677 */
FindSideForPortal(uPortal_t * p)678 static side_t *FindSideForPortal( uPortal_t *p ) {
679 int i, j, k;
680 node_t *node;
681 uBrush_t *b, *orig;
682 side_t *s, *s2;
683
684 // scan both bordering nodes brush lists for a portal brush
685 // that shares the plane
686 for ( i = 0 ; i < 2 ; i++ ) {
687 node = p->nodes[i];
688 for ( b = node->brushlist ; b ; b = b->next ) {
689 if ( !( b->contents & CONTENTS_AREAPORTAL ) ) {
690 continue;
691 }
692 orig = b->original;
693 for ( j = 0 ; j < orig->numsides ; j++ ) {
694 s = orig->sides + j;
695 if ( !s->visibleHull ) {
696 continue;
697 }
698 if ( !( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
699 continue;
700 }
701 if ( ( s->planenum & ~1 ) != ( p->onnode->planenum & ~1 ) ) {
702 continue;
703 }
704 // remove the visible hull from any other portal sides of this portal brush
705 for ( k = 0; k < orig->numsides; k++ ) {
706 if ( k == j ) {
707 continue;
708 }
709 s2 = orig->sides + k;
710 if ( s2->visibleHull == NULL ) {
711 continue;
712 }
713 if ( !( s2->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
714 continue;
715 }
716 common->Warning( "brush has multiple area portal sides at %s", s2->visibleHull->GetCenter().ToString() );
717 delete s2->visibleHull;
718 s2->visibleHull = NULL;
719 }
720 return s;
721 }
722 }
723 }
724 return NULL;
725 }
726
727 /*
728 =============
729 FloodAreas_r
730 =============
731 */
FloodAreas_r(node_t * node)732 void FloodAreas_r (node_t *node)
733 {
734 uPortal_t *p;
735 int s;
736
737 if ( node->area != -1 ) {
738 return; // already got it
739 }
740 if ( node->opaque ) {
741 return;
742 }
743
744 c_areaFloods++;
745 node->area = c_areas;
746
747 for ( p=node->portals ; p ; p = p->next[s] ) {
748 node_t *other;
749
750 s = (p->nodes[1] == node);
751 other = p->nodes[!s];
752
753 if ( !Portal_Passable(p) ) {
754 continue;
755 }
756
757 // can't flood through an area portal
758 if ( FindSideForPortal( p ) ) {
759 continue;
760 }
761
762 FloodAreas_r( other );
763 }
764 }
765
766 /*
767 =============
768 FindAreas_r
769
770 Just decend the tree, and for each node that hasn't had an
771 area set, flood fill out from there
772 =============
773 */
FindAreas_r(node_t * node)774 void FindAreas_r( node_t *node ) {
775 if ( node->planenum != PLANENUM_LEAF ) {
776 FindAreas_r (node->children[0]);
777 FindAreas_r (node->children[1]);
778 return;
779 }
780
781 if ( node->opaque ) {
782 return;
783 }
784
785 if ( node->area != -1 ) {
786 return; // already got it
787 }
788
789 c_areaFloods = 0;
790 FloodAreas_r (node);
791 common->Printf( "area %i has %i leafs\n", c_areas, c_areaFloods );
792 c_areas++;
793 }
794
795 /*
796 ============
797 CheckAreas_r
798 ============
799 */
CheckAreas_r(node_t * node)800 void CheckAreas_r( node_t *node ) {
801 if ( node->planenum != PLANENUM_LEAF ) {
802 CheckAreas_r (node->children[0]);
803 CheckAreas_r (node->children[1]);
804 return;
805 }
806 if ( !node->opaque && node->area < 0 ) {
807 common->Error( "CheckAreas_r: area = %i", node->area );
808 }
809 }
810
811 /*
812 ============
813 ClearAreas_r
814
815 Set all the areas to -1 before filling
816 ============
817 */
ClearAreas_r(node_t * node)818 void ClearAreas_r( node_t *node ) {
819 if ( node->planenum != PLANENUM_LEAF ) {
820 ClearAreas_r (node->children[0]);
821 ClearAreas_r (node->children[1]);
822 return;
823 }
824 node->area = -1;
825 }
826
827 //=============================================================
828
829
830 /*
831 =================
832 FindInterAreaPortals_r
833
834 =================
835 */
FindInterAreaPortals_r(node_t * node)836 static void FindInterAreaPortals_r( node_t *node ) {
837 uPortal_t *p;
838 int s;
839 int i;
840 idWinding *w;
841 interAreaPortal_t *iap;
842 side_t *side;
843
844 if ( node->planenum != PLANENUM_LEAF ) {
845 FindInterAreaPortals_r( node->children[0] );
846 FindInterAreaPortals_r( node->children[1] );
847 return;
848 }
849
850 if ( node->opaque ) {
851 return;
852 }
853
854 for ( p=node->portals ; p ; p = p->next[s] ) {
855 node_t *other;
856
857 s = (p->nodes[1] == node);
858 other = p->nodes[!s];
859
860 if ( other->opaque ) {
861 continue;
862 }
863
864 // only report areas going from lower number to higher number
865 // so we don't report the portal twice
866 if ( other->area <= node->area ) {
867 continue;
868 }
869
870 side = FindSideForPortal( p );
871 // w = p->winding;
872 if ( !side ) {
873 common->Warning( "FindSideForPortal failed at %s", p->winding->GetCenter().ToString() );
874 continue;
875 }
876 w = side->visibleHull;
877 if ( !w ) {
878 continue;
879 }
880
881 // see if we have created this portal before
882 for ( i = 0 ; i < numInterAreaPortals ; i++ ) {
883 iap = &interAreaPortals[i];
884
885 if ( side == iap->side &&
886 ( ( p->nodes[0]->area == iap->area0 && p->nodes[1]->area == iap->area1 )
887 || ( p->nodes[1]->area == iap->area0 && p->nodes[0]->area == iap->area1 ) ) ) {
888 break;
889 }
890 }
891
892 if ( i != numInterAreaPortals ) {
893 continue; // already emited
894 }
895
896 iap = &interAreaPortals[numInterAreaPortals];
897 numInterAreaPortals++;
898 if ( side->planenum == p->onnode->planenum ) {
899 iap->area0 = p->nodes[0]->area;
900 iap->area1 = p->nodes[1]->area;
901 } else {
902 iap->area0 = p->nodes[1]->area;
903 iap->area1 = p->nodes[0]->area;
904 }
905 iap->side = side;
906
907 }
908 }
909
910
911
912
913
914 /*
915 =============
916 FloodAreas
917
918 Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
919 Sets e->areas.numAreas
920 =============
921 */
FloodAreas(uEntity_t * e)922 void FloodAreas( uEntity_t *e ) {
923 common->Printf ("--- FloodAreas ---\n");
924
925 // set all areas to -1
926 ClearAreas_r( e->tree->headnode );
927
928 // flood fill from non-opaque areas
929 c_areas = 0;
930 FindAreas_r( e->tree->headnode );
931
932 common->Printf ("%5i areas\n", c_areas);
933 e->numAreas = c_areas;
934
935 // make sure we got all of them
936 CheckAreas_r( e->tree->headnode );
937
938 // identify all portals between areas if this is the world
939 if ( e == &dmapGlobals.uEntities[0] ) {
940 numInterAreaPortals = 0;
941 FindInterAreaPortals_r( e->tree->headnode );
942 }
943 }
944
945 /*
946 ======================================================
947
948 FILL OUTSIDE
949
950 ======================================================
951 */
952
953 static int c_outside;
954 static int c_inside;
955 static int c_solid;
956
FillOutside_r(node_t * node)957 void FillOutside_r (node_t *node)
958 {
959 if (node->planenum != PLANENUM_LEAF)
960 {
961 FillOutside_r (node->children[0]);
962 FillOutside_r (node->children[1]);
963 return;
964 }
965
966 // anything not reachable by an entity
967 // can be filled away
968 if (!node->occupied) {
969 if ( !node->opaque ) {
970 c_outside++;
971 node->opaque = true;
972 } else {
973 c_solid++;
974 }
975 } else {
976 c_inside++;
977 }
978
979 }
980
981 /*
982 =============
983 FillOutside
984
985 Fill (set node->opaque = true) all nodes that can't be reached by entities
986 =============
987 */
FillOutside(uEntity_t * e)988 void FillOutside( uEntity_t *e ) {
989 c_outside = 0;
990 c_inside = 0;
991 c_solid = 0;
992 common->Printf ("--- FillOutside ---\n");
993 FillOutside_r( e->tree->headnode );
994 common->Printf ("%5i solid leafs\n", c_solid);
995 common->Printf ("%5i leafs filled\n", c_outside);
996 common->Printf ("%5i inside leafs\n", c_inside);
997 }
998