ref: b8c0e4deccffcd668f7d08ffc1fe16147e9e894a
dir: /code/bspc/portals.c/
/*
===========================================================================
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