portals.c File Reference

#include "qbsp.h"
#include "l_mem.h"

Include dependency graph for portals.c:

Go to the source code of this file.

Defines
#define	BASE_WINDING_EPSILON   0.001
#define	SIDESPACE   8
#define	SPLIT_WINDING_EPSILON   0.001
Functions
void	AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
portal_t *	AllocPortal (void)
winding_t *	BaseWindingForNode (node_t *node)
void	CalcNodeBounds (node_t *node)
int	ClusterContents (node_t *node)
void	FillOutside (node_t *headnode)
void	FillOutside_r (node_t *node)
void	FindAreas_r (node_t *node)
void	FindPortalSide (portal_t *p)
void	FloodAreas (tree_t *tree)
void	FloodAreas_r (node_t *node)
qboolean	FloodEntities (tree_t *tree)
void	FloodPortals (node_t *firstnode)
void	FloodPortals_r (node_t *node, int dist)
void	FreePortal (portal_t *p)
void	MakeHeadnodePortals (tree_t *tree)
void	MakeNodePortal (node_t *node)
void	MakeTreePortals (tree_t *tree)
void	MakeTreePortals_r (node_t *node)
void	MarkVisibleSides (tree_t *tree, int startbrush, int endbrush)
void	MarkVisibleSides_r (node_t *node)
void	P_AddNodeToList (node_t *node)
node_t *	P_NextNodeFromList (void)
qboolean	PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant)
qboolean	Portal_EntityFlood (portal_t *p, int s)
qboolean	Portal_VisFlood (portal_t *p)
void	PrintPortal (portal_t *p)
void	RemovePortalFromNode (portal_t *portal, node_t *l)
void	SetAreaPortalAreas_r (node_t *node)
void	SplitNodePortals (node_t *node)
int	VisibleContents (int contents)
qboolean	WindingIsTiny (winding_t *w)
Variables
int	c_active_portals
int	c_areas
int	c_boundary
int	c_boundary_sides
int	c_inside
int	c_numportalizednodes
int	c_outside
int	c_peak_portals
int	c_portalmemory
int	c_solid
int	c_tinyportals
int	numrec
node_t *	p_firstnode
node_t *	p_lastnode

---

Define Documentation

#define BASE_WINDING_EPSILON   0.001

Definition at line 361 of file portals.c. Referenced by BaseWindingForNode().

#define SIDESPACE   8

Definition at line 293 of file portals.c.

#define SPLIT_WINDING_EPSILON   0.001

Definition at line 362 of file portals.c. Referenced by SplitNodePortals().

---

Function Documentation

void AddPortalToNodes (  portal_t *  p, node_t *  front, node_t *  back )

Definition at line 192 of file portals.c. References Error(), portal_s::next, node_t, portal_s::nodes, p, portal_t, and node_s::portals. { if (p->nodes[0] || p->nodes[1]) Error ("AddPortalToNode: allready included"); p->nodes[0] = front; p->next[0] = front->portals; front->portals = p; p->nodes[1] = back; p->next[1] = back->portals; back->portals = p; } //end of the function AddPortalToNodes

Here is the call graph for this function:

portal_t* AllocPortal (  void   )

Definition at line 39 of file portals.c. References c_active_portals, c_peak_portals, c_portalmemory, GetMemory(), MemorySize(), memset(), numthreads, p, and portal_t. Referenced by MakeHeadnodePortals(), MakeNodePortal(), and SplitNodePortals(). { portal_t *p; p = GetMemory(sizeof(portal_t)); memset (p, 0, sizeof(portal_t)); if (numthreads == 1) { c_active_portals++; if (c_active_portals > c_peak_portals) { c_peak_portals = c_active_portals; } //end if c_portalmemory += MemorySize(p); } //end if // p->nextportal = portallist; // portallist = p; return p; } //end of the function AllocPortal

Here is the call graph for this function:

winding_t* BaseWindingForNode (  node_t *  node  )

Definition at line 364 of file portals.c. References BASE_WINDING_EPSILON, BaseWindingForPlane(), node_s::children, ChopWindingInPlace(), plane_t::dist, mapplanes, n, node_t, plane_t::normal, node_s::parent, node_s::planenum, vec3_origin, vec3_t, vec_t, VectorSubtract, and w. { winding_t *w; node_t *n; plane_t *plane; vec3_t normal; vec_t dist; w = BaseWindingForPlane (mapplanes[node->planenum].normal , mapplanes[node->planenum].dist); // clip by all the parents for (n=node->parent ; n && w ; ) { plane = &mapplanes[n->planenum]; if (n->children[0] == node) { // take front ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON); } else { // take back VectorSubtract (vec3_origin, plane->normal, normal); dist = -plane->dist; ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON); } node = n; n = n->parent; } return w; } //end of the function BaseWindingForNode

Here is the call graph for this function:

void CalcNodeBounds (  node_t *  node  )

Definition at line 588 of file portals.c. References AddPointToBounds(), ClearBounds(), i, node_s::maxs, node_s::mins, portal_s::next, node_t, portal_s::nodes, winding_t::numpoints, winding_t::p, p, portal_t, node_s::portals, s, and portal_s::winding. { portal_t *p; int s; int i; // calc mins/maxs for both leaves and nodes ClearBounds (node->mins, node->maxs); for (p = node->portals ; p ; p = p->next[s]) { s = (p->nodes[1] == node); for (i=0 ; i<p->winding->numpoints ; i++) AddPointToBounds (p->winding->p[i], node->mins, node->maxs); } } //end of the function CalcNodeBounds

Here is the call graph for this function:

int ClusterContents (  node_t *  node  )

Definition at line 101 of file portals.c. References c, node_s::children, node_s::contents, node_t, and node_s::planenum. Referenced by Portal_VisFlood(). { int c1, c2, c; if (node->planenum == PLANENUM_LEAF) return node->contents; c1 = ClusterContents(node->children[0]); c2 = ClusterContents(node->children[1]); c = c1|c2; // a cluster may include some solid detail areas, but // still be seen into if ( ! (c1&CONTENTS_SOLID) || ! (c2&CONTENTS_SOLID) ) c &= ~CONTENTS_SOLID; return c; } //end of the function ClusterContents

void FillOutside (  node_t *  headnode  )

Definition at line 961 of file portals.c. { c_outside = 0; c_inside = 0; c_solid = 0; Log_Print("------- FillOutside --------\n"); FillOutside_r (headnode); Log_Print("%5i solid leaves\n", c_solid); Log_Print("%5i leaves filled\n", c_outside); Log_Print("%5i inside leaves\n", c_inside); } //end of the function FillOutside

void FillOutside_r (  node_t *  node  )

Definition at line 927 of file portals.c. References c_inside, c_outside, c_solid, node_s::children, node_s::contents, FillOutside_r(), node_t, node_s::occupied, and node_s::planenum. { if (node->planenum != PLANENUM_LEAF) { FillOutside_r (node->children[0]); FillOutside_r (node->children[1]); return; } //end if // anything not reachable by an entity // can be filled away (by setting solid contents) if (!node->occupied) { if (!(node->contents & CONTENTS_SOLID)) { c_outside++; node->contents |= CONTENTS_SOLID; } //end if else { c_solid++; } //end else } //end if else { c_inside++; } //end else } //end of the function FillOutside_r

Here is the call graph for this function:

void FindAreas_r (  node_t *  node  )

Definition at line 1046 of file portals.c. References node_s::area, c_areas, node_s::children, node_s::contents, FindAreas_r(), FloodAreas_r(), node_t, node_s::occupied, and node_s::planenum. { if (node->planenum != PLANENUM_LEAF) { FindAreas_r (node->children[0]); FindAreas_r (node->children[1]); return; } if (node->area) return; // allready got it if (node->contents & CONTENTS_SOLID) return; if (!node->occupied) return; // not reachable by entities // area portals are allways only flooded into, never // out of if (node->contents == CONTENTS_AREAPORTAL) return; c_areas++; FloodAreas_r (node); } //end of the function FindAreas_r

Here is the call graph for this function:

void FindPortalSide (  portal_t *  p  )

Definition at line 1175 of file portals.c. References node_s::brushlist, bspbrush_t, mapbrush_s::contents, node_s::contents, DotProduct, side_s::flags, i, j, Log_Print(), mapbrush_t, mapplanes, n, bspbrush_s::next, node_t, portal_s::nodes, plane_t::normal, mapbrush_s::numsides, portal_s::onnode, bspbrush_s::original, mapbrush_s::original_sides, p, p2, side_s::planenum, node_s::planenum, portal_t, portal_s::side, side_t, portal_s::sidefound, side_s::texinfo, and VisibleContents(). Referenced by MarkVisibleSides_r(). { int viscontents; bspbrush_t *bb; mapbrush_t *brush; node_t *n; int i,j; int planenum; side_t *side, *bestside; float dot, bestdot; plane_t *p1, *p2; // decide which content change is strongest // solid > lava > water, etc viscontents = VisibleContents (p->nodes[0]->contents ^ p->nodes[1]->contents); if (!viscontents) return; planenum = p->onnode->planenum; bestside = NULL; bestdot = 0; for (j=0 ; j<2 ; j++) { n = p->nodes[j]; p1 = &mapplanes[p->onnode->planenum]; for (bb=n->brushlist ; bb ; bb=bb->next) { brush = bb->original; if ( !(brush->contents & viscontents) ) continue; for (i=0 ; i<brush->numsides ; i++) { side = &brush->original_sides[i]; if (side->flags & SFL_BEVEL) continue; if (side->texinfo == TEXINFO_NODE) continue; // non-visible if ((side->planenum&~1) == planenum) { // exact match bestside = &brush->original_sides[i]; goto gotit; } //end if // see how close the match is p2 = &mapplanes[side->planenum&~1]; dot = DotProduct (p1->normal, p2->normal); if (dot > bestdot) { bestdot = dot; bestside = side; } //end if } //end for } //end for } //end for gotit: if (!bestside) Log_Print("WARNING: side not found for portal\n"); p->sidefound = true; p->side = bestside; } //end of the function FindPortalSide

Here is the call graph for this function:

void FloodAreas (  tree_t *  tree  )

Definition at line 1161 of file portals.c. { Log_Print("--- FloodAreas ---\n"); FindAreas_r (tree->headnode); SetAreaPortalAreas_r (tree->headnode); Log_Print("%5i areas\n", c_areas); } //end of the function FloodAreas

void FloodAreas_r (  node_t *  node  )

Definition at line 989 of file portals.c. References node_s::area, b, node_s::brushlist, bspbrush_t, c_areas, node_s::contents, e, entities, mapbrush_s::entitynum, FloodAreas_r(), Log_Print(), portal_s::next, node_t, portal_s::nodes, node_s::occupied, bspbrush_s::original, p, Portal_EntityFlood(), portal_t, entity_t::portalareas, node_s::portals, and s. { portal_t *p; int s; bspbrush_t *b; entity_t *e; if (node->contents == CONTENTS_AREAPORTAL) { // this node is part of an area portal b = node->brushlist; e = &entities[b->original->entitynum]; // if the current area has allready touched this // portal, we are done if (e->portalareas[0] == c_areas || e->portalareas[1] == c_areas) return; // note the current area as bounding the portal if (e->portalareas[1]) { Log_Print("WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum); return; } if (e->portalareas[0]) e->portalareas[1] = c_areas; else e->portalareas[0] = c_areas; return; } //end if if (node->area) return; // allready got it node->area = c_areas; for (p=node->portals ; p ; p = p->next[s]) { s = (p->nodes[1] == node); #if 0 if (p->nodes[!s]->occupied) continue; #endif if (!Portal_EntityFlood (p, s)) continue; FloodAreas_r (p->nodes[!s]); } //end for } //end of the function FloodAreas_r

Here is the call graph for this function:

qboolean FloodEntities (  tree_t *  tree  )

Definition at line 843 of file portals.c. { int i; int x, y; vec3_t origin; char *cl; qboolean inside; node_t *headnode; headnode = tree->headnode; Log_Print("------ FloodEntities -------\n"); inside = false; tree->outside_node.occupied = 0; //start at entity 1 not the world ( = 0) for (i = 1; i < num_entities; i++) { GetVectorForKey(&entities[i], "origin", origin); if (VectorCompare(origin, vec3_origin)) continue; cl = ValueForKey(&entities[i], "classname"); origin[2] += 1; //so objects on floor are ok // Log_Print("flooding from entity %d: %s\n", i, cl); //nudge playerstart around if needed so clipping hulls allways //have a valid point if (!strcmp(cl, "info_player_start")) { for (x = -16; x <= 16; x += 16) { for (y = -16; y <= 16; y += 16) { origin[0] += x; origin[1] += y; if (PlaceOccupant(headnode, origin, &entities[i])) { inside = true; x = 999; //stop for this info_player_start break; } //end if origin[0] -= x; origin[1] -= y; } //end for } //end for } //end if else { if (PlaceOccupant(headnode, origin, &entities[i])) { inside = true; } //end if } //end else } //end for if (!inside) { Log_Print("WARNING: no entities inside\n"); } //end if else if (tree->outside_node.occupied) { Log_Print("WARNING: entity reached from outside\n"); } //end else if return (qboolean)(inside && !tree->outside_node.occupied); } //end of the function FloodEntities

void FloodPortals (  node_t *  firstnode  )

Definition at line 728 of file portals.c. References firstnode, portal_s::next, node_t, portal_s::nodes, node_s::occupied, p, P_AddNodeToList(), P_NextNodeFromList(), Portal_EntityFlood(), portal_t, node_s::portals, and s. Referenced by PlaceOccupant(). { node_t *node; portal_t *p; int s; firstnode->occupied = 1; P_AddNodeToList(firstnode); for (node = P_NextNodeFromList(); node; node = P_NextNodeFromList()) { for (p = node->portals; p; p = p->next[s]) { s = (p->nodes[1] == node); //if the node at the other side of the portal is occupied already if (p->nodes[!s]->occupied) continue; //if it isn't possible to flood through this portal if (!Portal_EntityFlood(p, s)) continue; // p->nodes[!s]->occupied = node->occupied + 1; // P_AddNodeToList(p->nodes[!s]); } //end for } //end for } //end of the function FloodPortals

Here is the call graph for this function:

void FloodPortals_r (  node_t *  node, int  dist )

Definition at line 761 of file portals.c. References Error(), FloodPortals_r(), Log_Print(), portal_s::next, node_t, portal_s::nodes, numrec, node_s::occupied, p, Portal_EntityFlood(), portal_t, node_s::portals, and s. { portal_t *p; int s; // int i; Log_Print("\r%6d", ++numrec); if (node->occupied) Error("FloodPortals_r: node already occupied\n"); if (!node) { Error("FloodPortals_r: NULL node\n"); } //end if*/ node->occupied = dist; for (p = node->portals; p; p = p->next[s]) { s = (p->nodes[1] == node); //if the node at the other side of the portal is occupied already if (p->nodes[!s]->occupied) continue; //if it isn't possible to flood through this portal if (!Portal_EntityFlood(p, s)) continue; //flood recursively through the current portal FloodPortals_r(p->nodes[!s], dist+1); } //end for Log_Print("\r%6d", --numrec); } //end of the function FloodPortals_r

Here is the call graph for this function:

void FreePortal (  portal_t *  p  )

Definition at line 67 of file portals.c. { if (p->winding) FreeWinding(p->winding); if (numthreads == 1) { c_active_portals--; c_portalmemory -= MemorySize(p); } //end if FreeMemory(p); } //end of the function FreePortal

void MakeHeadnodePortals (  tree_t *  tree  )

Definition at line 295 of file portals.c. { vec3_t bounds[2]; int i, j, n; portal_t *p, *portals[6]; plane_t bplanes[6], *pl; node_t *node; node = tree->headnode; // pad with some space so there will never be null volume leaves for (i=0 ; i<3 ; i++) { bounds[0][i] = tree->mins[i] - SIDESPACE; bounds[1][i] = tree->maxs[i] + SIDESPACE; if ( bounds[0][i] > bounds[1][i] ) { Error("empty BSP tree"); } } tree->outside_node.planenum = PLANENUM_LEAF; tree->outside_node.brushlist = NULL; tree->outside_node.portals = NULL; tree->outside_node.contents = 0; for (i=0 ; i<3 ; i++) for (j=0 ; j<2 ; j++) { n = j*3 + i; p = AllocPortal (); portals[n] = p; pl = &bplanes[n]; memset (pl, 0, sizeof(*pl)); if (j) { pl->normal[i] = -1; pl->dist = -bounds[j][i]; } else { pl->normal[i] = 1; pl->dist = bounds[j][i]; } p->plane = *pl; p->winding = BaseWindingForPlane (pl->normal, pl->dist); AddPortalToNodes (p, node, &tree->outside_node); } // clip the basewindings by all the other planes for (i=0 ; i<6 ; i++) { for (j=0 ; j<6 ; j++) { if (j == i) continue; ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON); } //end for } //end for } //end of the function MakeHeadNodePortals

void MakeNodePortal (  node_t *  node  )

Definition at line 406 of file portals.c. { portal_t *new_portal, *p; winding_t *w; vec3_t normal; float dist; int side; w = BaseWindingForNode (node); // clip the portal by all the other portals in the node for (p = node->portals; p && w; p = p->next[side]) { if (p->nodes[0] == node) { side = 0; VectorCopy (p->plane.normal, normal); dist = p->plane.dist; } //end if else if (p->nodes[1] == node) { side = 1; VectorSubtract (vec3_origin, p->plane.normal, normal); dist = -p->plane.dist; } //end else if else { Error ("MakeNodePortal: mislinked portal"); } //end else ChopWindingInPlace (&w, normal, dist, 0.1); } //end for if (!w) { return; } //end if if (WindingIsTiny (w)) { c_tinyportals++; FreeWinding(w); return; } //end if #ifdef DEBUG /* //NOTE: don't use this winding ok check // all the invalid windings only have a degenerate edge if (WindingError(w)) { Log_Print("MakeNodePortal: %s\n", WindingErrorString()); FreeWinding(w); return; } //end if*/ #endif //DEBUG new_portal = AllocPortal(); new_portal->plane = mapplanes[node->planenum]; #ifdef ME new_portal->planenum = node->planenum; #endif //ME new_portal->onnode = node; new_portal->winding = w; AddPortalToNodes (new_portal, node->children[0], node->children[1]); } //end of the function MakeNodePortal

void MakeTreePortals (  tree_t *  tree  )

Definition at line 649 of file portals.c. { #ifdef ME Log_Print("---- Node Portalization ----\n"); c_numportalizednodes = 0; c_portalmemory = 0; qprintf("%6d nodes portalized", c_numportalizednodes); #endif //ME MakeHeadnodePortals(tree); MakeTreePortals_r(tree->headnode); #ifdef ME qprintf("\n"); Log_Write("%6d nodes portalized\r\n", c_numportalizednodes); Log_Print("%6d tiny portals\r\n", c_tinyportals); Log_Print("%6d KB of portal memory\r\n", c_portalmemory >> 10); Log_Print("%6i KB of winding memory\r\n", WindingMemory() >> 10); #endif //ME } //end of the function MakeTreePortals

void MakeTreePortals_r (  node_t *  node  )

Definition at line 611 of file portals.c. References c_numportalizednodes, CalcNodeBounds(), node_s::children, i, Log_Print(), MakeNodePortal(), MakeTreePortals_r(), MAX_MAP_BOUNDS, node_s::maxs, node_s::mins, node_t, node_s::planenum, qprintf(), and SplitNodePortals(). { int i; #ifdef ME qprintf("\r%6d", ++c_numportalizednodes); if (cancelconversion) return; #endif //ME CalcNodeBounds (node); if (node->mins[0] >= node->maxs[0]) { Log_Print("WARNING: node without a volume\n"); } for (i=0 ; i<3 ; i++) { if (node->mins[i] < -MAX_MAP_BOUNDS || node->maxs[i] > MAX_MAP_BOUNDS) { Log_Print("WARNING: node with unbounded volume\n"); break; } } if (node->planenum == PLANENUM_LEAF) return; MakeNodePortal (node); SplitNodePortals (node); MakeTreePortals_r (node->children[0]); MakeTreePortals_r (node->children[1]); } //end of the function MakeTreePortals_r

Here is the call graph for this function:

void MarkVisibleSides (  tree_t *  tree, int  startbrush, int  endbrush )

Definition at line 1276 of file portals.c. References side_s::flags, i, j, Log_Print(), mapbrush_t, mapbrushes, MarkVisibleSides_r(), mapbrush_s::numsides, mapbrush_s::original_sides, and tree(). { int i, j; mapbrush_t *mb; int numsides; Log_Print("--- MarkVisibleSides ---\n"); // clear all the visible flags for (i=startbrush ; i<endbrush ; i++) { mb = &mapbrushes[i]; numsides = mb->numsides; for (j=0 ; j<numsides ; j++) mb->original_sides[j].flags &= ~SFL_VISIBLE; } // set visible flags on the sides that are used by portals MarkVisibleSides_r (tree->headnode); } //end of the function MarkVisibleSides

Here is the call graph for this function:

void MarkVisibleSides_r (  node_t *  node  )

Definition at line 1243 of file portals.c. References node_s::children, node_s::contents, FindPortalSide(), side_s::flags, portal_s::next, node_t, portal_s::nodes, portal_s::onnode, p, node_s::planenum, portal_t, node_s::portals, s, portal_s::side, and portal_s::sidefound. Referenced by MarkVisibleSides(). { portal_t *p; int s; if (node->planenum != PLANENUM_LEAF) { MarkVisibleSides_r (node->children[0]); MarkVisibleSides_r (node->children[1]); return; } //end if // empty leaves are never boundary leaves if (!node->contents) return; // see if there is a visible face for (p=node->portals ; p ; p = p->next[!s]) { s = (p->nodes[0] == node); if (!p->onnode) continue; // edge of world if (!p->sidefound) FindPortalSide (p); if (p->side) p->side->flags |= SFL_VISIBLE; } //end for } //end of the function MarkVisibleSides_r

Here is the call graph for this function: