2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
21 ----------------------------------------------------------------------------------
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26 ------------------------------------------------------------------------------- */
40 /* ydnar: to fix broken portal windings */
41 extern qboolean FixWinding( winding_t *w );
54 portal_t *AllocPortal (void)
60 if (c_active_portals > c_peak_portals)
61 c_peak_portals = c_active_portals;
63 p = safe_malloc (sizeof(portal_t));
64 memset (p, 0, sizeof(portal_t));
69 void FreePortal (portal_t *p)
72 FreeWinding (p->winding);
82 returns true if the portal has non-opaque leafs on both sides
85 qboolean PortalPassable( portal_t *p )
87 /* is this to global outside leaf? */
91 /* this should never happen */
92 if( p->nodes[ 0 ]->planenum != PLANENUM_LEAF ||
93 p->nodes[ 1 ]->planenum != PLANENUM_LEAF )
94 Error( "Portal_EntityFlood: not a leaf" );
96 /* ydnar: added antiportal to supress portal generation for visibility blocking */
97 if( p->compileFlags & C_ANTIPORTAL )
100 /* both leaves on either side of the portal must be passable */
101 if( p->nodes[ 0 ]->opaque == qfalse && p->nodes[ 1 ]->opaque == qfalse )
104 /* otherwise this isn't a passable portal */
112 int c_badportals; /* ydnar */
119 void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
121 if (p->nodes[0] || p->nodes[1])
122 Error ("AddPortalToNode: allready included");
125 p->next[0] = front->portals;
129 p->next[1] = back->portals;
139 void RemovePortalFromNode (portal_t *portal, node_t *l)
143 // remove reference to the current portal
149 Error ("RemovePortalFromNode: portal not in leaf");
154 if (t->nodes[0] == l)
156 else if (t->nodes[1] == l)
159 Error ("RemovePortalFromNode: portal not bounding leaf");
162 if (portal->nodes[0] == l)
164 *pp = portal->next[0];
165 portal->nodes[0] = NULL;
167 else if (portal->nodes[1] == l)
169 *pp = portal->next[1];
170 portal->nodes[1] = NULL;
174 //============================================================================
176 void PrintPortal (portal_t *p)
182 for (i=0 ; i<w->numpoints ; i++)
183 Sys_Printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
184 , w->p[i][1], w->p[i][2]);
191 The created portals will face the global outside_node
195 void MakeHeadnodePortals (tree_t *tree)
199 portal_t *p, *portals[6];
200 plane_t bplanes[6], *pl;
203 node = tree->headnode;
205 // pad with some space so there will never be null volume leafs
206 for (i=0 ; i<3 ; i++)
208 bounds[0][i] = tree->mins[i] - SIDESPACE;
209 bounds[1][i] = tree->maxs[i] + SIDESPACE;
210 if ( bounds[0][i] >= bounds[1][i] ) {
211 Error( "Backwards tree volume" );
215 tree->outside_node.planenum = PLANENUM_LEAF;
216 tree->outside_node.brushlist = NULL;
217 tree->outside_node.portals = NULL;
218 tree->outside_node.opaque = qfalse;
220 for (i=0 ; i<3 ; i++)
221 for (j=0 ; j<2 ; j++)
229 memset (pl, 0, sizeof(*pl));
233 pl->dist = -bounds[j][i];
238 pl->dist = bounds[j][i];
241 p->winding = BaseWindingForPlane (pl->normal, pl->dist);
242 AddPortalToNodes (p, node, &tree->outside_node);
245 // clip the basewindings by all the other planes
246 for (i=0 ; i<6 ; i++)
248 for (j=0 ; j<6 ; j++)
252 ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);
257 //===================================================
265 #define BASE_WINDING_EPSILON 0.001
266 #define SPLIT_WINDING_EPSILON 0.001
268 winding_t *BaseWindingForNode (node_t *node)
276 w = BaseWindingForPlane (mapplanes[node->planenum].normal
277 , mapplanes[node->planenum].dist);
279 // clip by all the parents
280 for (n=node->parent ; n && w ; )
282 plane = &mapplanes[n->planenum];
284 if (n->children[0] == node)
286 ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);
290 VectorSubtract (vec3_origin, plane->normal, normal);
292 ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);
301 //============================================================
307 create the new portal by taking the full plane winding for the cutting plane
308 and clipping it by all of parents of this node
311 void MakeNodePortal (node_t *node)
313 portal_t *new_portal, *p;
319 w = BaseWindingForNode (node);
321 // clip the portal by all the other portals in the node
322 for (p = node->portals ; p && w; p = p->next[side])
324 if (p->nodes[0] == node)
327 VectorCopy (p->plane.normal, normal);
328 dist = p->plane.dist;
330 else if (p->nodes[1] == node)
333 VectorSubtract (vec3_origin, p->plane.normal, normal);
334 dist = -p->plane.dist;
337 Error ("CutNodePortals_r: mislinked portal");
339 ChopWindingInPlace (&w, normal, dist, CLIP_EPSILON);
348 /* ydnar: adding this here to fix degenerate windings */
350 if( FixWinding( w ) == qfalse )
358 if (WindingIsTiny (w))
365 new_portal = AllocPortal ();
366 new_portal->plane = mapplanes[node->planenum];
367 new_portal->onnode = node;
368 new_portal->winding = w;
369 new_portal->compileFlags = node->compileFlags;
370 AddPortalToNodes (new_portal, node->children[0], node->children[1]);
378 Move or split the portals that bound node so that the node's
379 children have portals instead of node.
382 void SplitNodePortals (node_t *node)
384 portal_t *p, *next_portal, *new_portal;
385 node_t *f, *b, *other_node;
388 winding_t *frontwinding, *backwinding;
390 plane = &mapplanes[node->planenum];
391 f = node->children[0];
392 b = node->children[1];
394 for (p = node->portals ; p ; p = next_portal)
396 if (p->nodes[0] == node)
398 else if (p->nodes[1] == node)
401 Error ("SplitNodePortals: mislinked portal");
402 next_portal = p->next[side];
404 other_node = p->nodes[!side];
405 RemovePortalFromNode (p, p->nodes[0]);
406 RemovePortalFromNode (p, p->nodes[1]);
409 // cut the portal into two portals, one on each side of the cut plane
411 ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
412 SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
414 if (frontwinding && WindingIsTiny(frontwinding))
417 VectorCopy(frontwinding->p[0], f->referencepoint);
419 if (!other_node->tinyportals)
420 VectorCopy(frontwinding->p[0], other_node->referencepoint);
421 other_node->tinyportals++;
423 FreeWinding (frontwinding);
428 if (backwinding && WindingIsTiny(backwinding))
431 VectorCopy(backwinding->p[0], b->referencepoint);
433 if (!other_node->tinyportals)
434 VectorCopy(backwinding->p[0], other_node->referencepoint);
435 other_node->tinyportals++;
437 FreeWinding (backwinding);
442 if (!frontwinding && !backwinding)
443 { // tiny windings on both sides
449 FreeWinding (backwinding);
451 AddPortalToNodes (p, b, other_node);
453 AddPortalToNodes (p, other_node, b);
458 FreeWinding (frontwinding);
460 AddPortalToNodes (p, f, other_node);
462 AddPortalToNodes (p, other_node, f);
466 // the winding is split
467 new_portal = AllocPortal ();
469 new_portal->winding = backwinding;
470 FreeWinding (p->winding);
471 p->winding = frontwinding;
475 AddPortalToNodes (p, f, other_node);
476 AddPortalToNodes (new_portal, b, other_node);
480 AddPortalToNodes (p, other_node, f);
481 AddPortalToNodes (new_portal, other_node, b);
485 node->portals = NULL;
494 void CalcNodeBounds (node_t *node)
500 // calc mins/maxs for both leafs and nodes
501 ClearBounds (node->mins, node->maxs);
502 for (p = node->portals ; p ; p = p->next[s])
504 s = (p->nodes[1] == node);
505 for (i=0 ; i<p->winding->numpoints ; i++)
506 AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
515 void MakeTreePortals_r (node_t *node)
519 CalcNodeBounds (node);
520 if (node->mins[0] >= node->maxs[0])
522 Sys_Printf ("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]);
529 for (i=0 ; i<3 ; i++)
531 if (node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD)
533 if(node->portals && node->portals->winding)
534 xml_Winding("WARNING: Node With Unbounded Volume", node->portals->winding->p, node->portals->winding->numpoints, qfalse);
539 if (node->planenum == PLANENUM_LEAF)
542 MakeNodePortal (node);
543 SplitNodePortals (node);
545 MakeTreePortals_r (node->children[0]);
546 MakeTreePortals_r (node->children[1]);
554 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 */
564 =========================================================
568 =========================================================
579 void FloodPortals_r( node_t *node, int dist, qboolean skybox )
586 node->skybox = skybox;
588 if( node->occupied || node->opaque )
592 node->occupied = dist;
594 for( p = node->portals; p; p = p->next[ s ] )
596 s = (p->nodes[ 1 ] == node);
597 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );
609 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant, qboolean skybox )
616 // find the leaf to start in
618 while( node->planenum != PLANENUM_LEAF )
620 plane = &mapplanes[ node->planenum ];
621 d = DotProduct( origin, plane->normal ) - plane->dist;
623 node = node->children[ 0 ];
625 node = node->children[ 1 ];
630 node->occupant = occupant;
631 node->skybox = skybox;
633 FloodPortals_r( node, 1, skybox );
642 Marks all nodes that can be reached by entites
646 qboolean FloodEntities( tree_t *tree )
649 vec3_t origin, offset, scale, angles;
650 qboolean r, inside, tripped, skybox;
656 headnode = tree->headnode;
657 Sys_FPrintf( SYS_VRB,"--- FloodEntities ---\n" );
659 tree->outside_node.occupied = 0;
663 for( i = 1; i < numEntities; i++ )
669 GetVectorForKey( e, "origin", origin );
670 if( VectorCompare( origin, vec3_origin ) )
673 /* handle skybox entities */
674 value = ValueForKey( e, "classname" );
675 if( !Q_stricmp( value, "_skybox" ) )
678 skyboxPresent = qtrue;
681 VectorScale( origin, -1.0f, offset );
684 VectorSet( scale, 64.0f, 64.0f, 64.0f );
685 value = ValueForKey( e, "_scale" );
686 if( value[ 0 ] != '\0' )
688 s = sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
691 scale[ 1 ] = scale[ 0 ];
692 scale[ 2 ] = scale[ 0 ];
696 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
697 VectorClear( angles );
698 angles[ 2 ] = FloatForKey( e, "angle" );
699 value = ValueForKey( e, "angles" );
700 if( value[ 0 ] != '\0' )
701 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
703 /* set transform matrix (thanks spog) */
704 m4x4_identity( skyboxTransform );
705 m4x4_pivoted_transform_by_vec3( skyboxTransform, offset, angles, eXYZ, scale, origin );
710 /* nudge off floor */
715 //% origin[ 2 ] += 4096;
718 r = PlaceOccupant( headnode, origin, e, skybox );
721 if( (!r || tree->outside_node.occupied) && !tripped )
723 xml_Select( "Entity leaked", e->mapEntityNum, 0, qfalse );
728 Sys_FPrintf( SYS_VRB, "%9d flooded leafs\n", c_floodedleafs );
731 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
732 else if( tree->outside_node.occupied )
733 Sys_FPrintf( SYS_VRB, "entity reached from outside -- no filling\n" );
735 return (qboolean) (inside && !tree->outside_node.occupied);
739 =========================================================
743 =========================================================
752 floods through leaf portals to tag leafs with an area
755 void FloodAreas_r( node_t *node )
762 if( node->areaportal )
764 if( node->area == -1 )
765 node->area = c_areas;
767 /* this node is part of an area portal brush */
768 b = node->brushlist->original;
770 /* if the current area has already touched this portal, we are done */
771 if( b->portalareas[ 0 ] == c_areas || b->portalareas[ 1 ] == c_areas )
774 // note the current area as bounding the portal
775 if( b->portalareas[ 1 ] != -1 )
777 Sys_Printf( "WARNING: areaportal brush %i touches > 2 areas\n", b->brushNum );
780 if( b->portalareas[ 0 ] != -1 )
781 b->portalareas[ 1 ] = c_areas;
783 b->portalareas[ 0 ] = c_areas;
788 if( node->area != -1 )
790 if( node->cluster == -1 )
793 node->area = c_areas;
795 /* ydnar: skybox nodes set the skybox area */
797 skyboxArea = c_areas;
799 for( p = node->portals; p; p = p->next[ s ] )
801 s = (p->nodes[1] == node);
803 /* ydnar: allow areaportal portals to block area flow */
804 if( p->compileFlags & C_AREAPORTAL )
807 if( !PortalPassable( p ) )
810 FloodAreas_r( p->nodes[ !s ] );
818 Just decend the tree, and for each node that hasn't had an
819 area set, flood fill out from there
822 void FindAreas_r( node_t *node )
824 if( node->planenum != PLANENUM_LEAF )
826 FindAreas_r( node->children[ 0 ] );
827 FindAreas_r( node->children[ 1 ] );
831 if( node->opaque || node->areaportal || node->area != -1 )
834 FloodAreas_r( node );
843 void CheckAreas_r (node_t *node)
847 if (node->planenum != PLANENUM_LEAF)
849 CheckAreas_r (node->children[0]);
850 CheckAreas_r (node->children[1]);
857 if (node->cluster != -1)
858 if (node->area == -1)
859 Sys_Printf("WARNING: cluster %d has area set to -1\n", node->cluster);
860 if (node->areaportal)
862 b = node->brushlist->original;
864 // check if the areaportal touches two areas
865 if (b->portalareas[0] == -1 || b->portalareas[1] == -1)
866 Sys_Printf ("WARNING: areaportal brush %i doesn't touch two areas\n", b->brushNum);
873 FloodSkyboxArea_r() - ydnar
874 sets all nodes with the skybox area to skybox
877 void FloodSkyboxArea_r( node_t *node )
882 if( node->planenum != PLANENUM_LEAF )
884 FloodSkyboxArea_r( node->children[ 0 ] );
885 FloodSkyboxArea_r( node->children[ 1 ] );
889 if( node->opaque || node->area != skyboxArea )
892 node->skybox = qtrue;
899 mark each leaf with an area, bounded by C_AREAPORTAL
902 void FloodAreas( tree_t *tree )
904 Sys_FPrintf( SYS_VRB,"--- FloodAreas ---\n" );
905 FindAreas_r( tree->headnode );
907 /* ydnar: flood all skybox nodes */
908 FloodSkyboxArea_r( tree->headnode );
910 /* check for areaportal brushes that don't touch two areas */
911 /* ydnar: fix this rather than just silence the warnings */
912 //% CheckAreas_r( tree->headnode );
914 Sys_FPrintf( SYS_VRB, "%9d areas\n", c_areas );
919 //======================================================
925 void FillOutside_r (node_t *node)
927 if (node->planenum != PLANENUM_LEAF)
929 FillOutside_r (node->children[0]);
930 FillOutside_r (node->children[1]);
934 // anything not reachable by an entity
935 // can be filled away
936 if (!node->occupied) {
937 if ( !node->opaque ) {
939 node->opaque = qtrue;
953 Fill all nodes that can't be reached by entities
956 void FillOutside (node_t *headnode)
961 Sys_FPrintf( SYS_VRB,"--- FillOutside ---\n" );
962 FillOutside_r( headnode );
963 Sys_FPrintf( SYS_VRB,"%9d solid leafs\n", c_solid );
964 Sys_Printf( "%9d leafs filled\n", c_outside );
965 Sys_FPrintf( SYS_VRB, "%9d inside leafs\n", c_inside );
969 //==============================================================