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