Using Sys_FPrintf with SYS_WRN and SYS_ERR
[xonotic/netradiant.git] / tools / quake3 / q3map2 / portals.c
1 /* -------------------------------------------------------------------------------
2
3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
4    For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6    This file is part of GtkRadiant.
7
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.
12
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.
17
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
21
22    ----------------------------------------------------------------------------------
23
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."
26
27    ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define PORTALS_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 /* ydnar: to fix broken portal windings */
42 extern qboolean FixWinding( winding_t *w );
43
44
45 int c_active_portals;
46 int c_peak_portals;
47 int c_boundary;
48 int c_boundary_sides;
49
50 /*
51    ===========
52    AllocPortal
53    ===========
54  */
55 portal_t *AllocPortal( void ){
56         portal_t    *p;
57
58         if ( numthreads == 1 ) {
59                 c_active_portals++;
60         }
61         if ( c_active_portals > c_peak_portals ) {
62                 c_peak_portals = c_active_portals;
63         }
64
65         p = safe_malloc( sizeof( portal_t ) );
66         memset( p, 0, sizeof( portal_t ) );
67
68         return p;
69 }
70
71 void FreePortal( portal_t *p ){
72         if ( p->winding ) {
73                 FreeWinding( p->winding );
74         }
75         if ( numthreads == 1 ) {
76                 c_active_portals--;
77         }
78         free( p );
79 }
80
81
82
83 /*
84    PortalPassable
85    returns true if the portal has non-opaque leafs on both sides
86  */
87
88 qboolean PortalPassable( portal_t *p ){
89         /* is this to global outside leaf? */
90         if ( !p->onnode ) {
91                 return qfalse;
92         }
93
94         /* this should never happen */
95         if ( p->nodes[ 0 ]->planenum != PLANENUM_LEAF ||
96                  p->nodes[ 1 ]->planenum != PLANENUM_LEAF ) {
97                 Error( "Portal_EntityFlood: not a leaf" );
98         }
99
100         /* ydnar: added antiportal to supress portal generation for visibility blocking */
101         if ( p->compileFlags & C_ANTIPORTAL ) {
102                 return qfalse;
103         }
104
105         /* both leaves on either side of the portal must be passable */
106         if ( p->nodes[ 0 ]->opaque == qfalse && p->nodes[ 1 ]->opaque == qfalse ) {
107                 return qtrue;
108         }
109
110         /* otherwise this isn't a passable portal */
111         return qfalse;
112 }
113
114
115
116
117 int c_tinyportals;
118 int c_badportals;       /* ydnar */
119
120 /*
121    =============
122    AddPortalToNodes
123    =============
124  */
125 void AddPortalToNodes( portal_t *p, node_t *front, node_t *back ){
126         if ( p->nodes[0] || p->nodes[1] ) {
127                 Error( "AddPortalToNode: allready included" );
128         }
129
130         p->nodes[0] = front;
131         p->next[0] = front->portals;
132         front->portals = p;
133
134         p->nodes[1] = back;
135         p->next[1] = back->portals;
136         back->portals = p;
137 }
138
139
140 /*
141    =============
142    RemovePortalFromNode
143    =============
144  */
145 void RemovePortalFromNode( portal_t *portal, node_t *l ){
146         portal_t    **pp, *t;
147
148 // remove reference to the current portal
149         pp = &l->portals;
150         while ( 1 )
151         {
152                 t = *pp;
153                 if ( !t ) {
154                         Error( "RemovePortalFromNode: portal not in leaf" );
155                 }
156
157                 if ( t == portal ) {
158                         break;
159                 }
160
161                 if ( t->nodes[0] == l ) {
162                         pp = &t->next[0];
163                 }
164                 else if ( t->nodes[1] == l ) {
165                         pp = &t->next[1];
166                 }
167                 else{
168                         Error( "RemovePortalFromNode: portal not bounding leaf" );
169                 }
170         }
171
172         if ( portal->nodes[0] == l ) {
173                 *pp = portal->next[0];
174                 portal->nodes[0] = NULL;
175         }
176         else if ( portal->nodes[1] == l ) {
177                 *pp = portal->next[1];
178                 portal->nodes[1] = NULL;
179         }
180 }
181
182 //============================================================================
183
184 void PrintPortal( portal_t *p ){
185         int i;
186         winding_t   *w;
187
188         w = p->winding;
189         for ( i = 0 ; i < w->numpoints ; i++ )
190                 Sys_Printf( "(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
191                                         , w->p[i][1], w->p[i][2] );
192 }
193
194 /*
195    ================
196    MakeHeadnodePortals
197
198    The created portals will face the global outside_node
199    ================
200  */
201 #define SIDESPACE   8
202 void MakeHeadnodePortals( tree_t *tree ){
203         vec3_t bounds[2];
204         int i, j, n;
205         portal_t    *p, *portals[6];
206         plane_t bplanes[6], *pl;
207         node_t *node;
208
209         node = tree->headnode;
210
211 // pad with some space so there will never be null volume leafs
212         for ( i = 0 ; i < 3 ; i++ )
213         {
214                 bounds[0][i] = tree->mins[i] - SIDESPACE;
215                 bounds[1][i] = tree->maxs[i] + SIDESPACE;
216                 if ( bounds[0][i] >= bounds[1][i] ) {
217                         Error( "Backwards tree volume" );
218                 }
219         }
220
221         tree->outside_node.planenum = PLANENUM_LEAF;
222         tree->outside_node.brushlist = NULL;
223         tree->outside_node.portals = NULL;
224         tree->outside_node.opaque = qfalse;
225
226         for ( i = 0 ; i < 3 ; i++ )
227                 for ( j = 0 ; j < 2 ; j++ )
228                 {
229                         n = j * 3 + i;
230
231                         p = AllocPortal();
232                         portals[n] = p;
233
234                         pl = &bplanes[n];
235                         memset( pl, 0, sizeof( *pl ) );
236                         if ( j ) {
237                                 pl->normal[i] = -1;
238                                 pl->dist = -bounds[j][i];
239                         }
240                         else
241                         {
242                                 pl->normal[i] = 1;
243                                 pl->dist = bounds[j][i];
244                         }
245                         p->plane = *pl;
246                         p->winding = BaseWindingForPlane( pl->normal, pl->dist );
247                         AddPortalToNodes( p, node, &tree->outside_node );
248                 }
249
250 // clip the basewindings by all the other planes
251         for ( i = 0 ; i < 6 ; i++ )
252         {
253                 for ( j = 0 ; j < 6 ; j++ )
254                 {
255                         if ( j == i ) {
256                                 continue;
257                         }
258                         ChopWindingInPlace( &portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON );
259                 }
260         }
261 }
262
263 //===================================================
264
265
266 /*
267    ================
268    BaseWindingForNode
269    ================
270  */
271 #define BASE_WINDING_EPSILON    0.001
272 #define SPLIT_WINDING_EPSILON   0.001
273
274 winding_t   *BaseWindingForNode( node_t *node ){
275         winding_t   *w;
276         node_t      *n;
277         plane_t     *plane;
278         vec3_t normal;
279         vec_t dist;
280
281         w = BaseWindingForPlane( mapplanes[node->planenum].normal
282                                                          , mapplanes[node->planenum].dist );
283
284         // clip by all the parents
285         for ( n = node->parent ; n && w ; )
286         {
287                 plane = &mapplanes[n->planenum];
288
289                 if ( n->children[0] == node ) { // take front
290                         ChopWindingInPlace( &w, plane->normal, plane->dist, BASE_WINDING_EPSILON );
291                 }
292                 else
293                 {   // take back
294                         VectorSubtract( vec3_origin, plane->normal, normal );
295                         dist = -plane->dist;
296                         ChopWindingInPlace( &w, normal, dist, BASE_WINDING_EPSILON );
297                 }
298                 node = n;
299                 n = n->parent;
300         }
301
302         return w;
303 }
304
305 //============================================================
306
307 /*
308    ==================
309    MakeNodePortal
310
311    create the new portal by taking the full plane winding for the cutting plane
312    and clipping it by all of parents of this node
313    ==================
314  */
315 void MakeNodePortal( node_t *node ){
316         portal_t    *new_portal, *p;
317         winding_t   *w;
318         vec3_t normal;
319         float dist;
320         int side;
321
322         w = BaseWindingForNode( node );
323
324         // clip the portal by all the other portals in the node
325         for ( p = node->portals ; p && w; p = p->next[side] )
326         {
327                 if ( p->nodes[0] == node ) {
328                         side = 0;
329                         VectorCopy( p->plane.normal, normal );
330                         dist = p->plane.dist;
331                 }
332                 else if ( p->nodes[1] == node ) {
333                         side = 1;
334                         VectorSubtract( vec3_origin, p->plane.normal, normal );
335                         dist = -p->plane.dist;
336                 }
337                 else{
338                         Error( "CutNodePortals_r: mislinked portal" );
339                 }
340
341                 ChopWindingInPlace( &w, normal, dist, CLIP_EPSILON );
342         }
343
344         if ( !w ) {
345                 return;
346         }
347
348
349         /* ydnar: adding this here to fix degenerate windings */
350         #if 0
351         if ( FixWinding( w ) == qfalse ) {
352                 c_badportals++;
353                 FreeWinding( w );
354                 return;
355         }
356         #endif
357
358         if ( WindingIsTiny( w ) ) {
359                 c_tinyportals++;
360                 FreeWinding( w );
361                 return;
362         }
363
364         new_portal = AllocPortal();
365         new_portal->plane = mapplanes[node->planenum];
366         new_portal->onnode = node;
367         new_portal->winding = w;
368         new_portal->compileFlags = node->compileFlags;
369         AddPortalToNodes( new_portal, node->children[0], node->children[1] );
370 }
371
372
373 /*
374    ==============
375    SplitNodePortals
376
377    Move or split the portals that bound node so that the node's
378    children have portals instead of node.
379    ==============
380  */
381 void SplitNodePortals( node_t *node ){
382         portal_t    *p, *next_portal, *new_portal;
383         node_t      *f, *b, *other_node;
384         int side;
385         plane_t     *plane;
386         winding_t   *frontwinding, *backwinding;
387
388         plane = &mapplanes[node->planenum];
389         f = node->children[0];
390         b = node->children[1];
391
392         for ( p = node->portals ; p ; p = next_portal )
393         {
394                 if ( p->nodes[0] == node ) {
395                         side = 0;
396                 }
397                 else if ( p->nodes[1] == node ) {
398                         side = 1;
399                 }
400                 else{
401                         Error( "SplitNodePortals: mislinked portal" );
402                 }
403                 next_portal = p->next[side];
404
405                 other_node = p->nodes[!side];
406                 RemovePortalFromNode( p, p->nodes[0] );
407                 RemovePortalFromNode( p, p->nodes[1] );
408
409 //
410 // cut the portal into two portals, one on each side of the cut plane
411 //
412                 ClipWindingEpsilon( p->winding, plane->normal, plane->dist,
413                                                         SPLIT_WINDING_EPSILON, &frontwinding, &backwinding ); /* not strict, we want to always keep one of them even if coplanar */
414
415                 if ( frontwinding && WindingIsTiny( frontwinding ) ) {
416                         if ( !f->tinyportals ) {
417                                 VectorCopy( frontwinding->p[0], f->referencepoint );
418                         }
419                         f->tinyportals++;
420                         if ( !other_node->tinyportals ) {
421                                 VectorCopy( frontwinding->p[0], other_node->referencepoint );
422                         }
423                         other_node->tinyportals++;
424
425                         FreeWinding( frontwinding );
426                         frontwinding = NULL;
427                         c_tinyportals++;
428                 }
429
430                 if ( backwinding && WindingIsTiny( backwinding ) ) {
431                         if ( !b->tinyportals ) {
432                                 VectorCopy( backwinding->p[0], b->referencepoint );
433                         }
434                         b->tinyportals++;
435                         if ( !other_node->tinyportals ) {
436                                 VectorCopy( backwinding->p[0], other_node->referencepoint );
437                         }
438                         other_node->tinyportals++;
439
440                         FreeWinding( backwinding );
441                         backwinding = NULL;
442                         c_tinyportals++;
443                 }
444
445                 if ( !frontwinding && !backwinding ) { // tiny windings on both sides
446                         continue;
447                 }
448
449                 if ( !frontwinding ) {
450                         FreeWinding( backwinding );
451                         if ( side == 0 ) {
452                                 AddPortalToNodes( p, b, other_node );
453                         }
454                         else{
455                                 AddPortalToNodes( p, other_node, b );
456                         }
457                         continue;
458                 }
459                 if ( !backwinding ) {
460                         FreeWinding( frontwinding );
461                         if ( side == 0 ) {
462                                 AddPortalToNodes( p, f, other_node );
463                         }
464                         else{
465                                 AddPortalToNodes( p, other_node, f );
466                         }
467                         continue;
468                 }
469
470                 // the winding is split
471                 new_portal = AllocPortal();
472                 *new_portal = *p;
473                 new_portal->winding = backwinding;
474                 FreeWinding( p->winding );
475                 p->winding = frontwinding;
476
477                 if ( side == 0 ) {
478                         AddPortalToNodes( p, f, other_node );
479                         AddPortalToNodes( new_portal, b, other_node );
480                 }
481                 else
482                 {
483                         AddPortalToNodes( p, other_node, f );
484                         AddPortalToNodes( new_portal, other_node, b );
485                 }
486         }
487
488         node->portals = NULL;
489 }
490
491
492 /*
493    ================
494    CalcNodeBounds
495    ================
496  */
497 void CalcNodeBounds( node_t *node ){
498         portal_t    *p;
499         int s;
500         int i;
501
502         // calc mins/maxs for both leafs and nodes
503         ClearBounds( node->mins, node->maxs );
504         for ( p = node->portals ; p ; p = p->next[s] )
505         {
506                 s = ( p->nodes[1] == node );
507                 for ( i = 0 ; i < p->winding->numpoints ; i++ )
508                         AddPointToBounds( p->winding->p[i], node->mins, node->maxs );
509         }
510 }
511
512 /*
513    ==================
514    MakeTreePortals_r
515    ==================
516  */
517 void MakeTreePortals_r( node_t *node ){
518         int i;
519
520         CalcNodeBounds( node );
521         if ( node->mins[0] >= node->maxs[0] ) {
522                 Sys_FPrintf( SYS_WRN, "WARNING: node without a volume\n" );
523                 Sys_Printf( "node has %d tiny portals\n", node->tinyportals );
524                 Sys_Printf( "node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0],
525                                         node->referencepoint[1],
526                                         node->referencepoint[2] );
527         }
528
529         for ( i = 0 ; i < 3 ; i++ )
530         {
531                 if ( node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD ) {
532                         if ( node->portals && node->portals->winding ) {
533                                 xml_Winding( "WARNING: Node With Unbounded Volume", node->portals->winding->p, node->portals->winding->numpoints, qfalse );
534                         }
535
536                         break;
537                 }
538         }
539         if ( node->planenum == PLANENUM_LEAF ) {
540                 return;
541         }
542
543         MakeNodePortal( node );
544         SplitNodePortals( node );
545
546         MakeTreePortals_r( node->children[0] );
547         MakeTreePortals_r( node->children[1] );
548 }
549
550 /*
551    ==================
552    MakeTreePortals
553    ==================
554  */
555 void MakeTreePortals( tree_t *tree ){
556         Sys_FPrintf( SYS_VRB, "--- MakeTreePortals ---\n" );
557         MakeHeadnodePortals( tree );
558         MakeTreePortals_r( tree->headnode );
559         Sys_FPrintf( SYS_VRB, "%9d tiny portals\n", c_tinyportals );
560         Sys_FPrintf( SYS_VRB, "%9d bad portals\n", c_badportals );  /* ydnar */
561 }
562
563 /*
564    =========================================================
565
566    FLOOD ENTITIES
567
568    =========================================================
569  */
570
571 int c_floodedleafs;
572
573 /*
574    =============
575    FloodPortals_r
576    =============
577  */
578
579 void FloodPortals_r( node_t *node, int dist, qboolean skybox ){
580         int s;
581         portal_t    *p;
582
583
584         if ( skybox ) {
585                 node->skybox = skybox;
586         }
587
588         if ( node->opaque ) {
589                 return;
590         }
591
592         if ( node->occupied ) {
593                 if ( node->occupied > dist ) {
594                         /* reduce distance! */
595                         /* for better leak line */
596                         /* note: node->occupied will also be true for all further nodes, then */
597                         node->occupied = dist;
598                         for ( p = node->portals; p; p = p->next[ s ] )
599                         {
600                                 s = ( p->nodes[ 1 ] == node );
601                                 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );
602                         }
603                 }
604                 return;
605         }
606
607         c_floodedleafs++;
608         node->occupied = dist;
609
610         for ( p = node->portals; p; p = p->next[ s ] )
611         {
612                 s = ( p->nodes[ 1 ] == node );
613                 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );
614         }
615 }
616
617
618
619 /*
620    =============
621    PlaceOccupant
622    =============
623  */
624
625 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant, qboolean skybox ){
626         vec_t d;
627         node_t  *node;
628         plane_t *plane;
629
630
631         // find the leaf to start in
632         node = headnode;
633         while ( node->planenum != PLANENUM_LEAF )
634         {
635                 plane = &mapplanes[ node->planenum ];
636                 d = DotProduct( origin, plane->normal ) - plane->dist;
637                 if ( d >= 0 ) {
638                         node = node->children[ 0 ];
639                 }
640                 else{
641                         node = node->children[ 1 ];
642                 }
643         }
644
645         if ( node->opaque ) {
646                 return qfalse;
647         }
648         node->occupant = occupant;
649         node->skybox = skybox;
650
651         FloodPortals_r( node, 1, skybox );
652
653         return qtrue;
654 }
655
656 /*
657    =============
658    FloodEntities
659
660    Marks all nodes that can be reached by entites
661    =============
662  */
663
664 int FloodEntities( tree_t *tree ){
665         int i, s;
666         vec3_t origin, offset, scale, angles;
667         qboolean r, inside, skybox;
668         node_t      *headnode;
669         entity_t    *e, *tripped;
670         const char  *value;
671         int tripcount;
672
673
674         headnode = tree->headnode;
675         Sys_FPrintf( SYS_VRB,"--- FloodEntities ---\n" );
676         inside = qfalse;
677         tree->outside_node.occupied = 0;
678
679         tripped = qfalse;
680         c_floodedleafs = 0;
681         for ( i = 1; i < numEntities; i++ )
682         {
683                 /* get entity */
684                 e = &entities[ i ];
685
686                 /* get origin */
687                 GetVectorForKey( e, "origin", origin );
688
689                 /* as a special case, allow origin-less entities */
690                 if ( VectorCompare( origin, vec3_origin ) ) {
691                         continue;
692                 }
693
694                 /* also allow bmodel entities outside, as they could be on a moving path that will go into the map */
695                 if ( e->brushes != NULL || e->patches != NULL ) {
696                         continue;
697                 }
698
699                 /* handle skybox entities */
700                 value = ValueForKey( e, "classname" );
701                 if ( !Q_stricmp( value, "_skybox" ) ) {
702                         skybox = qtrue;
703                         skyboxPresent = qtrue;
704
705                         /* invert origin */
706                         VectorScale( origin, -1.0f, offset );
707
708                         /* get scale */
709                         VectorSet( scale, 64.0f, 64.0f, 64.0f );
710                         value = ValueForKey( e, "_scale" );
711                         if ( value[ 0 ] != '\0' ) {
712                                 s = sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
713                                 if ( s == 1 ) {
714                                         scale[ 1 ] = scale[ 0 ];
715                                         scale[ 2 ] = scale[ 0 ];
716                                 }
717                         }
718
719                         /* get "angle" (yaw) or "angles" (pitch yaw roll) */
720                         VectorClear( angles );
721                         angles[ 2 ] = FloatForKey( e, "angle" );
722                         value = ValueForKey( e, "angles" );
723                         if ( value[ 0 ] != '\0' ) {
724                                 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
725                         }
726
727                         /* set transform matrix (thanks spog) */
728                         m4x4_identity( skyboxTransform );
729                         m4x4_pivoted_transform_by_vec3( skyboxTransform, offset, angles, eXYZ, scale, origin );
730                 }
731                 else{
732                         skybox = qfalse;
733                 }
734
735                 /* nudge off floor */
736                 origin[ 2 ] += 1;
737
738                 /* debugging code */
739                 //%     if( i == 1 )
740                 //%             origin[ 2 ] += 4096;
741
742                 /* find leaf */
743                 r = PlaceOccupant( headnode, origin, e, skybox );
744                 if ( r ) {
745                         inside = qtrue;
746                 }
747                 if ( !r ) {
748                         Sys_Printf( "Entity %i, Brush %i: Entity in solid\n", e->mapEntityNum, 0 );
749                 }
750                 else if ( tree->outside_node.occupied ) {
751                         if ( !tripped || tree->outside_node.occupied < tripcount ) {
752                                 tripped = e;
753                                 tripcount = tree->outside_node.occupied;
754                         }
755                 }
756         }
757
758         if ( tripped ) {
759                 xml_Select( "Entity leaked", e->mapEntityNum, 0, qfalse );
760         }
761
762         Sys_FPrintf( SYS_VRB, "%9d flooded leafs\n", c_floodedleafs );
763
764         if ( !inside ) {
765                 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
766                 return FLOODENTITIES_EMPTY;
767         }
768         if ( tree->outside_node.occupied ) {
769                 Sys_FPrintf( SYS_VRB, "entity reached from outside -- leak detected\n" );
770                 return FLOODENTITIES_LEAKED;
771         }
772
773         return FLOODENTITIES_GOOD;
774 }
775
776 /*
777    =========================================================
778
779    FLOOD AREAS
780
781    =========================================================
782  */
783
784 int c_areas;
785
786
787
788 /*
789    FloodAreas_r()
790    floods through leaf portals to tag leafs with an area
791  */
792
793 void FloodAreas_r( node_t *node ){
794         int s;
795         portal_t    *p;
796         brush_t     *b;
797
798
799         if ( node->areaportal ) {
800                 if ( node->area == -1 ) {
801                         node->area = c_areas;
802                 }
803
804                 /* this node is part of an area portal brush */
805                 b = node->brushlist->original;
806
807                 /* if the current area has already touched this portal, we are done */
808                 if ( b->portalareas[ 0 ] == c_areas || b->portalareas[ 1 ] == c_areas ) {
809                         return;
810                 }
811
812                 // note the current area as bounding the portal
813                 if ( b->portalareas[ 1 ] != -1 ) {
814                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal brush %i touches > 2 areas\n", b->brushNum );
815                         return;
816                 }
817                 if ( b->portalareas[ 0 ] != -1 ) {
818                         b->portalareas[ 1 ] = c_areas;
819                 }
820                 else{
821                         b->portalareas[ 0 ] = c_areas;
822                 }
823
824                 return;
825         }
826
827         if ( node->area != -1 ) {
828                 return;
829         }
830         if ( node->cluster == -1 ) {
831                 return;
832         }
833
834         node->area = c_areas;
835
836         /* ydnar: skybox nodes set the skybox area */
837         if ( node->skybox ) {
838                 skyboxArea = c_areas;
839         }
840
841         for ( p = node->portals; p; p = p->next[ s ] )
842         {
843                 s = ( p->nodes[1] == node );
844
845                 /* ydnar: allow areaportal portals to block area flow */
846                 if ( p->compileFlags & C_AREAPORTAL ) {
847                         continue;
848                 }
849
850                 if ( !PortalPassable( p ) ) {
851                         continue;
852                 }
853
854                 FloodAreas_r( p->nodes[ !s ] );
855         }
856 }
857
858 /*
859    =============
860    FindAreas_r
861
862    Just decend the tree, and for each node that hasn't had an
863    area set, flood fill out from there
864    =============
865  */
866 void FindAreas_r( node_t *node ){
867         if ( node->planenum != PLANENUM_LEAF ) {
868                 FindAreas_r( node->children[ 0 ] );
869                 FindAreas_r( node->children[ 1 ] );
870                 return;
871         }
872
873         if ( node->opaque || node->areaportal || node->area != -1 ) {
874                 return;
875         }
876
877         FloodAreas_r( node );
878         c_areas++;
879 }
880
881 /*
882    =============
883    CheckAreas_r
884    =============
885  */
886 void CheckAreas_r( node_t *node ){
887         brush_t *b;
888
889         if ( node->planenum != PLANENUM_LEAF ) {
890                 CheckAreas_r( node->children[0] );
891                 CheckAreas_r( node->children[1] );
892                 return;
893         }
894
895         if ( node->opaque ) {
896                 return;
897         }
898
899         if ( node->cluster != -1 ) {
900                 if ( node->area == -1 ) {
901                         Sys_FPrintf( SYS_WRN, "WARNING: cluster %d has area set to -1\n", node->cluster );
902                 }
903         }
904         if ( node->areaportal ) {
905                 b = node->brushlist->original;
906
907                 // check if the areaportal touches two areas
908                 if ( b->portalareas[0] == -1 || b->portalareas[1] == -1 ) {
909                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal brush %i doesn't touch two areas\n", b->brushNum );
910                 }
911         }
912 }
913
914
915
916 /*
917    FloodSkyboxArea_r() - ydnar
918    sets all nodes with the skybox area to skybox
919  */
920
921 void FloodSkyboxArea_r( node_t *node ){
922         if ( skyboxArea < 0 ) {
923                 return;
924         }
925
926         if ( node->planenum != PLANENUM_LEAF ) {
927                 FloodSkyboxArea_r( node->children[ 0 ] );
928                 FloodSkyboxArea_r( node->children[ 1 ] );
929                 return;
930         }
931
932         if ( node->opaque || node->area != skyboxArea ) {
933                 return;
934         }
935
936         node->skybox = qtrue;
937 }
938
939
940
941 /*
942    FloodAreas()
943    mark each leaf with an area, bounded by C_AREAPORTAL
944  */
945
946 void FloodAreas( tree_t *tree ){
947         Sys_FPrintf( SYS_VRB,"--- FloodAreas ---\n" );
948         FindAreas_r( tree->headnode );
949
950         /* ydnar: flood all skybox nodes */
951         FloodSkyboxArea_r( tree->headnode );
952
953         /* check for areaportal brushes that don't touch two areas */
954         /* ydnar: fix this rather than just silence the warnings */
955         //%     CheckAreas_r( tree->headnode );
956
957         Sys_FPrintf( SYS_VRB, "%9d areas\n", c_areas );
958 }
959
960
961
962 //======================================================
963
964 int c_outside;
965 int c_inside;
966 int c_solid;
967
968 void FillOutside_r( node_t *node ){
969         if ( node->planenum != PLANENUM_LEAF ) {
970                 FillOutside_r( node->children[0] );
971                 FillOutside_r( node->children[1] );
972                 return;
973         }
974
975         // anything not reachable by an entity
976         // can be filled away
977         if ( !node->occupied ) {
978                 if ( !node->opaque ) {
979                         c_outside++;
980                         node->opaque = qtrue;
981                 }
982                 else {
983                         c_solid++;
984                 }
985         }
986         else {
987                 c_inside++;
988         }
989
990 }
991
992 /*
993    =============
994    FillOutside
995
996    Fill all nodes that can't be reached by entities
997    =============
998  */
999 void FillOutside( node_t *headnode ){
1000         c_outside = 0;
1001         c_inside = 0;
1002         c_solid = 0;
1003         Sys_FPrintf( SYS_VRB,"--- FillOutside ---\n" );
1004         FillOutside_r( headnode );
1005         Sys_FPrintf( SYS_VRB,"%9d solid leafs\n", c_solid );
1006         Sys_Printf( "%9d leafs filled\n", c_outside );
1007         Sys_FPrintf( SYS_VRB, "%9d inside leafs\n", c_inside );
1008 }
1009
1010
1011 //==============================================================