aboutsummaryrefslogtreecommitdiffstats
path: root/code/bspc/portals.c
diff options
context:
space:
mode:
Diffstat (limited to 'code/bspc/portals.c')
-rw-r--r--code/bspc/portals.c1297
1 files changed, 0 insertions, 1297 deletions
diff --git a/code/bspc/portals.c b/code/bspc/portals.c
deleted file mode 100644
index 0c03aaf..0000000
--- a/code/bspc/portals.c
+++ /dev/null
@@ -1,1297 +0,0 @@
-/*
-===========================================================================
-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 Quake III Arena source code; 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
-
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-30 17:32:56 +0000