From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- code/bspc/portals.c | 2594 +++++++++++++++++++++++++-------------------------- 1 file changed, 1297 insertions(+), 1297 deletions(-) (limited to 'code/bspc/portals.c') diff --git a/code/bspc/portals.c b/code/bspc/portals.c index 3d3389d..cde4f60 100755 --- a/code/bspc/portals.c +++ b/code/bspc/portals.c @@ -1,1297 +1,1297 @@ -/* -=========================================================================== -Copyright (C) 1999-2005 Id Software, Inc. - -This file is part of Quake III Arena source code. - -Quake III Arena source code is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 2 of the License, -or (at your option) any later version. - -Quake III Arena source code is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with Foobar; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -=========================================================================== -*/ - -#include "qbsp.h" -#include "l_mem.h" - -int c_active_portals; -int c_peak_portals; -int c_boundary; -int c_boundary_sides; -int c_portalmemory; - -//portal_t *portallist = NULL; -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -portal_t *AllocPortal (void) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FreePortal (portal_t *p) -{ - 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 -//=========================================================================== -// Returns the single content bit of the -// strongest visible content present -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -int VisibleContents (int contents) -{ - int i; - - for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1) - if (contents & i ) - return i; - - return 0; -} //end of the function VisibleContents -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -int ClusterContents (node_t *node) -{ - 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 - -//=========================================================================== -// Returns true if the portal is empty or translucent, allowing -// the PVS calculation to see through it. -// The nodes on either side of the portal may actually be clusters, -// not leaves, so all contents should be ored together -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -qboolean Portal_VisFlood (portal_t *p) -{ - int c1, c2; - - if (!p->onnode) - return false; // to global outsideleaf - - c1 = ClusterContents(p->nodes[0]); - c2 = ClusterContents(p->nodes[1]); - - if (!VisibleContents (c1^c2)) - return true; - - if (c1 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL)) - c1 = 0; - if (c2 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL)) - c2 = 0; - - if ( (c1|c2) & CONTENTS_SOLID ) - return false; // can't see through solid - - if (! (c1 ^ c2)) - return true; // identical on both sides - - if (!VisibleContents (c1^c2)) - return true; - return false; -} //end of the function Portal_VisFlood -//=========================================================================== -// The entity flood determines which areas are -// "outside" on the map, which are then filled in. -// Flowing from side s to side !s -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -qboolean Portal_EntityFlood (portal_t *p, int s) -{ - if (p->nodes[0]->planenum != PLANENUM_LEAF - || p->nodes[1]->planenum != PLANENUM_LEAF) - Error ("Portal_EntityFlood: not a leaf"); - - // can never cross to a solid - if ( (p->nodes[0]->contents & CONTENTS_SOLID) - || (p->nodes[1]->contents & CONTENTS_SOLID) ) - return false; - - // can flood through everything else - return true; -} - - -//============================================================================= - -int c_tinyportals; - -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void AddPortalToNodes (portal_t *p, node_t *front, node_t *back) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void RemovePortalFromNode (portal_t *portal, node_t *l) -{ - portal_t **pp, *t; - - int s, i, n; - portal_t *p; - portal_t *portals[4096]; - -// remove reference to the current portal - pp = &l->portals; - while (1) - { - t = *pp; - if (!t) - Error ("RemovePortalFromNode: portal not in leaf"); - - if ( t == portal ) - break; - - if (t->nodes[0] == l) - pp = &t->next[0]; - else if (t->nodes[1] == l) - pp = &t->next[1]; - else - Error ("RemovePortalFromNode: portal not bounding leaf"); - } - - if (portal->nodes[0] == l) - { - *pp = portal->next[0]; - portal->nodes[0] = NULL; - } //end if - else if (portal->nodes[1] == l) - { - *pp = portal->next[1]; - portal->nodes[1] = NULL; - } //end else if - else - { - Error("RemovePortalFromNode: mislinked portal"); - } //end else -//#ifdef ME - n = 0; - for (p = l->portals; p; p = p->next[s]) - { - for (i = 0; i < n; i++) - { - if (p == portals[i]) Error("RemovePortalFromNode: circular linked\n"); - } //end for - if (p->nodes[0] != l && p->nodes[1] != l) - { - Error("RemovePortalFromNodes: portal does not belong to node\n"); - } //end if - portals[n] = p; - s = (p->nodes[1] == l); -// if (++n >= 4096) Error("RemovePortalFromNode: more than 4096 portals\n"); - } //end for -//#endif -} //end of the function RemovePortalFromNode -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void PrintPortal (portal_t *p) -{ - int i; - winding_t *w; - - w = p->winding; - for (i=0 ; inumpoints ; i++) - printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0] - , w->p[i][1], w->p[i][2]); -} //end of the function PrintPortal -//=========================================================================== -// The created portals will face the global outside_node -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -#define SIDESPACE 8 - -void MakeHeadnodePortals (tree_t *tree) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -#define BASE_WINDING_EPSILON 0.001 -#define SPLIT_WINDING_EPSILON 0.001 - -winding_t *BaseWindingForNode (node_t *node) -{ - 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 -//=========================================================================== -// create the new portal by taking the full plane winding for the cutting -// plane and clipping it by all of parents of this node -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -qboolean WindingIsTiny (winding_t *w); - -void MakeNodePortal (node_t *node) -{ - 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 -//=========================================================================== -// Move or split the portals that bound node so that the node's -// children have portals instead of node. -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void SplitNodePortals (node_t *node) -{ - portal_t *p, *next_portal, *new_portal; - node_t *f, *b, *other_node; - int side; - plane_t *plane; - winding_t *frontwinding, *backwinding; - - plane = &mapplanes[node->planenum]; - f = node->children[0]; - b = node->children[1]; - - for (p = node->portals ; p ; p = next_portal) - { - if (p->nodes[0] == node) side = 0; - else if (p->nodes[1] == node) side = 1; - else Error ("SplitNodePortals: mislinked portal"); - next_portal = p->next[side]; - - other_node = p->nodes[!side]; - RemovePortalFromNode (p, p->nodes[0]); - RemovePortalFromNode (p, p->nodes[1]); - -// -// cut the portal into two portals, one on each side of the cut plane -// - ClipWindingEpsilon (p->winding, plane->normal, plane->dist, - SPLIT_WINDING_EPSILON, &frontwinding, &backwinding); - - if (frontwinding && WindingIsTiny(frontwinding)) - { - FreeWinding (frontwinding); - frontwinding = NULL; - c_tinyportals++; - } //end if - - if (backwinding && WindingIsTiny(backwinding)) - { - FreeWinding (backwinding); - backwinding = NULL; - c_tinyportals++; - } //end if - -#ifdef DEBUG -/* //NOTE: don't use this winding ok check - // all the invalid windings only have a degenerate edge - if (frontwinding && WindingError(frontwinding)) - { - Log_Print("SplitNodePortals: front %s\n", WindingErrorString()); - FreeWinding(frontwinding); - frontwinding = NULL; - } //end if - if (backwinding && WindingError(backwinding)) - { - Log_Print("SplitNodePortals: back %s\n", WindingErrorString()); - FreeWinding(backwinding); - backwinding = NULL; - } //end if*/ -#endif //DEBUG - - if (!frontwinding && !backwinding) - { // tiny windings on both sides - continue; - } - - if (!frontwinding) - { - FreeWinding (backwinding); - if (side == 0) AddPortalToNodes (p, b, other_node); - else AddPortalToNodes (p, other_node, b); - continue; - } - if (!backwinding) - { - FreeWinding (frontwinding); - if (side == 0) AddPortalToNodes (p, f, other_node); - else AddPortalToNodes (p, other_node, f); - continue; - } - - // the winding is split - new_portal = AllocPortal(); - *new_portal = *p; - new_portal->winding = backwinding; - FreeWinding (p->winding); - p->winding = frontwinding; - - if (side == 0) - { - AddPortalToNodes (p, f, other_node); - AddPortalToNodes (new_portal, b, other_node); - } //end if - else - { - AddPortalToNodes (p, other_node, f); - AddPortalToNodes (new_portal, other_node, b); - } //end else - } - - node->portals = NULL; -} //end of the function SplitNodePortals -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void CalcNodeBounds (node_t *node) -{ - 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 ; iwinding->numpoints ; i++) - AddPointToBounds (p->winding->p[i], node->mins, node->maxs); - } -} //end of the function CalcNodeBounds -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -int c_numportalizednodes; - -void MakeTreePortals_r (node_t *node) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void MakeTreePortals(tree_t *tree) -{ - -#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 - -/* -========================================================= - -FLOOD ENTITIES - -========================================================= -*/ -//#define P_NODESTACK - -node_t *p_firstnode; -node_t *p_lastnode; - -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -#ifdef P_NODESTACK -void P_AddNodeToList(node_t *node) -{ - node->next = p_firstnode; - p_firstnode = node; - if (!p_lastnode) p_lastnode = node; -} //end of the function P_AddNodeToList -#else //it's a node queue -//add the node to the end of the node list -void P_AddNodeToList(node_t *node) -{ - node->next = NULL; - if (p_lastnode) p_lastnode->next = node; - else p_firstnode = node; - p_lastnode = node; -} //end of the function P_AddNodeToList -#endif //P_NODESTACK -//=========================================================================== -// get the first node from the front of the node list -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -node_t *P_NextNodeFromList(void) -{ - node_t *node; - - node = p_firstnode; - if (p_firstnode) p_firstnode = p_firstnode->next; - if (!p_firstnode) p_lastnode = NULL; - return node; -} //end of the function P_NextNodeFromList -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FloodPortals(node_t *firstnode) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -int numrec; - -void FloodPortals_r (node_t *node, int dist) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant) -{ - node_t *node; - vec_t d; - plane_t *plane; - - //find the leaf to start in - node = headnode; - while(node->planenum != PLANENUM_LEAF) - { - if (node->planenum < 0 || node->planenum > nummapplanes) - { - Error("PlaceOccupant: invalid node->planenum\n"); - } //end if - plane = &mapplanes[node->planenum]; - d = DotProduct(origin, plane->normal) - plane->dist; - if (d >= 0) node = node->children[0]; - else node = node->children[1]; - if (!node) - { - Error("PlaceOccupant: invalid child %d\n", d < 0); - } //end if - } //end while - //don't start in solid -// if (node->contents == CONTENTS_SOLID) - //ME: replaced because in LeafNode in brushbsp.c - // some nodes have contents solid with other contents - if (node->contents & CONTENTS_SOLID) return false; - //if the node is already occupied - if (node->occupied) return false; - - //place the occupant in the first leaf - node->occupant = occupant; - - numrec = 0; -// Log_Print("%6d recurses", numrec); -// FloodPortals_r(node, 1); -// Log_Print("\n"); - FloodPortals(node); - - return true; -} //end of the function PlaceOccupant -//=========================================================================== -// Marks all nodes that can be reached by entites -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -qboolean FloodEntities (tree_t *tree) -{ - 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 - -/* -========================================================= - -FILL OUTSIDE - -========================================================= -*/ - -int c_outside; -int c_inside; -int c_solid; - -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FillOutside_r (node_t *node) -{ - 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 -//=========================================================================== -// Fill all nodes that can't be reached by entities -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FillOutside (node_t *headnode) -{ - 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 - -/* -========================================================= - -FLOOD AREAS - -========================================================= -*/ - -int c_areas; - -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FloodAreas_r (node_t *node) -{ - 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 -//=========================================================================== -// Just decend the tree, and for each node that hasn't had an -// area set, flood fill out from there -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FindAreas_r (node_t *node) -{ - 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 -//=========================================================================== -// Just decend the tree, and for each node that hasn't had an -// area set, flood fill out from there -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void SetAreaPortalAreas_r (node_t *node) -{ - bspbrush_t *b; - entity_t *e; - - if (node->planenum != PLANENUM_LEAF) - { - SetAreaPortalAreas_r (node->children[0]); - SetAreaPortalAreas_r (node->children[1]); - return; - } //end if - - if (node->contents == CONTENTS_AREAPORTAL) - { - if (node->area) - return; // allready set - - b = node->brushlist; - e = &entities[b->original->entitynum]; - node->area = e->portalareas[0]; - if (!e->portalareas[1]) - { - Log_Print("WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum); - return; - } //end if - } //end if -} //end of the function SetAreaPortalAreas_r -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -/* -void EmitAreaPortals(node_t *headnode) -{ - int i, j; - entity_t *e; - dareaportal_t *dp; - - if (c_areas > MAX_MAP_AREAS) - Error ("MAX_MAP_AREAS"); - numareas = c_areas+1; - numareaportals = 1; // leave 0 as an error - - for (i=1 ; i<=c_areas ; i++) - { - dareas[i].firstareaportal = numareaportals; - for (j=0 ; jareaportalnum) - continue; - dp = &dareaportals[numareaportals]; - if (e->portalareas[0] == i) - { - dp->portalnum = e->areaportalnum; - dp->otherarea = e->portalareas[1]; - numareaportals++; - } //end if - else if (e->portalareas[1] == i) - { - dp->portalnum = e->areaportalnum; - dp->otherarea = e->portalareas[0]; - numareaportals++; - } //end else if - } //end for - dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal; - } //end for - - Log_Print("%5i numareas\n", numareas); - Log_Print("%5i numareaportals\n", numareaportals); -} //end of the function EmitAreaPortals -*/ -//=========================================================================== -// Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FloodAreas (tree_t *tree) -{ - Log_Print("--- FloodAreas ---\n"); - FindAreas_r (tree->headnode); - SetAreaPortalAreas_r (tree->headnode); - Log_Print("%5i areas\n", c_areas); -} //end of the function FloodAreas -//=========================================================================== -// Finds a brush side to use for texturing the given portal -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void FindPortalSide (portal_t *p) -{ - 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 ; inumsides ; 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void MarkVisibleSides_r (node_t *node) -{ - 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 -//=========================================================================== -// -// Parameter: - -// Returns: - -// Changes Globals: - -//=========================================================================== -void MarkVisibleSides(tree_t *tree, int startbrush, int endbrush) -{ - int i, j; - mapbrush_t *mb; - int numsides; - - Log_Print("--- MarkVisibleSides ---\n"); - - // clear all the visible flags - for (i=startbrush ; inumsides; - for (j=0 ; joriginal_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 - +/* +=========================================================================== +Copyright (C) 1999-2005 Id Software, Inc. + +This file is part of Quake III Arena source code. + +Quake III Arena source code is free software; you can redistribute it +and/or modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of the License, +or (at your option) any later version. + +Quake III Arena source code is distributed in the hope that it will be +useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with Foobar; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA +=========================================================================== +*/ + +#include "qbsp.h" +#include "l_mem.h" + +int c_active_portals; +int c_peak_portals; +int c_boundary; +int c_boundary_sides; +int c_portalmemory; + +//portal_t *portallist = NULL; +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +portal_t *AllocPortal (void) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FreePortal (portal_t *p) +{ + 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 +//=========================================================================== +// Returns the single content bit of the +// strongest visible content present +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +int VisibleContents (int contents) +{ + int i; + + for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1) + if (contents & i ) + return i; + + return 0; +} //end of the function VisibleContents +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +int ClusterContents (node_t *node) +{ + 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 + +//=========================================================================== +// Returns true if the portal is empty or translucent, allowing +// the PVS calculation to see through it. +// The nodes on either side of the portal may actually be clusters, +// not leaves, so all contents should be ored together +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +qboolean Portal_VisFlood (portal_t *p) +{ + int c1, c2; + + if (!p->onnode) + return false; // to global outsideleaf + + c1 = ClusterContents(p->nodes[0]); + c2 = ClusterContents(p->nodes[1]); + + if (!VisibleContents (c1^c2)) + return true; + + if (c1 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL)) + c1 = 0; + if (c2 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL)) + c2 = 0; + + if ( (c1|c2) & CONTENTS_SOLID ) + return false; // can't see through solid + + if (! (c1 ^ c2)) + return true; // identical on both sides + + if (!VisibleContents (c1^c2)) + return true; + return false; +} //end of the function Portal_VisFlood +//=========================================================================== +// The entity flood determines which areas are +// "outside" on the map, which are then filled in. +// Flowing from side s to side !s +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +qboolean Portal_EntityFlood (portal_t *p, int s) +{ + if (p->nodes[0]->planenum != PLANENUM_LEAF + || p->nodes[1]->planenum != PLANENUM_LEAF) + Error ("Portal_EntityFlood: not a leaf"); + + // can never cross to a solid + if ( (p->nodes[0]->contents & CONTENTS_SOLID) + || (p->nodes[1]->contents & CONTENTS_SOLID) ) + return false; + + // can flood through everything else + return true; +} + + +//============================================================================= + +int c_tinyportals; + +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void AddPortalToNodes (portal_t *p, node_t *front, node_t *back) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void RemovePortalFromNode (portal_t *portal, node_t *l) +{ + portal_t **pp, *t; + + int s, i, n; + portal_t *p; + portal_t *portals[4096]; + +// remove reference to the current portal + pp = &l->portals; + while (1) + { + t = *pp; + if (!t) + Error ("RemovePortalFromNode: portal not in leaf"); + + if ( t == portal ) + break; + + if (t->nodes[0] == l) + pp = &t->next[0]; + else if (t->nodes[1] == l) + pp = &t->next[1]; + else + Error ("RemovePortalFromNode: portal not bounding leaf"); + } + + if (portal->nodes[0] == l) + { + *pp = portal->next[0]; + portal->nodes[0] = NULL; + } //end if + else if (portal->nodes[1] == l) + { + *pp = portal->next[1]; + portal->nodes[1] = NULL; + } //end else if + else + { + Error("RemovePortalFromNode: mislinked portal"); + } //end else +//#ifdef ME + n = 0; + for (p = l->portals; p; p = p->next[s]) + { + for (i = 0; i < n; i++) + { + if (p == portals[i]) Error("RemovePortalFromNode: circular linked\n"); + } //end for + if (p->nodes[0] != l && p->nodes[1] != l) + { + Error("RemovePortalFromNodes: portal does not belong to node\n"); + } //end if + portals[n] = p; + s = (p->nodes[1] == l); +// if (++n >= 4096) Error("RemovePortalFromNode: more than 4096 portals\n"); + } //end for +//#endif +} //end of the function RemovePortalFromNode +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void PrintPortal (portal_t *p) +{ + int i; + winding_t *w; + + w = p->winding; + for (i=0 ; inumpoints ; i++) + printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0] + , w->p[i][1], w->p[i][2]); +} //end of the function PrintPortal +//=========================================================================== +// The created portals will face the global outside_node +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +#define SIDESPACE 8 + +void MakeHeadnodePortals (tree_t *tree) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +#define BASE_WINDING_EPSILON 0.001 +#define SPLIT_WINDING_EPSILON 0.001 + +winding_t *BaseWindingForNode (node_t *node) +{ + 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 +//=========================================================================== +// create the new portal by taking the full plane winding for the cutting +// plane and clipping it by all of parents of this node +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +qboolean WindingIsTiny (winding_t *w); + +void MakeNodePortal (node_t *node) +{ + 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 +//=========================================================================== +// Move or split the portals that bound node so that the node's +// children have portals instead of node. +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void SplitNodePortals (node_t *node) +{ + portal_t *p, *next_portal, *new_portal; + node_t *f, *b, *other_node; + int side; + plane_t *plane; + winding_t *frontwinding, *backwinding; + + plane = &mapplanes[node->planenum]; + f = node->children[0]; + b = node->children[1]; + + for (p = node->portals ; p ; p = next_portal) + { + if (p->nodes[0] == node) side = 0; + else if (p->nodes[1] == node) side = 1; + else Error ("SplitNodePortals: mislinked portal"); + next_portal = p->next[side]; + + other_node = p->nodes[!side]; + RemovePortalFromNode (p, p->nodes[0]); + RemovePortalFromNode (p, p->nodes[1]); + +// +// cut the portal into two portals, one on each side of the cut plane +// + ClipWindingEpsilon (p->winding, plane->normal, plane->dist, + SPLIT_WINDING_EPSILON, &frontwinding, &backwinding); + + if (frontwinding && WindingIsTiny(frontwinding)) + { + FreeWinding (frontwinding); + frontwinding = NULL; + c_tinyportals++; + } //end if + + if (backwinding && WindingIsTiny(backwinding)) + { + FreeWinding (backwinding); + backwinding = NULL; + c_tinyportals++; + } //end if + +#ifdef DEBUG +/* //NOTE: don't use this winding ok check + // all the invalid windings only have a degenerate edge + if (frontwinding && WindingError(frontwinding)) + { + Log_Print("SplitNodePortals: front %s\n", WindingErrorString()); + FreeWinding(frontwinding); + frontwinding = NULL; + } //end if + if (backwinding && WindingError(backwinding)) + { + Log_Print("SplitNodePortals: back %s\n", WindingErrorString()); + FreeWinding(backwinding); + backwinding = NULL; + } //end if*/ +#endif //DEBUG + + if (!frontwinding && !backwinding) + { // tiny windings on both sides + continue; + } + + if (!frontwinding) + { + FreeWinding (backwinding); + if (side == 0) AddPortalToNodes (p, b, other_node); + else AddPortalToNodes (p, other_node, b); + continue; + } + if (!backwinding) + { + FreeWinding (frontwinding); + if (side == 0) AddPortalToNodes (p, f, other_node); + else AddPortalToNodes (p, other_node, f); + continue; + } + + // the winding is split + new_portal = AllocPortal(); + *new_portal = *p; + new_portal->winding = backwinding; + FreeWinding (p->winding); + p->winding = frontwinding; + + if (side == 0) + { + AddPortalToNodes (p, f, other_node); + AddPortalToNodes (new_portal, b, other_node); + } //end if + else + { + AddPortalToNodes (p, other_node, f); + AddPortalToNodes (new_portal, other_node, b); + } //end else + } + + node->portals = NULL; +} //end of the function SplitNodePortals +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void CalcNodeBounds (node_t *node) +{ + 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 ; iwinding->numpoints ; i++) + AddPointToBounds (p->winding->p[i], node->mins, node->maxs); + } +} //end of the function CalcNodeBounds +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +int c_numportalizednodes; + +void MakeTreePortals_r (node_t *node) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void MakeTreePortals(tree_t *tree) +{ + +#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 + +/* +========================================================= + +FLOOD ENTITIES + +========================================================= +*/ +//#define P_NODESTACK + +node_t *p_firstnode; +node_t *p_lastnode; + +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +#ifdef P_NODESTACK +void P_AddNodeToList(node_t *node) +{ + node->next = p_firstnode; + p_firstnode = node; + if (!p_lastnode) p_lastnode = node; +} //end of the function P_AddNodeToList +#else //it's a node queue +//add the node to the end of the node list +void P_AddNodeToList(node_t *node) +{ + node->next = NULL; + if (p_lastnode) p_lastnode->next = node; + else p_firstnode = node; + p_lastnode = node; +} //end of the function P_AddNodeToList +#endif //P_NODESTACK +//=========================================================================== +// get the first node from the front of the node list +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +node_t *P_NextNodeFromList(void) +{ + node_t *node; + + node = p_firstnode; + if (p_firstnode) p_firstnode = p_firstnode->next; + if (!p_firstnode) p_lastnode = NULL; + return node; +} //end of the function P_NextNodeFromList +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FloodPortals(node_t *firstnode) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +int numrec; + +void FloodPortals_r (node_t *node, int dist) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant) +{ + node_t *node; + vec_t d; + plane_t *plane; + + //find the leaf to start in + node = headnode; + while(node->planenum != PLANENUM_LEAF) + { + if (node->planenum < 0 || node->planenum > nummapplanes) + { + Error("PlaceOccupant: invalid node->planenum\n"); + } //end if + plane = &mapplanes[node->planenum]; + d = DotProduct(origin, plane->normal) - plane->dist; + if (d >= 0) node = node->children[0]; + else node = node->children[1]; + if (!node) + { + Error("PlaceOccupant: invalid child %d\n", d < 0); + } //end if + } //end while + //don't start in solid +// if (node->contents == CONTENTS_SOLID) + //ME: replaced because in LeafNode in brushbsp.c + // some nodes have contents solid with other contents + if (node->contents & CONTENTS_SOLID) return false; + //if the node is already occupied + if (node->occupied) return false; + + //place the occupant in the first leaf + node->occupant = occupant; + + numrec = 0; +// Log_Print("%6d recurses", numrec); +// FloodPortals_r(node, 1); +// Log_Print("\n"); + FloodPortals(node); + + return true; +} //end of the function PlaceOccupant +//=========================================================================== +// Marks all nodes that can be reached by entites +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +qboolean FloodEntities (tree_t *tree) +{ + 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 + +/* +========================================================= + +FILL OUTSIDE + +========================================================= +*/ + +int c_outside; +int c_inside; +int c_solid; + +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FillOutside_r (node_t *node) +{ + 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 +//=========================================================================== +// Fill all nodes that can't be reached by entities +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FillOutside (node_t *headnode) +{ + 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 + +/* +========================================================= + +FLOOD AREAS + +========================================================= +*/ + +int c_areas; + +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FloodAreas_r (node_t *node) +{ + 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 +//=========================================================================== +// Just decend the tree, and for each node that hasn't had an +// area set, flood fill out from there +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FindAreas_r (node_t *node) +{ + 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 +//=========================================================================== +// Just decend the tree, and for each node that hasn't had an +// area set, flood fill out from there +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void SetAreaPortalAreas_r (node_t *node) +{ + bspbrush_t *b; + entity_t *e; + + if (node->planenum != PLANENUM_LEAF) + { + SetAreaPortalAreas_r (node->children[0]); + SetAreaPortalAreas_r (node->children[1]); + return; + } //end if + + if (node->contents == CONTENTS_AREAPORTAL) + { + if (node->area) + return; // allready set + + b = node->brushlist; + e = &entities[b->original->entitynum]; + node->area = e->portalareas[0]; + if (!e->portalareas[1]) + { + Log_Print("WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum); + return; + } //end if + } //end if +} //end of the function SetAreaPortalAreas_r +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +/* +void EmitAreaPortals(node_t *headnode) +{ + int i, j; + entity_t *e; + dareaportal_t *dp; + + if (c_areas > MAX_MAP_AREAS) + Error ("MAX_MAP_AREAS"); + numareas = c_areas+1; + numareaportals = 1; // leave 0 as an error + + for (i=1 ; i<=c_areas ; i++) + { + dareas[i].firstareaportal = numareaportals; + for (j=0 ; jareaportalnum) + continue; + dp = &dareaportals[numareaportals]; + if (e->portalareas[0] == i) + { + dp->portalnum = e->areaportalnum; + dp->otherarea = e->portalareas[1]; + numareaportals++; + } //end if + else if (e->portalareas[1] == i) + { + dp->portalnum = e->areaportalnum; + dp->otherarea = e->portalareas[0]; + numareaportals++; + } //end else if + } //end for + dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal; + } //end for + + Log_Print("%5i numareas\n", numareas); + Log_Print("%5i numareaportals\n", numareaportals); +} //end of the function EmitAreaPortals +*/ +//=========================================================================== +// Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FloodAreas (tree_t *tree) +{ + Log_Print("--- FloodAreas ---\n"); + FindAreas_r (tree->headnode); + SetAreaPortalAreas_r (tree->headnode); + Log_Print("%5i areas\n", c_areas); +} //end of the function FloodAreas +//=========================================================================== +// Finds a brush side to use for texturing the given portal +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void FindPortalSide (portal_t *p) +{ + 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 ; inumsides ; 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void MarkVisibleSides_r (node_t *node) +{ + 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 +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void MarkVisibleSides(tree_t *tree, int startbrush, int endbrush) +{ + int i, j; + mapbrush_t *mb; + int numsides; + + Log_Print("--- MarkVisibleSides ---\n"); + + // clear all the visible flags + for (i=startbrush ; inumsides; + for (j=0 ; joriginal_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 + -- cgit v1.2.3