level/vis_flow.c
/*	Flood fill through the leafs
	If src_portal is NULL, this is the originating leaf
*/
Flood fill through the leafs
If src_portal is NULL, this is the originating leaf
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;
	viswinding_t *source, *target;
	leaf_t 		*leaf;
	int			i, j;
	long		*test, *might, *vis;
	bool		more;
	c_chains++;
	leaf = &leafs[leafnum];
	CheckStack (leaf, thread);
	if (! (thread->leafvis[leafnum>>3] & (1<<(leafnum&7)) ) )
	{
		thread->leafvis[leafnum>>3] |= 1<<(leafnum&7);
		thread->base->numcansee++;
	}
	prevstack->next = &stack;
	stack.next = NULL;
	stack.leaf = leaf;
	stack.portal = NULL;
	stack.mightsee = qmalloc(bitlongs * sizeof(long));
	might = (long *)stack.mightsee;
	vis = (long *)thread->leafvis;
	for (i=0 ; i<leaf->numportals ; i++)
	{
		p = leaf->portals[i];
		if ( ! (prevstack->mightsee[p->leaf>>3] & (1<<(p->leaf&7)) ) )
		{
			c_leafskip++;
			continue;	
		}
		if (p->status == stat_done)
		{
			c_vistest++;
			test = (long *)p->visbits;
		}
		else
		{
			c_mighttest++;
			test = (long *)p->mightsee;
		}
		more = false;
		for (j=0 ; j<bitlongs ; j++)
		{
			might[j] = ((long *)prevstack->mightsee)[j] & test[j];
			if (might[j] & ~vis[j])
				more = true;
		}
		if (!more)
		{	
			c_portalskip++;
			continue;
		}
		stack.portalplane = p->plane;
		VectorNegate (p->plane.normal, backplane.normal);
		backplane.dist = -p->plane.dist;
		if (VectorCompare (prevstack->portalplane.normal, backplane.normal) )
			continue;	
		c_portalcheck++;
		stack.portal = p;
		stack.next = NULL;
		target = ClipVisWinding (p->winding, &thread->pstack_head.portalplane, false);
		if (!target)
			continue;
		if (!prevstack->pass)
		{	
			stack.source = prevstack->source;
			stack.pass = target;
			RecursiveLeafFlow (p->leaf, thread, &stack);
			FreeVisWinding (target);
			continue;
		}
		target = ClipVisWinding (target, &prevstack->portalplane, false);
		if (!target)
			continue;
		source = CopyVisWinding (prevstack->source);
		source = ClipVisWinding (source, &backplane, false);
		if (!source)
		{
			FreeVisWinding (target);
			continue;
		}
		c_portaltest++;
		if (testlevel > 0)
		{
			target = ClipToSeperators (source, prevstack->pass, target, false);
			if (!target)
			{
				FreeVisWinding (source);
				continue;
			}
		}
		if (testlevel > 1)
		{
			target = ClipToSeperators (prevstack->pass, source, target, true);
			if (!target)
			{
				FreeVisWinding (source);
				continue;
			}
		}
		if (testlevel > 2)
		{
			source = ClipToSeperators (target, prevstack->pass, source, false);
			if (!source)
			{
				FreeVisWinding (target);
				continue;
			}
		}
		if (testlevel > 3)
		{
			source = ClipToSeperators (prevstack->pass, target, source, true);
			if (!source)
			{
				FreeVisWinding (target);
				continue;
			}
		}
		stack.source = source;
		stack.pass = target;
		c_portalpass++;
		RecursiveLeafFlow (p->leaf, thread, &stack);
		FreeVisWinding (source);
		FreeVisWinding (target);
	}
	qfree (stack.mightsee);
}
void RecursiveLeafFlow ( int leafnum , threaddata_t * thread , pstack_t * prevstack ) { pstack_t stack ; portal_t * p ; plane_t backplane ; viswinding_t * source , * target ; leaf_t * leaf ; int i , j ; long * test , * might , * vis ; bool more ; c_chains ++ ; leaf = & leafs [ leafnum ] ; CheckStack ( leaf , thread ) ; if ( ! ( thread -> leafvis [ leafnum >> 3 ] & ( 1 << ( leafnum & 7 ) ) ) ) { thread -> leafvis [ leafnum >> 3 ] |= 1 << ( leafnum & 7 ) ; thread -> base -> numcansee ++ ; } prevstack -> next = & stack ; stack . next = NULL ; stack . leaf = leaf ; stack . portal = NULL ; stack . mightsee = qmalloc ( bitlongs * sizeof ( long ) ) ; might = ( long * ) stack . mightsee ; vis = ( long * ) thread -> leafvis ; for ( i = 0 ; i < leaf -> numportals ; i ++ ) { p = leaf -> portals [ i ] ; if ( ! ( prevstack -> mightsee [ p -> leaf >> 3 ] & ( 1 << ( p -> leaf & 7 ) ) ) ) { c_leafskip ++ ; continue ; } if ( p -> status == stat_done ) { c_vistest ++ ; test = ( long * ) p -> visbits ; } else { c_mighttest ++ ; test = ( long * ) p -> mightsee ; } more = false ; for ( j = 0 ; j < bitlongs ; j ++ ) { might [ j ] = ( ( long * ) prevstack -> mightsee ) [ j ] & test [ j ] ; if ( might [ j ] & ~ vis [ j ] ) more = true ; } if ( ! more ) { c_portalskip ++ ; continue ; } stack . portalplane = p -> plane ; VectorNegate ( p -> plane . normal , backplane . normal ) ; backplane . dist = - p -> plane . dist ; if ( VectorCompare ( prevstack -> portalplane . normal , backplane . normal ) ) continue ; c_portalcheck ++ ; stack . portal = p ; stack . next = NULL ; target = ClipVisWinding ( p -> winding , & thread -> pstack_head . portalplane , false ) ; if ( ! target ) continue ; if ( ! prevstack -> pass ) { stack . source = prevstack -> source ; stack . pass = target ; RecursiveLeafFlow ( p -> leaf , thread , & stack ) ; FreeVisWinding ( target ) ; continue ; } target = ClipVisWinding ( target , & prevstack -> portalplane , false ) ; if ( ! target ) continue ; source = CopyVisWinding ( prevstack -> source ) ; source = ClipVisWinding ( source , & backplane , false ) ; if ( ! source ) { FreeVisWinding ( target ) ; continue ; } c_portaltest ++ ; if ( testlevel > 0 ) { target = ClipToSeperators ( source , prevstack -> pass , target , false ) ; if ( ! target ) { FreeVisWinding ( source ) ; continue ; } } if ( testlevel > 1 ) { target = ClipToSeperators ( prevstack -> pass , source , target , true ) ; if ( ! target ) { FreeVisWinding ( source ) ; continue ; } } if ( testlevel > 2 ) { source = ClipToSeperators ( target , prevstack -> pass , source , false ) ; if ( ! source ) { FreeVisWinding ( target ) ; continue ; } } if ( testlevel > 3 ) { source = ClipToSeperators ( prevstack -> pass , target , source , true ) ; if ( ! source ) { FreeVisWinding ( target ) ; continue ; } } stack . source = source ; stack . pass = target ; c_portalpass ++ ; RecursiveLeafFlow ( p -> leaf , thread , & stack ) ; FreeVisWinding ( source ) ; FreeVisWinding ( target ) ; } qfree ( stack . mightsee ) ; }
Flood fill through the leafs
If src_portal is NULL, this is the originating leaf
Flood fill through the leafs If src_portal is NULL this is the originating leaf
// mark the leaf as visible // check all portals for flowing into other leafs // can't possibly see it // if the portal can't see anything we haven't allready seen, skip it // can't see anything new // get plane of portal, point normal into the neighbor leaf // can't go out a coplanar face // the second leaf can only be blocked if coplanar // flow through it for real