
#include "vis.h"

unsigned long c_chains;
int c_vistest, c_mighttest;

#ifdef USE_CHECK_STACK
int
CheckStack( leaf_t *leaf, threaddata_t *thread ) {
	pstack_t *p;

	for( p = thread->pstack_head.next; p; p = p->next ) {
		if( p->leaf == leaf ) {
			return 1;
			//sprintf (Str, "CheckStack: leaf recursion%s\n", GetCoord(leaf));
			//Error (Str);
		}
	}

	return 0;
}
#endif

qboolean
WindingOnPlane( winding_t *w, plane_t *plane ) {
	int i;
	vec_t d;
	int numOn = 0;

	for( i = 0; i < w->numpoints; ++i ) {
		d = DotProduct( w->points[i], plane->normal ) - plane->dist;

		if( d < ON_EPSILON && d > -ON_EPSILON )
			++numOn;
	}

	return ( numOn == w->numpoints );
}

// windings should be on the same plane
winding_t *
WindingOverlap( winding_t *w1, winding_t *w2 ) {
	int i, j, nextI;
	vec3_t edgeVec;
	plane_t plane;
	plane_t edgePlane;
	winding_t *outW;

	outW = CopyWinding( w2 );

	PlaneFromWinding( w1, &plane );

	for( i = 0; i < w1->numpoints; ++i ) {
		nextI = ( i + 1 ) % w1->numpoints;

		VectorSubtract( w1->points[ nextI ], w1->points[ i ], edgeVec );
		VectorNormalize( edgeVec );

		VectorCross( edgeVec, plane.normal, edgePlane.normal );
		edgePlane.dist = DotProduct( w1->points[i], edgePlane.normal );

		outW = ClipWinding( outW, &edgePlane, false );

		if( !outW )
			break;
	}

	return outW;
}

/*
==============
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 ) {
	int			i, j, k, l;
	plane_t		plane;
	vec3_t		v1, v2;
	vec_t		d;
	vec_t		length;
	int			side_front;
	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 );
			VectorCross( v1, v2, plane.normal );

			// if points don't make a valid plane, skip it
			length = DotProduct( plane.normal, plane.normal );

			if( length < ON_EPSILON )
				continue;

			length = 1.0 / 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
			//
			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_EPSILON ) { // source is on the negative side, so we want all pass and target on the positive side
					fliptest = false;
					break;
				}
				if( d > ON_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

			//
			// flip the normal if the source portal is backwards
			//
			if( fliptest ) {
				VectorInverse( plane.normal );
				plane.dist = -plane.dist;
			}

			//
			// if all of the pass portal points are now on the positive side,
			// this is the seperating plane
			//
			side_front = 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 )
					++side_front;
			}
			if( k != pass->numpoints )
				continue; // points on negative side, not a seperating plane

			if( !side_front )
				continue; // planar with seperating plane

			//
			// flip the normal if we want the back side
			//
			if( flipclip ) {
				VectorInverse( plane.normal );
				plane.dist = -plane.dist;
			}

			//
			// clip target by the seperating plane
			//
			target = ClipWinding( target, &plane, false );
			if( !target )
				return NULL; // target is not visible

			// RVis optimization
			break;
		}
	}

	return target;
}

/*
==================
ShowExtra
==================
*/
static void
ShowExtra( int Current, int Total ) {
	int TPercent, SRate;
	static double	PrevTime;
	static int	PrevTPerc;

	if( Total == 0 ) {
		// Init
		PrevTPerc = 0;
		PrevTime = I_FloatTime();
		return;
	}

	// Update no more than once each 10th percent
	TPercent = Current * 10 / Total;

	if( Current != 100 || Total != 100 ) {
		// Not final 100,100 input

		++TPercent; // Adjust for highly non-linear progress

		if( TPercent > 9 )
			return; // Prevent overflow and completion before 100,100 input
	}

	if( TPercent > PrevTPerc ) {
		SRate = SecRate == 0 ? 1 : SecRate;

		// Only update if at least (SecRate * 12) is spent in one portal. This should
		// prevent unnecessary or multiple portal bars between normal ShowPercent updates
		if( verbose || PrevTPerc > 0 || TPercent >= 1 && I_FloatTime() > PrevTime + SRate * 12 ) {
			if( PrevTPerc == 0 && !verbose )
				printf( "\n" );

			// Make sure bar reaches current value
			do
				printf( "%c", ++PrevTPerc % 5 == 0 ? '+' : '-' );
			while( PrevTPerc < TPercent );

			fflush( stdout );
		}
	}
}

unsigned long RecursLevel;

#define VisBitQuery( _visBits, _queryBit )	( _visBits[ _queryBit >> 3 ] & ( 1 << ( _queryBit & 7 )))
#define VisBitSet( _visBits, _setBit )		_visBits[ _setBit >> 3 ] |= ( 1 << ( _setBit & 7 ))
#define VisBitClear( _visBits, _setBit )	_visBits[ _setBit >> 3 ] &= ~( 1 << ( _setBit & 7 ))

/*
==================
RecursiveLeafFlow

Flood fill through the leafs
If src_portal is NULL, this is the originating leaf
==================
*/
void
RecursiveLeafFlow( const int leafnum, const threaddata_t *const thread, pstack_t *const prevstack ) {
	pstack_t		stack;
	portal_t		*p;
	plane_t			backplane;
	winding_t		*source, *target, *pass;
	int				i = 0, j;
	long			*test, *might;
	const long		*vis = (long *) thread->leafvis;
	qboolean		more;
	static int		L1Curr, L1Tot;
	const leaf_t	*leaf = &leafs[ leafnum ];

	++c_chains;

	#ifdef USE_CHECK_STACK
	if( CheckStack( leaf, thread ) != 0 ) {
		//logprintf("CheckStack: Leaf Recursion detected for leaf %i", leafnum );
		return;
	}
	#endif

	if( PercRate == 0 )
		++RecursLevel;

	// mark the leaf as visible from the head portal

	if( !VisBitQuery( thread->leafvis, leafnum )) {
		VisBitSet( thread->leafvis, leafnum );
		++thread->base->numcansee;
	}

	#ifdef USE_CHECK_STACK
	prevstack->next = &stack;
	stack.next = NULL;
	#endif

	stack.leaf = leaf;
	stack.portal = NULL;
	stack.mightsee = malloc( bitbytes );
	might = (long *) stack.mightsee;

	// Extra progress info
	if( RecursLevel == 1 ) {
		L1Tot = leaf->numportals;
		ShowExtra( L1Curr = i, L1Tot );
	} else
	if( RecursLevel == 2 ) {
		ShowExtra(( L1Curr * 100 + i * 100 / leaf->numportals ) / L1Tot, 99 );
	}

	// check all portals for flowing into other leafs
	for( i = 0; i != leaf->numportals; ++i ) {
		p = leaf->portals[ i ];

		if( !VisBitQuery( prevstack->mightsee, p->leaf ))
			continue; // can't possibly see it

		// if the portal can't see anything we haven't already seen, skip it
		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 )
			continue; // can't see anything new

		// get plane of portal, point normal into the neighbor leaf
		stack.portalplane = p->plane;
		VectorNegate( p->plane.normal, backplane.normal );
		backplane.dist = -p->plane.dist;

		if( VectorCompare( prevstack->portalplane.normal, backplane.normal ))
			continue; // can't go out a coplanar face

		++c_portalcheck;

		stack.portal = p;
		#ifdef USE_CHECK_STACK
		stack.next = NULL;
		#endif

#ifdef USE_PORTALOVERLAP
		// rebb: sometimes overlapping portals are created, causing false vis information ( HOM ), this is supposed to handle these cases
		if( WindingOnPlane( p->winding, &thread->pstack_head.portalplane )) {
			target = WindingOverlap( p->winding, prevstack->source );
			if( target ) {
				//stack.source = prevstack->source;
				stack.source = target;
				stack.pass = NULL;

				++c_portalpass;

				// flow through it for real
				RecursiveLeafFlow( p->leaf, thread, &stack );

				FreeWinding( target );
				continue;
			}
		}
#endif

		// clip target by base portal
		target = ClipWinding( p->winding, &thread->pstack_head.portalplane, false );
		if( !target ) {
			continue;
		}

		if( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
			stack.source = prevstack->source;
			stack.pass = target;
			RecursiveLeafFlow( p->leaf, thread, &stack );
			FreeWinding( target );
			continue;
		}

#ifdef USE_PORTALOVERLAP
		if( WindingOnPlane( p->winding, &prevstack->portalplane )) {
			target = WindingOverlap( p->winding, prevstack->pass );
			if( target ) {
				stack.source = prevstack->source;
				//stack.pass = p->winding;
				stack.pass = target;

				++c_portalpass;

				// flow through it for real
				RecursiveLeafFlow( p->leaf, thread, &stack );

				FreeWinding( target );
				continue;
			}
		}
#endif

		// clip target by previous portal
		target = ClipWinding( target, &prevstack->portalplane, false );
		if( !target ) {
			continue;
		}

		source = CopyWinding( prevstack->source );

		source = ClipWinding( source, &backplane, false );
		if( !source ) {
			FreeWinding( target );
			continue;
		}
		
		++c_portaltest;

		if( testlevel > 0 ) {
			target = ClipToSeperators( source, prevstack->pass, target, false );
			if( !target ) {
				FreeWinding( source );
				continue;
			}
		}

		if( testlevel > 1 ) {
			target = ClipToSeperators( prevstack->pass, source, target, true );
			if( !target ) {
				FreeWinding( source );
				continue;
			}
		}

		if( testlevel > 2 ) {
			source = ClipToSeperators( target, prevstack->pass, source, false );
			if( !source ) {
				FreeWinding( target );
				continue;
			}
		}

		if( testlevel > 3 ) {
			source = ClipToSeperators( prevstack->pass, target, source, true );
			if( !source ) {
				FreeWinding( target );
				continue;
			}
		}

		stack.source = source;
		stack.pass = target;

		++c_portalpass;

		// flow through it for real
		RecursiveLeafFlow( p->leaf, thread, &stack );

		FreeWinding( source );
		FreeWinding( target );
	}

	free( stack.mightsee );

	if( RecursLevel > 0 )
		--RecursLevel;
}

/*
===============
PortalFlow

===============
*/
void
PortalFlow( portal_t *p ) {
	threaddata_t data;

	if( p->status != stat_working )
		Error( "PortalFlow: reflowed" );

	p->visbits = calloc( 1, bitbytes );

	memset( &data, 0, sizeof( data ));
	data.leafvis = p->visbits;
	data.base = p;

	data.pstack_head.portal = p;
	data.pstack_head.source = p->winding;
	data.pstack_head.portalplane = p->plane;
	data.pstack_head.mightsee = p->mightsee;

	// Prevent excessive updates
	if( PercRate == 0 || verbose ) {
		RecursLevel = 0;
		ShowExtra( 0, 0 );
	}

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

	if( PercRate == 0 || verbose )
		ShowExtra( 100, 100 );

	p->status = stat_done;
}

/*
===============================================================================

This is a rough first-order aproximation that is used to trivially reject some
of the final calculations.

===============================================================================
*/

byte *portalsee;
int	c_leafsee, c_portalsee;

void
SimpleFlood( portal_t *srcportal, int leafnum ) {
	int			i;
	leaf_t		*leaf;
	portal_t	*p;
	
	if( VisBitQuery( srcportal->mightsee, leafnum ))
		return;

	VisBitSet( srcportal->mightsee, leafnum );

	++c_leafsee;

	leaf = &leafs[ leafnum ];

	for( i = 0; i < leaf->numportals; i++ ) {
		p = leaf->portals[ i ];

		if( !portalsee[ p - portals ] )
			continue;

		SimpleFlood( srcportal, p->leaf );
	}
}

float
FindMin( winding_t *w, portal_t *p ) {
	float	d, mind;
	int	k;

	mind = 99999999;

	for( k = 0; k < w->numpoints; ++k ) {
		d = fabs( DotProduct( w->points[ k ], p->plane.normal ) - p->plane.dist );

		if( d < mind )
			mind = d;
	}

	return mind;
}

/*
==============
BasePortalVis
==============
*/
void
BasePortalVis( void ) {
	int			i, j, k, Total, CutOff, prevk;
	portal_t	*tp, *p;
	vec_t		d;
	winding_t	*w, *prevw;

	int numOverlaps = 0;
	int maxPortals = numportals * 2;
	int numOn, numFront;

	if( SimpPercent )
		printf( "\n" );

	ShowPercent( "Base", 0, 0 );

	CutOff = State.VDCutOff;
	Total = State.VDTotal;
	TimeOffset = State.BaseTime;

	if( !State.BaseDone ) {
		portalsee = malloc( maxPortals );

#if 0
		for( i = State.CurrPortal, p = &portals[ i ]; i < maxPortals; i++, p++ ) {
			p->mightsee = (byte*) calloc( 1, bitbytes );

			c_portalsee = 0;
			memset( portalsee, 0, maxPortals );

			for( j = 0, tp = portals, prevw = NULL; j < maxPortals; j++, tp++ ) {
				if( j == i )
					continue;

				w = tp->winding;

				if( w == prevw )
					k = prevk; // Same winding as previous => same result
				else {
					for( k = 0; k < w->numpoints; k++ ) {
						d = DotProduct( w->points[ k ], p->plane.normal ) - p->plane.dist;
						if( d > ON_EPSILON )
							break;
					}

					prevk = k;
					prevw = w;
				}
				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

				++Total;

				if( visdist > 0 && ( FindMin( tp->winding, p ) > visdist ||
						     FindMin( p->winding, tp ) > visdist )) {
					++CutOff;
					continue;
				}

				portalsee[ j ] = 1;

				c_portalsee++;
			}

			c_leafsee = 0;
			SimpleFlood( p, p->leaf );
			p->nummightsee = c_leafsee;

			// printf ("portal:%4i  c_leafsee:%4i \n", i, c_leafsee);

			ShowPercent( NULL, i, maxPortals );

			State.VDCutOff = CutOff;
			State.VDTotal = Total;
			SaveState( NULL, i, false );
		}
#else
		for( i = State.CurrPortal, p = &portals[ i ]; i < maxPortals; i++, p++ ) {
			p->mightsee = calloc( 1, bitbytes );

			c_portalsee = 0;
			memset( portalsee, 0, maxPortals );

			for( j = 0, tp = portals; j < maxPortals; j++, tp++ ) {
				if( j == i )
					continue;

				w = tp->winding;

				numOn = 0;
				numFront = 0;

				for( k = 0; k < w->numpoints; k++ ) {
					d = DotProduct( w->points[ k ], p->plane.normal ) - p->plane.dist;

					if( d > ON_EPSILON ) {
						++numFront;
						continue;
					} else
					if( d < -ON_EPSILON ) {
						continue;
					}

					++numOn;
				}

				if(	numOn == w->numpoints ) {
					if(
						DotProduct( tp->plane.normal, p->plane.normal ) < 0.5 ||
						!WindingOverlap( tp->winding, p->winding )
					) {
						continue;
					}

					++numOverlaps;
				} else {
					if( numFront == 0 )
						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
				}

				++Total;

				if(
					visdist > 0 &&
					( FindMin( tp->winding, p ) > visdist || FindMin( p->winding, tp ) > visdist )
				) {
					++CutOff;
					continue;
				}

				portalsee[ j ] = 1;

				c_portalsee++;
			}

			c_leafsee = 0;
			SimpleFlood( p, p->leaf );
			p->nummightsee = c_leafsee;

			// printf ("portal:%4i  c_leafsee:%4i \n", i, c_leafsee);

			ShowPercent( NULL, i, maxPortals );

			State.VDCutOff = CutOff;
			State.VDTotal = Total;
			SaveState( NULL, i, false );
		}
#endif

		free( portalsee );
	}

	ShowPercent( NULL, 100, 100 );

	if( !SimpPercent )
		printf( "\n" );

	if( visdist > 0 ) {
		if( !SimpPercent )
			printf( "\n" );

		logprintf( "%d%% visdist cutoff\n", (int) ((double) CutOff * 100 / Total ));
	}

	logprintf("Overlap Portals : %i\n", numOverlaps );

	if( fastvis )
		printf( "\n" );
}