visflow.c

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

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

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

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

//		stack.portal = p;
		// mark the portal as visible
		thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
		// 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
		}