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
35 portal_t *AllocPortal( void ){
38 if ( numthreads == 1 ) {
41 if ( c_active_portals > c_peak_portals ) {
42 c_peak_portals = c_active_portals;
45 p = malloc( sizeof( portal_t ) );
46 memset( p, 0, sizeof( portal_t ) );
51 void FreePortal( portal_t *p ){
53 FreeWinding( p->winding );
55 if ( numthreads == 1 ) {
61 //==============================================================
67 Returns the single content bit of the
68 strongest visible content present
71 int VisibleContents( int contents ){
74 for ( i = 1 ; i <= LAST_VISIBLE_CONTENTS ; i <<= 1 )
88 int ClusterContents( node_t *node ){
91 if ( node->planenum == PLANENUM_LEAF ) {
92 return node->contents;
95 c1 = ClusterContents( node->children[0] );
96 c2 = ClusterContents( node->children[1] );
99 // a cluster may include some solid detail areas, but
100 // still be seen into
101 if ( !( c1 & CONTENTS_SOLID ) || !( c2 & CONTENTS_SOLID ) ) {
102 c &= ~CONTENTS_SOLID;
111 Returns true if the portal is empty or translucent, allowing
112 the PVS calculation to see through it.
113 The nodes on either side of the portal may actually be clusters,
114 not leafs, so all contents should be ored together
117 qboolean Portal_VisFlood( portal_t *p ){
121 return false; // to global outsideleaf
124 c1 = ClusterContents( p->nodes[0] );
125 c2 = ClusterContents( p->nodes[1] );
127 if ( !VisibleContents( c1 ^ c2 ) ) {
131 if ( c1 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
134 if ( c2 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
138 if ( ( c1 | c2 ) & CONTENTS_SOLID ) {
139 return false; // can't see through solid
142 if ( !( c1 ^ c2 ) ) {
143 return true; // identical on both sides
146 if ( !VisibleContents( c1 ^ c2 ) ) {
157 The entity flood determines which areas are
158 "outside" on the map, which are then filled in.
159 Flowing from side s to side !s
162 qboolean Portal_EntityFlood( portal_t *p, int s ){
163 if ( p->nodes[0]->planenum != PLANENUM_LEAF
164 || p->nodes[1]->planenum != PLANENUM_LEAF ) {
165 Error( "Portal_EntityFlood: not a leaf" );
168 // can never cross to a solid
169 if ( ( p->nodes[0]->contents & CONTENTS_SOLID )
170 || ( p->nodes[1]->contents & CONTENTS_SOLID ) ) {
174 // can flood through everything else
179 //=============================================================================
188 void AddPortalToNodes( portal_t *p, node_t *front, node_t *back ){
189 if ( p->nodes[0] || p->nodes[1] ) {
190 Error( "AddPortalToNode: allready included" );
194 p->next[0] = front->portals;
198 p->next[1] = back->portals;
208 void RemovePortalFromNode( portal_t *portal, node_t *l ){
211 // remove reference to the current portal
217 Error( "RemovePortalFromNode: portal not in leaf" );
224 if ( t->nodes[0] == l ) {
227 else if ( t->nodes[1] == l ) {
231 Error( "RemovePortalFromNode: portal not bounding leaf" );
235 if ( portal->nodes[0] == l ) {
236 *pp = portal->next[0];
237 portal->nodes[0] = NULL;
239 else if ( portal->nodes[1] == l ) {
240 *pp = portal->next[1];
241 portal->nodes[1] = NULL;
245 //============================================================================
247 void PrintPortal( portal_t *p ){
252 for ( i = 0 ; i < w->numpoints ; i++ )
253 Sys_Printf( "(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
254 , w->p[i][1], w->p[i][2] );
261 The created portals will face the global outside_node
265 void MakeHeadnodePortals( tree_t *tree ){
268 portal_t *p, *portals[6];
269 plane_t bplanes[6], *pl;
272 node = tree->headnode;
274 // pad with some space so there will never be null volume leafs
275 for ( i = 0 ; i < 3 ; i++ )
277 bounds[0][i] = tree->mins[i] - SIDESPACE;
278 bounds[1][i] = tree->maxs[i] + SIDESPACE;
281 tree->outside_node.planenum = PLANENUM_LEAF;
282 tree->outside_node.brushlist = NULL;
283 tree->outside_node.portals = NULL;
284 tree->outside_node.contents = 0;
286 for ( i = 0 ; i < 3 ; i++ )
287 for ( j = 0 ; j < 2 ; j++ )
295 memset( pl, 0, sizeof( *pl ) );
298 pl->dist = -bounds[j][i];
303 pl->dist = bounds[j][i];
306 p->winding = BaseWindingForPlane( pl->normal, pl->dist );
307 AddPortalToNodes( p, node, &tree->outside_node );
310 // clip the basewindings by all the other planes
311 for ( i = 0 ; i < 6 ; i++ )
313 for ( j = 0 ; j < 6 ; j++ )
318 ChopWindingInPlace( &portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON );
323 //===================================================
331 #define BASE_WINDING_EPSILON 0.001
332 #define SPLIT_WINDING_EPSILON 0.001
334 winding_t *BaseWindingForNode( node_t *node ){
341 w = BaseWindingForPlane( mapplanes[node->planenum].normal
342 , mapplanes[node->planenum].dist );
344 // clip by all the parents
345 for ( n = node->parent ; n && w ; )
347 plane = &mapplanes[n->planenum];
349 if ( n->children[0] == node ) { // take front
350 ChopWindingInPlace( &w, plane->normal, plane->dist, BASE_WINDING_EPSILON );
354 VectorSubtract( vec3_origin, plane->normal, normal );
356 ChopWindingInPlace( &w, normal, dist, BASE_WINDING_EPSILON );
365 //============================================================
367 qboolean WindingIsTiny( winding_t *w );
373 create the new portal by taking the full plane winding for the cutting plane
374 and clipping it by all of parents of this node
377 void MakeNodePortal( node_t *node ){
378 portal_t *new_portal, *p;
384 w = BaseWindingForNode( node );
386 // clip the portal by all the other portals in the node
387 for ( p = node->portals ; p && w; p = p->next[side] )
389 if ( p->nodes[0] == node ) {
391 VectorCopy( p->plane.normal, normal );
392 dist = p->plane.dist;
394 else if ( p->nodes[1] == node ) {
396 VectorSubtract( vec3_origin, p->plane.normal, normal );
397 dist = -p->plane.dist;
400 Error( "CutNodePortals_r: mislinked portal" );
403 ChopWindingInPlace( &w, normal, dist, 0.1 );
410 if ( WindingIsTiny( w ) ) {
417 new_portal = AllocPortal();
418 new_portal->plane = mapplanes[node->planenum];
419 new_portal->onnode = node;
420 new_portal->winding = w;
421 AddPortalToNodes( new_portal, node->children[0], node->children[1] );
429 Move or split the portals that bound node so that the node's
430 children have portals instead of node.
433 void SplitNodePortals( node_t *node ){
434 portal_t *p, *next_portal, *new_portal;
435 node_t *f, *b, *other_node;
438 winding_t *frontwinding, *backwinding;
440 plane = &mapplanes[node->planenum];
441 f = node->children[0];
442 b = node->children[1];
444 for ( p = node->portals ; p ; p = next_portal )
446 if ( p->nodes[0] == node ) {
449 else if ( p->nodes[1] == node ) {
453 Error( "CutNodePortals_r: mislinked portal" );
455 next_portal = p->next[side];
457 other_node = p->nodes[!side];
458 RemovePortalFromNode( p, p->nodes[0] );
459 RemovePortalFromNode( p, p->nodes[1] );
462 // cut the portal into two portals, one on each side of the cut plane
464 ClipWindingEpsilon( p->winding, plane->normal, plane->dist,
465 SPLIT_WINDING_EPSILON, &frontwinding, &backwinding );
467 if ( frontwinding && WindingIsTiny( frontwinding ) ) {
468 FreeWinding( frontwinding );
473 if ( backwinding && WindingIsTiny( backwinding ) ) {
474 FreeWinding( backwinding );
479 if ( !frontwinding && !backwinding ) { // tiny windings on both sides
483 if ( !frontwinding ) {
484 FreeWinding( backwinding );
486 AddPortalToNodes( p, b, other_node );
489 AddPortalToNodes( p, other_node, b );
493 if ( !backwinding ) {
494 FreeWinding( frontwinding );
496 AddPortalToNodes( p, f, other_node );
499 AddPortalToNodes( p, other_node, f );
504 // the winding is split
505 new_portal = AllocPortal();
507 new_portal->winding = backwinding;
508 FreeWinding( p->winding );
509 p->winding = frontwinding;
512 AddPortalToNodes( p, f, other_node );
513 AddPortalToNodes( new_portal, b, other_node );
517 AddPortalToNodes( p, other_node, f );
518 AddPortalToNodes( new_portal, other_node, b );
522 node->portals = NULL;
531 void CalcNodeBounds( node_t *node ){
536 // calc mins/maxs for both leafs and nodes
537 ClearBounds( node->mins, node->maxs );
538 for ( p = node->portals ; p ; p = p->next[s] )
540 s = ( p->nodes[1] == node );
541 for ( i = 0 ; i < p->winding->numpoints ; i++ )
542 AddPointToBounds( p->winding->p[i], node->mins, node->maxs );
552 void MakeTreePortals_r( node_t *node ){
555 CalcNodeBounds( node );
556 if ( node->mins[0] >= node->maxs[0] ) {
557 Sys_FPrintf( SYS_WRN, "WARNING: node without a volume\n" );
560 for ( i = 0 ; i < 3 ; i++ )
562 if ( node->mins[i] < -8000 || node->maxs[i] > 8000 ) {
563 Sys_FPrintf( SYS_WRN, "WARNING: node with unbounded volume\n" );
567 if ( node->planenum == PLANENUM_LEAF ) {
571 MakeNodePortal( node );
572 SplitNodePortals( node );
574 MakeTreePortals_r( node->children[0] );
575 MakeTreePortals_r( node->children[1] );
583 void MakeTreePortals( tree_t *tree ){
584 MakeHeadnodePortals( tree );
585 MakeTreePortals_r( tree->headnode );
589 =========================================================
593 =========================================================
601 void FloodPortals_r( node_t *node, int dist ){
605 node->occupied = dist;
607 for ( p = node->portals ; p ; p = p->next[s] )
609 s = ( p->nodes[1] == node );
611 if ( p->nodes[!s]->occupied ) {
615 if ( !Portal_EntityFlood( p, s ) ) {
619 FloodPortals_r( p->nodes[!s], dist + 1 );
628 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant ){
633 // find the leaf to start in
635 while ( node->planenum != PLANENUM_LEAF )
637 plane = &mapplanes[node->planenum];
638 d = DotProduct( origin, plane->normal ) - plane->dist;
640 node = node->children[0];
643 node = node->children[1];
647 if ( node->contents == CONTENTS_SOLID ) {
650 node->occupant = occupant;
652 FloodPortals_r( node, 1 );
661 Marks all nodes that can be reached by entites
664 qboolean FloodEntities( tree_t *tree ){
671 headnode = tree->headnode;
672 Sys_FPrintf( SYS_VRB, "--- FloodEntities ---\n" );
674 tree->outside_node.occupied = 0;
676 for ( i = 1 ; i < num_entities ; i++ )
678 GetVectorForKey( &entities[i], "origin", origin );
679 if ( VectorCompare( origin, vec3_origin ) ) {
683 cl = ValueForKey( &entities[i], "classname" );
684 origin[2] += 1; // so objects on floor are ok
686 // nudge playerstart around if needed so clipping hulls allways
687 // have a vlaid point
688 if ( !strcmp( cl, "info_player_start" ) ) {
691 for ( x = -16 ; x <= 16 ; x += 16 )
693 for ( y = -16 ; y <= 16 ; y += 16 )
697 if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
709 if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
716 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
718 else if ( tree->outside_node.occupied ) {
719 Sys_FPrintf( SYS_VRB, "entity reached from outside -- no filling\n" );
722 return (qboolean)( inside && !tree->outside_node.occupied );
726 =========================================================
730 =========================================================
740 void FloodAreas_r( node_t *node ){
746 if ( node->contents == CONTENTS_AREAPORTAL ) {
747 // this node is part of an area portal
749 e = &entities[b->original->entitynum];
751 // if the current area has allready touched this
752 // portal, we are done
753 if ( e->portalareas[0] == c_areas || e->portalareas[1] == c_areas ) {
757 // note the current area as bounding the portal
758 if ( e->portalareas[1] ) {
759 Sys_FPrintf( SYS_WRN, "WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum );
762 if ( e->portalareas[0] ) {
763 e->portalareas[1] = c_areas;
766 e->portalareas[0] = c_areas;
773 return; // allready got it
775 node->area = c_areas;
777 for ( p = node->portals ; p ; p = p->next[s] )
779 s = ( p->nodes[1] == node );
781 if ( p->nodes[!s]->occupied ) {
785 if ( !Portal_EntityFlood( p, s ) ) {
789 FloodAreas_r( p->nodes[!s] );
797 Just decend the tree, and for each node that hasn't had an
798 area set, flood fill out from there
801 void FindAreas_r( node_t *node ){
802 if ( node->planenum != PLANENUM_LEAF ) {
803 FindAreas_r( node->children[0] );
804 FindAreas_r( node->children[1] );
809 return; // allready got it
812 if ( node->contents & CONTENTS_SOLID ) {
816 if ( !node->occupied ) {
817 return; // not reachable by entities
820 // area portals are allways only flooded into, never
822 if ( node->contents == CONTENTS_AREAPORTAL ) {
827 FloodAreas_r( node );
834 Just decend the tree, and for each node that hasn't had an
835 area set, flood fill out from there
838 void SetAreaPortalAreas_r( node_t *node ){
842 if ( node->planenum != PLANENUM_LEAF ) {
843 SetAreaPortalAreas_r( node->children[0] );
844 SetAreaPortalAreas_r( node->children[1] );
848 if ( node->contents == CONTENTS_AREAPORTAL ) {
850 return; // allready set
854 e = &entities[b->original->entitynum];
855 node->area = e->portalareas[0];
856 if ( !e->portalareas[1] ) {
857 Sys_FPrintf( SYS_WRN, "WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum );
869 void EmitAreaPortals( node_t *headnode ){
874 if ( c_areas > MAX_MAP_AREAS ) {
875 Error( "MAX_MAP_AREAS" );
877 numareas = c_areas + 1;
878 numareaportals = 1; // leave 0 as an error
880 for ( i = 1 ; i <= c_areas ; i++ )
882 dareas[i].firstareaportal = numareaportals;
883 for ( j = 0 ; j < num_entities ; j++ )
886 if ( !e->areaportalnum ) {
889 dp = &dareaportals[numareaportals];
890 if ( e->portalareas[0] == i ) {
891 dp->portalnum = e->areaportalnum;
892 dp->otherarea = e->portalareas[1];
895 else if ( e->portalareas[1] == i ) {
896 dp->portalnum = e->areaportalnum;
897 dp->otherarea = e->portalareas[0];
901 dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
904 Sys_FPrintf( SYS_VRB, "%5i numareas\n", numareas );
905 Sys_FPrintf( SYS_VRB, "%5i numareaportals\n", numareaportals );
912 Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
915 void FloodAreas( tree_t *tree ){
916 Sys_FPrintf( SYS_VRB, "--- FloodAreas ---\n" );
917 FindAreas_r( tree->headnode );
918 SetAreaPortalAreas_r( tree->headnode );
919 Sys_FPrintf( SYS_VRB, "%5i areas\n", c_areas );
922 //======================================================
928 void FillOutside_r( node_t *node ){
929 if ( node->planenum != PLANENUM_LEAF ) {
930 FillOutside_r( node->children[0] );
931 FillOutside_r( node->children[1] );
935 // anything not reachable by an entity
936 // can be filled away
937 if ( !node->occupied ) {
938 if ( node->contents != CONTENTS_SOLID ) {
940 node->contents = CONTENTS_SOLID;
956 Fill all nodes that can't be reached by entities
959 void FillOutside( node_t *headnode ){
963 Sys_FPrintf( SYS_VRB, "--- FillOutside ---\n" );
964 FillOutside_r( headnode );
965 Sys_FPrintf( SYS_VRB, "%5i solid leafs\n", c_solid );
966 Sys_FPrintf( SYS_VRB, "%5i leafs filled\n", c_outside );
967 Sys_FPrintf( SYS_VRB, "%5i inside leafs\n", c_inside );
971 //==============================================================
977 Finds a brush side to use for texturing the given portal
980 void FindPortalSide( portal_t *p ){
987 side_t *side, *bestside;
991 // decide which content change is strongest
992 // solid > lava > water, etc
993 viscontents = VisibleContents( p->nodes[0]->contents ^ p->nodes[1]->contents );
994 if ( !viscontents ) {
998 planenum = p->onnode->planenum;
1002 for ( j = 0 ; j < 2 ; j++ )
1005 p1 = &mapplanes[p->onnode->planenum];
1006 for ( bb = n->brushlist ; bb ; bb = bb->next )
1008 brush = bb->original;
1009 if ( !( brush->contents & viscontents ) ) {
1012 for ( i = 0 ; i < brush->numsides ; i++ )
1014 side = &brush->original_sides[i];
1015 if ( side->bevel ) {
1018 if ( side->texinfo == TEXINFO_NODE ) {
1019 continue; // non-visible
1021 if ( ( side->planenum & ~1 ) == planenum ) { // exact match
1022 bestside = &brush->original_sides[i];
1025 // see how close the match is
1026 p2 = &mapplanes[side->planenum & ~1];
1027 dot = DotProduct( p1->normal, p2->normal );
1028 if ( dot > bestdot ) {
1038 Sys_FPrintf( SYS_VRB, "WARNING: side not found for portal\n" );
1041 p->sidefound = true;
1052 void MarkVisibleSides_r( node_t *node ){
1056 if ( node->planenum != PLANENUM_LEAF ) {
1057 MarkVisibleSides_r( node->children[0] );
1058 MarkVisibleSides_r( node->children[1] );
1062 // empty leafs are never boundary leafs
1063 if ( !node->contents ) {
1067 // see if there is a visible face
1068 for ( p = node->portals ; p ; p = p->next[!s] )
1070 s = ( p->nodes[0] == node );
1072 continue; // edge of world
1074 if ( !p->sidefound ) {
1075 FindPortalSide( p );
1078 p->side->visible = true;
1090 void MarkVisibleSides( tree_t *tree, int startbrush, int endbrush ){
1095 Sys_FPrintf( SYS_VRB, "--- MarkVisibleSides ---\n" );
1097 // clear all the visible flags
1098 for ( i = startbrush ; i < endbrush ; i++ )
1100 mb = &mapbrushes[i];
1102 numsides = mb->numsides;
1103 for ( j = 0 ; j < numsides ; j++ )
1104 mb->original_sides[j].visible = false;
1107 // set visible flags on the sides that are used by portals
1108 MarkVisibleSides_r( tree->headnode );