visflow.c

quake3工具源码。包括生成bsp文件

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