Fix line endings. WHAMMY.

1 files changed, 881 insertions, 881 deletions

diff --git a/mp/src/utils/vvis/flow.cpp b/mp/src/utils/vvis/flow.cpp
index 7234e68a..716fc1ae 100644
--- a/mp/src/utils/vvis/flow.cpp
+++ b/mp/src/utils/vvis/flow.cpp
@@ -1,881 +1,881 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose: 

-//

-// $NoKeywords: $

-//

-//=============================================================================//

-#include "vis.h"

-#include "vmpi.h"

-

-int g_TraceClusterStart = -1;

-int g_TraceClusterStop = -1;

-/*

-

-  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 ( CheckBit( bits, i ) )

-			c++;

-

-	return c;

-}

-

-int		c_fullskip;

-int		c_portalskip, c_leafskip;

-int		c_vistest, c_mighttest;

-

-int		c_chop, c_nochop;

-

-int		active;

-

-extern bool g_bVMPIEarlyExit;

-

-

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

-{

-	pstack_t	*p, *p2;

-

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

-	{

-//		Msg ("=");

-		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");

-	}

-//	Msg ("\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 ("Out of memory. 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;

-}

-

-/*

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

-ChopWinding

-

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

-*/

-

-#ifdef _WIN32

-#pragma warning (disable:4701)

-#endif

-

-winding_t	*ChopWinding (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;

-	Vector	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_VIS_EPSILON)

-			sides[i] = SIDE_FRONT;

-		else if (dot < -ON_VIS_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++)

-	{

-		Vector& 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

-		Vector& 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;

-}

-

-#ifdef _WIN32

-#pragma warning (default:4701)

-#endif

-

-/*

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

-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, bool flipclip, pstack_t *stack)

-{

-	int			i, j, k, l;

-	plane_t		plane;

-	Vector		v1, v2;

-	float		d;

-	vec_t		length;

-	int			counts[3];

-	bool		fliptest;

-

-// check all combinations	

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

-	{

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

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

-

-	// fing 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_VIS_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 = false;

-			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_VIS_EPSILON)

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

-					// pass and target on the positive side

-					fliptest = false;

-					break;

-				}

-				else if (d > ON_VIS_EPSILON)

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

-					// pass and target on the negative side

-					fliptest = true;

-					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_VIS_EPSILON)

-					break;

-				else if (d > ON_VIS_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_VIS_EPSILON)

-				continue;

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

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

-			if (d < -ON_VIS_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;

-			}

-			

-		//

-		// clip target by the seperating plane

-		//

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

-			if (!target)

-				return NULL;		// target is not visible

-

-			// JAY: End the loop, no need to find additional separators on this edge ?

-//			j = pass->numpoints;

-		}

-	}

-	

-	return target;

-}

-

-

-class CPortalTrace

-{

-public:

-	CUtlVector<Vector>	m_list;

-	CThreadFastMutex	m_mutex;

-} g_PortalTrace;

-

-void WindingCenter (winding_t *w, Vector &center)

-{

-	int		i;

-	float	scale;

-

-	VectorCopy (vec3_origin, center);

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

-		VectorAdd (w->points[i], center, center);

-

-	scale = 1.0/w->numpoints;

-	VectorScale (center, scale, center);

-}

-

-Vector ClusterCenter( int cluster )

-{

-	Vector mins, maxs;

-	ClearBounds(mins, maxs);

-	int count = leafs[cluster].portals.Count();

-	for ( int i = 0; i < count; i++ )

-	{

-		winding_t *w = leafs[cluster].portals[i]->winding;

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

-		{

-			AddPointToBounds( w->points[j], mins, maxs );

-		}

-	}

-	return (mins + maxs) * 0.5f;

-}

-

-

-void DumpPortalTrace( pstack_t *pStack )

-{

-	AUTO_LOCK_FM(g_PortalTrace.m_mutex);

-	if ( g_PortalTrace.m_list.Count() )

-		return;

-

-	Warning("Dumped cluster trace!!!\n");

-	Vector	mid;

-	mid = ClusterCenter( g_TraceClusterStart );

-	g_PortalTrace.m_list.AddToTail(mid);

-	for ( ; pStack != NULL; pStack = pStack->next )

-	{

-		winding_t *w = pStack->pass ? pStack->pass : pStack->portal->winding;

-		WindingCenter (w, mid);

-		g_PortalTrace.m_list.AddToTail(mid);

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

-		{

-			g_PortalTrace.m_list.AddToTail(w->points[i]);

-			g_PortalTrace.m_list.AddToTail(mid);

-		}

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

-		{

-			g_PortalTrace.m_list.AddToTail(w->points[i]);

-		}

-		g_PortalTrace.m_list.AddToTail(w->points[0]);

-		g_PortalTrace.m_list.AddToTail(mid);

-	}

-	mid = ClusterCenter( g_TraceClusterStop );

-	g_PortalTrace.m_list.AddToTail(mid);

-}

-

-void WritePortalTrace( const char *source )

-{

-	Vector	mid;

-	FILE	*linefile;

-	char	filename[1024];

-

-	if ( !g_PortalTrace.m_list.Count() )

-	{

-		Warning("No trace generated from %d to %d\n", g_TraceClusterStart, g_TraceClusterStop );

-		return;

-	}

-

-	sprintf (filename, "%s.lin", source);

-	linefile = fopen (filename, "w");

-	if (!linefile)

-		Error ("Couldn't open %s\n", filename);

-

-	for ( int i = 0; i < g_PortalTrace.m_list.Count(); i++ )

-	{

-		Vector p = g_PortalTrace.m_list[i];

-		fprintf (linefile, "%f %f %f\n", p[0], p[1], p[2]);

-	}

-	fclose (linefile);

-	Warning("Wrote %s!!!\n", filename);

-}

-

-/*

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

-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;

-	portal_t	*p;

-	plane_t		backplane;

-	leaf_t 		*leaf;

-	int			i, j;

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

-	int			pnum;

-

-	// Early-out if we're a VMPI worker that's told to exit. If we don't do this here, then the

-	// worker might spin its wheels for a while on an expensive work unit and not be available to the pool.

-	// This is pretty common in vis.

-	if ( g_bVMPIEarlyExit )

-		return;

-

-	if ( leafnum == g_TraceClusterStop )

-	{

-		DumpPortalTrace(&thread->pstack_head);

-		return;

-	}

-	thread->c_chains++;

-

-	leaf = &leafs[leafnum];

-

-	prevstack->next = &stack;

-

-	stack.next = NULL;

-	stack.leaf = leaf;

-	stack.portal = NULL;

-

-	might = (long *)stack.mightsee;

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

-	

-	// check all portals for flowing into other leafs	

-	for (i=0 ; i<leaf->portals.Count() ; i++)

-	{

-

-		p = leaf->portals[i];

-		pnum = p - 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;

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

-		{

-			might[j] = ((long *)prevstack->mightsee)[j] & test[j];

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

-		}

-		

-		if ( !more && CheckBit( thread->base->portalvis, pnum ) )

-		{	// 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;

-		

-		stack.portal = p;

-		stack.next = NULL;

-		stack.freewindings[0] = 1;

-		stack.freewindings[1] = 1;

-		stack.freewindings[2] = 1;

-		

-		float 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 = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);

-			if (!stack.pass)

-				continue;

-		}

-

-

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

-		d -= p->plane.dist;

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

-		{

-			continue;

-		}

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

-		{

-			stack.source = prevstack->source;

-		}

-		else	

-		{

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

-			if (!stack.source)

-				continue;

-		}

-

-

-		if (!prevstack->pass)

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

-

-			// mark the portal as visible

-			SetBit( thread->base->portalvis, pnum );

-

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

-			continue;

-		}

-

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

-		if (!stack.pass)

-			continue;

-		

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

-		if (!stack.pass)

-			continue;

-

-		// mark the portal as visible

-		SetBit( thread->base->portalvis, pnum );

-

-		// flow through it for real

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

-	}	

-}

-

-

-/*

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

-PortalFlow

-

-generates the portalvis bit vector

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

-*/

-void PortalFlow (int iThread, int portalnum)

-{

-	threaddata_t	data;

-	int				i;

-	portal_t		*p;

-	int				c_might, c_can;

-

-	p = sorted_portals[portalnum];

-	p->status = stat_working;

-				

-	c_might = CountBits (p->portalflood, g_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;

-	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, g_numportals*2);

-

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

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

-}

-

-

-/*

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

-

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

-of the final calculations.

-

-

-Calculates portalfront and portalflood bit vectors

-

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

-*/

-

-int		c_flood, c_vis;

-

-/*

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

-SimpleFlood

-

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

-*/

-void SimpleFlood (portal_t *srcportal, int leafnum)

-{

-	int		i;

-	leaf_t	*leaf;

-	portal_t	*p;

-	int		pnum;

-

-	leaf = &leafs[leafnum];

-	

-	for (i=0 ; i<leaf->portals.Count(); i++)

-	{

-		p = leaf->portals[i];

-		pnum = p - portals;

-		if ( !CheckBit( srcportal->portalfront, pnum ) )

-			continue;

-

-		if ( CheckBit( srcportal->portalflood, pnum ) )

-			continue;

-

-		SetBit( srcportal->portalflood, pnum );

-		

-		SimpleFlood (srcportal, p->leaf);

-	}

-}

-

-/*

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

-BasePortalVis

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

-*/

-void BasePortalVis (int iThread, int portalnum)

-{

-	int			j, k;

-	portal_t	*tp, *p;

-	float		d;

-	winding_t	*w;

-	Vector		segment;

-	double		dist2, minDist2;

-

-	// get the portal

-	p = portals+portalnum;

-

-	//

-	// allocate memory for bitwise vis solutions for this portal

-	//

-	p->portalfront = (byte*)malloc (portalbytes);

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

-

-	p->portalflood = (byte*)malloc (portalbytes);

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

-	

-	p->portalvis = (byte*)malloc (portalbytes);

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

-	

-	//

-	// test the given portal against all of the portals in the map

-	//

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

-	{

-		// don't test against itself

-		if (j == portalnum)

-			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_VIS_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_VIS_EPSILON)

-				break;

-		}

-		if (k == w->numpoints)

-			continue;	// no points on front

-

-		//

-		// if using radius visibility -- check to see if any portal points lie inside of the

-		// radius given

-		//

-		if( g_bUseRadius )

-		{

-			w = tp->winding;

-			minDist2 = 1024000000.0;			// 32000^2

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

-			{

-				VectorSubtract( w->points[k], p->origin, segment );

-				dist2 = ( segment[0] * segment[0] ) + ( segment[1] * segment[1] ) + ( segment[2] * segment[2] );

-				if( dist2 < minDist2 )

-				{

-					minDist2 = dist2;

-				}

-			}

-

-			if( minDist2 > g_VisRadius )

-				continue;

-		}

-

-		// add current portal to given portal's list of visible portals

-		SetBit( p->portalfront, j );

-	}

-	

-	SimpleFlood (p, p->leaf);

-

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

-//	Msg ("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)

-{

-	portal_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->portals.Count(); i++)

-	{

-		p = leaf->portals[i];

-		pnum = p - portals;

-

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

-		if ( !CheckBit( mightsee, pnum ) )

-			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

-

-		SetBit( cansee, pnum );

-

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

-	}	

-}

-

-/*

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

-BetterPortalVis

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

-*/

-void BetterPortalVis (int portalnum)

-{

-	portal_t	*p;

-

-	p = portals+portalnum;

-

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

-

-	// build leaf vis information

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

-	c_vis += p->nummightsee;

-}

-

-

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+// $NoKeywords: $
+//
+//=============================================================================//
+#include "vis.h"
+#include "vmpi.h"
+
+int g_TraceClusterStart = -1;
+int g_TraceClusterStop = -1;
+/*
+
+  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 ( CheckBit( bits, i ) )
+			c++;
+
+	return c;
+}
+
+int		c_fullskip;
+int		c_portalskip, c_leafskip;
+int		c_vistest, c_mighttest;
+
+int		c_chop, c_nochop;
+
+int		active;
+
+extern bool g_bVMPIEarlyExit;
+
+
+void CheckStack (leaf_t *leaf, threaddata_t *thread)
+{
+	pstack_t	*p, *p2;
+
+	for (p=thread->pstack_head.next ; p ; p=p->next)
+	{
+//		Msg ("=");
+		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");
+	}
+//	Msg ("\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 ("Out of memory. 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;
+}
+
+/*
+==============
+ChopWinding
+
+==============
+*/
+
+#ifdef _WIN32
+#pragma warning (disable:4701)
+#endif
+
+winding_t	*ChopWinding (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;
+	Vector	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_VIS_EPSILON)
+			sides[i] = SIDE_FRONT;
+		else if (dot < -ON_VIS_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++)
+	{
+		Vector& 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
+		Vector& 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;
+}
+
+#ifdef _WIN32
+#pragma warning (default:4701)
+#endif
+
+/*
+==============
+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, bool flipclip, pstack_t *stack)
+{
+	int			i, j, k, l;
+	plane_t		plane;
+	Vector		v1, v2;
+	float		d;
+	vec_t		length;
+	int			counts[3];
+	bool		fliptest;
+
+// check all combinations	
+	for (i=0 ; i<source->numpoints ; i++)
+	{
+		l = (i+1)%source->numpoints;
+		VectorSubtract (source->points[l] , source->points[i], v1);
+
+	// fing 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_VIS_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 = false;
+			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_VIS_EPSILON)
+				{	// source is on the negative side, so we want all
+					// pass and target on the positive side
+					fliptest = false;
+					break;
+				}
+				else if (d > ON_VIS_EPSILON)
+				{	// source is on the positive side, so we want all
+					// pass and target on the negative side
+					fliptest = true;
+					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_VIS_EPSILON)
+					break;
+				else if (d > ON_VIS_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_VIS_EPSILON)
+				continue;
+			k = (j+pass->numpoints-1)%pass->numpoints;
+			d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+			if (d < -ON_VIS_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;
+			}
+			
+		//
+		// clip target by the seperating plane
+		//
+			target = ChopWinding (target, stack, &plane);
+			if (!target)
+				return NULL;		// target is not visible
+
+			// JAY: End the loop, no need to find additional separators on this edge ?
+//			j = pass->numpoints;
+		}
+	}
+	
+	return target;
+}
+
+
+class CPortalTrace
+{
+public:
+	CUtlVector<Vector>	m_list;
+	CThreadFastMutex	m_mutex;
+} g_PortalTrace;
+
+void WindingCenter (winding_t *w, Vector &center)
+{
+	int		i;
+	float	scale;
+
+	VectorCopy (vec3_origin, center);
+	for (i=0 ; i<w->numpoints ; i++)
+		VectorAdd (w->points[i], center, center);
+
+	scale = 1.0/w->numpoints;
+	VectorScale (center, scale, center);
+}
+
+Vector ClusterCenter( int cluster )
+{
+	Vector mins, maxs;
+	ClearBounds(mins, maxs);
+	int count = leafs[cluster].portals.Count();
+	for ( int i = 0; i < count; i++ )
+	{
+		winding_t *w = leafs[cluster].portals[i]->winding;
+		for ( int j = 0; j < w->numpoints; j++ )
+		{
+			AddPointToBounds( w->points[j], mins, maxs );
+		}
+	}
+	return (mins + maxs) * 0.5f;
+}
+
+
+void DumpPortalTrace( pstack_t *pStack )
+{
+	AUTO_LOCK_FM(g_PortalTrace.m_mutex);
+	if ( g_PortalTrace.m_list.Count() )
+		return;
+
+	Warning("Dumped cluster trace!!!\n");
+	Vector	mid;
+	mid = ClusterCenter( g_TraceClusterStart );
+	g_PortalTrace.m_list.AddToTail(mid);
+	for ( ; pStack != NULL; pStack = pStack->next )
+	{
+		winding_t *w = pStack->pass ? pStack->pass : pStack->portal->winding;
+		WindingCenter (w, mid);
+		g_PortalTrace.m_list.AddToTail(mid);
+		for ( int i = 0; i < w->numpoints; i++ )
+		{
+			g_PortalTrace.m_list.AddToTail(w->points[i]);
+			g_PortalTrace.m_list.AddToTail(mid);
+		}
+		for ( int i = 0; i < w->numpoints; i++ )
+		{
+			g_PortalTrace.m_list.AddToTail(w->points[i]);
+		}
+		g_PortalTrace.m_list.AddToTail(w->points[0]);
+		g_PortalTrace.m_list.AddToTail(mid);
+	}
+	mid = ClusterCenter( g_TraceClusterStop );
+	g_PortalTrace.m_list.AddToTail(mid);
+}
+
+void WritePortalTrace( const char *source )
+{
+	Vector	mid;
+	FILE	*linefile;
+	char	filename[1024];
+
+	if ( !g_PortalTrace.m_list.Count() )
+	{
+		Warning("No trace generated from %d to %d\n", g_TraceClusterStart, g_TraceClusterStop );
+		return;
+	}
+
+	sprintf (filename, "%s.lin", source);
+	linefile = fopen (filename, "w");
+	if (!linefile)
+		Error ("Couldn't open %s\n", filename);
+
+	for ( int i = 0; i < g_PortalTrace.m_list.Count(); i++ )
+	{
+		Vector p = g_PortalTrace.m_list[i];
+		fprintf (linefile, "%f %f %f\n", p[0], p[1], p[2]);
+	}
+	fclose (linefile);
+	Warning("Wrote %s!!!\n", filename);
+}
+
+/*
+==================
+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;
+	portal_t	*p;
+	plane_t		backplane;
+	leaf_t 		*leaf;
+	int			i, j;
+	long		*test, *might, *vis, more;
+	int			pnum;
+
+	// Early-out if we're a VMPI worker that's told to exit. If we don't do this here, then the
+	// worker might spin its wheels for a while on an expensive work unit and not be available to the pool.
+	// This is pretty common in vis.
+	if ( g_bVMPIEarlyExit )
+		return;
+
+	if ( leafnum == g_TraceClusterStop )
+	{
+		DumpPortalTrace(&thread->pstack_head);
+		return;
+	}
+	thread->c_chains++;
+
+	leaf = &leafs[leafnum];
+
+	prevstack->next = &stack;
+
+	stack.next = NULL;
+	stack.leaf = leaf;
+	stack.portal = NULL;
+
+	might = (long *)stack.mightsee;
+	vis = (long *)thread->base->portalvis;
+	
+	// check all portals for flowing into other leafs	
+	for (i=0 ; i<leaf->portals.Count() ; i++)
+	{
+
+		p = leaf->portals[i];
+		pnum = p - 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;
+		for (j=0 ; j<portallongs ; j++)
+		{
+			might[j] = ((long *)prevstack->mightsee)[j] & test[j];
+			more |= (might[j] & ~vis[j]);
+		}
+		
+		if ( !more && CheckBit( thread->base->portalvis, pnum ) )
+		{	// 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;
+		
+		stack.portal = p;
+		stack.next = NULL;
+		stack.freewindings[0] = 1;
+		stack.freewindings[1] = 1;
+		stack.freewindings[2] = 1;
+		
+		float 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 = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+			if (!stack.pass)
+				continue;
+		}
+
+
+		d = DotProduct (thread->base->origin, p->plane.normal);
+		d -= p->plane.dist;
+		if (d > thread->base->radius)
+		{
+			continue;
+		}
+		else if (d < -thread->base->radius)
+		{
+			stack.source = prevstack->source;
+		}
+		else	
+		{
+			stack.source = ChopWinding (prevstack->source, &stack, &backplane);
+			if (!stack.source)
+				continue;
+		}
+
+
+		if (!prevstack->pass)
+		{	// the second leaf can only be blocked if coplanar
+
+			// mark the portal as visible
+			SetBit( thread->base->portalvis, pnum );
+
+			RecursiveLeafFlow (p->leaf, thread, &stack);
+			continue;
+		}
+
+		stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);
+		if (!stack.pass)
+			continue;
+		
+		stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);
+		if (!stack.pass)
+			continue;
+
+		// mark the portal as visible
+		SetBit( thread->base->portalvis, pnum );
+
+		// flow through it for real
+		RecursiveLeafFlow (p->leaf, thread, &stack);
+	}	
+}
+
+
+/*
+===============
+PortalFlow
+
+generates the portalvis bit vector
+===============
+*/
+void PortalFlow (int iThread, int portalnum)
+{
+	threaddata_t	data;
+	int				i;
+	portal_t		*p;
+	int				c_might, c_can;
+
+	p = sorted_portals[portalnum];
+	p->status = stat_working;
+				
+	c_might = CountBits (p->portalflood, g_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;
+	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, g_numportals*2);
+
+	qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
+		(int)(p - portals),	c_might, c_can, data.c_chains);
+}
+
+
+/*
+===============================================================================
+
+This is a rough first-order aproximation that is used to trivially reject some
+of the final calculations.
+
+
+Calculates portalfront and portalflood bit vectors
+
+===============================================================================
+*/
+
+int		c_flood, c_vis;
+
+/*
+==================
+SimpleFlood
+
+==================
+*/
+void SimpleFlood (portal_t *srcportal, int leafnum)
+{
+	int		i;
+	leaf_t	*leaf;
+	portal_t	*p;
+	int		pnum;
+
+	leaf = &leafs[leafnum];
+	
+	for (i=0 ; i<leaf->portals.Count(); i++)
+	{
+		p = leaf->portals[i];
+		pnum = p - portals;
+		if ( !CheckBit( srcportal->portalfront, pnum ) )
+			continue;
+
+		if ( CheckBit( srcportal->portalflood, pnum ) )
+			continue;
+
+		SetBit( srcportal->portalflood, pnum );
+		
+		SimpleFlood (srcportal, p->leaf);
+	}
+}
+
+/*
+==============
+BasePortalVis
+==============
+*/
+void BasePortalVis (int iThread, int portalnum)
+{
+	int			j, k;
+	portal_t	*tp, *p;
+	float		d;
+	winding_t	*w;
+	Vector		segment;
+	double		dist2, minDist2;
+
+	// get the portal
+	p = portals+portalnum;
+
+	//
+	// allocate memory for bitwise vis solutions for this portal
+	//
+	p->portalfront = (byte*)malloc (portalbytes);
+	memset (p->portalfront, 0, portalbytes);
+
+	p->portalflood = (byte*)malloc (portalbytes);
+	memset (p->portalflood, 0, portalbytes);
+	
+	p->portalvis = (byte*)malloc (portalbytes);
+	memset (p->portalvis, 0, portalbytes);
+	
+	//
+	// test the given portal against all of the portals in the map
+	//
+	for (j=0, tp = portals ; j<g_numportals*2 ; j++, tp++)
+	{
+		// don't test against itself
+		if (j == portalnum)
+			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_VIS_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_VIS_EPSILON)
+				break;
+		}
+		if (k == w->numpoints)
+			continue;	// no points on front
+
+		//
+		// if using radius visibility -- check to see if any portal points lie inside of the
+		// radius given
+		//
+		if( g_bUseRadius )
+		{
+			w = tp->winding;
+			minDist2 = 1024000000.0;			// 32000^2
+			for( k = 0; k < w->numpoints; k++ )
+			{
+				VectorSubtract( w->points[k], p->origin, segment );
+				dist2 = ( segment[0] * segment[0] ) + ( segment[1] * segment[1] ) + ( segment[2] * segment[2] );
+				if( dist2 < minDist2 )
+				{
+					minDist2 = dist2;
+				}
+			}
+
+			if( minDist2 > g_VisRadius )
+				continue;
+		}
+
+		// add current portal to given portal's list of visible portals
+		SetBit( p->portalfront, j );
+	}
+	
+	SimpleFlood (p, p->leaf);
+
+	p->nummightsee = CountBits (p->portalflood, g_numportals*2);
+//	Msg ("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)
+{
+	portal_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->portals.Count(); i++)
+	{
+		p = leaf->portals[i];
+		pnum = p - portals;
+
+		// if some previous portal can't see it, skip
+		if ( !CheckBit( mightsee, pnum ) )
+			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
+
+		SetBit( cansee, pnum );
+
+		RecursiveLeafBitFlow (p->leaf, newmight, cansee);
+	}	
+}
+
+/*
+==============
+BetterPortalVis
+==============
+*/
+void BetterPortalVis (int portalnum)
+{
+	portal_t	*p;
+
+	p = portals+portalnum;
+
+	RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
+
+	// build leaf vis information
+	p->nummightsee = CountBits (p->portalvis, g_numportals*2);
+	c_vis += p->nummightsee;
+}
+
+