diff options
author | zakk <zakk@edf5b092-35ff-0310-97b2-ce42778d08ea> | 2005-08-26 17:39:27 +0000 |
---|---|---|
committer | zakk <zakk@edf5b092-35ff-0310-97b2-ce42778d08ea> | 2005-08-26 17:39:27 +0000 |
commit | 6bf20c78f5b69d40bcc4931df93d29198435ab67 (patch) | |
tree | e3eda937a05d7db42de725b7013bd0344b987f34 /code/bspc/portals.c | |
parent | 872d4d7f55af706737ffb361bb76ad13e7496770 (diff) | |
download | ioquake3-aero-6bf20c78f5b69d40bcc4931df93d29198435ab67.tar.gz ioquake3-aero-6bf20c78f5b69d40bcc4931df93d29198435ab67.zip |
newlines fixed
git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea
Diffstat (limited to 'code/bspc/portals.c')
-rwxr-xr-x | code/bspc/portals.c | 2594 |
1 files changed, 1297 insertions, 1297 deletions
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 ; i<w->numpoints ; 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 ; i<p->winding->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 ; j<num_entities ; j++)
- {
- e = &entities[j];
- if (!e->areaportalnum)
- 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 ; 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
-//===========================================================================
-//
-// 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 ; 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
-
+/* +=========================================================================== +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 ; i<w->numpoints ; 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 ; i<p->winding->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 ; j<num_entities ; j++) + { + e = &entities[j]; + if (!e->areaportalnum) + 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 ; 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 +//=========================================================================== +// +// 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 ; 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 + |