From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- q3map/portals.c | 1644 +++++++++++++++++++++++++++---------------------------- 1 file changed, 822 insertions(+), 822 deletions(-) (limited to 'q3map/portals.c') diff --git a/q3map/portals.c b/q3map/portals.c index dee708f..059760f 100755 --- a/q3map/portals.c +++ b/q3map/portals.c @@ -19,825 +19,825 @@ 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" - - -int c_active_portals; -int c_peak_portals; -int c_boundary; -int c_boundary_sides; - -/* -=========== -AllocPortal -=========== -*/ -portal_t *AllocPortal (void) -{ - portal_t *p; - - if (numthreads == 1) - c_active_portals++; - if (c_active_portals > c_peak_portals) - c_peak_portals = c_active_portals; - - p = malloc (sizeof(portal_t)); - memset (p, 0, sizeof(portal_t)); - - return p; -} - -void FreePortal (portal_t *p) -{ - if (p->winding) - FreeWinding (p->winding); - if (numthreads == 1) - c_active_portals--; - free (p); -} - -//============================================================== - -/* -============= -Portal_Passable - -Returns true if the portal has non-opaque leafs on both sides -============= -*/ -qboolean Portal_Passable(portal_t *p) { - if (!p->onnode) { - return qfalse; // to global outsideleaf - } - - if (p->nodes[0]->planenum != PLANENUM_LEAF - || p->nodes[1]->planenum != PLANENUM_LEAF) { - Error ("Portal_EntityFlood: not a leaf"); - } - - if ( !p->nodes[0]->opaque && !p->nodes[1]->opaque ) { - return qtrue; - } - - return qfalse; -} - - -//============================================================================= - -int c_tinyportals; - -/* -============= -AddPortalToNodes -============= -*/ -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; -} - - -/* -============= -RemovePortalFromNode -============= -*/ -void RemovePortalFromNode (portal_t *portal, node_t *l) -{ - portal_t **pp, *t; - -// 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; - } - else if (portal->nodes[1] == l) - { - *pp = portal->next[1]; - portal->nodes[1] = NULL; - } -} - -//============================================================================ - -void PrintPortal (portal_t *p) -{ - int i; - winding_t *w; - - w = p->winding; - for (i=0 ; inumpoints ; i++) - _printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0] - , w->p[i][1], w->p[i][2]); -} - -/* -================ -MakeHeadnodePortals - -The created portals will face the global outside_node -================ -*/ -#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 leafs - 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( "Backwards tree volume" ); - } - } - - tree->outside_node.planenum = PLANENUM_LEAF; - tree->outside_node.brushlist = NULL; - tree->outside_node.portals = NULL; - tree->outside_node.opaque = qfalse; - - 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); - } - } -} - -//=================================================== - - -/* -================ -BaseWindingForNode -================ -*/ -#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; -} - -//============================================================ - -/* -================== -MakeNodePortal - -create the new portal by taking the full plane winding for the cutting plane -and clipping it by all of parents of this node -================== -*/ -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; - } - else if (p->nodes[1] == node) - { - side = 1; - VectorSubtract (vec3_origin, p->plane.normal, normal); - dist = -p->plane.dist; - } - else - Error ("CutNodePortals_r: mislinked portal"); - - ChopWindingInPlace (&w, normal, dist, CLIP_EPSILON); - } - - if (!w) - { - return; - } - - if (WindingIsTiny (w)) - { - c_tinyportals++; - FreeWinding (w); - return; - } - - new_portal = AllocPortal (); - new_portal->plane = mapplanes[node->planenum]; - new_portal->onnode = node; - new_portal->winding = w; - new_portal->hint = node->hint; - AddPortalToNodes (new_portal, node->children[0], node->children[1]); -} - - -/* -============== -SplitNodePortals - -Move or split the portals that bound node so that the node's -children have portals instead of node. -============== -*/ -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)) - { - if (!f->tinyportals) - VectorCopy(frontwinding->p[0], f->referencepoint); - f->tinyportals++; - if (!other_node->tinyportals) - VectorCopy(frontwinding->p[0], other_node->referencepoint); - other_node->tinyportals++; - - FreeWinding (frontwinding); - frontwinding = NULL; - c_tinyportals++; - } - - if (backwinding && WindingIsTiny(backwinding)) - { - if (!b->tinyportals) - VectorCopy(backwinding->p[0], b->referencepoint); - b->tinyportals++; - if (!other_node->tinyportals) - VectorCopy(backwinding->p[0], other_node->referencepoint); - other_node->tinyportals++; - - FreeWinding (backwinding); - backwinding = NULL; - c_tinyportals++; - } - - 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); - } - else - { - AddPortalToNodes (p, other_node, f); - AddPortalToNodes (new_portal, other_node, b); - } - } - - node->portals = NULL; -} - - -/* -================ -CalcNodeBounds -================ -*/ -void CalcNodeBounds (node_t *node) -{ - portal_t *p; - int s; - int i; - - // calc mins/maxs for both leafs and nodes - ClearBounds (node->mins, node->maxs); - for (p = node->portals ; p ; p = p->next[s]) - { - s = (p->nodes[1] == node); - for (i=0 ; iwinding->numpoints ; i++) - AddPointToBounds (p->winding->p[i], node->mins, node->maxs); - } -} - -/* -================== -MakeTreePortals_r -================== -*/ -void MakeTreePortals_r (node_t *node) -{ - int i; - - CalcNodeBounds (node); - if (node->mins[0] >= node->maxs[0]) - { - _printf ("WARNING: node without a volume\n"); - _printf("node has %d tiny portals\n", node->tinyportals); - _printf("node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0], - node->referencepoint[1], - node->referencepoint[2]); - } - - for (i=0 ; i<3 ; i++) - { - if (node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD) - { - _printf ("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]); -} - -/* -================== -MakeTreePortals -================== -*/ -void MakeTreePortals (tree_t *tree) -{ - qprintf( "----- MakeTreePortals -----\n"); - MakeHeadnodePortals (tree); - MakeTreePortals_r (tree->headnode); - qprintf("%6d tiny portals\n", c_tinyportals); -} - -/* -========================================================= - -FLOOD ENTITIES - -========================================================= -*/ - -int c_floodedleafs; - -/* -============= -FloodPortals_r -============= -*/ -void FloodPortals_r (node_t *node, int dist) { - portal_t *p; - int s; - - if ( node->occupied ) { - return; - } - - if ( node->opaque ) { - return; - } - - c_floodedleafs++; - node->occupied = dist; - - for (p=node->portals ; p ; p = p->next[s]) { - s = (p->nodes[1] == node); - FloodPortals_r (p->nodes[!s], dist+1); - } -} - -/* -============= -PlaceOccupant -============= -*/ -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) - { - 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->opaque ) - return qfalse; - node->occupant = occupant; - - FloodPortals_r (node, 1); - - return qtrue; -} - -/* -============= -FloodEntities - -Marks all nodes that can be reached by entites -============= -*/ -qboolean FloodEntities( tree_t *tree ) { - int i; - vec3_t origin; - const char *cl; - qboolean inside; - node_t *headnode; - - headnode = tree->headnode; - qprintf ("--- FloodEntities ---\n"); - inside = qfalse; - tree->outside_node.occupied = 0; - - c_floodedleafs = 0; - for (i=1 ; ioutside_node.occupied) - { - qprintf ("entity reached from outside -- no filling\n"); - } - - return (qboolean)(inside && !tree->outside_node.occupied); -} - -/* -========================================================= - -FLOOD AREAS - -========================================================= -*/ - -int c_areas; - -/* -============= -FloodAreas_r -============= -*/ -void FloodAreas_r (node_t *node) -{ - portal_t *p; - int s; - bspbrush_t *b; - - if ( node->areaportal ) { - // - if ( node->area == -1 ) { - node->area = c_areas; - } - // this node is part of an area portal brush - b = node->brushlist->original; - - // if the current area has allready touched this - // portal, we are done - if (b->portalareas[0] == c_areas || b->portalareas[1] == c_areas) - return; - - // note the current area as bounding the portal - if (b->portalareas[1] != -1) - { - _printf ("WARNING: areaportal brush %i touches > 2 areas\n", b->brushnum ); - return; - } - if (b->portalareas[0] != -1) { - b->portalareas[1] = c_areas; - } else { - b->portalareas[0] = c_areas; - } - - return; - } - - if (node->area != -1) { - return; // allready got it - } - if ( node->cluster == -1 ) { - return; - } - - node->area = c_areas; - - for (p=node->portals ; p ; p = p->next[s]) - { - s = (p->nodes[1] == node); - - if ( !Portal_Passable(p) ) - continue; - - FloodAreas_r (p->nodes[!s]); - } -} - - -/* -============= -FindAreas_r - -Just decend the tree, and for each node that hasn't had an -area set, flood fill out from there -============= -*/ -void FindAreas_r (node_t *node) -{ - if (node->planenum != PLANENUM_LEAF) - { - FindAreas_r (node->children[0]); - FindAreas_r (node->children[1]); - return; - } - - if (node->opaque) - return; - - if (node->areaportal) - return; - - if (node->area != -1) - return; // allready got it - - FloodAreas_r (node); - c_areas++; -} - -/* -============= -CheckAreas_r -============= -*/ -void CheckAreas_r (node_t *node) -{ - bspbrush_t *b; - - if (node->planenum != PLANENUM_LEAF) - { - CheckAreas_r (node->children[0]); - CheckAreas_r (node->children[1]); - return; - } - - if (node->opaque) - return; - - if (node->cluster != -1) - if (node->area == -1) - _printf("WARNING: cluster %d has area set to -1\n", node->cluster); - if (node->areaportal) - { - b = node->brushlist->original; - - // check if the areaportal touches two areas - if (b->portalareas[0] == -1 || b->portalareas[1] == -1) - _printf ("WARNING: areaportal brush %i doesn't touch two areas\n", b->brushnum); - } -} - -/* -============= -FloodAreas - -Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL -============= -*/ -void FloodAreas (tree_t *tree) -{ - qprintf ("--- FloodAreas ---\n"); - FindAreas_r( tree->headnode ); - - // check for areaportal brushes that don't touch two areas - CheckAreas_r( tree->headnode ); - - qprintf ("%5i areas\n", c_areas); -} - -//====================================================== - -int c_outside; -int c_inside; -int c_solid; - -void FillOutside_r (node_t *node) -{ - if (node->planenum != PLANENUM_LEAF) - { - FillOutside_r (node->children[0]); - FillOutside_r (node->children[1]); - return; - } - - // anything not reachable by an entity - // can be filled away - if (!node->occupied) { - if ( !node->opaque ) { - c_outside++; - node->opaque = qtrue; - } else { - c_solid++; - } - } else { - c_inside++; - } - -} - -/* -============= -FillOutside - -Fill all nodes that can't be reached by entities -============= -*/ -void FillOutside (node_t *headnode) -{ - c_outside = 0; - c_inside = 0; - c_solid = 0; - qprintf ("--- FillOutside ---\n"); - FillOutside_r (headnode); - qprintf ("%5i solid leafs\n", c_solid); - qprintf ("%5i leafs filled\n", c_outside); - qprintf ("%5i inside leafs\n", c_inside); -} - - -//============================================================== - + +#include "qbsp.h" + + +int c_active_portals; +int c_peak_portals; +int c_boundary; +int c_boundary_sides; + +/* +=========== +AllocPortal +=========== +*/ +portal_t *AllocPortal (void) +{ + portal_t *p; + + if (numthreads == 1) + c_active_portals++; + if (c_active_portals > c_peak_portals) + c_peak_portals = c_active_portals; + + p = malloc (sizeof(portal_t)); + memset (p, 0, sizeof(portal_t)); + + return p; +} + +void FreePortal (portal_t *p) +{ + if (p->winding) + FreeWinding (p->winding); + if (numthreads == 1) + c_active_portals--; + free (p); +} + +//============================================================== + +/* +============= +Portal_Passable + +Returns true if the portal has non-opaque leafs on both sides +============= +*/ +qboolean Portal_Passable(portal_t *p) { + if (!p->onnode) { + return qfalse; // to global outsideleaf + } + + if (p->nodes[0]->planenum != PLANENUM_LEAF + || p->nodes[1]->planenum != PLANENUM_LEAF) { + Error ("Portal_EntityFlood: not a leaf"); + } + + if ( !p->nodes[0]->opaque && !p->nodes[1]->opaque ) { + return qtrue; + } + + return qfalse; +} + + +//============================================================================= + +int c_tinyportals; + +/* +============= +AddPortalToNodes +============= +*/ +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; +} + + +/* +============= +RemovePortalFromNode +============= +*/ +void RemovePortalFromNode (portal_t *portal, node_t *l) +{ + portal_t **pp, *t; + +// 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; + } + else if (portal->nodes[1] == l) + { + *pp = portal->next[1]; + portal->nodes[1] = NULL; + } +} + +//============================================================================ + +void PrintPortal (portal_t *p) +{ + int i; + winding_t *w; + + w = p->winding; + for (i=0 ; inumpoints ; i++) + _printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0] + , w->p[i][1], w->p[i][2]); +} + +/* +================ +MakeHeadnodePortals + +The created portals will face the global outside_node +================ +*/ +#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 leafs + 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( "Backwards tree volume" ); + } + } + + tree->outside_node.planenum = PLANENUM_LEAF; + tree->outside_node.brushlist = NULL; + tree->outside_node.portals = NULL; + tree->outside_node.opaque = qfalse; + + 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); + } + } +} + +//=================================================== + + +/* +================ +BaseWindingForNode +================ +*/ +#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; +} + +//============================================================ + +/* +================== +MakeNodePortal + +create the new portal by taking the full plane winding for the cutting plane +and clipping it by all of parents of this node +================== +*/ +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; + } + else if (p->nodes[1] == node) + { + side = 1; + VectorSubtract (vec3_origin, p->plane.normal, normal); + dist = -p->plane.dist; + } + else + Error ("CutNodePortals_r: mislinked portal"); + + ChopWindingInPlace (&w, normal, dist, CLIP_EPSILON); + } + + if (!w) + { + return; + } + + if (WindingIsTiny (w)) + { + c_tinyportals++; + FreeWinding (w); + return; + } + + new_portal = AllocPortal (); + new_portal->plane = mapplanes[node->planenum]; + new_portal->onnode = node; + new_portal->winding = w; + new_portal->hint = node->hint; + AddPortalToNodes (new_portal, node->children[0], node->children[1]); +} + + +/* +============== +SplitNodePortals + +Move or split the portals that bound node so that the node's +children have portals instead of node. +============== +*/ +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)) + { + if (!f->tinyportals) + VectorCopy(frontwinding->p[0], f->referencepoint); + f->tinyportals++; + if (!other_node->tinyportals) + VectorCopy(frontwinding->p[0], other_node->referencepoint); + other_node->tinyportals++; + + FreeWinding (frontwinding); + frontwinding = NULL; + c_tinyportals++; + } + + if (backwinding && WindingIsTiny(backwinding)) + { + if (!b->tinyportals) + VectorCopy(backwinding->p[0], b->referencepoint); + b->tinyportals++; + if (!other_node->tinyportals) + VectorCopy(backwinding->p[0], other_node->referencepoint); + other_node->tinyportals++; + + FreeWinding (backwinding); + backwinding = NULL; + c_tinyportals++; + } + + 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); + } + else + { + AddPortalToNodes (p, other_node, f); + AddPortalToNodes (new_portal, other_node, b); + } + } + + node->portals = NULL; +} + + +/* +================ +CalcNodeBounds +================ +*/ +void CalcNodeBounds (node_t *node) +{ + portal_t *p; + int s; + int i; + + // calc mins/maxs for both leafs and nodes + ClearBounds (node->mins, node->maxs); + for (p = node->portals ; p ; p = p->next[s]) + { + s = (p->nodes[1] == node); + for (i=0 ; iwinding->numpoints ; i++) + AddPointToBounds (p->winding->p[i], node->mins, node->maxs); + } +} + +/* +================== +MakeTreePortals_r +================== +*/ +void MakeTreePortals_r (node_t *node) +{ + int i; + + CalcNodeBounds (node); + if (node->mins[0] >= node->maxs[0]) + { + _printf ("WARNING: node without a volume\n"); + _printf("node has %d tiny portals\n", node->tinyportals); + _printf("node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0], + node->referencepoint[1], + node->referencepoint[2]); + } + + for (i=0 ; i<3 ; i++) + { + if (node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD) + { + _printf ("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]); +} + +/* +================== +MakeTreePortals +================== +*/ +void MakeTreePortals (tree_t *tree) +{ + qprintf( "----- MakeTreePortals -----\n"); + MakeHeadnodePortals (tree); + MakeTreePortals_r (tree->headnode); + qprintf("%6d tiny portals\n", c_tinyportals); +} + +/* +========================================================= + +FLOOD ENTITIES + +========================================================= +*/ + +int c_floodedleafs; + +/* +============= +FloodPortals_r +============= +*/ +void FloodPortals_r (node_t *node, int dist) { + portal_t *p; + int s; + + if ( node->occupied ) { + return; + } + + if ( node->opaque ) { + return; + } + + c_floodedleafs++; + node->occupied = dist; + + for (p=node->portals ; p ; p = p->next[s]) { + s = (p->nodes[1] == node); + FloodPortals_r (p->nodes[!s], dist+1); + } +} + +/* +============= +PlaceOccupant +============= +*/ +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) + { + 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->opaque ) + return qfalse; + node->occupant = occupant; + + FloodPortals_r (node, 1); + + return qtrue; +} + +/* +============= +FloodEntities + +Marks all nodes that can be reached by entites +============= +*/ +qboolean FloodEntities( tree_t *tree ) { + int i; + vec3_t origin; + const char *cl; + qboolean inside; + node_t *headnode; + + headnode = tree->headnode; + qprintf ("--- FloodEntities ---\n"); + inside = qfalse; + tree->outside_node.occupied = 0; + + c_floodedleafs = 0; + for (i=1 ; ioutside_node.occupied) + { + qprintf ("entity reached from outside -- no filling\n"); + } + + return (qboolean)(inside && !tree->outside_node.occupied); +} + +/* +========================================================= + +FLOOD AREAS + +========================================================= +*/ + +int c_areas; + +/* +============= +FloodAreas_r +============= +*/ +void FloodAreas_r (node_t *node) +{ + portal_t *p; + int s; + bspbrush_t *b; + + if ( node->areaportal ) { + // + if ( node->area == -1 ) { + node->area = c_areas; + } + // this node is part of an area portal brush + b = node->brushlist->original; + + // if the current area has allready touched this + // portal, we are done + if (b->portalareas[0] == c_areas || b->portalareas[1] == c_areas) + return; + + // note the current area as bounding the portal + if (b->portalareas[1] != -1) + { + _printf ("WARNING: areaportal brush %i touches > 2 areas\n", b->brushnum ); + return; + } + if (b->portalareas[0] != -1) { + b->portalareas[1] = c_areas; + } else { + b->portalareas[0] = c_areas; + } + + return; + } + + if (node->area != -1) { + return; // allready got it + } + if ( node->cluster == -1 ) { + return; + } + + node->area = c_areas; + + for (p=node->portals ; p ; p = p->next[s]) + { + s = (p->nodes[1] == node); + + if ( !Portal_Passable(p) ) + continue; + + FloodAreas_r (p->nodes[!s]); + } +} + + +/* +============= +FindAreas_r + +Just decend the tree, and for each node that hasn't had an +area set, flood fill out from there +============= +*/ +void FindAreas_r (node_t *node) +{ + if (node->planenum != PLANENUM_LEAF) + { + FindAreas_r (node->children[0]); + FindAreas_r (node->children[1]); + return; + } + + if (node->opaque) + return; + + if (node->areaportal) + return; + + if (node->area != -1) + return; // allready got it + + FloodAreas_r (node); + c_areas++; +} + +/* +============= +CheckAreas_r +============= +*/ +void CheckAreas_r (node_t *node) +{ + bspbrush_t *b; + + if (node->planenum != PLANENUM_LEAF) + { + CheckAreas_r (node->children[0]); + CheckAreas_r (node->children[1]); + return; + } + + if (node->opaque) + return; + + if (node->cluster != -1) + if (node->area == -1) + _printf("WARNING: cluster %d has area set to -1\n", node->cluster); + if (node->areaportal) + { + b = node->brushlist->original; + + // check if the areaportal touches two areas + if (b->portalareas[0] == -1 || b->portalareas[1] == -1) + _printf ("WARNING: areaportal brush %i doesn't touch two areas\n", b->brushnum); + } +} + +/* +============= +FloodAreas + +Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL +============= +*/ +void FloodAreas (tree_t *tree) +{ + qprintf ("--- FloodAreas ---\n"); + FindAreas_r( tree->headnode ); + + // check for areaportal brushes that don't touch two areas + CheckAreas_r( tree->headnode ); + + qprintf ("%5i areas\n", c_areas); +} + +//====================================================== + +int c_outside; +int c_inside; +int c_solid; + +void FillOutside_r (node_t *node) +{ + if (node->planenum != PLANENUM_LEAF) + { + FillOutside_r (node->children[0]); + FillOutside_r (node->children[1]); + return; + } + + // anything not reachable by an entity + // can be filled away + if (!node->occupied) { + if ( !node->opaque ) { + c_outside++; + node->opaque = qtrue; + } else { + c_solid++; + } + } else { + c_inside++; + } + +} + +/* +============= +FillOutside + +Fill all nodes that can't be reached by entities +============= +*/ +void FillOutside (node_t *headnode) +{ + c_outside = 0; + c_inside = 0; + c_solid = 0; + qprintf ("--- FillOutside ---\n"); + FillOutside_r (headnode); + qprintf ("%5i solid leafs\n", c_solid); + qprintf ("%5i leafs filled\n", c_outside); + qprintf ("%5i inside leafs\n", c_inside); +} + + +//============================================================== + -- cgit v1.2.3