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