X-Git-Url: http://de.git.xonotic.org/?p=xonotic%2Fnetradiant.git;a=blobdiff_plain;f=tools%2Fquake3%2Fq3map2%2Fvisflow.c;h=5a7ffd92de65c6ed8cc77889b3a22e07e76aa666;hp=672b91a5aa53ad277f517546e97bec4d4384a3ce;hb=dac8329952745dbb494bad1c301e44bab05ec0db;hpb=34d45e210f74edf0690df413b45cc7630d91bd01 diff --git a/tools/quake3/q3map2/visflow.c b/tools/quake3/q3map2/visflow.c index 672b91a5..5a7ffd92 100644 --- a/tools/quake3/q3map2/visflow.c +++ b/tools/quake3/q3map2/visflow.c @@ -1,30 +1,30 @@ /* ------------------------------------------------------------------------------- -Copyright (C) 1999-2007 id Software, Inc. and contributors. -For a list of contributors, see the accompanying CONTRIBUTORS file. + Copyright (C) 1999-2007 id Software, Inc. and contributors. + For a list of contributors, see the accompanying CONTRIBUTORS file. -This file is part of GtkRadiant. + This file is part of GtkRadiant. -GtkRadiant 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. + GtkRadiant 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. -GtkRadiant 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. + GtkRadiant 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 GtkRadiant; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + You should have received a copy of the GNU General Public License + along with GtkRadiant; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA ----------------------------------------------------------------------------------- + ---------------------------------------------------------------------------------- -This code has been altered significantly from its original form, to support -several games based on the Quake III Arena engine, in the form of "Q3Map2." + This code has been altered significantly from its original form, to support + several games based on the Quake III Arena engine, in the form of "Q3Map2." -------------------------------------------------------------------------------- */ + ------------------------------------------------------------------------------- */ @@ -41,122 +41,123 @@ several games based on the Quake III Arena engine, in the form of "Q3Map2." /* - each portal will have a list of all possible to see from first portal + each portal will have a list of all possible to see from first portal - if (!thread->portalmightsee[portalnum]) + if (!thread->portalmightsee[portalnum]) - portal mightsee + 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 + 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, -*/ + void CalcMightSee (leaf_t *leaf, + */ -int CountBits (byte *bits, int numbits) -{ - int i; - int c; +int CountBits( byte *bits, int numbits ){ + int i; + int c; c = 0; - for (i=0 ; i>3] & (1<<(i&7)) ) + 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_fullskip; +int c_portalskip, c_leafskip; +int c_vistest, c_mighttest; -int c_chop, c_nochop; +int c_chop, c_nochop; -int active; +int active; -void CheckStack (leaf_t *leaf, threaddata_t *thread) -{ - pstack_t *p, *p2; +void CheckStack( leaf_t *leaf, threaddata_t *thread ){ + pstack_t *p, *p2; - for (p=thread->pstack_head.next ; p ; p=p->next) + for ( p = thread->pstack_head.next ; p ; p = p->next ) { // Sys_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"); + 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" ); + } } // Sys_Printf ("\n"); } -fixedWinding_t *AllocStackWinding (pstack_t *stack) -{ - int i; +fixedWinding_t *AllocStackWinding( pstack_t *stack ){ + int i; - for (i=0 ; i<3 ; i++) + for ( i = 0 ; i < 3 ; i++ ) { - if (stack->freewindings[i]) - { + if ( stack->freewindings[i] ) { stack->freewindings[i] = 0; return &stack->windings[i]; } } - Error ("AllocStackWinding: failed"); + Error( "AllocStackWinding: failed" ); return NULL; } -void FreeStackWinding (fixedWinding_t *w, pstack_t *stack) -{ - int i; +void FreeStackWinding( fixedWinding_t *w, pstack_t *stack ){ + int i; i = w - stack->windings; - if (i<0 || i>2) - return; // not from local + if ( i < 0 || i > 2 ) { + return; // not from local - if (stack->freewindings[i]) - Error ("FreeStackWinding: allready free"); + } + if ( stack->freewindings[i] ) { + Error( "FreeStackWinding: allready free" ); + } stack->freewindings[i] = 1; } /* -============== -VisChopWinding - -============== -*/ -fixedWinding_t *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_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; - fixedWinding_t *neww; + ============== + VisChopWinding + + ============== + */ +fixedWinding_t *VisChopWinding( fixedWinding_t *in, pstack_t *stack, visPlane_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; + fixedWinding_t *neww; counts[0] = counts[1] = counts[2] = 0; // determine sides for each point - for (i=0 ; inumpoints ; i++) + for ( i = 0 ; i < in->numpoints ; i++ ) { - dot = DotProduct (in->points[i], split->normal); + dot = DotProduct( in->points[i], split->normal ); dot -= split->dist; dists[i] = dot; - if (dot > ON_EPSILON) + if ( dot > ON_EPSILON ) { sides[i] = SIDE_FRONT; - else if (dot < -ON_EPSILON) + } + else if ( dot < -ON_EPSILON ) { sides[i] = SIDE_BACK; + } else { sides[i] = SIDE_ON; @@ -164,137 +165,137 @@ fixedWinding_t *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_t counts[sides[i]]++; } - if (!counts[1]) - return in; // completely on front side - - if (!counts[0]) - { - FreeStackWinding (in, stack); + 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 = AllocStackWinding( stack ); neww->numpoints = 0; - for (i=0 ; inumpoints ; i++) + 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 ( 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]); + 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]); + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, neww->points[neww->numpoints] ); neww->numpoints++; } - - if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + + 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 + } + + 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) + 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) + } + else if ( split->normal[j] == -1 ) { mid[j] = -split->dist; - else - mid[j] = p1[j] + dot*(p2[j]-p1[j]); + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } } - - VectorCopy (mid, neww->points[neww->numpoints]); + + VectorCopy( mid, neww->points[neww->numpoints] ); neww->numpoints++; } - + // free the original winding - FreeStackWinding (in, stack); - + 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. -============== -*/ -fixedWinding_t *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack) -{ - int i, j, k, l; - visPlane_t plane; - vec3_t v1, v2; - float d; - vec_t length; - int counts[3]; - qboolean fliptest; - - // check all combinations - for (i=0 ; inumpoints ; i++) + ============== + 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. + ============== + */ +fixedWinding_t *ClipToSeperators( fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack ){ + int i, j, k, l; + visPlane_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); + 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 ; jnumpoints ; j++) + for ( j = 0 ; j < pass->numpoints ; j++ ) { - VectorSubtract (pass->points[j], source->points[i], v2); + 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]; - 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) + + plane.normal[1] * plane.normal[1] + + plane.normal[2] * plane.normal[2]; + + if ( length < ON_EPSILON ) { continue; + } + + length = 1 / sqrt( length ); - length = 1/sqrt(length); - plane.normal[0] *= length; plane.normal[1] *= length; plane.normal[2] *= length; - plane.dist = DotProduct (pass->points[j], plane.normal); + plane.dist = DotProduct( pass->points[j], plane.normal ); // // find out which side of the generated seperating plane has the @@ -302,35 +303,34 @@ fixedWinding_t *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, // #if 1 fliptest = qfalse; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < source->numpoints ; k++ ) { - if (k == i || k == l) + 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 + } + 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 + 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 + 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); + if ( fliptest ) { + VectorSubtract( vec3_origin, plane.normal, plane.normal ); plane.dist = -plane.dist; } #if 1 @@ -339,87 +339,97 @@ fixedWinding_t *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, // this is the seperating plane // counts[0] = counts[1] = counts[2] = 0; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < pass->numpoints ; k++ ) { - if (k==j) + if ( k == j ) { continue; - d = DotProduct (pass->points[k], plane.normal) - plane.dist; - if (d < -ON_EPSILON) + } + d = DotProduct( pass->points[k], plane.normal ) - plane.dist; + if ( d < -ON_EPSILON ) { break; - else if (d > ON_EPSILON) + } + else if ( d > ON_EPSILON ) { counts[0]++; - else + } + else{ counts[2]++; + } + } + if ( k != pass->numpoints ) { + continue; // points on negative side, not a seperating plane + + } + if ( !counts[0] ) { + continue; // planar with seperating plane } - 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) + 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; + } + 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); + 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"); + if ( ++stack->numseperators[flipclip] >= MAX_SEPERATORS ) { + Error( "MAX_SEPERATORS" ); + } #endif //MrE: fast check first - d = DotProduct (stack->portal->origin, plane.normal) - plane.dist; + d = DotProduct( stack->portal->origin, plane.normal ) - plane.dist; //if completely at the back of the seperator plane - if (d < -stack->portal->radius) + if ( d < -stack->portal->radius ) { return NULL; + } //if completely on the front of the seperator plane - if (d > stack->portal->radius) + 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 + target = VisChopWinding( target, stack, &plane ); + if ( !target ) { + return NULL; // target is not visible - break; // optimization by Antony Suter + } + 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; - visPlane_t backplane; - leaf_t *leaf; - int i, j, n; - long *test, *might, *prevmight, *vis, more; - int pnum; + ================== + 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; + visPlane_t backplane; + leaf_t *leaf; + int i, j, n; + long *test, *might, *prevmight, *vis, more; + int pnum; thread->c_chains++; @@ -440,42 +450,41 @@ void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack) might = (long *)stack.mightsee; vis = (long *)thread->base->portalvis; - - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++) + + // check all portals for flowing into other leafs + for ( i = 0; i < leaf->numportals; i++ ) { p = leaf->portals[i]; - if (p->removed) + 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 + { + 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) - { + if ( p->status == stat_done ) { test = (long *)p->portalvis; } else @@ -485,217 +494,215 @@ void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack) more = 0; prevmight = (long *)prevstack->mightsee; - for (j=0 ; jbase->portalvis[pnum>>3] & (1<<(pnum&7))) ) - { // can't see anything new + + 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); + 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 = DotProduct( p->origin, thread->pstack_head.portalplane.normal ); d -= thread->pstack_head.portalplane.dist; - if (d < -p->radius) - { + if ( d < -p->radius ) { continue; } - else if (d > p->radius) - { + else if ( d > p->radius ) { stack.pass = p->winding; } - else + else { - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) + 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) + 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 = DotProduct( thread->base->origin, p->plane.normal ); d -= p->plane.dist; //MrE: vis-bug fix //if (d > p->radius) - if (d > thread->base->radius) - { + if ( d > thread->base->radius ) { continue; } //MrE: vis-bug fix //if (d < -p->radius) - else if (d < -thread->base->radius) - { + else if ( d < -thread->base->radius ) { stack.source = prevstack->source; } - else + else { - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); + stack.source = VisChopWinding( prevstack->source, &stack, &backplane ); //FIXME: shouldn't we create a new source origin and radius for fast checks? - if (!stack.source) + if ( !stack.source ) { continue; + } } } #else - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - if (!stack.source) + stack.source = VisChopWinding( prevstack->source, &stack, &backplane ); + if ( !stack.source ) { continue; + } #endif - if (!prevstack->pass) - { // the second leaf can only be blocked if coplanar + 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)); + thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) ); - RecursiveLeafFlow (p->leaf, thread, &stack); + RecursiveLeafFlow( p->leaf, thread, &stack ); continue; } #ifdef SEPERATORCACHE - if (stack.numseperators[0]) - { - for (n = 0; n < stack.numseperators[0]; n++) + 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 + stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] ); + if ( !stack.pass ) { + break; // target is not visible + } } - if (n < stack.numseperators[0]) + if ( n < stack.numseperators[0] ) { continue; + } } else { - stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack); + stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack ); } #else - stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack); + stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack ); #endif - if (!stack.pass) + if ( !stack.pass ) { continue; + } #ifdef SEPERATORCACHE - if (stack.numseperators[1]) - { - for (n = 0; n < stack.numseperators[1]; n++) + 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 + 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); + stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack ); } #else - stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack); + stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack ); #endif - if (!stack.pass) + if ( !stack.pass ) { continue; + } // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); + thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) ); // flow through it for real - RecursiveLeafFlow (p->leaf, thread, &stack); + 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; + =============== + 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 - Sys_Printf("\r%6d", portalnum); + Sys_Printf( "\r%6d", portalnum ); #endif p = sorted_portals[portalnum]; - if (p->removed) - { + if ( p->removed ) { p->status = stat_done; return; } p->status = stat_working; - c_might = CountBits (p->portalflood, numportals*2); + c_might = CountBits( p->portalflood, numportals * 2 ); - memset (&data, 0, sizeof(data)); + 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 ; iportalflood)[i]; + for ( i = 0 ; i < portallongs ; i++ ) + ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i]; - RecursiveLeafFlow (p->leaf, &data, &data.pstack_head); + RecursiveLeafFlow( p->leaf, &data, &data.pstack_head ); p->status = stat_done; - c_can = CountBits (p->portalvis, numportals*2); + c_can = CountBits( p->portalvis, numportals * 2 ); - Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", - (int)(p - portals), c_might, c_can, data.c_chains); + Sys_FPrintf( SYS_VRB,"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; + ================== + 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]; @@ -708,8 +715,8 @@ void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *pr passage = portal->passages; nextpassage = passage; - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++, passage = nextpassage) + // check all portals for flowing into other leafs + for ( i = 0; i < leaf->numportals; i++, passage = nextpassage ) { p = leaf->portals[i]; if ( p->removed ) { @@ -718,28 +725,29 @@ void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *pr nextpassage = passage->next; pnum = p - portals; - if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) { - continue; // can't possibly see it + 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)); + 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) + memcpy( might, prevmight, portalbytes ); + if ( p->status == stat_done ) { portalvis = (long *) p->portalvis; - else + } + else{ portalvis = (long *) p->portalflood; + } more = 0; - for (j = 0; j < portallongs; j++) + for ( j = 0; j < portallongs; j++ ) { - if (*might) - { + if ( *might ) { *might &= *cansee++ & *portalvis++; - more |= (*might & ~vis[j]); + more |= ( *might & ~vis[j] ); } else { @@ -755,32 +763,30 @@ void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *pr } // flow through it for real - RecursivePassageFlow(p, thread, &stack); + RecursivePassageFlow( p, thread, &stack ); stack.next = NULL; } } /* -=============== -PassageFlow -=============== -*/ -void PassageFlow (int portalnum) -{ - threaddata_t data; - int i; - vportal_t *p; + =============== + PassageFlow + =============== + */ +void PassageFlow( int portalnum ){ + threaddata_t data; + int i; + vportal_t *p; // int c_might, c_can; #ifdef MREDEBUG - Sys_Printf("\r%6d", portalnum); + Sys_Printf( "\r%6d", portalnum ); #endif p = sorted_portals[portalnum]; - if (p->removed) - { + if ( p->removed ) { p->status = stat_done; return; } @@ -789,43 +795,42 @@ void PassageFlow (int portalnum) // c_might = CountBits (p->portalflood, numportals*2); - memset (&data, 0, sizeof(data)); + 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 ; iportalflood)[i]; + for ( i = 0 ; i < portallongs ; i++ ) + ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i]; - RecursivePassageFlow (p, &data, &data.pstack_head); + RecursivePassageFlow( p, &data, &data.pstack_head ); p->status = stat_done; /* - c_can = CountBits (p->portalvis, numportals*2); + c_can = CountBits (p->portalvis, numportals*2); - Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", - (int)(p - portals), c_might, c_can, data.c_chains); - */ + Sys_FPrintf (SYS_VRB,"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; - visPlane_t backplane; - passage_t *passage, *nextpassage; - int i, j, n; - long *might, *vis, *prevmight, *cansee, *portalvis, more; - int pnum; + ================== + RecursivePassagePortalFlow + ================== + */ +void RecursivePassagePortalFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){ + pstack_t stack; + vportal_t *p; + leaf_t *leaf; + visPlane_t backplane; + passage_t *passage, *nextpassage; + int i, j, n; + long *might, *vis, *prevmight, *cansee, *portalvis, more; + int pnum; // thread->c_chains++; @@ -848,33 +853,36 @@ void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack passage = portal->passages; nextpassage = passage; - // check all portals for flowing into other leafs - for (i = 0; i < leaf->numportals; i++, passage = nextpassage) + // check all portals for flowing into other leafs + for ( i = 0; i < leaf->numportals; i++, passage = nextpassage ) { p = leaf->portals[i]; - if (p->removed) + if ( p->removed ) { continue; + } nextpassage = passage->next; pnum = p - portals; - if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) - continue; // can't possibly see it + 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) + memcpy( might, prevmight, portalbytes ); + if ( p->status == stat_done ) { portalvis = (long *) p->portalvis; - else + } + else{ portalvis = (long *) p->portalflood; + } more = 0; - for (j = 0; j < portallongs; j++) + for ( j = 0; j < portallongs; j++ ) { - if (*might) - { + if ( *might ) { *might &= *cansee++ & *portalvis++; - more |= (*might & ~vis[j]); + more |= ( *might & ~vis[j] ); } else { @@ -884,18 +892,17 @@ void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack might++; } - if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) ) - { // can't see anything new + 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); + 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; @@ -906,144 +913,144 @@ void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack { float d; - d = DotProduct (p->origin, thread->pstack_head.portalplane.normal); + d = DotProduct( p->origin, thread->pstack_head.portalplane.normal ); d -= thread->pstack_head.portalplane.dist; - if (d < -p->radius) - { + if ( d < -p->radius ) { continue; } - else if (d > p->radius) - { + else if ( d > p->radius ) { stack.pass = p->winding; } - else + else { - stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane); - if (!stack.pass) + 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) + 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 = DotProduct( thread->base->origin, p->plane.normal ); d -= p->plane.dist; //MrE: vis-bug fix //if (d > p->radius) - if (d > thread->base->radius) - { + if ( d > thread->base->radius ) { continue; } //MrE: vis-bug fix //if (d < -p->radius) - else if (d < -thread->base->radius) - { + else if ( d < -thread->base->radius ) { stack.source = prevstack->source; } - else + else { - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); + stack.source = VisChopWinding( prevstack->source, &stack, &backplane ); //FIXME: shouldn't we create a new source origin and radius for fast checks? - if (!stack.source) + if ( !stack.source ) { continue; + } } } #else - stack.source = VisChopWinding (prevstack->source, &stack, &backplane); - if (!stack.source) + stack.source = VisChopWinding( prevstack->source, &stack, &backplane ); + if ( !stack.source ) { continue; + } #endif - if (!prevstack->pass) - { // the second leaf can only be blocked if coplanar + 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)); + thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) ); - RecursivePassagePortalFlow (p, thread, &stack); + RecursivePassagePortalFlow( p, thread, &stack ); continue; } #ifdef SEPERATORCACHE - if (stack.numseperators[0]) - { - for (n = 0; n < stack.numseperators[0]; n++) + 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 + stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] ); + if ( !stack.pass ) { + break; // target is not visible + } } - if (n < stack.numseperators[0]) + if ( n < stack.numseperators[0] ) { continue; + } } else { - stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack); + stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack ); } #else - stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack); + stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack ); #endif - if (!stack.pass) + if ( !stack.pass ) { continue; + } #ifdef SEPERATORCACHE - if (stack.numseperators[1]) - { - for (n = 0; n < stack.numseperators[1]; n++) + 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 + 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); + stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack ); } #else - stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack); + stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack ); #endif - if (!stack.pass) + if ( !stack.pass ) { continue; + } // mark the portal as visible - thread->base->portalvis[pnum>>3] |= (1<<(pnum&7)); + thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) ); // flow through it for real - RecursivePassagePortalFlow(p, thread, &stack); + RecursivePassagePortalFlow( p, thread, &stack ); // stack.next = NULL; } } /* -=============== -PassagePortalFlow -=============== -*/ -void PassagePortalFlow (int portalnum) -{ - threaddata_t data; - int i; - vportal_t *p; + =============== + PassagePortalFlow + =============== + */ +void PassagePortalFlow( int portalnum ){ + threaddata_t data; + int i; + vportal_t *p; // int c_might, c_can; #ifdef MREDEBUG - Sys_Printf("\r%6d", portalnum); + Sys_Printf( "\r%6d", portalnum ); #endif p = sorted_portals[portalnum]; - if (p->removed) - { + if ( p->removed ) { p->status = stat_done; return; } @@ -1052,51 +1059,52 @@ void PassagePortalFlow (int portalnum) // c_might = CountBits (p->portalflood, numportals*2); - memset (&data, 0, sizeof(data)); + 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 ; iportalflood)[i]; + for ( i = 0 ; i < portallongs ; i++ ) + ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i]; - RecursivePassagePortalFlow (p, &data, &data.pstack_head); + RecursivePassagePortalFlow( p, &data, &data.pstack_head ); p->status = stat_done; /* - c_can = CountBits (p->portalvis, numportals*2); + c_can = CountBits (p->portalvis, numportals*2); - Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", - (int)(p - portals), c_might, c_can, data.c_chains); - */ + Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", + (int)(p - portals), c_might, c_can, data.c_chains); + */ } -fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_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; - fixedWinding_t *neww; +fixedWinding_t *PassageChopWinding( fixedWinding_t *in, fixedWinding_t *out, visPlane_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; + fixedWinding_t *neww; counts[0] = counts[1] = counts[2] = 0; // determine sides for each point - for (i=0 ; inumpoints ; i++) + for ( i = 0 ; i < in->numpoints ; i++ ) { - dot = DotProduct (in->points[i], split->normal); + dot = DotProduct( in->points[i], split->normal ); dot -= split->dist; dists[i] = dot; - if (dot > ON_EPSILON) + if ( dot > ON_EPSILON ) { sides[i] = SIDE_FRONT; - else if (dot < -ON_EPSILON) + } + else if ( dot < -ON_EPSILON ) { sides[i] = SIDE_BACK; + } else { sides[i] = SIDE_ON; @@ -1104,121 +1112,121 @@ fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, vis counts[sides[i]]++; } - if (!counts[1]) - return in; // completely on front side - - if (!counts[0]) - { + 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 ; inumpoints ; i++) + 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 ( 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]); + 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]); + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, neww->points[neww->numpoints] ); neww->numpoints++; } - - if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + + 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 + } + + 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) + 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) + } + else if ( split->normal[j] == -1 ) { mid[j] = -split->dist; - else - mid[j] = p1[j] + dot*(p2[j]-p1[j]); + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } } - - VectorCopy (mid, neww->points[neww->numpoints]); + + VectorCopy( mid, neww->points[neww->numpoints] ); neww->numpoints++; } - + return neww; } /* -=============== -AddSeperators -=============== -*/ -int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators) -{ - int i, j, k, l; - visPlane_t plane; - vec3_t v1, v2; - float d; - vec_t length; - int counts[3], numseperators; - qboolean fliptest; + =============== + AddSeperators + =============== + */ +int AddSeperators( fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators ){ + int i, j, k, l; + visPlane_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 ; inumpoints ; i++) + // check all combinations + for ( i = 0 ; i < source->numpoints ; i++ ) { - l = (i+1)%source->numpoints; - VectorSubtract (source->points[l] , source->points[i], v1); + 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 ; jnumpoints ; j++) + for ( j = 0 ; j < pass->numpoints ; j++ ) { - VectorSubtract (pass->points[j], source->points[i], v2); + 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]; - 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) + + plane.normal[1] * plane.normal[1] + + plane.normal[2] * plane.normal[2]; + + if ( length < ON_EPSILON ) { continue; + } + + length = 1 / sqrt( length ); - length = 1/sqrt(length); - plane.normal[0] *= length; plane.normal[1] *= length; plane.normal[2] *= length; - plane.dist = DotProduct (pass->points[j], plane.normal); + plane.dist = DotProduct( pass->points[j], plane.normal ); // // find out which side of the generated seperating plane has the @@ -1226,35 +1234,34 @@ int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipcl // #if 1 fliptest = qfalse; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < source->numpoints ; k++ ) { - if (k == i || k == l) + 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 + } + 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 + 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 + 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); + if ( fliptest ) { + VectorSubtract( vec3_origin, plane.normal, plane.normal ); plane.dist = -plane.dist; } #if 1 @@ -1263,44 +1270,52 @@ int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipcl // this is the seperating plane // counts[0] = counts[1] = counts[2] = 0; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < pass->numpoints ; k++ ) { - if (k==j) + if ( k == j ) { continue; - d = DotProduct (pass->points[k], plane.normal) - plane.dist; - if (d < -ON_EPSILON) + } + d = DotProduct( pass->points[k], plane.normal ) - plane.dist; + if ( d < -ON_EPSILON ) { break; - else if (d > ON_EPSILON) + } + else if ( d > ON_EPSILON ) { counts[0]++; - else + } + else{ counts[2]++; + } + } + if ( k != pass->numpoints ) { + continue; // points on negative side, not a seperating plane + + } + if ( !counts[0] ) { + continue; // planar with seperating plane } - 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) + 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; + } + 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); + if ( flipclip ) { + VectorSubtract( vec3_origin, plane.normal, plane.normal ); plane.dist = -plane.dist; } - if (numseperators >= maxseperators) - Error("max seperators"); + if ( numseperators >= maxseperators ) { + Error( "max seperators" ); + } seperators[numseperators] = plane; numseperators++; break; @@ -1310,316 +1325,336 @@ int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipcl } /* -=============== -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; - visPlane_t seperators[MAX_SEPERATORS*2]; - fixedWinding_t *w; - fixedWinding_t in, out, *res; - - + =============== + 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; + visPlane_t seperators[MAX_SEPERATORS * 2]; + fixedWinding_t *w; + fixedWinding_t in, out, *res; + + #ifdef MREDEBUG - Sys_Printf("\r%6d", portalnum); + Sys_Printf( "\r%6d", portalnum ); #endif portal = sorted_portals[portalnum]; - if (portal->removed) - { + if ( portal->removed ) { portal->status = stat_done; return; } lastpassage = NULL; leaf = &leafs[portal->leaf]; - for (i = 0; i < leaf->numportals; i++) + for ( i = 0; i < leaf->numportals; i++ ) { target = leaf->portals[i]; - if (target->removed) + if ( target->removed ) { continue; + } - passage = (passage_t *) safe_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 = (passage_t *) safe_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) + if ( lastpassage ) { lastpassage->next = passage; - else + } + else{ portal->passages = passage; + } lastpassage = passage; numsee = 0; //create the passage->cansee - for (j = 0; j < numportals * 2; j++) + for ( j = 0; j < numportals * 2; j++ ) { p = &portals[j]; - if (p->removed) + if ( p->removed ) { continue; - if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) ) + } + if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) { continue; - if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) ) + } + if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) { continue; - for (k = 0; k < numseperators; k++) + } + for ( k = 0; k < numseperators; k++ ) { // - d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist; + 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) + if ( d < -p->radius + ON_EPSILON ) { break; + } w = p->winding; - for (n = 0; n < w->numpoints; n++) + for ( n = 0; n < w->numpoints; n++ ) { - d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist; + d = DotProduct( w->points[n], seperators[k].normal ) - seperators[k].dist; //if at the front of the seperator - if (d > ON_EPSILON) + if ( d > ON_EPSILON ) { break; + } } //if no points are at the front of the seperator - if (n >= w->numpoints) + if ( n >= w->numpoints ) { break; + } } - if (k < numseperators) + if ( k < numseperators ) { continue; - + } + /* explitive deleted */ - - + + /* ydnar: prefer correctness to stack overflow */ //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] ); - if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) - memcpy( &in, p->winding, (size_t) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) ); - else + if ( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) { + memcpy( &in, p->winding, (size_t) &( ( (fixedWinding_t*) 0 )->points[ p->winding->numpoints ] ) ); + } + else{ memcpy( &in, p->winding, sizeof( fixedWinding_t ) ); - - - for( k = 0; k < numseperators; k++ ) + } + + + for ( k = 0; k < numseperators; k++ ) { /* ydnar: this is a shitty crutch */ - if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) - { + if ( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) { //% Sys_Printf( "[%d]", p->winding->numpoints ); in.numpoints = MAX_POINTS_ON_FIXED_WINDING; } - + res = PassageChopWinding( &in, &out, &seperators[ k ] ); - if( res == &out ) + if ( res == &out ) { memcpy( &in, &out, sizeof( fixedWinding_t ) ); + } - - if( res == NULL ) + + if ( res == NULL ) { break; + } } - if (k < numseperators) + if ( k < numseperators ) { continue; - passage->cansee[j >> 3] |= (1<<(j&7)); + } + passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) ); numsee++; } } } -void PassageMemory(void) -{ +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++) + for ( i = 0; i < numportals; i++ ) { portal = sorted_portals[i]; - if (portal->removed) + if ( portal->removed ) { continue; + } leaf = &leafs[portal->leaf]; - for (j = 0; j < leaf->numportals; j++) + for ( j = 0; j < leaf->numportals; j++ ) { target = leaf->portals[j]; - if (target->removed) + if ( target->removed ) { continue; - totalmem += sizeof(passage_t) + portalbytes; + } + totalmem += sizeof( passage_t ) + portalbytes; totalportals++; } } - Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals); - Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10); + Sys_Printf( "%7i average number of passages per leaf\n", totalportals / numportals ); + Sys_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. + This is a rough first-order aproximation that is used to trivially reject some + of the final calculations. -Calculates portalfront and portalflood bit vectors + Calculates portalfront and portalflood bit vectors -thinking about: + thinking about: -typedef struct passage_s -{ - struct passage_s *next; - struct portal_s *to; - stryct sep_s *seperators; - byte *mightsee; -} passage_t; + 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; + typedef struct portal_s + { + struct passage_s *passages; + int leaf; // leaf portal faces into + } portal_s; -leaf = portal->leaf -clear -for all portals + leaf = portal->leaf + clear + for all portals -calc portal visibility - clear bit vector - for all passages - passage visibility + 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 + 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; +int c_flood, c_vis; /* -================== -SimpleFlood - -================== -*/ -void SimpleFlood (vportal_t *srcportal, int leafnum) -{ - int i; - leaf_t *leaf; - vportal_t *p; - int pnum; + ================== + SimpleFlood + + ================== + */ +void SimpleFlood( vportal_t *srcportal, int leafnum ){ + int i; + leaf_t *leaf; + vportal_t *p; + int pnum; leaf = &leafs[leafnum]; - - for (i=0 ; inumportals ; i++) + + for ( i = 0 ; i < leaf->numportals ; i++ ) { p = leaf->portals[i]; - if (p->removed) + if ( p->removed ) { continue; + } pnum = p - portals; - if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) ) + if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { continue; + } - if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) ) + if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) { continue; + } - srcportal->portalflood[pnum>>3] |= (1<<(pnum&7)); - - SimpleFlood (srcportal, p->leaf); + 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; - fixedWinding_t *w; - vec3_t dir; - - - p = portals+portalnum; - - if (p->removed) + ============== + BasePortalVis + ============== + */ +void BasePortalVis( int portalnum ){ + int j, k; + vportal_t *tp, *p; + float d; + fixedWinding_t *w; + vec3_t dir; + + + p = portals + portalnum; + + if ( p->removed ) { return; + } + + p->portalfront = safe_malloc( portalbytes ); + memset( p->portalfront, 0, portalbytes ); + + p->portalflood = safe_malloc( portalbytes ); + memset( p->portalflood, 0, portalbytes ); - p->portalfront = safe_malloc (portalbytes); - memset (p->portalfront, 0, portalbytes); + p->portalvis = safe_malloc( portalbytes ); + memset( p->portalvis, 0, portalbytes ); - p->portalflood = safe_malloc (portalbytes); - memset (p->portalflood, 0, portalbytes); - - p->portalvis = safe_malloc (portalbytes); - memset (p->portalvis, 0, portalbytes); - - for (j=0, tp = portals ; jremoved ) + } + if ( tp->removed ) { continue; + } /* ydnar: this is old farplane vis code from mre */ /* - if (farplanedist >= 0) - { - vec3_t dir; - VectorSubtract(p->origin, tp->origin, dir); - if (VectorLength(dir) > farplanedist - p->radius - tp->radius) - continue; - } - */ - + if (farplanedist >= 0) + { + vec3_t dir; + VectorSubtract(p->origin, tp->origin, dir); + if (VectorLength(dir) > farplanedist - p->radius - tp->radius) + continue; + } + */ + /* ydnar: this is known-to-be-working farplane code */ - if( !p->sky && !tp->sky ) - if( farPlaneDist > 0.0f ) - { + if ( !p->sky && !tp->sky && farPlaneDist > 0.0f ) { VectorSubtract( p->origin, tp->origin, dir ); - if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) + if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) { continue; + } } - - + + w = tp->winding; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < w->numpoints ; k++ ) { - d = DotProduct (w->points[k], p->plane.normal) + d = DotProduct( w->points[k], p->plane.normal ) - p->plane.dist; - if (d > ON_EPSILON) + if ( d > ON_EPSILON ) { break; + } } - if (k == w->numpoints) - continue; // no points on front + if ( k == w->numpoints ) { + continue; // no points on front + } w = p->winding; - for (k=0 ; knumpoints ; k++) + for ( k = 0 ; k < w->numpoints ; k++ ) { - d = DotProduct (w->points[k], tp->plane.normal) + d = DotProduct( w->points[k], tp->plane.normal ) - tp->plane.dist; - if (d < -ON_EPSILON) + if ( d < -ON_EPSILON ) { break; + } } - if (k == w->numpoints) - continue; // no points on front + if ( k == w->numpoints ) { + continue; // no points on front - p->portalfront[j>>3] |= (1<<(j&7)); + } + p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) ); } - - SimpleFlood (p, p->leaf); - p->nummightsee = CountBits (p->portalflood, numportals*2); + SimpleFlood( p, p->leaf ); + + p->nummightsee = CountBits( p->portalflood, numportals * 2 ); // Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee); c_flood += p->nummightsee; } @@ -1629,83 +1664,83 @@ void BasePortalVis( int portalnum ) /* -=============================================================================== + =============================================================================== -This is a second order aproximation + This is a second order aproximation -Calculates portalvis bit vector + Calculates portalvis bit vector -WAAAAAAY too slow. + 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]; + ================== + 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 ; inumportals ; i++) + for ( i = 0 ; i < leaf->numportals ; i++ ) { p = leaf->portals[i]; - if (p->removed) + if ( p->removed ) { continue; + } pnum = p - portals; // if some previous portal can't see it, skip - if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) ) + if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { continue; + } // if this portal can see some portals we mightsee, recurse more = 0; - for (j=0 ; jportalflood)[j]; - more |= ((long *)newmight)[j] & ~((long *)cansee)[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 + if ( !more ) { + continue; // can't see anything new - cansee[pnum>>3] |= (1<<(pnum&7)); + } + cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) ); - RecursiveLeafBitFlow (p->leaf, newmight, cansee); - } + RecursiveLeafBitFlow( p->leaf, newmight, cansee ); + } } /* -============== -BetterPortalVis -============== -*/ -void BetterPortalVis (int portalnum) -{ - vportal_t *p; + ============== + BetterPortalVis + ============== + */ +void BetterPortalVis( int portalnum ){ + vportal_t *p; - p = portals+portalnum; + p = portals + portalnum; - if (p->removed) + if ( p->removed ) { return; + } - RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis); + RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis ); // build leaf vis information - p->nummightsee = CountBits (p->portalvis, numportals*2); + p->nummightsee = CountBits( p->portalvis, numportals * 2 ); c_vis += p->nummightsee; } - -