diff options
Diffstat (limited to 'q3map/visflow.c')
| -rw-r--r-- | q3map/visflow.c | 1657 |
1 files changed, 0 insertions, 1657 deletions
diff --git a/q3map/visflow.c b/q3map/visflow.c deleted file mode 100644 index 5948b08..0000000 --- a/q3map/visflow.c +++ /dev/null @@ -1,1657 +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 Foobar; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -=========================================================================== -*/ -#include "vis.h" - -/* - - each portal will have a list of all possible to see from first portal - - if (!thread->portalmightsee[portalnum]) - - portal mightsee - - for p2 = all other portals in leaf - get sperating planes - for all portals that might be seen by p2 - mark as unseen if not present in seperating plane - flood fill a new mightsee - save as passagemightsee - - - void CalcMightSee (leaf_t *leaf, -*/ - -int CountBits (byte *bits, int numbits) -{ - int i; - int c; - - c = 0; - for (i=0 ; i<numbits ; i++) - if (bits[i>>3] & (1<<(i&7)) ) - c++; - - return c; -} - -int c_fullskip; -int c_portalskip, c_leafskip; -int c_vistest, c_mighttest; - -int c_chop, c_nochop; - -int active; - -void CheckStack (leaf_t *leaf, threaddata_t *thread) -{ - 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"); -} - - -winding_t *AllocStackWinding (pstack_t *stack) -{ - 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; -} - -void FreeStackWinding (winding_t *w, pstack_t *stack) -{ - 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; -} - -/* -============== -VisChopWinding - -============== -*/ -winding_t *VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split) -{ - 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]) - { - FreeStackWinding (in, stack); - return NULL; - } - - sides[i] = sides[0]; - dists[i] = dists[0]; - - neww = AllocStackWinding (stack); - - neww->numpoints = 0; - - for (i=0 ; i<in->numpoints ; i++) - { - p1 = in->points[i]; - - if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING) - { - FreeStackWinding (neww, stack); - 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) - { - FreeStackWinding (neww, stack); - 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++; - } - - // free the original winding - FreeStackWinding (in, stack); - - return neww; -} - -/* -============== -ClipToSeperators - -Source, pass, and target are an ordering of portals. - -Generates seperating planes canidates by taking two points from source and one -point from pass, and clips target by them. - -If target is totally clipped away, that portal can not be seen through. - -Normal clip keeps target on the same side as pass, which is correct if the -order goes source, pass, target. If the order goes pass, source, target then -flipclip should be set. -============== -*/ -winding_t *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack) -{ - 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; -} - -/* -================== -RecursiveLeafFlow - -Flood fill through the leafs -If src_portal is NULL, this is the originating leaf -================== -*/ -void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack) -{ - pstack_t stack; - vportal_t *p; - plane_t backplane; - leaf_t *leaf; - int i, j, n; - long *test, *might, *prevmight, *vis, more; - int pnum; - - thread->c_chains++; - - leaf = &leafs[leafnum]; -// CheckStack (leaf, thread); - - prevstack->next = &stack; - - stack.next = NULL; - stack.leaf = leaf; - stack.portal = NULL; - stack.depth = prevstack->depth + 1; - -#ifdef SEPERATORCACHE - stack.numseperators[0] = 0; - stack.numseperators[1] = 0; -#endif - - might = (long *)stack.mightsee; - vis = (long *)thread->base->portalvis; - - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++) - { - p = leaf->portals[i]; - if (p->removed) - continue; - pnum = p - portals; - - /* MrE: portal trace debug code - { - int portaltrace[] = {13, 16, 17, 37}; - pstack_t *s; - - s = &thread->pstack_head; - for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next) - { - if (s->portal->num != portaltrace[j]) - break; - } - if (j >= sizeof(portaltrace)/sizeof(int) - 1) - { - if (p->num == portaltrace[j]) - n = 0; //traced through all the portals - } - } - */ - - if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) - { - continue; // can't possibly see it - } - - // if the portal can't see anything we haven't allready seen, skip it - if (p->status == stat_done) - { - test = (long *)p->portalvis; - } - else - { - test = (long *)p->portalflood; - } - - more = 0; - prevmight = (long *)prevstack->mightsee; - for (j=0 ; j<portallongs ; j++) - { - might[j] = prevmight[j] & test[j]; - more |= (might[j] & ~vis[j]); - } - - if (!more && - (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) ) - { // can't see anything new - continue; - } - - // get plane of portal, point normal into the neighbor leaf - stack.portalplane = p->plane; - VectorSubtract (vec3_origin, p->plane.normal, backplane.normal); - backplane.dist = -p->plane.dist; - -// c_portalcheck++; - - stack.portal = p; - stack.next = NULL; - stack.freewindings[0] = 1; - stack.freewindings[1] = 1; - stack.freewindings[2] = 1; - -#if 1 - { - float d; - - d = DotProduct (p->origin, thread->pstack_head.portalplane.normal); - d -= thread->pstack_head.portalplane.dist; - if (d < -p->radius) - { - continue; - } - else if (d > p->radius) - { - stack.pass = p->winding; - } - else - { - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) - continue; - } - } -#else - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) - continue; -#endif - - -#if 1 - { - float d; - - d = DotProduct (thread->base->origin, p->plane.normal); - d -= p->plane.dist; - //MrE: vis-bug fix - //if (d > p->radius) - if (d > thread->base->radius) - { - continue; - } - //MrE: vis-bug fix - //if (d < -p->radius) - else if (d < -thread->base->radius) - { - stack.source = prevstack->source; - } - else - { - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - //FIXME: shouldn't we create a new source origin and radius for fast checks? - if (!stack.source) - continue; - } - } -#else - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - if (!stack.source) - continue; -#endif - - if (!prevstack->pass) - { // the second leaf can only be blocked if coplanar - - // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); - - RecursiveLeafFlow (p->leaf, thread, &stack); - continue; - } - -#ifdef SEPERATORCACHE - if (stack.numseperators[0]) - { - for (n = 0; n < stack.numseperators[0]; n++) - { - stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]); - if (!stack.pass) - break; // target is not visible - } - if (n < stack.numseperators[0]) - continue; - } - else - { - stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack); - } -#else - stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack); -#endif - if (!stack.pass) - continue; - -#ifdef SEPERATORCACHE - if (stack.numseperators[1]) - { - for (n = 0; n < stack.numseperators[1]; n++) - { - stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]); - if (!stack.pass) - break; // target is not visible - } - } - else - { - stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack); - } -#else - stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack); -#endif - if (!stack.pass) - continue; - - // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); - - // flow through it for real - RecursiveLeafFlow (p->leaf, thread, &stack); - // - stack.next = NULL; - } -} - -/* -=============== -PortalFlow - -generates the portalvis bit vector -=============== -*/ -void PortalFlow (int portalnum) -{ - 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]; - - RecursiveLeafFlow (p->leaf, &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); -} - -/* -================== -RecursivePassageFlow -================== -*/ -void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack) -{ - pstack_t stack; - vportal_t *p; - leaf_t *leaf; - passage_t *passage, *nextpassage; - int i, j; - long *might, *vis, *prevmight, *cansee, *portalvis, more; - int pnum; - - leaf = &leafs[portal->leaf]; - - prevstack->next = &stack; - - stack.next = NULL; - stack.depth = prevstack->depth + 1; - - vis = (long *)thread->base->portalvis; - - passage = portal->passages; - nextpassage = passage; - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++, passage = nextpassage) - { - p = leaf->portals[i]; - if ( p->removed ) { - continue; - } - nextpassage = passage->next; - pnum = p - portals; - - if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) { - continue; // can't possibly see it - } - - // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); - - prevmight = (long *)prevstack->mightsee; - cansee = (long *)passage->cansee; - might = (long *)stack.mightsee; - memcpy(might, prevmight, portalbytes); - if (p->status == stat_done) - portalvis = (long *) p->portalvis; - else - portalvis = (long *) p->portalflood; - more = 0; - for (j = 0; j < portallongs; j++) - { - if (*might) - { - *might &= *cansee++ & *portalvis++; - more |= (*might & ~vis[j]); - } - else - { - cansee++; - portalvis++; - } - might++; - } - - if ( !more ) { - // can't see anything new - continue; - } - - // flow through it for real - RecursivePassageFlow(p, thread, &stack); - - stack.next = NULL; - } -} - -/* -=============== -PassageFlow -=============== -*/ -void PassageFlow (int portalnum) -{ - 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); - */ -} - -/* -================== -RecursivePassagePortalFlow -================== -*/ -void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack) -{ - pstack_t stack; - vportal_t *p; - leaf_t *leaf; - plane_t backplane; - passage_t *passage, *nextpassage; - int i, j, n; - long *might, *vis, *prevmight, *cansee, *portalvis, more; - int pnum; - -// thread->c_chains++; - - leaf = &leafs[portal->leaf]; -// CheckStack (leaf, thread); - - prevstack->next = &stack; - - stack.next = NULL; - stack.leaf = leaf; - stack.portal = NULL; - stack.depth = prevstack->depth + 1; - -#ifdef SEPERATORCACHE - stack.numseperators[0] = 0; - stack.numseperators[1] = 0; -#endif - - vis = (long *)thread->base->portalvis; - - passage = portal->passages; - nextpassage = passage; - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++, passage = nextpassage) - { - p = leaf->portals[i]; - if (p->removed) - continue; - nextpassage = passage->next; - pnum = p - portals; - - if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) - continue; // can't possibly see it - - prevmight = (long *)prevstack->mightsee; - cansee = (long *)passage->cansee; - might = (long *)stack.mightsee; - memcpy(might, prevmight, portalbytes); - if (p->status == stat_done) - portalvis = (long *) p->portalvis; - else - portalvis = (long *) p->portalflood; - more = 0; - for (j = 0; j < portallongs; j++) - { - if (*might) - { - *might &= *cansee++ & *portalvis++; - more |= (*might & ~vis[j]); - } - else - { - cansee++; - portalvis++; - } - might++; - } - - if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) ) - { // can't see anything new - continue; - } - - // get plane of portal, point normal into the neighbor leaf - stack.portalplane = p->plane; - VectorSubtract (vec3_origin, p->plane.normal, backplane.normal); - backplane.dist = -p->plane.dist; - -// c_portalcheck++; - - stack.portal = p; - stack.next = NULL; - stack.freewindings[0] = 1; - stack.freewindings[1] = 1; - stack.freewindings[2] = 1; - -#if 1 - { - float d; - - d = DotProduct (p->origin, thread->pstack_head.portalplane.normal); - d -= thread->pstack_head.portalplane.dist; - if (d < -p->radius) - { - continue; - } - else if (d > p->radius) - { - stack.pass = p->winding; - } - else - { - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) - continue; - } - } -#else - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) - continue; -#endif - - -#if 1 - { - float d; - - d = DotProduct (thread->base->origin, p->plane.normal); - d -= p->plane.dist; - //MrE: vis-bug fix - //if (d > p->radius) - if (d > thread->base->radius) - { - continue; - } - //MrE: vis-bug fix - //if (d < -p->radius) - else if (d < -thread->base->radius) - { - stack.source = prevstack->source; - } - else - { - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - //FIXME: shouldn't we create a new source origin and radius for fast checks? - if (!stack.source) - continue; - } - } -#else - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - if (!stack.source) - continue; -#endif - - if (!prevstack->pass) - { // the second leaf can only be blocked if coplanar - - // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); - - RecursivePassagePortalFlow (p, thread, &stack); - continue; - } - -#ifdef SEPERATORCACHE - if (stack.numseperators[0]) - { - for (n = 0; n < stack.numseperators[0]; n++) - { - stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]); - if (!stack.pass) - break; // target is not visible - } - if (n < stack.numseperators[0]) - continue; - } - else - { - stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack); - } -#else - stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack); -#endif - if (!stack.pass) - continue; - -#ifdef SEPERATORCACHE - if (stack.numseperators[1]) - { - for (n = 0; n < stack.numseperators[1]; n++) - { - stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]); - if (!stack.pass) - break; // target is not visible - } - } - else - { - stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack); - } -#else - stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack); -#endif - if (!stack.pass) - continue; - - // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); - - // flow through it for real - RecursivePassagePortalFlow(p, thread, &stack); - // - stack.next = NULL; - } -} - -/* -=============== -PassagePortalFlow -=============== -*/ -void PassagePortalFlow (int portalnum) -{ - 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); - */ -} - -winding_t *PassageChopWinding (winding_t *in, winding_t *out, plane_t *split) -{ - 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; -} - -/* -=============== -AddSeperators -=============== -*/ -int AddSeperators (winding_t *source, winding_t *pass, qboolean flipclip, plane_t *seperators, int maxseperators) -{ - 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; -} - -/* -=============== -CreatePassages - -MrE: create passages from one portal to all the portals in the leaf the portal leads to - every passage has a cansee bit string with all the portals that can be - seen through the passage -=============== -*/ -void CreatePassages(int portalnum) -{ - 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++; - } - } -} - -void PassageMemory(void) -{ - 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); -} - -/* -=============================================================================== - -This is a rough first-order aproximation that is used to trivially reject some -of the final calculations. - - -Calculates portalfront and portalflood bit vectors - -thinking about: - -typedef struct passage_s -{ - struct passage_s *next; - struct portal_s *to; - stryct sep_s *seperators; - byte *mightsee; -} passage_t; - -typedef struct portal_s -{ - struct passage_s *passages; - int leaf; // leaf portal faces into -} portal_s; - -leaf = portal->leaf -clear -for all portals - - -calc portal visibility - clear bit vector - for all passages - passage visibility - - -for a portal to be visible to a passage, it must be on the front of -all seperating planes, and both portals must be behind the new portal - -=============================================================================== -*/ - -int c_flood, c_vis; - - -/* -================== -SimpleFlood - -================== -*/ -void SimpleFlood (vportal_t *srcportal, int leafnum) -{ - int i; - leaf_t *leaf; - vportal_t *p; - int pnum; - - leaf = &leafs[leafnum]; - - for (i=0 ; i<leaf->numportals ; i++) - { - p = leaf->portals[i]; - if (p->removed) - continue; - pnum = p - portals; - if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) ) - continue; - - if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) ) - continue; - - srcportal->portalflood[pnum>>3] |= (1<<(pnum&7)); - - SimpleFlood (srcportal, p->leaf); - } -} - -/* -============== -BasePortalVis -============== -*/ -void BasePortalVis (int portalnum) -{ - 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; -} - - - - - -/* -=============================================================================== - -This is a second order aproximation - -Calculates portalvis bit vector - -WAAAAAAY too slow. - -=============================================================================== -*/ - -/* -================== -RecursiveLeafBitFlow - -================== -*/ -void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee) -{ - vportal_t *p; - leaf_t *leaf; - int i, j; - long more; - int pnum; - byte newmight[MAX_PORTALS/8]; - - leaf = &leafs[leafnum]; - - // check all portals for flowing into other leafs - for (i=0 ; i<leaf->numportals ; i++) - { - p = leaf->portals[i]; - if (p->removed) - continue; - pnum = p - portals; - - // if some previous portal can't see it, skip - if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) ) - continue; - - // if this portal can see some portals we mightsee, recurse - more = 0; - for (j=0 ; j<portallongs ; j++) - { - ((long *)newmight)[j] = ((long *)mightsee)[j] - & ((long *)p->portalflood)[j]; - more |= ((long *)newmight)[j] & ~((long *)cansee)[j]; - } - - if (!more) - continue; // can't see anything new - - cansee[pnum>>3] |= (1<<(pnum&7)); - - RecursiveLeafBitFlow (p->leaf, newmight, cansee); - } -} - -/* -============== -BetterPortalVis -============== -*/ -void BetterPortalVis (int portalnum) -{ - 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; -} - - |