newlines fixed

git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea

1 files changed, 1636 insertions, 1636 deletions

diff --git a/q3map/visflow.c b/q3map/visflow.c
index c62a33b..5948b08 100755
--- a/q3map/visflow.c
+++ b/q3map/visflow.c
@@ -19,1639 +19,1639 @@ along with Foobar; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 ===========================================================================
 */
-#include "vis.h"

-

-/*

-

-  each portal will have a list of all possible to see from first portal

-

-  if (!thread->portalmightsee[portalnum])

-

-  portal mightsee

-

-  for p2 = all other portals in leaf

-	get sperating planes

-	for all portals that might be seen by p2

-		mark as unseen if not present in seperating plane

-	flood fill a new mightsee

-	save as passagemightsee

-

-

-  void CalcMightSee (leaf_t *leaf, 

-*/

-

-int CountBits (byte *bits, int numbits)

-{

-	int		i;

-	int		c;

-

-	c = 0;

-	for (i=0 ; i<numbits ; i++)

-		if (bits[i>>3] & (1<<(i&7)) )

-			c++;

-

-	return c;

-}

-

-int		c_fullskip;

-int		c_portalskip, c_leafskip;

-int		c_vistest, c_mighttest;

-

-int		c_chop, c_nochop;

-

-int		active;

-

-void CheckStack (leaf_t *leaf, threaddata_t *thread)

-{

-	pstack_t	*p, *p2;

-

-	for (p=thread->pstack_head.next ; p ; p=p->next)

-	{

-//		_printf ("=");

-		if (p->leaf == leaf)

-			Error ("CheckStack: leaf recursion");

-		for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)

-			if (p2->leaf == p->leaf)

-				Error ("CheckStack: late leaf recursion");

-	}

-//	_printf ("\n");

-}

-

-

-winding_t *AllocStackWinding (pstack_t *stack)

-{

-	int		i;

-

-	for (i=0 ; i<3 ; i++)

-	{

-		if (stack->freewindings[i])

-		{

-			stack->freewindings[i] = 0;

-			return &stack->windings[i];

-		}

-	}

-

-	Error ("AllocStackWinding: failed");

-

-	return NULL;

-}

-

-void FreeStackWinding (winding_t *w, pstack_t *stack)

-{

-	int		i;

-

-	i = w - stack->windings;

-

-	if (i<0 || i>2)

-		return;		// not from local

-

-	if (stack->freewindings[i])

-		Error ("FreeStackWinding: allready free");

-	stack->freewindings[i] = 1;

-}

-

-/*

-==============

-VisChopWinding

-

-==============

-*/

-winding_t	*VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split)

-{

-	vec_t	dists[128];

-	int		sides[128];

-	int		counts[3];

-	vec_t	dot;

-	int		i, j;

-	vec_t	*p1, *p2;

-	vec3_t	mid;

-	winding_t	*neww;

-

-	counts[0] = counts[1] = counts[2] = 0;

-

-	// determine sides for each point

-	for (i=0 ; i<in->numpoints ; i++)

-	{

-		dot = DotProduct (in->points[i], split->normal);

-		dot -= split->dist;

-		dists[i] = dot;

-		if (dot > ON_EPSILON)

-			sides[i] = SIDE_FRONT;

-		else if (dot < -ON_EPSILON)

-			sides[i] = SIDE_BACK;

-		else

-		{

-			sides[i] = SIDE_ON;

-		}

-		counts[sides[i]]++;

-	}

-

-	if (!counts[1])

-		return in;		// completely on front side

-	

-	if (!counts[0])

-	{

-		FreeStackWinding (in, stack);

-		return NULL;

-	}

-

-	sides[i] = sides[0];

-	dists[i] = dists[0];

-	

-	neww = AllocStackWinding (stack);

-

-	neww->numpoints = 0;

-

-	for (i=0 ; i<in->numpoints ; i++)

-	{

-		p1 = in->points[i];

-

-		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)

-		{

-			FreeStackWinding (neww, stack);

-			return in;		// can't chop -- fall back to original

-		}

-

-		if (sides[i] == SIDE_ON)

-		{

-			VectorCopy (p1, neww->points[neww->numpoints]);

-			neww->numpoints++;

-			continue;

-		}

-	

-		if (sides[i] == SIDE_FRONT)

-		{

-			VectorCopy (p1, neww->points[neww->numpoints]);

-			neww->numpoints++;

-		}

-		

-		if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])

-			continue;

-			

-		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)

-		{

-			FreeStackWinding (neww, stack);

-			return in;		// can't chop -- fall back to original

-		}

-

-		// generate a split point

-		p2 = in->points[(i+1)%in->numpoints];

-		

-		dot = dists[i] / (dists[i]-dists[i+1]);

-		for (j=0 ; j<3 ; j++)

-		{	// avoid round off error when possible

-			if (split->normal[j] == 1)

-				mid[j] = split->dist;

-			else if (split->normal[j] == -1)

-				mid[j] = -split->dist;

-			else

-				mid[j] = p1[j] + dot*(p2[j]-p1[j]);

-		}

-			

-		VectorCopy (mid, neww->points[neww->numpoints]);

-		neww->numpoints++;

-	}

-	

-	// free the original winding

-	FreeStackWinding (in, stack);

-	

-	return neww;

-}

-

-/*

-==============

-ClipToSeperators

-

-Source, pass, and target are an ordering of portals.

-

-Generates seperating planes canidates by taking two points from source and one

-point from pass, and clips target by them.

-

-If target is totally clipped away, that portal can not be seen through.

-

-Normal clip keeps target on the same side as pass, which is correct if the

-order goes source, pass, target.  If the order goes pass, source, target then

-flipclip should be set.

-==============

-*/

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

-{

-	int			i, j, k, l;

-	plane_t		plane;

-	vec3_t		v1, v2;

-	float		d;

-	vec_t		length;

-	int			counts[3];

-	qboolean		fliptest;

-

-	// check all combinations	

-	for (i=0 ; i<source->numpoints ; i++)

-	{

-		l = (i+1)%source->numpoints;

-		VectorSubtract (source->points[l] , source->points[i], v1);

-

-		// find a vertex of pass that makes a plane that puts all of the

-		// vertexes of pass on the front side and all of the vertexes of

-		// source on the back side

-		for (j=0 ; j<pass->numpoints ; j++)

-		{

-			VectorSubtract (pass->points[j], source->points[i], v2);

-

-			plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];

-			plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];

-			plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];

-			

-			// if points don't make a valid plane, skip it

-

-			length = plane.normal[0] * plane.normal[0]

-			+ plane.normal[1] * plane.normal[1]

-			+ plane.normal[2] * plane.normal[2];

-			

-			if (length < ON_EPSILON)

-				continue;

-

-			length = 1/sqrt(length);

-			

-			plane.normal[0] *= length;

-			plane.normal[1] *= length;

-			plane.normal[2] *= length;

-

-			plane.dist = DotProduct (pass->points[j], plane.normal);

-

-			//

-			// find out which side of the generated seperating plane has the

-			// source portal

-			//

-#if 1

-			fliptest = qfalse;

-			for (k=0 ; k<source->numpoints ; k++)

-			{

-				if (k == i || k == l)

-					continue;

-				d = DotProduct (source->points[k], plane.normal) - plane.dist;

-				if (d < -ON_EPSILON)

-				{	// source is on the negative side, so we want all

-					// pass and target on the positive side

-					fliptest = qfalse;

-					break;

-				}

-				else if (d > ON_EPSILON)

-				{	// source is on the positive side, so we want all

-					// pass and target on the negative side

-					fliptest = qtrue;

-					break;

-				}

-			}

-			if (k == source->numpoints)

-				continue;		// planar with source portal

-#else

-			fliptest = flipclip;

-#endif

-			//

-			// flip the normal if the source portal is backwards

-			//

-			if (fliptest)

-			{

-				VectorSubtract (vec3_origin, plane.normal, plane.normal);

-				plane.dist = -plane.dist;

-			}

-#if 1

-			//

-			// if all of the pass portal points are now on the positive side,

-			// this is the seperating plane

-			//

-			counts[0] = counts[1] = counts[2] = 0;

-			for (k=0 ; k<pass->numpoints ; k++)

-			{

-				if (k==j)

-					continue;

-				d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-				if (d < -ON_EPSILON)

-					break;

-				else if (d > ON_EPSILON)

-					counts[0]++;

-				else

-					counts[2]++;

-			}

-			if (k != pass->numpoints)

-				continue;	// points on negative side, not a seperating plane

-				

-			if (!counts[0])

-				continue;	// planar with seperating plane

-#else

-			k = (j+1)%pass->numpoints;

-			d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-			if (d < -ON_EPSILON)

-				continue;

-			k = (j+pass->numpoints-1)%pass->numpoints;

-			d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-			if (d < -ON_EPSILON)

-				continue;			

-#endif

-			//

-			// flip the normal if we want the back side

-			//

-			if (flipclip)

-			{

-				VectorSubtract (vec3_origin, plane.normal, plane.normal);

-				plane.dist = -plane.dist;

-			}

-

-#ifdef SEPERATORCACHE

-			stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;

-			if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)

-				Error("MAX_SEPERATORS");

-#endif

-			//MrE: fast check first

-			d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;

-			//if completely at the back of the seperator plane

-			if (d < -stack->portal->radius)

-				return NULL;

-			//if completely on the front of the seperator plane

-			if (d > stack->portal->radius)

-				break;

-

-			//

-			// clip target by the seperating plane

-			//

-			target = VisChopWinding (target, stack, &plane);

-			if (!target)

-				return NULL;		// target is not visible

-

-			break;		// optimization by Antony Suter

-		}

-	}

-	

-	return target;

-}

-

-/*

-==================

-RecursiveLeafFlow

-

-Flood fill through the leafs

-If src_portal is NULL, this is the originating leaf

-==================

-*/

-void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)

-{

-	pstack_t	stack;

-	vportal_t	*p;

-	plane_t		backplane;

-	leaf_t 		*leaf;

-	int			i, j, n;

-	long		*test, *might, *prevmight, *vis, more;

-	int			pnum;

-

-	thread->c_chains++;

-

-	leaf = &leafs[leafnum];

-//	CheckStack (leaf, thread);

-

-	prevstack->next = &stack;

-

-	stack.next = NULL;

-	stack.leaf = leaf;

-	stack.portal = NULL;

-	stack.depth = prevstack->depth + 1;

-

-#ifdef SEPERATORCACHE

-	stack.numseperators[0] = 0;

-	stack.numseperators[1] = 0;

-#endif

-

-	might = (long *)stack.mightsee;

-	vis = (long *)thread->base->portalvis;

-	

-	// check all portals for flowing into other leafs	

-	for (i = 0; i < leaf->numportals; i++)

-	{

-		p = leaf->portals[i];

-		if (p->removed)

-			continue;

-		pnum = p - portals;

-

-		/* MrE: portal trace debug code

-		{

-			int portaltrace[] = {13, 16, 17, 37};

-			pstack_t *s;

-

-			s = &thread->pstack_head;

-			for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)

-			{

-				if (s->portal->num != portaltrace[j])

-					break;

-			}

-			if (j >= sizeof(portaltrace)/sizeof(int) - 1)

-			{

-				if (p->num == portaltrace[j])

-					n = 0; //traced through all the portals

-			}

-		}

-		*/

-

-		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )

-		{

-			continue;	// can't possibly see it

-		}

-

-		// if the portal can't see anything we haven't allready seen, skip it

-		if (p->status == stat_done)

-		{

-			test = (long *)p->portalvis;

-		}

-		else

-		{

-			test = (long *)p->portalflood;

-		}

-

-		more = 0;

-		prevmight = (long *)prevstack->mightsee;

-		for (j=0 ; j<portallongs ; j++)

-		{

-			might[j] = prevmight[j] & test[j];

-			more |= (might[j] & ~vis[j]);

-		}

-		

-		if (!more && 

-			(thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )

-		{	// can't see anything new

-			continue;

-		}

-

-		// get plane of portal, point normal into the neighbor leaf

-		stack.portalplane = p->plane;

-		VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);

-		backplane.dist = -p->plane.dist;

-		

-//		c_portalcheck++;

-		

-		stack.portal = p;

-		stack.next = NULL;

-		stack.freewindings[0] = 1;

-		stack.freewindings[1] = 1;

-		stack.freewindings[2] = 1;

-		

-#if 1

-		{

-			float d;

-

-			d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);

-			d -= thread->pstack_head.portalplane.dist;

-			if (d < -p->radius)

-			{

-				continue;

-			}

-			else if (d > p->radius)

-			{

-				stack.pass = p->winding;

-			}

-			else	

-			{

-				stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);

-				if (!stack.pass)

-					continue;

-			}

-		}

-#else

-		stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);

-		if (!stack.pass)

-			continue;

-#endif

-

-	

-#if 1

-		{

-			float d;

-

-			d = DotProduct (thread->base->origin, p->plane.normal);

-			d -= p->plane.dist;

-			//MrE: vis-bug fix

-			//if (d > p->radius)

-			if (d > thread->base->radius)

-			{

-				continue;

-			}

-			//MrE: vis-bug fix

-			//if (d < -p->radius)

-			else if (d < -thread->base->radius)

-			{

-				stack.source = prevstack->source;

-			}

-			else	

-			{

-				stack.source = VisChopWinding (prevstack->source, &stack, &backplane);

-				//FIXME: shouldn't we create a new source origin and radius for fast checks?

-				if (!stack.source)

-					continue;

-			}

-		}

-#else

-		stack.source = VisChopWinding (prevstack->source, &stack, &backplane);

-		if (!stack.source)

-			continue;

-#endif

-

-		if (!prevstack->pass)

-		{	// the second leaf can only be blocked if coplanar

-

-			// mark the portal as visible

-			thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

-

-			RecursiveLeafFlow (p->leaf, thread, &stack);

-			continue;

-		}

-

-#ifdef SEPERATORCACHE

-		if (stack.numseperators[0])

-		{

-			for (n = 0; n < stack.numseperators[0]; n++)

-			{

-				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);

-				if (!stack.pass)

-					break;		// target is not visible

-			}

-			if (n < stack.numseperators[0])

-				continue;

-		}

-		else

-		{

-			stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);

-		}

-#else

-		stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);

-#endif

-		if (!stack.pass)

-			continue;

-

-#ifdef SEPERATORCACHE

-		if (stack.numseperators[1])

-		{

-			for (n = 0; n < stack.numseperators[1]; n++)

-			{

-				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);

-				if (!stack.pass)

-					break;		// target is not visible

-			}

-		}

-		else

-		{

-			stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);

-		}

-#else

-		stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);

-#endif

-		if (!stack.pass)

-			continue;

-

-		// mark the portal as visible

-		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

-

-		// flow through it for real

-		RecursiveLeafFlow (p->leaf, thread, &stack);

-		//

-		stack.next = NULL;

-	}	

-}

-

-/*

-===============

-PortalFlow

-

-generates the portalvis bit vector

-===============

-*/

-void PortalFlow (int portalnum)

-{

-	threaddata_t	data;

-	int				i;

-	vportal_t		*p;

-	int				c_might, c_can;

-

-#ifdef MREDEBUG

-	_printf("\r%6d", portalnum);

-#endif

-

-	p = sorted_portals[portalnum];

-

-	if (p->removed)

-	{

-		p->status = stat_done;

-		return;

-	}

-

-	p->status = stat_working;

-

-	c_might = CountBits (p->portalflood, numportals*2);

-

-	memset (&data, 0, sizeof(data));

-	data.base = p;

-	

-	data.pstack_head.portal = p;

-	data.pstack_head.source = p->winding;

-	data.pstack_head.portalplane = p->plane;

-	data.pstack_head.depth = 0;

-	for (i=0 ; i<portallongs ; i++)

-		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

-

-	RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);

-

-	p->status = stat_done;

-

-	c_can = CountBits (p->portalvis, numportals*2);

-

-	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 

-		(int)(p - portals),	c_might, c_can, data.c_chains);

-}

-

-/*

-==================

-RecursivePassageFlow

-==================

-*/

-void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)

-{

-	pstack_t	stack;

-	vportal_t	*p;

-	leaf_t 		*leaf;

-	passage_t	*passage, *nextpassage;

-	int			i, j;

-	long		*might, *vis, *prevmight, *cansee, *portalvis, more;

-	int			pnum;

-

-	leaf = &leafs[portal->leaf];

-

-	prevstack->next = &stack;

-

-	stack.next = NULL;

-	stack.depth = prevstack->depth + 1;

-

-	vis = (long *)thread->base->portalvis;

-

-	passage = portal->passages;

-	nextpassage = passage;

-	// check all portals for flowing into other leafs	

-	for (i = 0; i < leaf->numportals; i++, passage = nextpassage)

-	{

-		p = leaf->portals[i];

-		if ( p->removed ) {

-			continue;

-		}

-		nextpassage = passage->next;

-		pnum = p - portals;

-

-		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {

-			continue;	// can't possibly see it

-		}

-

-		// mark the portal as visible

-		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

-

-		prevmight = (long *)prevstack->mightsee;

-		cansee = (long *)passage->cansee;

-		might = (long *)stack.mightsee;

-		memcpy(might, prevmight, portalbytes);

-		if (p->status == stat_done)

-			portalvis = (long *) p->portalvis;

-		else

-			portalvis = (long *) p->portalflood;

-		more = 0;

-		for (j = 0; j < portallongs; j++)

-		{

-			if (*might)

-			{

-				*might &= *cansee++ & *portalvis++;

-				more |= (*might & ~vis[j]);

-			}

-			else

-			{

-				cansee++;

-				portalvis++;

-			}

-			might++;

-		}

-

-		if ( !more ) {

-			// can't see anything new

-			continue;

-		}

-

-		// flow through it for real

-		RecursivePassageFlow(p, thread, &stack);

-

-		stack.next = NULL;

-	}

-}

-

-/*

-===============

-PassageFlow

-===============

-*/

-void PassageFlow (int portalnum)

-{

-	threaddata_t	data;

-	int				i;

-	vportal_t		*p;

-//	int				c_might, c_can;

-

-#ifdef MREDEBUG

-	_printf("\r%6d", portalnum);

-#endif

-

-	p = sorted_portals[portalnum];

-

-	if (p->removed)

-	{

-		p->status = stat_done;

-		return;

-	}

-

-	p->status = stat_working;

-

-//	c_might = CountBits (p->portalflood, numportals*2);

-

-	memset (&data, 0, sizeof(data));

-	data.base = p;

-	

-	data.pstack_head.portal = p;

-	data.pstack_head.source = p->winding;

-	data.pstack_head.portalplane = p->plane;

-	data.pstack_head.depth = 0;

-	for (i=0 ; i<portallongs ; i++)

-		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

-

-	RecursivePassageFlow (p, &data, &data.pstack_head);

-

-	p->status = stat_done;

-

-	/*

-	c_can = CountBits (p->portalvis, numportals*2);

-

-	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 

-		(int)(p - portals),	c_might, c_can, data.c_chains);

-	*/

-}

-

-/*

-==================

-RecursivePassagePortalFlow

-==================

-*/

-void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)

-{

-	pstack_t	stack;

-	vportal_t	*p;

-	leaf_t 		*leaf;

-	plane_t		backplane;

-	passage_t	*passage, *nextpassage;

-	int			i, j, n;

-	long		*might, *vis, *prevmight, *cansee, *portalvis, more;

-	int			pnum;

-

-//	thread->c_chains++;

-

-	leaf = &leafs[portal->leaf];

-//	CheckStack (leaf, thread);

-

-	prevstack->next = &stack;

-

-	stack.next = NULL;

-	stack.leaf = leaf;

-	stack.portal = NULL;

-	stack.depth = prevstack->depth + 1;

-

-#ifdef SEPERATORCACHE

-	stack.numseperators[0] = 0;

-	stack.numseperators[1] = 0;

-#endif

-

-	vis = (long *)thread->base->portalvis;

-

-	passage = portal->passages;

-	nextpassage = passage;

-	// check all portals for flowing into other leafs	

-	for (i = 0; i < leaf->numportals; i++, passage = nextpassage)

-	{

-		p = leaf->portals[i];

-		if (p->removed)

-			continue;

-		nextpassage = passage->next;

-		pnum = p - portals;

-

-		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )

-			continue;	// can't possibly see it

-

-		prevmight = (long *)prevstack->mightsee;

-		cansee = (long *)passage->cansee;

-		might = (long *)stack.mightsee;

-		memcpy(might, prevmight, portalbytes);

-		if (p->status == stat_done)

-			portalvis = (long *) p->portalvis;

-		else

-			portalvis = (long *) p->portalflood;

-		more = 0;

-		for (j = 0; j < portallongs; j++)

-		{

-			if (*might)

-			{

-				*might &= *cansee++ & *portalvis++;

-				more |= (*might & ~vis[j]);

-			}

-			else

-			{

-				cansee++;

-				portalvis++;

-			}

-			might++;

-		}

-

-		if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )

-		{	// can't see anything new

-			continue;

-		}

-

-		// get plane of portal, point normal into the neighbor leaf

-		stack.portalplane = p->plane;

-		VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);

-		backplane.dist = -p->plane.dist;

-		

-//		c_portalcheck++;

-		

-		stack.portal = p;

-		stack.next = NULL;

-		stack.freewindings[0] = 1;

-		stack.freewindings[1] = 1;

-		stack.freewindings[2] = 1;

-

-#if 1

-		{

-			float d;

-

-			d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);

-			d -= thread->pstack_head.portalplane.dist;

-			if (d < -p->radius)

-			{

-				continue;

-			}

-			else if (d > p->radius)

-			{

-				stack.pass = p->winding;

-			}

-			else	

-			{

-				stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);

-				if (!stack.pass)

-					continue;

-			}

-		}

-#else

-		stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);

-		if (!stack.pass)

-			continue;

-#endif

-

-	

-#if 1

-		{

-			float d;

-

-			d = DotProduct (thread->base->origin, p->plane.normal);

-			d -= p->plane.dist;

-			//MrE: vis-bug fix

-			//if (d > p->radius)

-			if (d > thread->base->radius)

-			{

-				continue;

-			}

-			//MrE: vis-bug fix

-			//if (d < -p->radius)

-			else if (d < -thread->base->radius)

-			{

-				stack.source = prevstack->source;

-			}

-			else	

-			{

-				stack.source = VisChopWinding (prevstack->source, &stack, &backplane);

-				//FIXME: shouldn't we create a new source origin and radius for fast checks?

-				if (!stack.source)

-					continue;

-			}

-		}

-#else

-		stack.source = VisChopWinding (prevstack->source, &stack, &backplane);

-		if (!stack.source)

-			continue;

-#endif

-

-		if (!prevstack->pass)

-		{	// the second leaf can only be blocked if coplanar

-

-			// mark the portal as visible

-			thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

-

-			RecursivePassagePortalFlow (p, thread, &stack);

-			continue;

-		}

-

-#ifdef SEPERATORCACHE

-		if (stack.numseperators[0])

-		{

-			for (n = 0; n < stack.numseperators[0]; n++)

-			{

-				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);

-				if (!stack.pass)

-					break;		// target is not visible

-			}

-			if (n < stack.numseperators[0])

-				continue;

-		}

-		else

-		{

-			stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);

-		}

-#else

-		stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);

-#endif

-		if (!stack.pass)

-			continue;

-

-#ifdef SEPERATORCACHE

-		if (stack.numseperators[1])

-		{

-			for (n = 0; n < stack.numseperators[1]; n++)

-			{

-				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);

-				if (!stack.pass)

-					break;		// target is not visible

-			}

-		}

-		else

-		{

-			stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);

-		}

-#else

-		stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);

-#endif

-		if (!stack.pass)

-			continue;

-

-		// mark the portal as visible

-		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

-

-		// flow through it for real

-		RecursivePassagePortalFlow(p, thread, &stack);

-		//

-		stack.next = NULL;

-	}

-}

-

-/*

-===============

-PassagePortalFlow

-===============

-*/

-void PassagePortalFlow (int portalnum)

-{

-	threaddata_t	data;

-	int				i;

-	vportal_t		*p;

-//	int				c_might, c_can;

-

-#ifdef MREDEBUG

-	_printf("\r%6d", portalnum);

-#endif

-

-	p = sorted_portals[portalnum];

-

-	if (p->removed)

-	{

-		p->status = stat_done;

-		return;

-	}

-

-	p->status = stat_working;

-

-//	c_might = CountBits (p->portalflood, numportals*2);

-

-	memset (&data, 0, sizeof(data));

-	data.base = p;

-	

-	data.pstack_head.portal = p;

-	data.pstack_head.source = p->winding;

-	data.pstack_head.portalplane = p->plane;

-	data.pstack_head.depth = 0;

-	for (i=0 ; i<portallongs ; i++)

-		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

-

-	RecursivePassagePortalFlow (p, &data, &data.pstack_head);

-

-	p->status = stat_done;

-

-	/*

-	c_can = CountBits (p->portalvis, numportals*2);

-

-	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 

-		(int)(p - portals),	c_might, c_can, data.c_chains);

-	*/

-}

-

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

-{

-	vec_t	dists[128];

-	int		sides[128];

-	int		counts[3];

-	vec_t	dot;

-	int		i, j;

-	vec_t	*p1, *p2;

-	vec3_t	mid;

-	winding_t	*neww;

-

-	counts[0] = counts[1] = counts[2] = 0;

-

-	// determine sides for each point

-	for (i=0 ; i<in->numpoints ; i++)

-	{

-		dot = DotProduct (in->points[i], split->normal);

-		dot -= split->dist;

-		dists[i] = dot;

-		if (dot > ON_EPSILON)

-			sides[i] = SIDE_FRONT;

-		else if (dot < -ON_EPSILON)

-			sides[i] = SIDE_BACK;

-		else

-		{

-			sides[i] = SIDE_ON;

-		}

-		counts[sides[i]]++;

-	}

-

-	if (!counts[1])

-		return in;		// completely on front side

-	

-	if (!counts[0])

-	{

-		return NULL;

-	}

-

-	sides[i] = sides[0];

-	dists[i] = dists[0];

-	

-	neww = out;

-

-	neww->numpoints = 0;

-

-	for (i=0 ; i<in->numpoints ; i++)

-	{

-		p1 = in->points[i];

-

-		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)

-		{

-			return in;		// can't chop -- fall back to original

-		}

-

-		if (sides[i] == SIDE_ON)

-		{

-			VectorCopy (p1, neww->points[neww->numpoints]);

-			neww->numpoints++;

-			continue;

-		}

-	

-		if (sides[i] == SIDE_FRONT)

-		{

-			VectorCopy (p1, neww->points[neww->numpoints]);

-			neww->numpoints++;

-		}

-		

-		if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])

-			continue;

-			

-		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)

-		{

-			return in;		// can't chop -- fall back to original

-		}

-

-		// generate a split point

-		p2 = in->points[(i+1)%in->numpoints];

-		

-		dot = dists[i] / (dists[i]-dists[i+1]);

-		for (j=0 ; j<3 ; j++)

-		{	// avoid round off error when possible

-			if (split->normal[j] == 1)

-				mid[j] = split->dist;

-			else if (split->normal[j] == -1)

-				mid[j] = -split->dist;

-			else

-				mid[j] = p1[j] + dot*(p2[j]-p1[j]);

-		}

-			

-		VectorCopy (mid, neww->points[neww->numpoints]);

-		neww->numpoints++;

-	}

-	

-	return neww;

-}

-

-/*

-===============

-AddSeperators

-===============

-*/

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

-{

-	int			i, j, k, l;

-	plane_t		plane;

-	vec3_t		v1, v2;

-	float		d;

-	vec_t		length;

-	int			counts[3], numseperators;

-	qboolean	fliptest;

-

-	numseperators = 0;

-	// check all combinations	

-	for (i=0 ; i<source->numpoints ; i++)

-	{

-		l = (i+1)%source->numpoints;

-		VectorSubtract (source->points[l] , source->points[i], v1);

-

-		// find a vertex of pass that makes a plane that puts all of the

-		// vertexes of pass on the front side and all of the vertexes of

-		// source on the back side

-		for (j=0 ; j<pass->numpoints ; j++)

-		{

-			VectorSubtract (pass->points[j], source->points[i], v2);

-

-			plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];

-			plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];

-			plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];

-			

-			// if points don't make a valid plane, skip it

-

-			length = plane.normal[0] * plane.normal[0]

-			+ plane.normal[1] * plane.normal[1]

-			+ plane.normal[2] * plane.normal[2];

-			

-			if (length < ON_EPSILON)

-				continue;

-

-			length = 1/sqrt(length);

-			

-			plane.normal[0] *= length;

-			plane.normal[1] *= length;

-			plane.normal[2] *= length;

-

-			plane.dist = DotProduct (pass->points[j], plane.normal);

-

-			//

-			// find out which side of the generated seperating plane has the

-			// source portal

-			//

-#if 1

-			fliptest = qfalse;

-			for (k=0 ; k<source->numpoints ; k++)

-			{

-				if (k == i || k == l)

-					continue;

-				d = DotProduct (source->points[k], plane.normal) - plane.dist;

-				if (d < -ON_EPSILON)

-				{	// source is on the negative side, so we want all

-					// pass and target on the positive side

-					fliptest = qfalse;

-					break;

-				}

-				else if (d > ON_EPSILON)

-				{	// source is on the positive side, so we want all

-					// pass and target on the negative side

-					fliptest = qtrue;

-					break;

-				}

-			}

-			if (k == source->numpoints)

-				continue;		// planar with source portal

-#else

-			fliptest = flipclip;

-#endif

-			//

-			// flip the normal if the source portal is backwards

-			//

-			if (fliptest)

-			{

-				VectorSubtract (vec3_origin, plane.normal, plane.normal);

-				plane.dist = -plane.dist;

-			}

-#if 1

-			//

-			// if all of the pass portal points are now on the positive side,

-			// this is the seperating plane

-			//

-			counts[0] = counts[1] = counts[2] = 0;

-			for (k=0 ; k<pass->numpoints ; k++)

-			{

-				if (k==j)

-					continue;

-				d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-				if (d < -ON_EPSILON)

-					break;

-				else if (d > ON_EPSILON)

-					counts[0]++;

-				else

-					counts[2]++;

-			}

-			if (k != pass->numpoints)

-				continue;	// points on negative side, not a seperating plane

-				

-			if (!counts[0])

-				continue;	// planar with seperating plane

-#else

-			k = (j+1)%pass->numpoints;

-			d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-			if (d < -ON_EPSILON)

-				continue;

-			k = (j+pass->numpoints-1)%pass->numpoints;

-			d = DotProduct (pass->points[k], plane.normal) - plane.dist;

-			if (d < -ON_EPSILON)

-				continue;			

-#endif

-			//

-			// flip the normal if we want the back side

-			//

-			if (flipclip)

-			{

-				VectorSubtract (vec3_origin, plane.normal, plane.normal);

-				plane.dist = -plane.dist;

-			}

-

-			if (numseperators >= maxseperators)

-				Error("max seperators");

-			seperators[numseperators] = plane;

-			numseperators++;

-			break;

-		}

-	}

-	return numseperators;

-}

-

-/*

-===============

-CreatePassages

-

-MrE: create passages from one portal to all the portals in the leaf the portal leads to

-	 every passage has a cansee bit string with all the portals that can be

-	 seen through the passage

-===============

-*/

-void CreatePassages(int portalnum)

-{

-	int i, j, k, n, numseperators, numsee;

-	float d;

-	vportal_t *portal, *p, *target;

-	leaf_t *leaf;

-	passage_t	*passage, *lastpassage;

-	plane_t seperators[MAX_SEPERATORS*2];

-	winding_t *w;

-	winding_t in, out, *res;

-

-#ifdef MREDEBUG

-	_printf("\r%6d", portalnum);

-#endif

-

-	portal = sorted_portals[portalnum];

-

-	if (portal->removed)

-	{

-		portal->status = stat_done;

-		return;

-	}

-

-	lastpassage = NULL;

-	leaf = &leafs[portal->leaf];

-	for (i = 0; i < leaf->numportals; i++)

-	{

-		target = leaf->portals[i];

-		if (target->removed)

-			continue;

-

-		passage = (passage_t *) malloc(sizeof(passage_t) + portalbytes);

-		memset(passage, 0, sizeof(passage_t) + portalbytes);

-		numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);

-		numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);

-

-		passage->next = NULL;

-		if (lastpassage)

-			lastpassage->next = passage;

-		else

-			portal->passages = passage;

-		lastpassage = passage;

-

-		numsee = 0;

-		//create the passage->cansee

-		for (j = 0; j < numportals * 2; j++)

-		{

-			p = &portals[j];

-			if (p->removed)

-				continue;

-			if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )

-				continue;

-			if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )

-				continue;

-			for (k = 0; k < numseperators; k++)

-			{

-				//

-				d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;

-				//if completely at the back of the seperator plane

-				if (d < -p->radius + ON_EPSILON)

-					break;

-				w = p->winding;

-				for (n = 0; n < w->numpoints; n++)

-				{

-					d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;

-					//if at the front of the seperator

-					if (d > ON_EPSILON)

-						break;

-				}

-				//if no points are at the front of the seperator

-				if (n >= w->numpoints)

-					break;

-			}

-			if (k < numseperators)

-				continue;

-			memcpy(&in, p->winding, sizeof(winding_t));

-			for (k = 0; k < numseperators; k++)

-			{

-				res = PassageChopWinding(&in, &out, &seperators[k]);

-				if (res == &out)

-					memcpy(&in, &out, sizeof(winding_t));

-				if (res == NULL)

-					break;

-			}

-			if (k < numseperators)

-				continue;

-			passage->cansee[j >> 3] |= (1<<(j&7));

-			numsee++;

-		}

-	}

-}

-

-void PassageMemory(void)

-{

-	int i, j, totalmem, totalportals;

-	vportal_t *portal, *target;

-	leaf_t *leaf;

-

-	totalmem = 0;

-	totalportals = 0;

-	for (i = 0; i < numportals; i++)

-	{

-		portal = sorted_portals[i];

-		if (portal->removed)

-			continue;

-		leaf = &leafs[portal->leaf];

-		for (j = 0; j < leaf->numportals; j++)

-		{

-			target = leaf->portals[j];

-			if (target->removed)

-				continue;

-			totalmem += sizeof(passage_t) + portalbytes;

-			totalportals++;

-		}

-	}

-	_printf("%7i average number of passages per leaf\n", totalportals / numportals);

-	_printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);

-}

-

-/*

-===============================================================================

-

-This is a rough first-order aproximation that is used to trivially reject some

-of the final calculations.

-

-

-Calculates portalfront and portalflood bit vectors

-

-thinking about:

-

-typedef struct passage_s

-{

-	struct passage_s	*next;

-	struct portal_s		*to;

-	stryct sep_s		*seperators;

-	byte				*mightsee;

-} passage_t;

-

-typedef struct portal_s

-{

-	struct passage_s	*passages;

-	int					leaf;		// leaf portal faces into

-} portal_s;

-

-leaf = portal->leaf

-clear 

-for all portals

-

-

-calc portal visibility

-	clear bit vector

-	for all passages

-		passage visibility

-

-

-for a portal to be visible to a passage, it must be on the front of

-all seperating planes, and both portals must be behind the new portal

-

-===============================================================================

-*/

-

-int		c_flood, c_vis;

-

-

-/*

-==================

-SimpleFlood

-

-==================

-*/

-void SimpleFlood (vportal_t *srcportal, int leafnum)

-{

-	int		i;

-	leaf_t	*leaf;

-	vportal_t	*p;

-	int		pnum;

-

-	leaf = &leafs[leafnum];

-	

-	for (i=0 ; i<leaf->numportals ; i++)

-	{

-		p = leaf->portals[i];

-		if (p->removed)

-			continue;

-		pnum = p - portals;

-		if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )

-			continue;

-

-		if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )

-			continue;

-

-		srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));

-		

-		SimpleFlood (srcportal, p->leaf);

-	}

-}

-

-/*

-==============

-BasePortalVis

-==============

-*/

-void BasePortalVis (int portalnum)

-{

-	int			j, k;

-	vportal_t	*tp, *p;

-	float		d;

-	winding_t	*w;

-

-	p = portals+portalnum;

-

-	if (p->removed)

-		return;

-

-	p->portalfront = malloc (portalbytes);

-	memset (p->portalfront, 0, portalbytes);

-

-	p->portalflood = malloc (portalbytes);

-	memset (p->portalflood, 0, portalbytes);

-	

-	p->portalvis = malloc (portalbytes);

-	memset (p->portalvis, 0, portalbytes);

-	

-	for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)

-	{

-		if (j == portalnum)

-			continue;

-		if (tp->removed)

-			continue;

-		/*

-		if (farplanedist >= 0)

-		{

-			vec3_t dir;

-			VectorSubtract(p->origin, tp->origin, dir);

-			if (VectorLength(dir) > farplanedist - p->radius - tp->radius)

-				continue;

-		}

-		*/

-		w = tp->winding;

-		for (k=0 ; k<w->numpoints ; k++)

-		{

-			d = DotProduct (w->points[k], p->plane.normal)

-				- p->plane.dist;

-			if (d > ON_EPSILON)

-				break;

-		}

-		if (k == w->numpoints)

-			continue;	// no points on front

-

-		w = p->winding;

-		for (k=0 ; k<w->numpoints ; k++)

-		{

-			d = DotProduct (w->points[k], tp->plane.normal)

-				- tp->plane.dist;

-			if (d < -ON_EPSILON)

-				break;

-		}

-		if (k == w->numpoints)

-			continue;	// no points on front

-

-		p->portalfront[j>>3] |= (1<<(j&7));

-	}

-	

-	SimpleFlood (p, p->leaf);

-

-	p->nummightsee = CountBits (p->portalflood, numportals*2);

-//	_printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);

-	c_flood += p->nummightsee;

-}

-

-

-

-

-

-/*

-===============================================================================

-

-This is a second order aproximation 

-

-Calculates portalvis bit vector

-

-WAAAAAAY too slow.

-

-===============================================================================

-*/

-

-/*

-==================

-RecursiveLeafBitFlow

-

-==================

-*/

-void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)

-{

-	vportal_t	*p;

-	leaf_t 		*leaf;

-	int			i, j;

-	long		more;

-	int			pnum;

-	byte		newmight[MAX_PORTALS/8];

-

-	leaf = &leafs[leafnum];

-	

-	// check all portals for flowing into other leafs

-	for (i=0 ; i<leaf->numportals ; i++)

-	{

-		p = leaf->portals[i];

-		if (p->removed)

-			continue;

-		pnum = p - portals;

-

-		// if some previous portal can't see it, skip

-		if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )

-			continue;

-

-		// if this portal can see some portals we mightsee, recurse

-		more = 0;

-		for (j=0 ; j<portallongs ; j++)

-		{

-			((long *)newmight)[j] = ((long *)mightsee)[j] 

-				& ((long *)p->portalflood)[j];

-			more |= ((long *)newmight)[j] & ~((long *)cansee)[j];

-		}

-

-		if (!more)

-			continue;	// can't see anything new

-

-		cansee[pnum>>3] |= (1<<(pnum&7));

-

-		RecursiveLeafBitFlow (p->leaf, newmight, cansee);

-	}	

-}

-

-/*

-==============

-BetterPortalVis

-==============

-*/

-void BetterPortalVis (int portalnum)

-{

-	vportal_t	*p;

-

-	p = portals+portalnum;

-

-	if (p->removed)

-		return;

-

-	RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);

-

-	// build leaf vis information

-	p->nummightsee = CountBits (p->portalvis, numportals*2);

-	c_vis += p->nummightsee;

-}

-

-

+#include "vis.h"
+
+/*
+
+  each portal will have a list of all possible to see from first portal
+
+  if (!thread->portalmightsee[portalnum])
+
+  portal mightsee
+
+  for p2 = all other portals in leaf
+	get sperating planes
+	for all portals that might be seen by p2
+		mark as unseen if not present in seperating plane
+	flood fill a new mightsee
+	save as passagemightsee
+
+
+  void CalcMightSee (leaf_t *leaf, 
+*/
+
+int CountBits (byte *bits, int numbits)
+{
+	int		i;
+	int		c;
+
+	c = 0;
+	for (i=0 ; i<numbits ; i++)
+		if (bits[i>>3] & (1<<(i&7)) )
+			c++;
+
+	return c;
+}
+
+int		c_fullskip;
+int		c_portalskip, c_leafskip;
+int		c_vistest, c_mighttest;
+
+int		c_chop, c_nochop;
+
+int		active;
+
+void CheckStack (leaf_t *leaf, threaddata_t *thread)
+{
+	pstack_t	*p, *p2;
+
+	for (p=thread->pstack_head.next ; p ; p=p->next)
+	{
+//		_printf ("=");
+		if (p->leaf == leaf)
+			Error ("CheckStack: leaf recursion");
+		for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
+			if (p2->leaf == p->leaf)
+				Error ("CheckStack: late leaf recursion");
+	}
+//	_printf ("\n");
+}
+
+
+winding_t *AllocStackWinding (pstack_t *stack)
+{
+	int		i;
+
+	for (i=0 ; i<3 ; i++)
+	{
+		if (stack->freewindings[i])
+		{
+			stack->freewindings[i] = 0;
+			return &stack->windings[i];
+		}
+	}
+
+	Error ("AllocStackWinding: failed");
+
+	return NULL;
+}
+
+void FreeStackWinding (winding_t *w, pstack_t *stack)
+{
+	int		i;
+
+	i = w - stack->windings;
+
+	if (i<0 || i>2)
+		return;		// not from local
+
+	if (stack->freewindings[i])
+		Error ("FreeStackWinding: allready free");
+	stack->freewindings[i] = 1;
+}
+
+/*
+==============
+VisChopWinding
+
+==============
+*/
+winding_t	*VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
+{
+	vec_t	dists[128];
+	int		sides[128];
+	int		counts[3];
+	vec_t	dot;
+	int		i, j;
+	vec_t	*p1, *p2;
+	vec3_t	mid;
+	winding_t	*neww;
+
+	counts[0] = counts[1] = counts[2] = 0;
+
+	// determine sides for each point
+	for (i=0 ; i<in->numpoints ; i++)
+	{
+		dot = DotProduct (in->points[i], split->normal);
+		dot -= split->dist;
+		dists[i] = dot;
+		if (dot > ON_EPSILON)
+			sides[i] = SIDE_FRONT;
+		else if (dot < -ON_EPSILON)
+			sides[i] = SIDE_BACK;
+		else
+		{
+			sides[i] = SIDE_ON;
+		}
+		counts[sides[i]]++;
+	}
+
+	if (!counts[1])
+		return in;		// completely on front side
+	
+	if (!counts[0])
+	{
+		FreeStackWinding (in, stack);
+		return NULL;
+	}
+
+	sides[i] = sides[0];
+	dists[i] = dists[0];
+	
+	neww = AllocStackWinding (stack);
+
+	neww->numpoints = 0;
+
+	for (i=0 ; i<in->numpoints ; i++)
+	{
+		p1 = in->points[i];
+
+		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+		{
+			FreeStackWinding (neww, stack);
+			return in;		// can't chop -- fall back to original
+		}
+
+		if (sides[i] == SIDE_ON)
+		{
+			VectorCopy (p1, neww->points[neww->numpoints]);
+			neww->numpoints++;
+			continue;
+		}
+	
+		if (sides[i] == SIDE_FRONT)
+		{
+			VectorCopy (p1, neww->points[neww->numpoints]);
+			neww->numpoints++;
+		}
+		
+		if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+			continue;
+			
+		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+		{
+			FreeStackWinding (neww, stack);
+			return in;		// can't chop -- fall back to original
+		}
+
+		// generate a split point
+		p2 = in->points[(i+1)%in->numpoints];
+		
+		dot = dists[i] / (dists[i]-dists[i+1]);
+		for (j=0 ; j<3 ; j++)
+		{	// avoid round off error when possible
+			if (split->normal[j] == 1)
+				mid[j] = split->dist;
+			else if (split->normal[j] == -1)
+				mid[j] = -split->dist;
+			else
+				mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+		}
+			
+		VectorCopy (mid, neww->points[neww->numpoints]);
+		neww->numpoints++;
+	}
+	
+	// free the original winding
+	FreeStackWinding (in, stack);
+	
+	return neww;
+}
+
+/*
+==============
+ClipToSeperators
+
+Source, pass, and target are an ordering of portals.
+
+Generates seperating planes canidates by taking two points from source and one
+point from pass, and clips target by them.
+
+If target is totally clipped away, that portal can not be seen through.
+
+Normal clip keeps target on the same side as pass, which is correct if the
+order goes source, pass, target.  If the order goes pass, source, target then
+flipclip should be set.
+==============
+*/
+winding_t	*ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
+{
+	int			i, j, k, l;
+	plane_t		plane;
+	vec3_t		v1, v2;
+	float		d;
+	vec_t		length;
+	int			counts[3];
+	qboolean		fliptest;
+
+	// check all combinations	
+	for (i=0 ; i<source->numpoints ; i++)
+	{
+		l = (i+1)%source->numpoints;
+		VectorSubtract (source->points[l] , source->points[i], v1);
+
+		// find a vertex of pass that makes a plane that puts all of the
+		// vertexes of pass on the front side and all of the vertexes of
+		// source on the back side
+		for (j=0 ; j<pass->numpoints ; j++)
+		{
+			VectorSubtract (pass->points[j], source->points[i], v2);
+
+			plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
+			plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
+			plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
+			
+			// if points don't make a valid plane, skip it
+
+			length = plane.normal[0] * plane.normal[0]
+			+ plane.normal[1] * plane.normal[1]
+			+ plane.normal[2] * plane.normal[2];
+			
+			if (length < ON_EPSILON)
+				continue;
+
+			length = 1/sqrt(length);
+			
+			plane.normal[0] *= length;
+			plane.normal[1] *= length;
+			plane.normal[2] *= length;
+
+			plane.dist = DotProduct (pass->points[j], plane.normal);
+
+			//
+			// find out which side of the generated seperating plane has the
+			// source portal
+			//
+#if 1
+			fliptest = qfalse;
+			for (k=0 ; k<source->numpoints ; k++)
+			{
+				if (k == i || k == l)
+					continue;
+				d = DotProduct (source->points[k], plane.normal) - plane.dist;
+				if (d < -ON_EPSILON)
+				{	// source is on the negative side, so we want all
+					// pass and target on the positive side
+					fliptest = qfalse;
+					break;
+				}
+				else if (d > ON_EPSILON)
+				{	// source is on the positive side, so we want all
+					// pass and target on the negative side
+					fliptest = qtrue;
+					break;
+				}
+			}
+			if (k == source->numpoints)
+				continue;		// planar with source portal
+#else
+			fliptest = flipclip;
+#endif
+			//
+			// flip the normal if the source portal is backwards
+			//
+			if (fliptest)
+			{
+				VectorSubtract (vec3_origin, plane.normal, plane.normal);
+				plane.dist = -plane.dist;
+			}
+#if 1
+			//
+			// if all of the pass portal points are now on the positive side,
+			// this is the seperating plane
+			//
+			counts[0] = counts[1] = counts[2] = 0;
+			for (k=0 ; k<pass->numpoints ; k++)
+			{
+				if (k==j)
+					continue;
+				d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+				if (d < -ON_EPSILON)
+					break;
+				else if (d > ON_EPSILON)
+					counts[0]++;
+				else
+					counts[2]++;
+			}
+			if (k != pass->numpoints)
+				continue;	// points on negative side, not a seperating plane
+				
+			if (!counts[0])
+				continue;	// planar with seperating plane
+#else
+			k = (j+1)%pass->numpoints;
+			d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+			if (d < -ON_EPSILON)
+				continue;
+			k = (j+pass->numpoints-1)%pass->numpoints;
+			d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+			if (d < -ON_EPSILON)
+				continue;			
+#endif
+			//
+			// flip the normal if we want the back side
+			//
+			if (flipclip)
+			{
+				VectorSubtract (vec3_origin, plane.normal, plane.normal);
+				plane.dist = -plane.dist;
+			}
+
+#ifdef SEPERATORCACHE
+			stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
+			if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
+				Error("MAX_SEPERATORS");
+#endif
+			//MrE: fast check first
+			d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
+			//if completely at the back of the seperator plane
+			if (d < -stack->portal->radius)
+				return NULL;
+			//if completely on the front of the seperator plane
+			if (d > stack->portal->radius)
+				break;
+
+			//
+			// clip target by the seperating plane
+			//
+			target = VisChopWinding (target, stack, &plane);
+			if (!target)
+				return NULL;		// target is not visible
+
+			break;		// optimization by Antony Suter
+		}
+	}
+	
+	return target;
+}
+
+/*
+==================
+RecursiveLeafFlow
+
+Flood fill through the leafs
+If src_portal is NULL, this is the originating leaf
+==================
+*/
+void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
+{
+	pstack_t	stack;
+	vportal_t	*p;
+	plane_t		backplane;
+	leaf_t 		*leaf;
+	int			i, j, n;
+	long		*test, *might, *prevmight, *vis, more;
+	int			pnum;
+
+	thread->c_chains++;
+
+	leaf = &leafs[leafnum];
+//	CheckStack (leaf, thread);
+
+	prevstack->next = &stack;
+
+	stack.next = NULL;
+	stack.leaf = leaf;
+	stack.portal = NULL;
+	stack.depth = prevstack->depth + 1;
+
+#ifdef SEPERATORCACHE
+	stack.numseperators[0] = 0;
+	stack.numseperators[1] = 0;
+#endif
+
+	might = (long *)stack.mightsee;
+	vis = (long *)thread->base->portalvis;
+	
+	// check all portals for flowing into other leafs	
+	for (i = 0; i < leaf->numportals; i++)
+	{
+		p = leaf->portals[i];
+		if (p->removed)
+			continue;
+		pnum = p - portals;
+
+		/* MrE: portal trace debug code
+		{
+			int portaltrace[] = {13, 16, 17, 37};
+			pstack_t *s;
+
+			s = &thread->pstack_head;
+			for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
+			{
+				if (s->portal->num != portaltrace[j])
+					break;
+			}
+			if (j >= sizeof(portaltrace)/sizeof(int) - 1)
+			{
+				if (p->num == portaltrace[j])
+					n = 0; //traced through all the portals
+			}
+		}
+		*/
+
+		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
+		{
+			continue;	// can't possibly see it
+		}
+
+		// if the portal can't see anything we haven't allready seen, skip it
+		if (p->status == stat_done)
+		{
+			test = (long *)p->portalvis;
+		}
+		else
+		{
+			test = (long *)p->portalflood;
+		}
+
+		more = 0;
+		prevmight = (long *)prevstack->mightsee;
+		for (j=0 ; j<portallongs ; j++)
+		{
+			might[j] = prevmight[j] & test[j];
+			more |= (might[j] & ~vis[j]);
+		}
+		
+		if (!more && 
+			(thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
+		{	// can't see anything new
+			continue;
+		}
+
+		// get plane of portal, point normal into the neighbor leaf
+		stack.portalplane = p->plane;
+		VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
+		backplane.dist = -p->plane.dist;
+		
+//		c_portalcheck++;
+		
+		stack.portal = p;
+		stack.next = NULL;
+		stack.freewindings[0] = 1;
+		stack.freewindings[1] = 1;
+		stack.freewindings[2] = 1;
+		
+#if 1
+		{
+			float d;
+
+			d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
+			d -= thread->pstack_head.portalplane.dist;
+			if (d < -p->radius)
+			{
+				continue;
+			}
+			else if (d > p->radius)
+			{
+				stack.pass = p->winding;
+			}
+			else	
+			{
+				stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+				if (!stack.pass)
+					continue;
+			}
+		}
+#else
+		stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+		if (!stack.pass)
+			continue;
+#endif
+
+	
+#if 1
+		{
+			float d;
+
+			d = DotProduct (thread->base->origin, p->plane.normal);
+			d -= p->plane.dist;
+			//MrE: vis-bug fix
+			//if (d > p->radius)
+			if (d > thread->base->radius)
+			{
+				continue;
+			}
+			//MrE: vis-bug fix
+			//if (d < -p->radius)
+			else if (d < -thread->base->radius)
+			{
+				stack.source = prevstack->source;
+			}
+			else	
+			{
+				stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+				//FIXME: shouldn't we create a new source origin and radius for fast checks?
+				if (!stack.source)
+					continue;
+			}
+		}
+#else
+		stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+		if (!stack.source)
+			continue;
+#endif
+
+		if (!prevstack->pass)
+		{	// the second leaf can only be blocked if coplanar
+
+			// mark the portal as visible
+			thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+			RecursiveLeafFlow (p->leaf, thread, &stack);
+			continue;
+		}
+
+#ifdef SEPERATORCACHE
+		if (stack.numseperators[0])
+		{
+			for (n = 0; n < stack.numseperators[0]; n++)
+			{
+				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
+				if (!stack.pass)
+					break;		// target is not visible
+			}
+			if (n < stack.numseperators[0])
+				continue;
+		}
+		else
+		{
+			stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
+		}
+#else
+		stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
+#endif
+		if (!stack.pass)
+			continue;
+
+#ifdef SEPERATORCACHE
+		if (stack.numseperators[1])
+		{
+			for (n = 0; n < stack.numseperators[1]; n++)
+			{
+				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
+				if (!stack.pass)
+					break;		// target is not visible
+			}
+		}
+		else
+		{
+			stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
+		}
+#else
+		stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
+#endif
+		if (!stack.pass)
+			continue;
+
+		// mark the portal as visible
+		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+		// flow through it for real
+		RecursiveLeafFlow (p->leaf, thread, &stack);
+		//
+		stack.next = NULL;
+	}	
+}
+
+/*
+===============
+PortalFlow
+
+generates the portalvis bit vector
+===============
+*/
+void PortalFlow (int portalnum)
+{
+	threaddata_t	data;
+	int				i;
+	vportal_t		*p;
+	int				c_might, c_can;
+
+#ifdef MREDEBUG
+	_printf("\r%6d", portalnum);
+#endif
+
+	p = sorted_portals[portalnum];
+
+	if (p->removed)
+	{
+		p->status = stat_done;
+		return;
+	}
+
+	p->status = stat_working;
+
+	c_might = CountBits (p->portalflood, numportals*2);
+
+	memset (&data, 0, sizeof(data));
+	data.base = p;
+	
+	data.pstack_head.portal = p;
+	data.pstack_head.source = p->winding;
+	data.pstack_head.portalplane = p->plane;
+	data.pstack_head.depth = 0;
+	for (i=0 ; i<portallongs ; i++)
+		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+	RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
+
+	p->status = stat_done;
+
+	c_can = CountBits (p->portalvis, numportals*2);
+
+	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
+		(int)(p - portals),	c_might, c_can, data.c_chains);
+}
+
+/*
+==================
+RecursivePassageFlow
+==================
+*/
+void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
+{
+	pstack_t	stack;
+	vportal_t	*p;
+	leaf_t 		*leaf;
+	passage_t	*passage, *nextpassage;
+	int			i, j;
+	long		*might, *vis, *prevmight, *cansee, *portalvis, more;
+	int			pnum;
+
+	leaf = &leafs[portal->leaf];
+
+	prevstack->next = &stack;
+
+	stack.next = NULL;
+	stack.depth = prevstack->depth + 1;
+
+	vis = (long *)thread->base->portalvis;
+
+	passage = portal->passages;
+	nextpassage = passage;
+	// check all portals for flowing into other leafs	
+	for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
+	{
+		p = leaf->portals[i];
+		if ( p->removed ) {
+			continue;
+		}
+		nextpassage = passage->next;
+		pnum = p - portals;
+
+		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
+			continue;	// can't possibly see it
+		}
+
+		// mark the portal as visible
+		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+		prevmight = (long *)prevstack->mightsee;
+		cansee = (long *)passage->cansee;
+		might = (long *)stack.mightsee;
+		memcpy(might, prevmight, portalbytes);
+		if (p->status == stat_done)
+			portalvis = (long *) p->portalvis;
+		else
+			portalvis = (long *) p->portalflood;
+		more = 0;
+		for (j = 0; j < portallongs; j++)
+		{
+			if (*might)
+			{
+				*might &= *cansee++ & *portalvis++;
+				more |= (*might & ~vis[j]);
+			}
+			else
+			{
+				cansee++;
+				portalvis++;
+			}
+			might++;
+		}
+
+		if ( !more ) {
+			// can't see anything new
+			continue;
+		}
+
+		// flow through it for real
+		RecursivePassageFlow(p, thread, &stack);
+
+		stack.next = NULL;
+	}
+}
+
+/*
+===============
+PassageFlow
+===============
+*/
+void PassageFlow (int portalnum)
+{
+	threaddata_t	data;
+	int				i;
+	vportal_t		*p;
+//	int				c_might, c_can;
+
+#ifdef MREDEBUG
+	_printf("\r%6d", portalnum);
+#endif
+
+	p = sorted_portals[portalnum];
+
+	if (p->removed)
+	{
+		p->status = stat_done;
+		return;
+	}
+
+	p->status = stat_working;
+
+//	c_might = CountBits (p->portalflood, numportals*2);
+
+	memset (&data, 0, sizeof(data));
+	data.base = p;
+	
+	data.pstack_head.portal = p;
+	data.pstack_head.source = p->winding;
+	data.pstack_head.portalplane = p->plane;
+	data.pstack_head.depth = 0;
+	for (i=0 ; i<portallongs ; i++)
+		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+	RecursivePassageFlow (p, &data, &data.pstack_head);
+
+	p->status = stat_done;
+
+	/*
+	c_can = CountBits (p->portalvis, numportals*2);
+
+	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
+		(int)(p - portals),	c_might, c_can, data.c_chains);
+	*/
+}
+
+/*
+==================
+RecursivePassagePortalFlow
+==================
+*/
+void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
+{
+	pstack_t	stack;
+	vportal_t	*p;
+	leaf_t 		*leaf;
+	plane_t		backplane;
+	passage_t	*passage, *nextpassage;
+	int			i, j, n;
+	long		*might, *vis, *prevmight, *cansee, *portalvis, more;
+	int			pnum;
+
+//	thread->c_chains++;
+
+	leaf = &leafs[portal->leaf];
+//	CheckStack (leaf, thread);
+
+	prevstack->next = &stack;
+
+	stack.next = NULL;
+	stack.leaf = leaf;
+	stack.portal = NULL;
+	stack.depth = prevstack->depth + 1;
+
+#ifdef SEPERATORCACHE
+	stack.numseperators[0] = 0;
+	stack.numseperators[1] = 0;
+#endif
+
+	vis = (long *)thread->base->portalvis;
+
+	passage = portal->passages;
+	nextpassage = passage;
+	// check all portals for flowing into other leafs	
+	for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
+	{
+		p = leaf->portals[i];
+		if (p->removed)
+			continue;
+		nextpassage = passage->next;
+		pnum = p - portals;
+
+		if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
+			continue;	// can't possibly see it
+
+		prevmight = (long *)prevstack->mightsee;
+		cansee = (long *)passage->cansee;
+		might = (long *)stack.mightsee;
+		memcpy(might, prevmight, portalbytes);
+		if (p->status == stat_done)
+			portalvis = (long *) p->portalvis;
+		else
+			portalvis = (long *) p->portalflood;
+		more = 0;
+		for (j = 0; j < portallongs; j++)
+		{
+			if (*might)
+			{
+				*might &= *cansee++ & *portalvis++;
+				more |= (*might & ~vis[j]);
+			}
+			else
+			{
+				cansee++;
+				portalvis++;
+			}
+			might++;
+		}
+
+		if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
+		{	// can't see anything new
+			continue;
+		}
+
+		// get plane of portal, point normal into the neighbor leaf
+		stack.portalplane = p->plane;
+		VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
+		backplane.dist = -p->plane.dist;
+		
+//		c_portalcheck++;
+		
+		stack.portal = p;
+		stack.next = NULL;
+		stack.freewindings[0] = 1;
+		stack.freewindings[1] = 1;
+		stack.freewindings[2] = 1;
+
+#if 1
+		{
+			float d;
+
+			d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
+			d -= thread->pstack_head.portalplane.dist;
+			if (d < -p->radius)
+			{
+				continue;
+			}
+			else if (d > p->radius)
+			{
+				stack.pass = p->winding;
+			}
+			else	
+			{
+				stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+				if (!stack.pass)
+					continue;
+			}
+		}
+#else
+		stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+		if (!stack.pass)
+			continue;
+#endif
+
+	
+#if 1
+		{
+			float d;
+
+			d = DotProduct (thread->base->origin, p->plane.normal);
+			d -= p->plane.dist;
+			//MrE: vis-bug fix
+			//if (d > p->radius)
+			if (d > thread->base->radius)
+			{
+				continue;
+			}
+			//MrE: vis-bug fix
+			//if (d < -p->radius)
+			else if (d < -thread->base->radius)
+			{
+				stack.source = prevstack->source;
+			}
+			else	
+			{
+				stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+				//FIXME: shouldn't we create a new source origin and radius for fast checks?
+				if (!stack.source)
+					continue;
+			}
+		}
+#else
+		stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+		if (!stack.source)
+			continue;
+#endif
+
+		if (!prevstack->pass)
+		{	// the second leaf can only be blocked if coplanar
+
+			// mark the portal as visible
+			thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+			RecursivePassagePortalFlow (p, thread, &stack);
+			continue;
+		}
+
+#ifdef SEPERATORCACHE
+		if (stack.numseperators[0])
+		{
+			for (n = 0; n < stack.numseperators[0]; n++)
+			{
+				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
+				if (!stack.pass)
+					break;		// target is not visible
+			}
+			if (n < stack.numseperators[0])
+				continue;
+		}
+		else
+		{
+			stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
+		}
+#else
+		stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
+#endif
+		if (!stack.pass)
+			continue;
+
+#ifdef SEPERATORCACHE
+		if (stack.numseperators[1])
+		{
+			for (n = 0; n < stack.numseperators[1]; n++)
+			{
+				stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
+				if (!stack.pass)
+					break;		// target is not visible
+			}
+		}
+		else
+		{
+			stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
+		}
+#else
+		stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
+#endif
+		if (!stack.pass)
+			continue;
+
+		// mark the portal as visible
+		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+		// flow through it for real
+		RecursivePassagePortalFlow(p, thread, &stack);
+		//
+		stack.next = NULL;
+	}
+}
+
+/*
+===============
+PassagePortalFlow
+===============
+*/
+void PassagePortalFlow (int portalnum)
+{
+	threaddata_t	data;
+	int				i;
+	vportal_t		*p;
+//	int				c_might, c_can;
+
+#ifdef MREDEBUG
+	_printf("\r%6d", portalnum);
+#endif
+
+	p = sorted_portals[portalnum];
+
+	if (p->removed)
+	{
+		p->status = stat_done;
+		return;
+	}
+
+	p->status = stat_working;
+
+//	c_might = CountBits (p->portalflood, numportals*2);
+
+	memset (&data, 0, sizeof(data));
+	data.base = p;
+	
+	data.pstack_head.portal = p;
+	data.pstack_head.source = p->winding;
+	data.pstack_head.portalplane = p->plane;
+	data.pstack_head.depth = 0;
+	for (i=0 ; i<portallongs ; i++)
+		((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+	RecursivePassagePortalFlow (p, &data, &data.pstack_head);
+
+	p->status = stat_done;
+
+	/*
+	c_can = CountBits (p->portalvis, numportals*2);
+
+	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
+		(int)(p - portals),	c_might, c_can, data.c_chains);
+	*/
+}
+
+winding_t *PassageChopWinding (winding_t *in, winding_t *out, plane_t *split)
+{
+	vec_t	dists[128];
+	int		sides[128];
+	int		counts[3];
+	vec_t	dot;
+	int		i, j;
+	vec_t	*p1, *p2;
+	vec3_t	mid;
+	winding_t	*neww;
+
+	counts[0] = counts[1] = counts[2] = 0;
+
+	// determine sides for each point
+	for (i=0 ; i<in->numpoints ; i++)
+	{
+		dot = DotProduct (in->points[i], split->normal);
+		dot -= split->dist;
+		dists[i] = dot;
+		if (dot > ON_EPSILON)
+			sides[i] = SIDE_FRONT;
+		else if (dot < -ON_EPSILON)
+			sides[i] = SIDE_BACK;
+		else
+		{
+			sides[i] = SIDE_ON;
+		}
+		counts[sides[i]]++;
+	}
+
+	if (!counts[1])
+		return in;		// completely on front side
+	
+	if (!counts[0])
+	{
+		return NULL;
+	}
+
+	sides[i] = sides[0];
+	dists[i] = dists[0];
+	
+	neww = out;
+
+	neww->numpoints = 0;
+
+	for (i=0 ; i<in->numpoints ; i++)
+	{
+		p1 = in->points[i];
+
+		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+		{
+			return in;		// can't chop -- fall back to original
+		}
+
+		if (sides[i] == SIDE_ON)
+		{
+			VectorCopy (p1, neww->points[neww->numpoints]);
+			neww->numpoints++;
+			continue;
+		}
+	
+		if (sides[i] == SIDE_FRONT)
+		{
+			VectorCopy (p1, neww->points[neww->numpoints]);
+			neww->numpoints++;
+		}
+		
+		if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+			continue;
+			
+		if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+		{
+			return in;		// can't chop -- fall back to original
+		}
+
+		// generate a split point
+		p2 = in->points[(i+1)%in->numpoints];
+		
+		dot = dists[i] / (dists[i]-dists[i+1]);
+		for (j=0 ; j<3 ; j++)
+		{	// avoid round off error when possible
+			if (split->normal[j] == 1)
+				mid[j] = split->dist;
+			else if (split->normal[j] == -1)
+				mid[j] = -split->dist;
+			else
+				mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+		}
+			
+		VectorCopy (mid, neww->points[neww->numpoints]);
+		neww->numpoints++;
+	}
+	
+	return neww;
+}
+
+/*
+===============
+AddSeperators
+===============
+*/
+int AddSeperators (winding_t *source, winding_t *pass, qboolean flipclip, plane_t *seperators, int maxseperators)
+{
+	int			i, j, k, l;
+	plane_t		plane;
+	vec3_t		v1, v2;
+	float		d;
+	vec_t		length;
+	int			counts[3], numseperators;
+	qboolean	fliptest;
+
+	numseperators = 0;
+	// check all combinations	
+	for (i=0 ; i<source->numpoints ; i++)
+	{
+		l = (i+1)%source->numpoints;
+		VectorSubtract (source->points[l] , source->points[i], v1);
+
+		// find a vertex of pass that makes a plane that puts all of the
+		// vertexes of pass on the front side and all of the vertexes of
+		// source on the back side
+		for (j=0 ; j<pass->numpoints ; j++)
+		{
+			VectorSubtract (pass->points[j], source->points[i], v2);
+
+			plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
+			plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
+			plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
+			
+			// if points don't make a valid plane, skip it
+
+			length = plane.normal[0] * plane.normal[0]
+			+ plane.normal[1] * plane.normal[1]
+			+ plane.normal[2] * plane.normal[2];
+			
+			if (length < ON_EPSILON)
+				continue;
+
+			length = 1/sqrt(length);
+			
+			plane.normal[0] *= length;
+			plane.normal[1] *= length;
+			plane.normal[2] *= length;
+
+			plane.dist = DotProduct (pass->points[j], plane.normal);
+
+			//
+			// find out which side of the generated seperating plane has the
+			// source portal
+			//
+#if 1
+			fliptest = qfalse;
+			for (k=0 ; k<source->numpoints ; k++)
+			{
+				if (k == i || k == l)
+					continue;
+				d = DotProduct (source->points[k], plane.normal) - plane.dist;
+				if (d < -ON_EPSILON)
+				{	// source is on the negative side, so we want all
+					// pass and target on the positive side
+					fliptest = qfalse;
+					break;
+				}
+				else if (d > ON_EPSILON)
+				{	// source is on the positive side, so we want all
+					// pass and target on the negative side
+					fliptest = qtrue;
+					break;
+				}
+			}
+			if (k == source->numpoints)
+				continue;		// planar with source portal
+#else
+			fliptest = flipclip;
+#endif
+			//
+			// flip the normal if the source portal is backwards
+			//
+			if (fliptest)
+			{
+				VectorSubtract (vec3_origin, plane.normal, plane.normal);
+				plane.dist = -plane.dist;
+			}
+#if 1
+			//
+			// if all of the pass portal points are now on the positive side,
+			// this is the seperating plane
+			//
+			counts[0] = counts[1] = counts[2] = 0;
+			for (k=0 ; k<pass->numpoints ; k++)
+			{
+				if (k==j)
+					continue;
+				d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+				if (d < -ON_EPSILON)
+					break;
+				else if (d > ON_EPSILON)
+					counts[0]++;
+				else
+					counts[2]++;
+			}
+			if (k != pass->numpoints)
+				continue;	// points on negative side, not a seperating plane
+				
+			if (!counts[0])
+				continue;	// planar with seperating plane
+#else
+			k = (j+1)%pass->numpoints;
+			d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+			if (d < -ON_EPSILON)
+				continue;
+			k = (j+pass->numpoints-1)%pass->numpoints;
+			d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+			if (d < -ON_EPSILON)
+				continue;			
+#endif
+			//
+			// flip the normal if we want the back side
+			//
+			if (flipclip)
+			{
+				VectorSubtract (vec3_origin, plane.normal, plane.normal);
+				plane.dist = -plane.dist;
+			}
+
+			if (numseperators >= maxseperators)
+				Error("max seperators");
+			seperators[numseperators] = plane;
+			numseperators++;
+			break;
+		}
+	}
+	return numseperators;
+}
+
+/*
+===============
+CreatePassages
+
+MrE: create passages from one portal to all the portals in the leaf the portal leads to
+	 every passage has a cansee bit string with all the portals that can be
+	 seen through the passage
+===============
+*/
+void CreatePassages(int portalnum)
+{
+	int i, j, k, n, numseperators, numsee;
+	float d;
+	vportal_t *portal, *p, *target;
+	leaf_t *leaf;
+	passage_t	*passage, *lastpassage;
+	plane_t seperators[MAX_SEPERATORS*2];
+	winding_t *w;
+	winding_t in, out, *res;
+
+#ifdef MREDEBUG
+	_printf("\r%6d", portalnum);
+#endif
+
+	portal = sorted_portals[portalnum];
+
+	if (portal->removed)
+	{
+		portal->status = stat_done;
+		return;
+	}
+
+	lastpassage = NULL;
+	leaf = &leafs[portal->leaf];
+	for (i = 0; i < leaf->numportals; i++)
+	{
+		target = leaf->portals[i];
+		if (target->removed)
+			continue;
+
+		passage = (passage_t *) malloc(sizeof(passage_t) + portalbytes);
+		memset(passage, 0, sizeof(passage_t) + portalbytes);
+		numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
+		numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
+
+		passage->next = NULL;
+		if (lastpassage)
+			lastpassage->next = passage;
+		else
+			portal->passages = passage;
+		lastpassage = passage;
+
+		numsee = 0;
+		//create the passage->cansee
+		for (j = 0; j < numportals * 2; j++)
+		{
+			p = &portals[j];
+			if (p->removed)
+				continue;
+			if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
+				continue;
+			if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
+				continue;
+			for (k = 0; k < numseperators; k++)
+			{
+				//
+				d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
+				//if completely at the back of the seperator plane
+				if (d < -p->radius + ON_EPSILON)
+					break;
+				w = p->winding;
+				for (n = 0; n < w->numpoints; n++)
+				{
+					d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
+					//if at the front of the seperator
+					if (d > ON_EPSILON)
+						break;
+				}
+				//if no points are at the front of the seperator
+				if (n >= w->numpoints)
+					break;
+			}
+			if (k < numseperators)
+				continue;
+			memcpy(&in, p->winding, sizeof(winding_t));
+			for (k = 0; k < numseperators; k++)
+			{
+				res = PassageChopWinding(&in, &out, &seperators[k]);
+				if (res == &out)
+					memcpy(&in, &out, sizeof(winding_t));
+				if (res == NULL)
+					break;
+			}
+			if (k < numseperators)
+				continue;
+			passage->cansee[j >> 3] |= (1<<(j&7));
+			numsee++;
+		}
+	}
+}
+
+void PassageMemory(void)
+{
+	int i, j, totalmem, totalportals;
+	vportal_t *portal, *target;
+	leaf_t *leaf;
+
+	totalmem = 0;
+	totalportals = 0;
+	for (i = 0; i < numportals; i++)
+	{
+		portal = sorted_portals[i];
+		if (portal->removed)
+			continue;
+		leaf = &leafs[portal->leaf];
+		for (j = 0; j < leaf->numportals; j++)
+		{
+			target = leaf->portals[j];
+			if (target->removed)
+				continue;
+			totalmem += sizeof(passage_t) + portalbytes;
+			totalportals++;
+		}
+	}
+	_printf("%7i average number of passages per leaf\n", totalportals / numportals);
+	_printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
+}
+
+/*
+===============================================================================
+
+This is a rough first-order aproximation that is used to trivially reject some
+of the final calculations.
+
+
+Calculates portalfront and portalflood bit vectors
+
+thinking about:
+
+typedef struct passage_s
+{
+	struct passage_s	*next;
+	struct portal_s		*to;
+	stryct sep_s		*seperators;
+	byte				*mightsee;
+} passage_t;
+
+typedef struct portal_s
+{
+	struct passage_s	*passages;
+	int					leaf;		// leaf portal faces into
+} portal_s;
+
+leaf = portal->leaf
+clear 
+for all portals
+
+
+calc portal visibility
+	clear bit vector
+	for all passages
+		passage visibility
+
+
+for a portal to be visible to a passage, it must be on the front of
+all seperating planes, and both portals must be behind the new portal
+
+===============================================================================
+*/
+
+int		c_flood, c_vis;
+
+
+/*
+==================
+SimpleFlood
+
+==================
+*/
+void SimpleFlood (vportal_t *srcportal, int leafnum)
+{
+	int		i;
+	leaf_t	*leaf;
+	vportal_t	*p;
+	int		pnum;
+
+	leaf = &leafs[leafnum];
+	
+	for (i=0 ; i<leaf->numportals ; i++)
+	{
+		p = leaf->portals[i];
+		if (p->removed)
+			continue;
+		pnum = p - portals;
+		if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
+			continue;
+
+		if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
+			continue;
+
+		srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
+		
+		SimpleFlood (srcportal, p->leaf);
+	}
+}
+
+/*
+==============
+BasePortalVis
+==============
+*/
+void BasePortalVis (int portalnum)
+{
+	int			j, k;
+	vportal_t	*tp, *p;
+	float		d;
+	winding_t	*w;
+
+	p = portals+portalnum;
+
+	if (p->removed)
+		return;
+
+	p->portalfront = malloc (portalbytes);
+	memset (p->portalfront, 0, portalbytes);
+
+	p->portalflood = malloc (portalbytes);
+	memset (p->portalflood, 0, portalbytes);
+	
+	p->portalvis = malloc (portalbytes);
+	memset (p->portalvis, 0, portalbytes);
+	
+	for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
+	{
+		if (j == portalnum)
+			continue;
+		if (tp->removed)
+			continue;
+		/*
+		if (farplanedist >= 0)
+		{
+			vec3_t dir;
+			VectorSubtract(p->origin, tp->origin, dir);
+			if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
+				continue;
+		}
+		*/
+		w = tp->winding;
+		for (k=0 ; k<w->numpoints ; k++)
+		{
+			d = DotProduct (w->points[k], p->plane.normal)
+				- p->plane.dist;
+			if (d > ON_EPSILON)
+				break;
+		}
+		if (k == w->numpoints)
+			continue;	// no points on front
+
+		w = p->winding;
+		for (k=0 ; k<w->numpoints ; k++)
+		{
+			d = DotProduct (w->points[k], tp->plane.normal)
+				- tp->plane.dist;
+			if (d < -ON_EPSILON)
+				break;
+		}
+		if (k == w->numpoints)
+			continue;	// no points on front
+
+		p->portalfront[j>>3] |= (1<<(j&7));
+	}
+	
+	SimpleFlood (p, p->leaf);
+
+	p->nummightsee = CountBits (p->portalflood, numportals*2);
+//	_printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
+	c_flood += p->nummightsee;
+}
+
+
+
+
+
+/*
+===============================================================================
+
+This is a second order aproximation 
+
+Calculates portalvis bit vector
+
+WAAAAAAY too slow.
+
+===============================================================================
+*/
+
+/*
+==================
+RecursiveLeafBitFlow
+
+==================
+*/
+void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
+{
+	vportal_t	*p;
+	leaf_t 		*leaf;
+	int			i, j;
+	long		more;
+	int			pnum;
+	byte		newmight[MAX_PORTALS/8];
+
+	leaf = &leafs[leafnum];
+	
+	// check all portals for flowing into other leafs
+	for (i=0 ; i<leaf->numportals ; i++)
+	{
+		p = leaf->portals[i];
+		if (p->removed)
+			continue;
+		pnum = p - portals;
+
+		// if some previous portal can't see it, skip
+		if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
+			continue;
+
+		// if this portal can see some portals we mightsee, recurse
+		more = 0;
+		for (j=0 ; j<portallongs ; j++)
+		{
+			((long *)newmight)[j] = ((long *)mightsee)[j] 
+				& ((long *)p->portalflood)[j];
+			more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
+		}
+
+		if (!more)
+			continue;	// can't see anything new
+
+		cansee[pnum>>3] |= (1<<(pnum&7));
+
+		RecursiveLeafBitFlow (p->leaf, newmight, cansee);
+	}	
+}
+
+/*
+==============
+BetterPortalVis
+==============
+*/
+void BetterPortalVis (int portalnum)
+{
+	vportal_t	*p;
+
+	p = portals+portalnum;
+
+	if (p->removed)
+		return;
+
+	RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
+
+	// build leaf vis information
+	p->nummightsee = CountBits (p->portalvis, numportals*2);
+	c_vis += p->nummightsee;
+}
+
+