2 Copyright (C) 1999-2006 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)
41 if (c_active_portals > c_peak_portals)
42 c_peak_portals = c_active_portals;
44 p = malloc (sizeof(portal_t));
45 memset (p, 0, sizeof(portal_t));
50 void FreePortal (portal_t *p)
53 FreeWinding (p->winding);
59 //==============================================================
65 Returns the single content bit of the
66 strongest visible content present
69 int VisibleContents (int contents)
73 for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1)
86 int ClusterContents (node_t *node)
90 if (node->planenum == PLANENUM_LEAF)
91 return node->contents;
93 c1 = ClusterContents(node->children[0]);
94 c2 = ClusterContents(node->children[1]);
97 // a cluster may include some solid detail areas, but
99 if ( ! (c1&CONTENTS_SOLID) || ! (c2&CONTENTS_SOLID) )
100 c &= ~CONTENTS_SOLID;
108 Returns true if the portal is empty or translucent, allowing
109 the PVS calculation to see through it.
110 The nodes on either side of the portal may actually be clusters,
111 not leafs, so all contents should be ored together
114 qboolean Portal_VisFlood (portal_t *p)
119 return false; // to global outsideleaf
121 c1 = ClusterContents(p->nodes[0]);
122 c2 = ClusterContents(p->nodes[1]);
124 if (!VisibleContents (c1^c2))
127 if (c1 & (CONTENTS_TRANSLUCENT|CONTENTS_DETAIL))
129 if (c2 & (CONTENTS_TRANSLUCENT|CONTENTS_DETAIL))
132 if ( (c1|c2) & CONTENTS_SOLID )
133 return false; // can't see through solid
136 return true; // identical on both sides
138 if (!VisibleContents (c1^c2))
148 The entity flood determines which areas are
149 "outside" on the map, which are then filled in.
150 Flowing from side s to side !s
153 qboolean Portal_EntityFlood (portal_t *p, int s)
155 if (p->nodes[0]->planenum != PLANENUM_LEAF
156 || p->nodes[1]->planenum != PLANENUM_LEAF)
157 Error ("Portal_EntityFlood: not a leaf");
159 // can never cross to a solid
160 if ( (p->nodes[0]->contents & CONTENTS_SOLID)
161 || (p->nodes[1]->contents & CONTENTS_SOLID) )
164 // can flood through everything else
169 //=============================================================================
178 void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
180 if (p->nodes[0] || p->nodes[1])
181 Error ("AddPortalToNode: allready included");
184 p->next[0] = front->portals;
188 p->next[1] = back->portals;
198 void RemovePortalFromNode (portal_t *portal, node_t *l)
202 // remove reference to the current portal
208 Error ("RemovePortalFromNode: portal not in leaf");
213 if (t->nodes[0] == l)
215 else if (t->nodes[1] == l)
218 Error ("RemovePortalFromNode: portal not bounding leaf");
221 if (portal->nodes[0] == l)
223 *pp = portal->next[0];
224 portal->nodes[0] = NULL;
226 else if (portal->nodes[1] == l)
228 *pp = portal->next[1];
229 portal->nodes[1] = NULL;
233 //============================================================================
235 void PrintPortal (portal_t *p)
241 for (i=0 ; i<w->numpoints ; i++)
242 Sys_Printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
243 , w->p[i][1], w->p[i][2]);
250 The created portals will face the global outside_node
254 void MakeHeadnodePortals (tree_t *tree)
258 portal_t *p, *portals[6];
259 plane_t bplanes[6], *pl;
262 node = tree->headnode;
264 // pad with some space so there will never be null volume leafs
265 for (i=0 ; i<3 ; i++)
267 bounds[0][i] = tree->mins[i] - SIDESPACE;
268 bounds[1][i] = tree->maxs[i] + SIDESPACE;
271 tree->outside_node.planenum = PLANENUM_LEAF;
272 tree->outside_node.brushlist = NULL;
273 tree->outside_node.portals = NULL;
274 tree->outside_node.contents = 0;
276 for (i=0 ; i<3 ; i++)
277 for (j=0 ; j<2 ; j++)
285 memset (pl, 0, sizeof(*pl));
289 pl->dist = -bounds[j][i];
294 pl->dist = bounds[j][i];
297 p->winding = BaseWindingForPlane (pl->normal, pl->dist);
298 AddPortalToNodes (p, node, &tree->outside_node);
301 // clip the basewindings by all the other planes
302 for (i=0 ; i<6 ; i++)
304 for (j=0 ; j<6 ; j++)
308 ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);
313 //===================================================
321 #define BASE_WINDING_EPSILON 0.001
322 #define SPLIT_WINDING_EPSILON 0.001
324 winding_t *BaseWindingForNode (node_t *node)
332 w = BaseWindingForPlane (mapplanes[node->planenum].normal
333 , mapplanes[node->planenum].dist);
335 // clip by all the parents
336 for (n=node->parent ; n && w ; )
338 plane = &mapplanes[n->planenum];
340 if (n->children[0] == node)
342 ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);
346 VectorSubtract (vec3_origin, plane->normal, normal);
348 ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);
357 //============================================================
359 qboolean WindingIsTiny (winding_t *w);
365 create the new portal by taking the full plane winding for the cutting plane
366 and clipping it by all of parents of this node
369 void MakeNodePortal (node_t *node)
371 portal_t *new_portal, *p;
377 w = BaseWindingForNode (node);
379 // clip the portal by all the other portals in the node
380 for (p = node->portals ; p && w; p = p->next[side])
382 if (p->nodes[0] == node)
385 VectorCopy (p->plane.normal, normal);
386 dist = p->plane.dist;
388 else if (p->nodes[1] == node)
391 VectorSubtract (vec3_origin, p->plane.normal, normal);
392 dist = -p->plane.dist;
395 Error ("CutNodePortals_r: mislinked portal");
397 ChopWindingInPlace (&w, normal, dist, 0.1);
405 if (WindingIsTiny (w))
413 new_portal = AllocPortal ();
414 new_portal->plane = mapplanes[node->planenum];
415 new_portal->onnode = node;
416 new_portal->winding = w;
417 AddPortalToNodes (new_portal, node->children[0], node->children[1]);
425 Move or split the portals that bound node so that the node's
426 children have portals instead of node.
429 void SplitNodePortals (node_t *node)
431 portal_t *p, *next_portal, *new_portal;
432 node_t *f, *b, *other_node;
435 winding_t *frontwinding, *backwinding;
437 plane = &mapplanes[node->planenum];
438 f = node->children[0];
439 b = node->children[1];
441 for (p = node->portals ; p ; p = next_portal)
443 if (p->nodes[0] == node)
445 else if (p->nodes[1] == node)
448 Error ("CutNodePortals_r: mislinked portal");
449 next_portal = p->next[side];
451 other_node = p->nodes[!side];
452 RemovePortalFromNode (p, p->nodes[0]);
453 RemovePortalFromNode (p, p->nodes[1]);
456 // cut the portal into two portals, one on each side of the cut plane
458 ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
459 SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
461 if (frontwinding && WindingIsTiny(frontwinding))
463 FreeWinding (frontwinding);
468 if (backwinding && WindingIsTiny(backwinding))
470 FreeWinding (backwinding);
475 if (!frontwinding && !backwinding)
476 { // tiny windings on both sides
482 FreeWinding (backwinding);
484 AddPortalToNodes (p, b, other_node);
486 AddPortalToNodes (p, other_node, b);
491 FreeWinding (frontwinding);
493 AddPortalToNodes (p, f, other_node);
495 AddPortalToNodes (p, other_node, f);
499 // the winding is split
500 new_portal = AllocPortal ();
502 new_portal->winding = backwinding;
503 FreeWinding (p->winding);
504 p->winding = frontwinding;
508 AddPortalToNodes (p, f, other_node);
509 AddPortalToNodes (new_portal, b, other_node);
513 AddPortalToNodes (p, other_node, f);
514 AddPortalToNodes (new_portal, other_node, b);
518 node->portals = NULL;
527 void CalcNodeBounds (node_t *node)
533 // calc mins/maxs for both leafs and nodes
534 ClearBounds (node->mins, node->maxs);
535 for (p = node->portals ; p ; p = p->next[s])
537 s = (p->nodes[1] == node);
538 for (i=0 ; i<p->winding->numpoints ; i++)
539 AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
549 void MakeTreePortals_r (node_t *node)
553 CalcNodeBounds (node);
554 if (node->mins[0] >= node->maxs[0])
556 Sys_Printf ("WARNING: node without a volume\n");
559 for (i=0 ; i<3 ; i++)
561 if (node->mins[i] < -8000 || node->maxs[i] > 8000)
563 Sys_Printf ("WARNING: node with unbounded volume\n");
567 if (node->planenum == PLANENUM_LEAF)
570 MakeNodePortal (node);
571 SplitNodePortals (node);
573 MakeTreePortals_r (node->children[0]);
574 MakeTreePortals_r (node->children[1]);
582 void MakeTreePortals (tree_t *tree)
584 MakeHeadnodePortals (tree);
585 MakeTreePortals_r (tree->headnode);
589 =========================================================
593 =========================================================
601 void FloodPortals_r (node_t *node, int dist)
606 node->occupied = dist;
608 for (p=node->portals ; p ; p = p->next[s])
610 s = (p->nodes[1] == node);
612 if (p->nodes[!s]->occupied)
615 if (!Portal_EntityFlood (p, s))
618 FloodPortals_r (p->nodes[!s], dist+1);
627 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];
642 node = node->children[1];
645 if (node->contents == CONTENTS_SOLID)
647 node->occupant = occupant;
649 FloodPortals_r (node, 1);
658 Marks all nodes that can be reached by entites
661 qboolean FloodEntities (tree_t *tree)
669 headnode = tree->headnode;
670 Sys_FPrintf( SYS_VRB, "--- FloodEntities ---\n");
672 tree->outside_node.occupied = 0;
674 for (i=1 ; i<num_entities ; i++)
676 GetVectorForKey (&entities[i], "origin", origin);
677 if (VectorCompare(origin, vec3_origin))
680 cl = ValueForKey (&entities[i], "classname");
681 origin[2] += 1; // so objects on floor are ok
683 // nudge playerstart around if needed so clipping hulls allways
684 // have a vlaid point
685 if (!strcmp (cl, "info_player_start"))
689 for (x=-16 ; x<=16 ; x += 16)
691 for (y=-16 ; y<=16 ; y += 16)
695 if (PlaceOccupant (headnode, origin, &entities[i]))
708 if (PlaceOccupant (headnode, origin, &entities[i]))
715 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n");
717 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)
747 if (node->contents == CONTENTS_AREAPORTAL)
749 // this node is part of an area portal
751 e = &entities[b->original->entitynum];
753 // if the current area has allready touched this
754 // portal, we are done
755 if (e->portalareas[0] == c_areas || e->portalareas[1] == c_areas)
758 // note the current area as bounding the portal
759 if (e->portalareas[1])
761 Sys_Printf ("WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum);
764 if (e->portalareas[0])
765 e->portalareas[1] = c_areas;
767 e->portalareas[0] = c_areas;
773 return; // allready got it
774 node->area = c_areas;
776 for (p=node->portals ; p ; p = p->next[s])
778 s = (p->nodes[1] == node);
780 if (p->nodes[!s]->occupied)
783 if (!Portal_EntityFlood (p, s))
786 FloodAreas_r (p->nodes[!s]);
794 Just decend the tree, and for each node that hasn't had an
795 area set, flood fill out from there
798 void FindAreas_r (node_t *node)
800 if (node->planenum != PLANENUM_LEAF)
802 FindAreas_r (node->children[0]);
803 FindAreas_r (node->children[1]);
808 return; // allready got it
810 if (node->contents & CONTENTS_SOLID)
814 return; // not reachable by entities
816 // area portals are allways only flooded into, never
818 if (node->contents == CONTENTS_AREAPORTAL)
829 Just decend the tree, and for each node that hasn't had an
830 area set, flood fill out from there
833 void SetAreaPortalAreas_r (node_t *node)
838 if (node->planenum != PLANENUM_LEAF)
840 SetAreaPortalAreas_r (node->children[0]);
841 SetAreaPortalAreas_r (node->children[1]);
845 if (node->contents == CONTENTS_AREAPORTAL)
848 return; // allready set
851 e = &entities[b->original->entitynum];
852 node->area = e->portalareas[0];
853 if (!e->portalareas[1])
855 Sys_Printf ("WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum);
867 void EmitAreaPortals (node_t *headnode)
873 if (c_areas > MAX_MAP_AREAS)
874 Error ("MAX_MAP_AREAS");
875 numareas = c_areas+1;
876 numareaportals = 1; // leave 0 as an error
878 for (i=1 ; i<=c_areas ; i++)
880 dareas[i].firstareaportal = numareaportals;
881 for (j=0 ; j<num_entities ; j++)
884 if (!e->areaportalnum)
886 dp = &dareaportals[numareaportals];
887 if (e->portalareas[0] == i)
889 dp->portalnum = e->areaportalnum;
890 dp->otherarea = e->portalareas[1];
893 else if (e->portalareas[1] == i)
895 dp->portalnum = e->areaportalnum;
896 dp->otherarea = e->portalareas[0];
900 dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
903 Sys_FPrintf( SYS_VRB, "%5i numareas\n", numareas);
904 Sys_FPrintf( SYS_VRB, "%5i numareaportals\n", numareaportals);
911 Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
914 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)
930 if (node->planenum != PLANENUM_LEAF)
932 FillOutside_r (node->children[0]);
933 FillOutside_r (node->children[1]);
937 // anything not reachable by an entity
938 // can be filled away
941 if (node->contents != CONTENTS_SOLID)
944 node->contents = CONTENTS_SOLID;
958 Fill all nodes that can't be reached by entities
961 void FillOutside (node_t *headnode)
966 Sys_FPrintf( SYS_VRB, "--- FillOutside ---\n");
967 FillOutside_r (headnode);
968 Sys_FPrintf( SYS_VRB, "%5i solid leafs\n", c_solid);
969 Sys_FPrintf( SYS_VRB, "%5i leafs filled\n", c_outside);
970 Sys_FPrintf( SYS_VRB, "%5i inside leafs\n", c_inside);
974 //==============================================================
980 Finds a brush side to use for texturing the given portal
983 void FindPortalSide (portal_t *p)
991 side_t *side, *bestside;
995 // decide which content change is strongest
996 // solid > lava > water, etc
997 viscontents = VisibleContents (p->nodes[0]->contents ^ p->nodes[1]->contents);
1001 planenum = p->onnode->planenum;
1005 for (j=0 ; j<2 ; j++)
1008 p1 = &mapplanes[p->onnode->planenum];
1009 for (bb=n->brushlist ; bb ; bb=bb->next)
1011 brush = bb->original;
1012 if ( !(brush->contents & viscontents) )
1014 for (i=0 ; i<brush->numsides ; i++)
1016 side = &brush->original_sides[i];
1019 if (side->texinfo == TEXINFO_NODE)
1020 continue; // non-visible
1021 if ((side->planenum&~1) == planenum)
1023 bestside = &brush->original_sides[i];
1026 // see how close the match is
1027 p2 = &mapplanes[side->planenum&~1];
1028 dot = DotProduct (p1->normal, p2->normal);
1040 Sys_FPrintf( SYS_VRB, "WARNING: side not found for portal\n");
1042 p->sidefound = true;
1053 void MarkVisibleSides_r (node_t *node)
1058 if (node->planenum != PLANENUM_LEAF)
1060 MarkVisibleSides_r (node->children[0]);
1061 MarkVisibleSides_r (node->children[1]);
1065 // empty leafs are never boundary leafs
1066 if (!node->contents)
1069 // see if there is a visible face
1070 for (p=node->portals ; p ; p = p->next[!s])
1072 s = (p->nodes[0] == node);
1074 continue; // edge of world
1078 p->side->visible = true;
1089 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);