visflow.c File Reference

#include "vis.h"

Include dependency graph for visflow.c:

Go to the source code of this file.

Functions
int	AddSeperators (winding_t *source, winding_t *pass, qboolean flipclip, plane_t *seperators, int maxseperators)
winding_t *	AllocStackWinding (pstack_t *stack)
void	BasePortalVis (int portalnum)
void	BetterPortalVis (int portalnum)
void	CheckStack (leaf_t *leaf, threaddata_t *thread)
winding_t *	ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
int	CountBits (byte *bits, int numbits)
void	CreatePassages (int portalnum)
void	FreeStackWinding (winding_t *w, pstack_t *stack)
winding_t *	PassageChopWinding (winding_t *in, winding_t *out, plane_t *split)
void	PassageFlow (int portalnum)
void	PassageMemory (void)
void	PassagePortalFlow (int portalnum)
void	PortalFlow (int portalnum)
void	RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
void	RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
void	RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
void	RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
void	SimpleFlood (vportal_t *srcportal, int leafnum)
winding_t *	VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
Variables
int	active
int	c_chop
int	c_flood
int	c_fullskip
int	c_leafskip
int	c_mighttest
int	c_nochop
int	c_portalskip
int	c_vis
int	c_vistest

---

Function Documentation

int AddSeperators (  winding_t *  source, winding_t *  pass, qboolean  flipclip, plane_t *  seperators, int  maxseperators )

Definition at line 1160 of file visflow.c. References d, plane_t::dist, DotProduct, Error(), i, j, k, l, length(), plane_t::normal, winding_t::numpoints, winding_t::points, qboolean, source, sqrt(), v1, v2, vec3_origin, vec3_t, vec_t, and VectorSubtract. Referenced by CreatePassages(). { int i, j, k, l; plane_t plane; vec3_t v1, v2; float d; vec_t length; int counts[3], numseperators; qboolean fliptest; numseperators = 0; // check all combinations for (i=0 ; i<source->numpoints ; i++) { l = (i+1)%source->numpoints; VectorSubtract (source->points[l] , source->points[i], v1); // find a vertex of pass that makes a plane that puts all of the // vertexes of pass on the front side and all of the vertexes of // source on the back side for (j=0 ; j<pass->numpoints ; j++) { VectorSubtract (pass->points[j], source->points[i], v2); plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1]; plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2]; plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0]; // if points don't make a valid plane, skip it length = plane.normal[0] * plane.normal[0] + plane.normal[1] * plane.normal[1] + plane.normal[2] * plane.normal[2]; if (length < ON_EPSILON) continue; length = 1/sqrt(length); plane.normal[0] *= length; plane.normal[1] *= length; plane.normal[2] *= length; plane.dist = DotProduct (pass->points[j], plane.normal); // // find out which side of the generated seperating plane has the // source portal // #if 1 fliptest = qfalse; for (k=0 ; k<source->numpoints ; k++) { if (k == i || k == l) continue; d = DotProduct (source->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) { // source is on the negative side, so we want all // pass and target on the positive side fliptest = qfalse; break; } else if (d > ON_EPSILON) { // source is on the positive side, so we want all // pass and target on the negative side fliptest = qtrue; break; } } if (k == source->numpoints) continue; // planar with source portal #else fliptest = flipclip; #endif // // flip the normal if the source portal is backwards // if (fliptest) { VectorSubtract (vec3_origin, plane.normal, plane.normal); plane.dist = -plane.dist; } #if 1 // // if all of the pass portal points are now on the positive side, // this is the seperating plane // counts[0] = counts[1] = counts[2] = 0; for (k=0 ; k<pass->numpoints ; k++) { if (k==j) continue; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) break; else if (d > ON_EPSILON) counts[0]++; else counts[2]++; } if (k != pass->numpoints) continue; // points on negative side, not a seperating plane if (!counts[0]) continue; // planar with seperating plane #else k = (j+1)%pass->numpoints; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) continue; k = (j+pass->numpoints-1)%pass->numpoints; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) continue; #endif // // flip the normal if we want the back side // if (flipclip) { VectorSubtract (vec3_origin, plane.normal, plane.normal); plane.dist = -plane.dist; } if (numseperators >= maxseperators) Error("max seperators"); seperators[numseperators] = plane; numseperators++; break; } } return numseperators; }

Here is the call graph for this function:

winding_t* AllocStackWinding (  pstack_t *  stack  )

Definition at line 81 of file visflow.c. References Error(), pstack_s::freewindings, i, pstack_t, and pstack_s::windings. Referenced by VisChopWinding(). { int i; for (i=0 ; i<3 ; i++) { if (stack->freewindings[i]) { stack->freewindings[i] = 0; return &stack->windings[i]; } } Error ("AllocStackWinding: failed"); return NULL; }

Here is the call graph for this function:

void BasePortalVis (  int  portalnum  )

Definition at line 1505 of file visflow.c. References c_flood, CountBits(), d, plane_t::dist, DotProduct, j, k, vportal_t::leaf, malloc(), memset(), plane_t::normal, vportal_t::nummightsee, winding_t::numpoints, numportals, p, vportal_t::plane, winding_t::points, portalbytes, vportal_t::portalflood, vportal_t::portalfront, portals, vportal_t::portalvis, vportal_t::removed, SimpleFlood(), w, and vportal_t::winding. Referenced by CalcVis(). { int j, k; vportal_t *tp, *p; float d; winding_t *w; p = portals+portalnum; if (p->removed) return; p->portalfront = malloc (portalbytes); memset (p->portalfront, 0, portalbytes); p->portalflood = malloc (portalbytes); memset (p->portalflood, 0, portalbytes); p->portalvis = malloc (portalbytes); memset (p->portalvis, 0, portalbytes); for (j=0, tp = portals ; j<numportals*2 ; j++, tp++) { if (j == portalnum) continue; if (tp->removed) continue; /* if (farplanedist >= 0) { vec3_t dir; VectorSubtract(p->origin, tp->origin, dir); if (VectorLength(dir) > farplanedist - p->radius - tp->radius) continue; } */ w = tp->winding; for (k=0 ; k<w->numpoints ; k++) { d = DotProduct (w->points[k], p->plane.normal) - p->plane.dist; if (d > ON_EPSILON) break; } if (k == w->numpoints) continue; // no points on front w = p->winding; for (k=0 ; k<w->numpoints ; k++) { d = DotProduct (w->points[k], tp->plane.normal) - tp->plane.dist; if (d < -ON_EPSILON) break; } if (k == w->numpoints) continue; // no points on front p->portalfront[j>>3] |= (1<<(j&7)); } SimpleFlood (p, p->leaf); p->nummightsee = CountBits (p->portalflood, numportals*2); // _printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee); c_flood += p->nummightsee; }

Here is the call graph for this function:

void BetterPortalVis (  int  portalnum  )

Definition at line 1641 of file visflow.c. References c_vis, CountBits(), vportal_t::leaf, vportal_t::nummightsee, numportals, p, vportal_t::portalflood, portals, vportal_t::portalvis, RecursiveLeafBitFlow(), and vportal_t::removed. { vportal_t *p; p = portals+portalnum; if (p->removed) return; RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis); // build leaf vis information p->nummightsee = CountBits (p->portalvis, numportals*2); c_vis += p->nummightsee; }

Here is the call graph for this function:

void CheckStack (  leaf_t *  leaf, threaddata_t *  thread )

Definition at line 64 of file visflow.c. References Error(), pstack_s::leaf, leaf_t, pstack_s::next, p, p2, threaddata_t::pstack_head, and pstack_t. { pstack_t *p, *p2; for (p=thread->pstack_head.next ; p ; p=p->next) { // _printf ("="); if (p->leaf == leaf) Error ("CheckStack: leaf recursion"); for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next) if (p2->leaf == p->leaf) Error ("CheckStack: late leaf recursion"); } // _printf ("\n"); }

Here is the call graph for this function:

winding_t* ClipToSeperators (  winding_t *  source, winding_t *  pass, winding_t *  target, qboolean  flipclip, pstack_t *  stack )

Definition at line 237 of file visflow.c. References d, plane_t::dist, DotProduct, Error(), i, j, k, l, length(), plane_t::normal, winding_t::numpoints, pstack_s::numseperators, vportal_t::origin, winding_t::points, pstack_s::portal, pstack_t, qboolean, vportal_t::radius, pstack_s::seperators, source, sqrt(), v1, v2, vec3_origin, vec3_t, vec_t, VectorSubtract, and VisChopWinding(). Referenced by RecursiveLeafFlow(), and RecursivePassagePortalFlow(). { int i, j, k, l; plane_t plane; vec3_t v1, v2; float d; vec_t length; int counts[3]; qboolean fliptest; // check all combinations for (i=0 ; i<source->numpoints ; i++) { l = (i+1)%source->numpoints; VectorSubtract (source->points[l] , source->points[i], v1); // find a vertex of pass that makes a plane that puts all of the // vertexes of pass on the front side and all of the vertexes of // source on the back side for (j=0 ; j<pass->numpoints ; j++) { VectorSubtract (pass->points[j], source->points[i], v2); plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1]; plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2]; plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0]; // if points don't make a valid plane, skip it length = plane.normal[0] * plane.normal[0] + plane.normal[1] * plane.normal[1] + plane.normal[2] * plane.normal[2]; if (length < ON_EPSILON) continue; length = 1/sqrt(length); plane.normal[0] *= length; plane.normal[1] *= length; plane.normal[2] *= length; plane.dist = DotProduct (pass->points[j], plane.normal); // // find out which side of the generated seperating plane has the // source portal // #if 1 fliptest = qfalse; for (k=0 ; k<source->numpoints ; k++) { if (k == i || k == l) continue; d = DotProduct (source->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) { // source is on the negative side, so we want all // pass and target on the positive side fliptest = qfalse; break; } else if (d > ON_EPSILON) { // source is on the positive side, so we want all // pass and target on the negative side fliptest = qtrue; break; } } if (k == source->numpoints) continue; // planar with source portal #else fliptest = flipclip; #endif // // flip the normal if the source portal is backwards // if (fliptest) { VectorSubtract (vec3_origin, plane.normal, plane.normal); plane.dist = -plane.dist; } #if 1 // // if all of the pass portal points are now on the positive side, // this is the seperating plane // counts[0] = counts[1] = counts[2] = 0; for (k=0 ; k<pass->numpoints ; k++) { if (k==j) continue; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) break; else if (d > ON_EPSILON) counts[0]++; else counts[2]++; } if (k != pass->numpoints) continue; // points on negative side, not a seperating plane if (!counts[0]) continue; // planar with seperating plane #else k = (j+1)%pass->numpoints; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) continue; k = (j+pass->numpoints-1)%pass->numpoints; d = DotProduct (pass->points[k], plane.normal) - plane.dist; if (d < -ON_EPSILON) continue; #endif // // flip the normal if we want the back side // if (flipclip) { VectorSubtract (vec3_origin, plane.normal, plane.normal); plane.dist = -plane.dist; } #ifdef SEPERATORCACHE stack->seperators[flipclip][stack->numseperators[flipclip]] = plane; if (++stack->numseperators[flipclip] >= MAX_SEPERATORS) Error("MAX_SEPERATORS"); #endif //MrE: fast check first d = DotProduct (stack->portal->origin, plane.normal) - plane.dist; //if completely at the back of the seperator plane if (d < -stack->portal->radius) return NULL; //if completely on the front of the seperator plane if (d > stack->portal->radius) break; // // clip target by the seperating plane // target = VisChopWinding (target, stack, &plane); if (!target) return NULL; // target is not visible break; // optimization by Antony Suter } } return target; }

Here is the call graph for this function:

int CountBits (  byte *  bits, int  numbits )

Definition at line 43 of file visflow.c. References bits, byte, c, and i. Referenced by BasePortalVis(), BetterPortalVis(), LeafVectorFromPortalVector(), and PortalFlow(). { int i; int c; c = 0; for (i=0 ; i<numbits ; i++) if (bits[i>>3] & (1<<(i&7)) ) c++; return c; }

void CreatePassages (  int  portalnum  )

Definition at line 1303 of file visflow.c. References _printf(), AddSeperators(), passage_s::cansee, d, plane_t::dist, DotProduct, i, in, j, k, vportal_t::leaf, leaf_t, leafs, malloc(), MAX_SEPERATORS, memcpy(), memset(), n, passage_s::next, plane_t::normal, winding_t::numpoints, numportals, leaf_s::numportals, vportal_t::origin, p, passage_t, PassageChopWinding(), vportal_t::passages, winding_t::points, portalbytes, vportal_t::portalflood, portals, leaf_s::portals, qfalse, qtrue, vportal_t::radius, vportal_t::removed, sorted_portals, vportal_t::status, w, and vportal_t::winding. Referenced by CalcPassagePortalVis(), and CalcPassageVis(). { int i, j, k, n, numseperators, numsee; float d; vportal_t *portal, *p, *target; leaf_t *leaf; passage_t *passage, *lastpassage; plane_t seperators[MAX_SEPERATORS*2]; winding_t *w; winding_t in, out, *res; #ifdef MREDEBUG _printf("\r%6d", portalnum); #endif portal = sorted_portals[portalnum]; if (portal->removed) { portal->status = stat_done; return; } lastpassage = NULL; leaf = &leafs[portal->leaf]; for (i = 0; i < leaf->numportals; i++) { target = leaf->portals[i]; if (target->removed) continue; passage = (passage_t *) malloc(sizeof(passage_t) + portalbytes); memset(passage, 0, sizeof(passage_t) + portalbytes); numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2); numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators); passage->next = NULL; if (lastpassage) lastpassage->next = passage; else portal->passages = passage; lastpassage = passage; numsee = 0; //create the passage->cansee for (j = 0; j < numportals * 2; j++) { p = &portals[j]; if (p->removed) continue; if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) ) continue; if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) ) continue; for (k = 0; k < numseperators; k++) { // d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist; //if completely at the back of the seperator plane if (d < -p->radius + ON_EPSILON) break; w = p->winding; for (n = 0; n < w->numpoints; n++) { d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist; //if at the front of the seperator if (d > ON_EPSILON) break; } //if no points are at the front of the seperator if (n >= w->numpoints) break; } if (k < numseperators) continue; memcpy(&in, p->winding, sizeof(winding_t)); for (k = 0; k < numseperators; k++) { res = PassageChopWinding(&in, &out, &seperators[k]); if (res == &out) memcpy(&in, &out, sizeof(winding_t)); if (res == NULL) break; } if (k < numseperators) continue; passage->cansee[j >> 3] |= (1<<(j&7)); numsee++; } } }

Here is the call graph for this function:

void FreeStackWinding (  winding_t *  w, pstack_t *  stack )

Definition at line 99 of file visflow.c. References Error(), pstack_s::freewindings, i, pstack_t, w, and pstack_s::windings. Referenced by VisChopWinding(). { int i; i = w - stack->windings; if (i<0 || i>2) return; // not from local if (stack->freewindings[i]) Error ("FreeStackWinding: allready free"); stack->freewindings[i] = 1; }

Here is the call graph for this function:

winding_t* PassageChopWinding (  winding_t *  in, winding_t *  out, plane_t *  split )

Definition at line 1059 of file visflow.c. References plane_t::dist, DotProduct, i, in, j, plane_t::normal, winding_t::numpoints, p2, winding_t::points, SIDE_ON, vec3_t, vec_t, and VectorCopy. Referenced by CreatePassages(). { vec_t dists[128]; int sides[128]; int counts[3]; vec_t dot; int i, j; vec_t *p1, *p2; vec3_t mid; winding_t *neww; counts[0] = counts[1] = counts[2] = 0; // determine sides for each point for (i=0 ; i<in->numpoints ; i++) { dot = DotProduct (in->points[i], split->normal); dot -= split->dist; dists[i] = dot; if (dot > ON_EPSILON) sides[i] = SIDE_FRONT; else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK; else { sides[i] = SIDE_ON; } counts[sides[i]]++; } if (!counts[1]) return in; // completely on front side if (!counts[0]) { return NULL; } sides[i] = sides[0]; dists[i] = dists[0]; neww = out; neww->numpoints = 0; for (i=0 ; i<in->numpoints ; i++) { p1 = in->points[i]; if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING) { return in; // can't chop -- fall back to original } if (sides[i] == SIDE_ON) { VectorCopy (p1, neww->points[neww->numpoints]); neww->numpoints++; continue; } if (sides[i] == SIDE_FRONT) { VectorCopy (p1, neww->points[neww->numpoints]); neww->numpoints++; } if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) continue; if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING) { return in; // can't chop -- fall back to original } // generate a split point p2 = in->points[(i+1)%in->numpoints]; dot = dists[i] / (dists[i]-dists[i+1]); for (j=0 ; j<3 ; j++) { // avoid round off error when possible if (split->normal[j] == 1) mid[j] = split->dist; else if (split->normal[j] == -1) mid[j] = -split->dist; else mid[j] = p1[j] + dot*(p2[j]-p1[j]); } VectorCopy (mid, neww->points[neww->numpoints]); neww->numpoints++; } return neww; }

void PassageFlow (  int  portalnum  )

Definition at line 751 of file visflow.c. References _printf(), data, i, memset(), p, vportal_t::plane, vportal_t::portalflood, RecursivePassageFlow(), vportal_t::removed, sorted_portals, vportal_t::status, and vportal_t::winding. Referenced by CalcPassageVis(). { threaddata_t data; int i; vportal_t *p; // int c_might, c_can; #ifdef MREDEBUG _printf("\r%6d", portalnum); #endif p = sorted_portals[portalnum]; if (p->removed) { p->status = stat_done; return; } p->status = stat_working; // c_might = CountBits (p->portalflood, numportals*2); memset (&data, 0, sizeof(data)); data.base = p; data.pstack_head.portal = p; data.pstack_head.source = p->winding; data.pstack_head.portalplane = p->plane; data.pstack_head.depth = 0; for (i=0 ; i<portallongs ; i++) ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i]; RecursivePassageFlow (p, &data, &data.pstack_head); p->status = stat_done; /* c_can = CountBits (p->portalvis, numportals*2); qprintf ("portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", (int)(p - portals), c_might, c_can, data.c_chains); */ }

Here is the call graph for this function:

void PassageMemory (  void   )

Definition at line 1395 of file visflow.c. References _printf(), i, j, vportal_t::leaf, leaf_t, leafs, numportals, leaf_s::numportals, passage_t, leaf_s::portals, vportal_t::removed, and sorted_portals. Referenced by CalcPassagePortalVis(), and CalcPassageVis(). { int i, j, totalmem, totalportals; vportal_t *portal, *target; leaf_t *leaf; totalmem = 0; totalportals = 0; for (i = 0; i < numportals; i++) { portal = sorted_portals[i]; if (portal->removed) continue; leaf = &leafs[portal->leaf]; for (j = 0; j < leaf->numportals; j++) { target = leaf->portals[j]; if (target->removed) continue; totalmem += sizeof(passage_t) + portalbytes; totalportals++; } } _printf("%7i average number of passages per leaf\n", totalportals / numportals); _printf("%7i MB required passage memory\n", totalmem >> 10 >> 10); }

Here is the call graph for this function:

void PassagePortalFlow (  int  portalnum  )

Definition at line 1014 of file visflow.c. References _printf(), data, i, memset(), p, vportal_t::plane, vportal_t::portalflood, RecursivePassagePortalFlow(), vportal_t::removed, sorted_portals, vportal_t::status, and vportal_t::winding. Referenced by CalcPassagePortalVis(). { threaddata_t data; int i; vportal_t *p; // int c_might, c_can; #ifdef MREDEBUG _printf("\r%6d", portalnum); #endif p = sorted_portals[portalnum]; if (p->removed) { p->status = stat_done; return; } p->status = stat_working; // c_might = CountBits (p->portalflood, numportals*2); memset (&data, 0, sizeof(data)); data.base = p; data.pstack_head.portal = p; data.pstack_head.source = p->winding; data.pstack_head.portalplane = p->plane; data.pstack_head.depth = 0; for (i=0 ; i<portallongs ; i++) ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i]; RecursivePassagePortalFlow (p, &data, &data.pstack_head); p->status = stat_done; /* c_can = CountBits (p->portalvis, numportals*2); qprintf ("portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", (int)(p - portals), c_might, c_can, data.c_chains); */ }

Here is the call graph for this function:

void PortalFlow (  int  portalnum  )

Definition at line 624 of file visflow.c. References _printf(), CountBits(), data, i,