1745 lines
39 KiB
C
1745 lines
39 KiB
C
/* -------------------------------------------------------------------------------
|
|
|
|
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.
|
|
|
|
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.
|
|
|
|
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."
|
|
|
|
------------------------------------------------------------------------------- */
|
|
|
|
|
|
|
|
/* marker */
|
|
#define VISFLOW_C
|
|
|
|
|
|
|
|
/* dependencies */
|
|
#include "vmap.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_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 )
|
|
{
|
|
// 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" );
|
|
}
|
|
}
|
|
// Sys_Printf ("\n");
|
|
}
|
|
|
|
|
|
fixedWinding_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( fixedWinding_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
|
|
|
|
==============
|
|
*/
|
|
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; 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.
|
|
==============
|
|
*/
|
|
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 );
|
|
|
|
// 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;
|
|
visPlane_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
|
|
Sys_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 );
|
|
|
|
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;
|
|
|
|
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
|
|
Sys_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);
|
|
|
|
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;
|
|
|
|
// 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
|
|
Sys_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);
|
|
|
|
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;
|
|
|
|
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( 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; 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;
|
|
visPlane_t seperators[MAX_SEPERATORS * 2];
|
|
fixedWinding_t *w;
|
|
fixedWinding_t in, out, *res;
|
|
|
|
|
|
#ifdef MREDEBUG
|
|
Sys_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 *) 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 ) {
|
|
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;
|
|
}
|
|
|
|
/* 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{
|
|
memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
|
|
}
|
|
|
|
|
|
for ( k = 0; k < numseperators; k++ )
|
|
{
|
|
/* ydnar: this is a shitty crutch */
|
|
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 ) {
|
|
memcpy( &in, &out, sizeof( fixedWinding_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++;
|
|
}
|
|
}
|
|
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.
|
|
|
|
|
|
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;
|
|
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->portalvis = safe_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;
|
|
}
|
|
|
|
/* 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;
|
|
}
|
|
*/
|
|
|
|
/* ydnar: this is known-to-be-working farplane code */
|
|
if ( !p->sky && !tp->sky && farPlaneDist > 0.0f ) {
|
|
VectorSubtract( p->origin, tp->origin, dir );
|
|
if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) {
|
|
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 );
|
|
// Sys_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;
|
|
}
|