1 /*
2 Copyright (C) 1999-2006 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 #include "qbsp.h"
23
24
25 int c_active_portals;
26 int c_peak_portals;
27 int c_boundary;
28 int c_boundary_sides;
29
30 /*
31 ===========
32 AllocPortal
33 ===========
34 */
AllocPortal(void)35 portal_t *AllocPortal( void ){
36 portal_t *p;
37
38 if ( numthreads == 1 ) {
39 c_active_portals++;
40 }
41 if ( c_active_portals > c_peak_portals ) {
42 c_peak_portals = c_active_portals;
43 }
44
45 p = malloc( sizeof( portal_t ) );
46 memset( p, 0, sizeof( portal_t ) );
47
48 return p;
49 }
50
FreePortal(portal_t * p)51 void FreePortal( portal_t *p ){
52 if ( p->winding ) {
53 FreeWinding( p->winding );
54 }
55 if ( numthreads == 1 ) {
56 c_active_portals--;
57 }
58 free( p );
59 }
60
61 //==============================================================
62
63 /*
64 ==============
65 VisibleContents
66
67 Returns the single content bit of the
68 strongest visible content present
69 ==============
70 */
VisibleContents(int contents)71 int VisibleContents( int contents ){
72 int i;
73
74 for ( i = 1 ; i <= LAST_VISIBLE_CONTENTS ; i <<= 1 )
75 if ( contents & i ) {
76 return i;
77 }
78
79 return 0;
80 }
81
82
83 /*
84 ===============
85 ClusterContents
86 ===============
87 */
ClusterContents(node_t * node)88 int ClusterContents( node_t *node ){
89 int c1, c2, c;
90
91 if ( node->planenum == PLANENUM_LEAF ) {
92 return node->contents;
93 }
94
95 c1 = ClusterContents( node->children[0] );
96 c2 = ClusterContents( node->children[1] );
97 c = c1 | c2;
98
99 // a cluster may include some solid detail areas, but
100 // still be seen into
101 if ( !( c1 & CONTENTS_SOLID ) || !( c2 & CONTENTS_SOLID ) ) {
102 c &= ~CONTENTS_SOLID;
103 }
104 return c;
105 }
106
107 /*
108 =============
109 Portal_VisFlood
110
111 Returns true if the portal is empty or translucent, allowing
112 the PVS calculation to see through it.
113 The nodes on either side of the portal may actually be clusters,
114 not leafs, so all contents should be ored together
115 =============
116 */
Portal_VisFlood(portal_t * p)117 qboolean Portal_VisFlood( portal_t *p ){
118 int c1, c2;
119
120 if ( !p->onnode ) {
121 return false; // to global outsideleaf
122
123 }
124 c1 = ClusterContents( p->nodes[0] );
125 c2 = ClusterContents( p->nodes[1] );
126
127 if ( !VisibleContents( c1 ^ c2 ) ) {
128 return true;
129 }
130
131 if ( c1 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
132 c1 = 0;
133 }
134 if ( c2 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
135 c2 = 0;
136 }
137
138 if ( ( c1 | c2 ) & CONTENTS_SOLID ) {
139 return false; // can't see through solid
140
141 }
142 if ( !( c1 ^ c2 ) ) {
143 return true; // identical on both sides
144
145 }
146 if ( !VisibleContents( c1 ^ c2 ) ) {
147 return true;
148 }
149 return false;
150 }
151
152
153 /*
154 ===============
155 Portal_EntityFlood
156
157 The entity flood determines which areas are
158 "outside" on the map, which are then filled in.
159 Flowing from side s to side !s
160 ===============
161 */
Portal_EntityFlood(portal_t * p,int s)162 qboolean Portal_EntityFlood( portal_t *p, int s ){
163 if ( p->nodes[0]->planenum != PLANENUM_LEAF
164 || p->nodes[1]->planenum != PLANENUM_LEAF ) {
165 Error( "Portal_EntityFlood: not a leaf" );
166 }
167
168 // can never cross to a solid
169 if ( ( p->nodes[0]->contents & CONTENTS_SOLID )
170 || ( p->nodes[1]->contents & CONTENTS_SOLID ) ) {
171 return false;
172 }
173
174 // can flood through everything else
175 return true;
176 }
177
178
179 //=============================================================================
180
181 int c_tinyportals;
182
183 /*
184 =============
185 AddPortalToNodes
186 =============
187 */
AddPortalToNodes(portal_t * p,node_t * front,node_t * back)188 void AddPortalToNodes( portal_t *p, node_t *front, node_t *back ){
189 if ( p->nodes[0] || p->nodes[1] ) {
190 Error( "AddPortalToNode: allready included" );
191 }
192
193 p->nodes[0] = front;
194 p->next[0] = front->portals;
195 front->portals = p;
196
197 p->nodes[1] = back;
198 p->next[1] = back->portals;
199 back->portals = p;
200 }
201
202
203 /*
204 =============
205 RemovePortalFromNode
206 =============
207 */
RemovePortalFromNode(portal_t * portal,node_t * l)208 void RemovePortalFromNode( portal_t *portal, node_t *l ){
209 portal_t **pp, *t;
210
211 // remove reference to the current portal
212 pp = &l->portals;
213 while ( 1 )
214 {
215 t = *pp;
216 if ( !t ) {
217 Error( "RemovePortalFromNode: portal not in leaf" );
218 }
219
220 if ( t == portal ) {
221 break;
222 }
223
224 if ( t->nodes[0] == l ) {
225 pp = &t->next[0];
226 }
227 else if ( t->nodes[1] == l ) {
228 pp = &t->next[1];
229 }
230 else{
231 Error( "RemovePortalFromNode: portal not bounding leaf" );
232 }
233 }
234
235 if ( portal->nodes[0] == l ) {
236 *pp = portal->next[0];
237 portal->nodes[0] = NULL;
238 }
239 else if ( portal->nodes[1] == l ) {
240 *pp = portal->next[1];
241 portal->nodes[1] = NULL;
242 }
243 }
244
245 //============================================================================
246
PrintPortal(portal_t * p)247 void PrintPortal( portal_t *p ){
248 int i;
249 winding_t *w;
250
251 w = p->winding;
252 for ( i = 0 ; i < w->numpoints ; i++ )
253 Sys_Printf( "(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
254 , w->p[i][1], w->p[i][2] );
255 }
256
257 /*
258 ================
259 MakeHeadnodePortals
260
261 The created portals will face the global outside_node
262 ================
263 */
264 #define SIDESPACE 8
MakeHeadnodePortals(tree_t * tree)265 void MakeHeadnodePortals( tree_t *tree ){
266 vec3_t bounds[2];
267 int i, j, n;
268 portal_t *p, *portals[6];
269 plane_t bplanes[6], *pl;
270 node_t *node;
271
272 node = tree->headnode;
273
274 // pad with some space so there will never be null volume leafs
275 for ( i = 0 ; i < 3 ; i++ )
276 {
277 bounds[0][i] = tree->mins[i] - SIDESPACE;
278 bounds[1][i] = tree->maxs[i] + SIDESPACE;
279 }
280
281 tree->outside_node.planenum = PLANENUM_LEAF;
282 tree->outside_node.brushlist = NULL;
283 tree->outside_node.portals = NULL;
284 tree->outside_node.contents = 0;
285
286 for ( i = 0 ; i < 3 ; i++ )
287 for ( j = 0 ; j < 2 ; j++ )
288 {
289 n = j * 3 + i;
290
291 p = AllocPortal();
292 portals[n] = p;
293
294 pl = &bplanes[n];
295 memset( pl, 0, sizeof( *pl ) );
296 if ( j ) {
297 pl->normal[i] = -1;
298 pl->dist = -bounds[j][i];
299 }
300 else
301 {
302 pl->normal[i] = 1;
303 pl->dist = bounds[j][i];
304 }
305 p->plane = *pl;
306 p->winding = BaseWindingForPlane( pl->normal, pl->dist );
307 AddPortalToNodes( p, node, &tree->outside_node );
308 }
309
310 // clip the basewindings by all the other planes
311 for ( i = 0 ; i < 6 ; i++ )
312 {
313 for ( j = 0 ; j < 6 ; j++ )
314 {
315 if ( j == i ) {
316 continue;
317 }
318 ChopWindingInPlace( &portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON );
319 }
320 }
321 }
322
323 //===================================================
324
325
326 /*
327 ================
328 BaseWindingForNode
329 ================
330 */
331 #define BASE_WINDING_EPSILON 0.001
332 #define SPLIT_WINDING_EPSILON 0.001
333
BaseWindingForNode(node_t * node)334 winding_t *BaseWindingForNode( node_t *node ){
335 winding_t *w;
336 node_t *n;
337 plane_t *plane;
338 vec3_t normal;
339 vec_t dist;
340
341 w = BaseWindingForPlane( mapplanes[node->planenum].normal
342 , mapplanes[node->planenum].dist );
343
344 // clip by all the parents
345 for ( n = node->parent ; n && w ; )
346 {
347 plane = &mapplanes[n->planenum];
348
349 if ( n->children[0] == node ) { // take front
350 ChopWindingInPlace( &w, plane->normal, plane->dist, BASE_WINDING_EPSILON );
351 }
352 else
353 { // take back
354 VectorSubtract( vec3_origin, plane->normal, normal );
355 dist = -plane->dist;
356 ChopWindingInPlace( &w, normal, dist, BASE_WINDING_EPSILON );
357 }
358 node = n;
359 n = n->parent;
360 }
361
362 return w;
363 }
364
365 //============================================================
366
367 qboolean WindingIsTiny( winding_t *w );
368
369 /*
370 ==================
371 MakeNodePortal
372
373 create the new portal by taking the full plane winding for the cutting plane
374 and clipping it by all of parents of this node
375 ==================
376 */
MakeNodePortal(node_t * node)377 void MakeNodePortal( node_t *node ){
378 portal_t *new_portal, *p;
379 winding_t *w;
380 vec3_t normal;
381 float dist;
382 int side;
383
384 w = BaseWindingForNode( node );
385
386 // clip the portal by all the other portals in the node
387 for ( p = node->portals ; p && w; p = p->next[side] )
388 {
389 if ( p->nodes[0] == node ) {
390 side = 0;
391 VectorCopy( p->plane.normal, normal );
392 dist = p->plane.dist;
393 }
394 else if ( p->nodes[1] == node ) {
395 side = 1;
396 VectorSubtract( vec3_origin, p->plane.normal, normal );
397 dist = -p->plane.dist;
398 }
399 else{
400 Error( "CutNodePortals_r: mislinked portal" );
401 }
402
403 ChopWindingInPlace( &w, normal, dist, 0.1 );
404 }
405
406 if ( !w ) {
407 return;
408 }
409
410 if ( WindingIsTiny( w ) ) {
411 c_tinyportals++;
412 FreeWinding( w );
413 return;
414 }
415
416
417 new_portal = AllocPortal();
418 new_portal->plane = mapplanes[node->planenum];
419 new_portal->onnode = node;
420 new_portal->winding = w;
421 AddPortalToNodes( new_portal, node->children[0], node->children[1] );
422 }
423
424
425 /*
426 ==============
427 SplitNodePortals
428
429 Move or split the portals that bound node so that the node's
430 children have portals instead of node.
431 ==============
432 */
SplitNodePortals(node_t * node)433 void SplitNodePortals( node_t *node ){
434 portal_t *p, *next_portal, *new_portal;
435 node_t *f, *b, *other_node;
436 int side;
437 plane_t *plane;
438 winding_t *frontwinding, *backwinding;
439
440 plane = &mapplanes[node->planenum];
441 f = node->children[0];
442 b = node->children[1];
443
444 for ( p = node->portals ; p ; p = next_portal )
445 {
446 if ( p->nodes[0] == node ) {
447 side = 0;
448 }
449 else if ( p->nodes[1] == node ) {
450 side = 1;
451 }
452 else{
453 Error( "CutNodePortals_r: mislinked portal" );
454 }
455 next_portal = p->next[side];
456
457 other_node = p->nodes[!side];
458 RemovePortalFromNode( p, p->nodes[0] );
459 RemovePortalFromNode( p, p->nodes[1] );
460
461 //
462 // cut the portal into two portals, one on each side of the cut plane
463 //
464 ClipWindingEpsilon( p->winding, plane->normal, plane->dist,
465 SPLIT_WINDING_EPSILON, &frontwinding, &backwinding );
466
467 if ( frontwinding && WindingIsTiny( frontwinding ) ) {
468 FreeWinding( frontwinding );
469 frontwinding = NULL;
470 c_tinyportals++;
471 }
472
473 if ( backwinding && WindingIsTiny( backwinding ) ) {
474 FreeWinding( backwinding );
475 backwinding = NULL;
476 c_tinyportals++;
477 }
478
479 if ( !frontwinding && !backwinding ) { // tiny windings on both sides
480 continue;
481 }
482
483 if ( !frontwinding ) {
484 FreeWinding( backwinding );
485 if ( side == 0 ) {
486 AddPortalToNodes( p, b, other_node );
487 }
488 else{
489 AddPortalToNodes( p, other_node, b );
490 }
491 continue;
492 }
493 if ( !backwinding ) {
494 FreeWinding( frontwinding );
495 if ( side == 0 ) {
496 AddPortalToNodes( p, f, other_node );
497 }
498 else{
499 AddPortalToNodes( p, other_node, f );
500 }
501 continue;
502 }
503
504 // the winding is split
505 new_portal = AllocPortal();
506 *new_portal = *p;
507 new_portal->winding = backwinding;
508 FreeWinding( p->winding );
509 p->winding = frontwinding;
510
511 if ( side == 0 ) {
512 AddPortalToNodes( p, f, other_node );
513 AddPortalToNodes( new_portal, b, other_node );
514 }
515 else
516 {
517 AddPortalToNodes( p, other_node, f );
518 AddPortalToNodes( new_portal, other_node, b );
519 }
520 }
521
522 node->portals = NULL;
523 }
524
525
526 /*
527 ================
528 CalcNodeBounds
529 ================
530 */
CalcNodeBounds(node_t * node)531 void CalcNodeBounds( node_t *node ){
532 portal_t *p;
533 int s;
534 int i;
535
536 // calc mins/maxs for both leafs and nodes
537 ClearBounds( node->mins, node->maxs );
538 for ( p = node->portals ; p ; p = p->next[s] )
539 {
540 s = ( p->nodes[1] == node );
541 for ( i = 0 ; i < p->winding->numpoints ; i++ )
542 AddPointToBounds( p->winding->p[i], node->mins, node->maxs );
543 }
544 }
545
546
547 /*
548 ==================
549 MakeTreePortals_r
550 ==================
551 */
MakeTreePortals_r(node_t * node)552 void MakeTreePortals_r( node_t *node ){
553 int i;
554
555 CalcNodeBounds( node );
556 if ( node->mins[0] >= node->maxs[0] ) {
557 Sys_Printf( "WARNING: node without a volume\n" );
558 }
559
560 for ( i = 0 ; i < 3 ; i++ )
561 {
562 if ( node->mins[i] < -8000 || node->maxs[i] > 8000 ) {
563 Sys_Printf( "WARNING: node with unbounded volume\n" );
564 break;
565 }
566 }
567 if ( node->planenum == PLANENUM_LEAF ) {
568 return;
569 }
570
571 MakeNodePortal( node );
572 SplitNodePortals( node );
573
574 MakeTreePortals_r( node->children[0] );
575 MakeTreePortals_r( node->children[1] );
576 }
577
578 /*
579 ==================
580 MakeTreePortals
581 ==================
582 */
MakeTreePortals(tree_t * tree)583 void MakeTreePortals( tree_t *tree ){
584 MakeHeadnodePortals( tree );
585 MakeTreePortals_r( tree->headnode );
586 }
587
588 /*
589 =========================================================
590
591 FLOOD ENTITIES
592
593 =========================================================
594 */
595
596 /*
597 =============
598 FloodPortals_r
599 =============
600 */
FloodPortals_r(node_t * node,int dist)601 void FloodPortals_r( node_t *node, int dist ){
602 portal_t *p;
603 int s;
604
605 node->occupied = dist;
606
607 for ( p = node->portals ; p ; p = p->next[s] )
608 {
609 s = ( p->nodes[1] == node );
610
611 if ( p->nodes[!s]->occupied ) {
612 continue;
613 }
614
615 if ( !Portal_EntityFlood( p, s ) ) {
616 continue;
617 }
618
619 FloodPortals_r( p->nodes[!s], dist + 1 );
620 }
621 }
622
623 /*
624 =============
625 PlaceOccupant
626 =============
627 */
PlaceOccupant(node_t * headnode,vec3_t origin,entity_t * occupant)628 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant ){
629 node_t *node;
630 vec_t d;
631 plane_t *plane;
632
633 // find the leaf to start in
634 node = headnode;
635 while ( node->planenum != PLANENUM_LEAF )
636 {
637 plane = &mapplanes[node->planenum];
638 d = DotProduct( origin, plane->normal ) - plane->dist;
639 if ( d >= 0 ) {
640 node = node->children[0];
641 }
642 else{
643 node = node->children[1];
644 }
645 }
646
647 if ( node->contents == CONTENTS_SOLID ) {
648 return false;
649 }
650 node->occupant = occupant;
651
652 FloodPortals_r( node, 1 );
653
654 return true;
655 }
656
657 /*
658 =============
659 FloodEntities
660
661 Marks all nodes that can be reached by entites
662 =============
663 */
FloodEntities(tree_t * tree)664 qboolean FloodEntities( tree_t *tree ){
665 int i;
666 vec3_t origin;
667 char *cl;
668 qboolean inside;
669 node_t *headnode;
670
671 headnode = tree->headnode;
672 Sys_FPrintf( SYS_VRB, "--- FloodEntities ---\n" );
673 inside = false;
674 tree->outside_node.occupied = 0;
675
676 for ( i = 1 ; i < num_entities ; i++ )
677 {
678 GetVectorForKey( &entities[i], "origin", origin );
679 if ( VectorCompare( origin, vec3_origin ) ) {
680 continue;
681 }
682
683 cl = ValueForKey( &entities[i], "classname" );
684 origin[2] += 1; // so objects on floor are ok
685
686 // nudge playerstart around if needed so clipping hulls allways
687 // have a vlaid point
688 if ( !strcmp( cl, "info_player_start" ) ) {
689 int x, y;
690
691 for ( x = -16 ; x <= 16 ; x += 16 )
692 {
693 for ( y = -16 ; y <= 16 ; y += 16 )
694 {
695 origin[0] += x;
696 origin[1] += y;
697 if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
698 inside = true;
699 goto gotit;
700 }
701 origin[0] -= x;
702 origin[1] -= y;
703 }
704 }
705 gotit: ;
706 }
707 else
708 {
709 if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
710 inside = true;
711 }
712 }
713 }
714
715 if ( !inside ) {
716 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
717 }
718 else if ( tree->outside_node.occupied ) {
719 Sys_FPrintf( SYS_VRB, "entity reached from outside -- no filling\n" );
720 }
721
722 return (qboolean)( inside && !tree->outside_node.occupied );
723 }
724
725 /*
726 =========================================================
727
728 FLOOD AREAS
729
730 =========================================================
731 */
732
733 int c_areas;
734
735 /*
736 =============
737 FloodAreas_r
738 =============
739 */
FloodAreas_r(node_t * node)740 void FloodAreas_r( node_t *node ){
741 portal_t *p;
742 int s;
743 bspbrush_t *b;
744 entity_t *e;
745
746 if ( node->contents == CONTENTS_AREAPORTAL ) {
747 // this node is part of an area portal
748 b = node->brushlist;
749 e = &entities[b->original->entitynum];
750
751 // if the current area has allready touched this
752 // portal, we are done
753 if ( e->portalareas[0] == c_areas || e->portalareas[1] == c_areas ) {
754 return;
755 }
756
757 // note the current area as bounding the portal
758 if ( e->portalareas[1] ) {
759 Sys_Printf( "WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum );
760 return;
761 }
762 if ( e->portalareas[0] ) {
763 e->portalareas[1] = c_areas;
764 }
765 else{
766 e->portalareas[0] = c_areas;
767 }
768
769 return;
770 }
771
772 if ( node->area ) {
773 return; // allready got it
774 }
775 node->area = c_areas;
776
777 for ( p = node->portals ; p ; p = p->next[s] )
778 {
779 s = ( p->nodes[1] == node );
780 #if 0
781 if ( p->nodes[!s]->occupied ) {
782 continue;
783 }
784 #endif
785 if ( !Portal_EntityFlood( p, s ) ) {
786 continue;
787 }
788
789 FloodAreas_r( p->nodes[!s] );
790 }
791 }
792
793 /*
794 =============
795 FindAreas_r
796
797 Just decend the tree, and for each node that hasn't had an
798 area set, flood fill out from there
799 =============
800 */
FindAreas_r(node_t * node)801 void FindAreas_r( node_t *node ){
802 if ( node->planenum != PLANENUM_LEAF ) {
803 FindAreas_r( node->children[0] );
804 FindAreas_r( node->children[1] );
805 return;
806 }
807
808 if ( node->area ) {
809 return; // allready got it
810
811 }
812 if ( node->contents & CONTENTS_SOLID ) {
813 return;
814 }
815
816 if ( !node->occupied ) {
817 return; // not reachable by entities
818
819 }
820 // area portals are allways only flooded into, never
821 // out of
822 if ( node->contents == CONTENTS_AREAPORTAL ) {
823 return;
824 }
825
826 c_areas++;
827 FloodAreas_r( node );
828 }
829
830 /*
831 =============
832 SetAreaPortalAreas_r
833
834 Just decend the tree, and for each node that hasn't had an
835 area set, flood fill out from there
836 =============
837 */
SetAreaPortalAreas_r(node_t * node)838 void SetAreaPortalAreas_r( node_t *node ){
839 bspbrush_t *b;
840 entity_t *e;
841
842 if ( node->planenum != PLANENUM_LEAF ) {
843 SetAreaPortalAreas_r( node->children[0] );
844 SetAreaPortalAreas_r( node->children[1] );
845 return;
846 }
847
848 if ( node->contents == CONTENTS_AREAPORTAL ) {
849 if ( node->area ) {
850 return; // allready set
851
852 }
853 b = node->brushlist;
854 e = &entities[b->original->entitynum];
855 node->area = e->portalareas[0];
856 if ( !e->portalareas[1] ) {
857 Sys_Printf( "WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum );
858 return;
859 }
860 }
861 }
862
863 /*
864 =============
865 EmitAreaPortals
866
867 =============
868 */
EmitAreaPortals(node_t * headnode)869 void EmitAreaPortals( node_t *headnode ){
870 int i, j;
871 entity_t *e;
872 dareaportal_t *dp;
873
874 if ( c_areas > MAX_MAP_AREAS ) {
875 Error( "MAX_MAP_AREAS" );
876 }
877 numareas = c_areas + 1;
878 numareaportals = 1; // leave 0 as an error
879
880 for ( i = 1 ; i <= c_areas ; i++ )
881 {
882 dareas[i].firstareaportal = numareaportals;
883 for ( j = 0 ; j < num_entities ; j++ )
884 {
885 e = &entities[j];
886 if ( !e->areaportalnum ) {
887 continue;
888 }
889 dp = &dareaportals[numareaportals];
890 if ( e->portalareas[0] == i ) {
891 dp->portalnum = e->areaportalnum;
892 dp->otherarea = e->portalareas[1];
893 numareaportals++;
894 }
895 else if ( e->portalareas[1] == i ) {
896 dp->portalnum = e->areaportalnum;
897 dp->otherarea = e->portalareas[0];
898 numareaportals++;
899 }
900 }
901 dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
902 }
903
904 Sys_FPrintf( SYS_VRB, "%5i numareas\n", numareas );
905 Sys_FPrintf( SYS_VRB, "%5i numareaportals\n", numareaportals );
906 }
907
908 /*
909 =============
910 FloodAreas
911
912 Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
913 =============
914 */
FloodAreas(tree_t * tree)915 void FloodAreas( tree_t *tree ){
916 Sys_FPrintf( SYS_VRB, "--- FloodAreas ---\n" );
917 FindAreas_r( tree->headnode );
918 SetAreaPortalAreas_r( tree->headnode );
919 Sys_FPrintf( SYS_VRB, "%5i areas\n", c_areas );
920 }
921
922 //======================================================
923
924 int c_outside;
925 int c_inside;
926 int c_solid;
927
FillOutside_r(node_t * node)928 void FillOutside_r( node_t *node ){
929 if ( node->planenum != PLANENUM_LEAF ) {
930 FillOutside_r( node->children[0] );
931 FillOutside_r( node->children[1] );
932 return;
933 }
934
935 // anything not reachable by an entity
936 // can be filled away
937 if ( !node->occupied ) {
938 if ( node->contents != CONTENTS_SOLID ) {
939 c_outside++;
940 node->contents = CONTENTS_SOLID;
941 }
942 else{
943 c_solid++;
944 }
945 }
946 else{
947 c_inside++;
948 }
949
950 }
951
952 /*
953 =============
954 FillOutside
955
956 Fill all nodes that can't be reached by entities
957 =============
958 */
FillOutside(node_t * headnode)959 void FillOutside( node_t *headnode ){
960 c_outside = 0;
961 c_inside = 0;
962 c_solid = 0;
963 Sys_FPrintf( SYS_VRB, "--- FillOutside ---\n" );
964 FillOutside_r( headnode );
965 Sys_FPrintf( SYS_VRB, "%5i solid leafs\n", c_solid );
966 Sys_FPrintf( SYS_VRB, "%5i leafs filled\n", c_outside );
967 Sys_FPrintf( SYS_VRB, "%5i inside leafs\n", c_inside );
968 }
969
970
971 //==============================================================
972
973 /*
974 ============
975 FindPortalSide
976
977 Finds a brush side to use for texturing the given portal
978 ============
979 */
FindPortalSide(portal_t * p)980 void FindPortalSide( portal_t *p ){
981 int viscontents;
982 bspbrush_t *bb;
983 mapbrush_t *brush;
984 node_t *n;
985 int i,j;
986 int planenum;
987 side_t *side, *bestside;
988 float dot, bestdot;
989 plane_t *p1, *p2;
990
991 // decide which content change is strongest
992 // solid > lava > water, etc
993 viscontents = VisibleContents( p->nodes[0]->contents ^ p->nodes[1]->contents );
994 if ( !viscontents ) {
995 return;
996 }
997
998 planenum = p->onnode->planenum;
999 bestside = NULL;
1000 bestdot = 0;
1001
1002 for ( j = 0 ; j < 2 ; j++ )
1003 {
1004 n = p->nodes[j];
1005 p1 = &mapplanes[p->onnode->planenum];
1006 for ( bb = n->brushlist ; bb ; bb = bb->next )
1007 {
1008 brush = bb->original;
1009 if ( !( brush->contents & viscontents ) ) {
1010 continue;
1011 }
1012 for ( i = 0 ; i < brush->numsides ; i++ )
1013 {
1014 side = &brush->original_sides[i];
1015 if ( side->bevel ) {
1016 continue;
1017 }
1018 if ( side->texinfo == TEXINFO_NODE ) {
1019 continue; // non-visible
1020 }
1021 if ( ( side->planenum & ~1 ) == planenum ) { // exact match
1022 bestside = &brush->original_sides[i];
1023 goto gotit;
1024 }
1025 // see how close the match is
1026 p2 = &mapplanes[side->planenum & ~1];
1027 dot = DotProduct( p1->normal, p2->normal );
1028 if ( dot > bestdot ) {
1029 bestdot = dot;
1030 bestside = side;
1031 }
1032 }
1033 }
1034 }
1035
1036 gotit:
1037 if ( !bestside ) {
1038 Sys_FPrintf( SYS_VRB, "WARNING: side not found for portal\n" );
1039 }
1040
1041 p->sidefound = true;
1042 p->side = bestside;
1043 }
1044
1045
1046 /*
1047 ===============
1048 MarkVisibleSides_r
1049
1050 ===============
1051 */
MarkVisibleSides_r(node_t * node)1052 void MarkVisibleSides_r( node_t *node ){
1053 portal_t *p;
1054 int s;
1055
1056 if ( node->planenum != PLANENUM_LEAF ) {
1057 MarkVisibleSides_r( node->children[0] );
1058 MarkVisibleSides_r( node->children[1] );
1059 return;
1060 }
1061
1062 // empty leafs are never boundary leafs
1063 if ( !node->contents ) {
1064 return;
1065 }
1066
1067 // see if there is a visible face
1068 for ( p = node->portals ; p ; p = p->next[!s] )
1069 {
1070 s = ( p->nodes[0] == node );
1071 if ( !p->onnode ) {
1072 continue; // edge of world
1073 }
1074 if ( !p->sidefound ) {
1075 FindPortalSide( p );
1076 }
1077 if ( p->side ) {
1078 p->side->visible = true;
1079 }
1080 }
1081
1082 }
1083
1084 /*
1085 =============
1086 MarkVisibleSides
1087
1088 =============
1089 */
MarkVisibleSides(tree_t * tree,int startbrush,int endbrush)1090 void MarkVisibleSides( tree_t *tree, int startbrush, int endbrush ){
1091 int i, j;
1092 mapbrush_t *mb;
1093 int numsides;
1094
1095 Sys_FPrintf( SYS_VRB, "--- MarkVisibleSides ---\n" );
1096
1097 // clear all the visible flags
1098 for ( i = startbrush ; i < endbrush ; i++ )
1099 {
1100 mb = &mapbrushes[i];
1101
1102 numsides = mb->numsides;
1103 for ( j = 0 ; j < numsides ; j++ )
1104 mb->original_sides[j].visible = false;
1105 }
1106
1107 // set visible flags on the sides that are used by portals
1108 MarkVisibleSides_r( tree->headnode );
1109 }
1110