// Shadow volume class
//
// Written by Harald JOHNSEN, started June 2005.
//
// Copyright (C) 2005  Harald JOHNSEN - hjohnsen@evc.net
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; either version 2 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
//
//

#ifdef HAVE_CONFIG_H
#  include <simgear_config.h>
#endif

#include <plib/sg.h>
#include <simgear/debug/logstream.hxx>
#include <simgear/screen/extensions.hxx>
#include <simgear/scene/model/animation.hxx>
#include <simgear/scene/model/model.hxx>
#include <simgear/environment/visual_enviro.hxx>
#include <osg/GLU>

#include "shadowvolume.hxx"

/*
 geometry and edge list
 - traverse object graph until leaf to get geometry
 - what about transform and selection ?
	- use sub objects rather then objects
	- get local transform and selection
		- range anim : ssgRangeSelector ( min, max ) => ssgSelector ( true/false )
			=> selection [0..n], kids [0..n]
		- select/timed anim : ssgSelector ( true/false )
			=> isSelected( nkid )
		- spin/rotate/trans/scale/... : ssgTransform ( matrix )
			=> getNetTransform
 - on new object :
	- for one object branch
		- for each leaf
			- save geometry
			- save address in cache
 - when rendering object
	- for each leaf
		- getNetTransform + object global rotation (ac) => transform for light position
		- go up in tree and check isSelected( self )
 - generate connectivity each time the geometry change
	=> using local light so connectivity never changes
 - generate active edge list when :
	- light moves
	- subpart moves (animation code)
	- ac rotate
		=> cache rotation matrix and generate edge list only if something change
		=> even if it changes, no need to do that every frame

 - static objects have static edge list if light does not move

 shadowing a scene
 - render full scene as normal
 - render occluder in stencil buffer with their shadow volumes
 - apply stencil to framebuffer (darkens shadowed parts)

	shadows using the alpha buffer
	http://wwwvis.informatik.uni-stuttgart.de/~roettger/html/Pages/shadows.html
*/

// TODO
//	- shadow for objects
//		* aircraft
//		* tile objects (from .stg)
//		- ai objects
//		- random objects => tie shadow geometry to lib objects and reuse them
//	- zfail if camera inside shadow
//	- queue geometry work if lot of objects
//	* add a render property on/off (for aircraft, for scene objects, for ai)
//	* add a render property in rendering dialog
//	* filter : halo, light, shadow, disc, disk, flame, (exhaust), noshadow

static int statSilhouette=0;
static int statGeom=0;
static int statObj=0;

static SGShadowVolume *states;
static glBlendEquationProc glBlendEquationPtr = NULL;
#define GL_MIN_EXT                          0x8007
#define GL_MAX_EXT                          0x8008


SGShadowVolume::ShadowCaster::ShadowCaster( int _num_tri, ssgBranch * _geometry_leaf ) : 
	geometry_leaf ( _geometry_leaf ),
	scenery_object ( 0 ),
	first_select ( 0 ),
	frameNumber ( 0 ),
	indices ( 0 ),
	numTriangles ( 0 ),
	vertices ( 0 ),
	lastSilhouetteIndicesCount ( 0 )
{
	int num_tri = _num_tri;
	numTriangles = num_tri;
	triangles = new triData[ num_tri ];
	indices = new int[1 + num_tri * 3];
	vertices = new sgVec4[1 + num_tri * 3];
	silhouetteEdgeIndices = new GLushort[(1+num_tri) * 3*3];
	indices [ num_tri * 3 ] = num_tri * 3;
	sgSetVec3(last_lightpos, 0.0, 0.0, 0.0);
	statGeom ++;

	ssgBranch *branch = (ssgBranch *) _geometry_leaf;
	while( branch && branch->getNumParents() > 0 ) {
		if( branch->isAKindOf(ssgTypeSelector())) {
			first_select = branch;
			break;
		}
		if( sgCheckAnimationBranch( (ssgEntity *) branch ) )
			if( ((SGAnimation *) branch->getUserData())->get_animation_type() == 1) {
				first_select = branch;
				break;
			}
		branch = branch->getParent(0);
	}
}

void SGShadowVolume::ShadowCaster::addLeaf( int & tri_idx, int & ind_idx, ssgLeaf *geometry_leaf ) {
	int num_tri = geometry_leaf->getNumTriangles();
	for(int i = 0; i < num_tri ; i ++ ) {
		short v1, v2, v3;
		sgVec3 a, b, c;
		geometry_leaf->getTriangle( i, &v1, &v2, &v3 );
		sgCopyVec3(a, geometry_leaf->getVertex(v1));
		sgCopyVec3(b, geometry_leaf->getVertex(v2));
		sgCopyVec3(c, geometry_leaf->getVertex(v3));

		int p = tri_idx;
		sgMakePlane ( triangles[p].planeEquations, a, b, c );
		sgCopyVec3(vertices[ind_idx + v1], a);
		sgCopyVec3(vertices[ind_idx + v2], b);
		sgCopyVec3(vertices[ind_idx + v3], c);
		vertices[ind_idx + v1][SG_W] = 1.0f;
		vertices[ind_idx + v2][SG_W] = 1.0f;
		vertices[ind_idx + v3][SG_W] = 1.0f;
		indices[p*3] = ind_idx + v1;
		indices[p*3+1] = ind_idx + v2;
		indices[p*3+2] = ind_idx + v3;

		tri_idx++;
	}
	if( num_tri == 0 )
		return;
	isTranslucent |= geometry_leaf->isTranslucent() ? true : false;
	int num_ind = geometry_leaf->getNumVertices();
	ind_idx += num_ind;
}

SGShadowVolume::ShadowCaster::~ShadowCaster() {
	delete [] indices ;
	delete [] vertices ;
	delete [] triangles;
	delete [] silhouetteEdgeIndices;
}



bool SGShadowVolume::ShadowCaster::sameVertex(int edge1, int edge2) {
	if( edge1 == edge2)
		return true;
	sgVec3 delta_v;
	sgSubVec3( delta_v, vertices[edge1], vertices[edge2]);
	if( delta_v[SG_X] != 0.0)	return false;
	if( delta_v[SG_Y] != 0.0)	return false;
	if( delta_v[SG_Z] != 0.0)	return false;
	return true;
}


//Calculate neighbour faces for each edge
// caution, this is O(n2)
void SGShadowVolume::ShadowCaster::SetConnectivity(void)
{
	int edgeCount = 0;

	//set the neighbour indices to be -1
	for(int ii=0; ii<numTriangles; ++ii)
		triangles[ii].neighbourIndices[0] = 
		triangles[ii].neighbourIndices[1] = 
		triangles[ii].neighbourIndices[2] = -1;

	//loop through triangles
	for(int i=0; i<numTriangles-1; ++i)
	{
		//loop through edges on the first triangle
		for(int edgeI=0; edgeI<3; ++edgeI)
		{
			//continue if this edge already has a neighbour set
			if(triangles[i].neighbourIndices[ edgeI ]!=-1)
				continue;

			//get the vertex indices on each edge
			int edgeI1=indices[i*3+edgeI];
			int edgeI2=indices[i*3+(edgeI == 2 ? 0 : edgeI+1)];

			//loop through triangles with greater indices than this one
			for(int j=i+1; j<numTriangles; ++j)
			{
				//loop through edges on triangle j
				for(int edgeJ=0; edgeJ<3; ++edgeJ)
				{
					//continue if this edge already has a neighbour set
					if(triangles[j].neighbourIndices[ edgeJ ]!=-1) {
						continue;
					}
					//get the vertex indices on each edge
					int edgeJ1=indices[j*3+edgeJ];
					int edgeJ2=indices[j*3+(edgeJ == 2 ? 0 : edgeJ+1)];

					//if these are the same (possibly reversed order), these faces are neighbours
#if 0
					//no, we only use reverse order because same order means that
					//the triangle is wrongly oriented and that will cause shadow artifact
					if(	sameVertex(edgeI1, edgeJ1) && sameVertex(edgeI2, edgeJ2) ) {
							// can happens with 'bad' geometry
//							printf("flipped triangle detected...check your model\n");
						continue;
					}
#endif
					if(	sameVertex(edgeI1, edgeJ2) && sameVertex(edgeI2, edgeJ1) )
					{
						int edgeI3=indices[i*3+(edgeI == 0 ? 2 : edgeI-1)];
						int edgeJ3=indices[j*3+(edgeJ == 0 ? 2 : edgeJ-1)];
						if(	sameVertex(edgeI3, edgeJ3) ) {
							// can happens with 'bad' geometry
//							printf("duplicated tri...check your model\n");
							// exit loop
							break;
						}
						triangles[i].neighbourIndices[edgeI]=j;
						triangles[j].neighbourIndices[edgeJ]=i;
						edgeCount ++;
						// exit loop
						j = numTriangles;
						break;
					}
				}
			}
		}
	}
//	printf("submodel has %d triangles and %d shared edges\n", numTriangles, edgeCount);
}

//calculate silhouette edges
void SGShadowVolume::ShadowCaster::CalculateSilhouetteEdges(sgVec3 lightPosition)
{
	//Calculate which faces face the light
	for(int i=0; i<numTriangles; ++i)
	{
		if( sgDistToPlaneVec3 ( triangles[i].planeEquations, lightPosition ) > 0.0 )
			triangles[i].isFacingLight=true;
		else
			triangles[i].isFacingLight=false;
	}

	//loop through faces
	int iEdgeIndices = 0;
	sgVec4 farCap = {-lightPosition[SG_X], -lightPosition[SG_Y], -lightPosition[SG_Z], 1.0f};
	sgCopyVec4( vertices[ numTriangles*3 ], farCap );

	for(int t=0; t < numTriangles; t++) {
		int v = t * 3;
		//if this face is not facing the light, not a silhouette edge
		if(!triangles[t].isFacingLight)
		{
			triangles[t].isSilhouetteEdge[0]=false;
			triangles[t].isSilhouetteEdge[1]=false;
			triangles[t].isSilhouetteEdge[2]=false;
			continue;
		}
		//loop through edges
		for(int j = 0 ; j < 3 ; j++) {
			//this face is facing the light
			//if the neighbouring face is not facing the light, or there is no neighbouring face,
			//then this is a silhouette edge
			if(triangles[t].neighbourIndices[j]==-1 || 
				!triangles[triangles[t].neighbourIndices[j]].isFacingLight ) {
				triangles[t].isSilhouetteEdge[j]=true;
				silhouetteEdgeIndices[ iEdgeIndices++ ] = indices[v+(j == 2 ? 0 : j+1)];
				silhouetteEdgeIndices[ iEdgeIndices++ ] = indices[v+j];
				silhouetteEdgeIndices[ iEdgeIndices++ ] = numTriangles * 3;
			}
			else 
				triangles[t].isSilhouetteEdge[j]=false;
		}
	}
	lastSilhouetteIndicesCount = iEdgeIndices;
}

void SGShadowVolume::ShadowCaster::DrawInfiniteShadowVolume(sgVec3 lightPosition, bool drawCaps)
{
	glEnableClientState ( GL_VERTEX_ARRAY ) ;
	glVertexPointer ( 4, GL_FLOAT, 0, vertices ) ;
	glDrawElements ( GL_TRIANGLES, lastSilhouetteIndicesCount, GL_UNSIGNED_SHORT, silhouetteEdgeIndices ) ;

	//Draw caps if required
 	if(drawCaps)
	{
		glBegin(GL_TRIANGLES);
		{
			for(int i=0; i<numTriangles; ++i)
			{
				if(triangles[i].isFacingLight) {
					int v = i*3;
					glVertex3fv( vertices[indices[v+0]] );
					glVertex3fv( vertices[indices[v+1]] );
					glVertex3fv( vertices[indices[v+2]] );
				}
			}
		}
		glEnd();
	}
}


void SGShadowVolume::ShadowCaster::getNetTransform ( ssgBranch * branch, sgMat4 xform )
{
	// one less matmult...
	bool first = true;
	while( branch && branch != lib_object ) {
		if( branch->isA(ssgTypeTransform()) ) {
			sgMat4 transform;
			if( first ) {
				((ssgTransform *) branch)->getTransform( xform );
				first = false;
			} else {
				((ssgTransform *) branch)->getTransform(transform);
				sgPostMultMat4 ( xform, transform ) ;
			}
		}
		branch = branch->getParent( 0 );
	}
	if( first )
		sgMakeIdentMat4 ( xform ) ;
}

// check the value of <select> and <range> animation
// wich have been computed during the rendering
bool SGShadowVolume::ShadowCaster::isSelected (  ssgBranch * branch, float dist ) {
	while( branch && branch != lib_object) {
		if( sgCheckAnimationBranch( (ssgEntity *) branch ) ) {
			if( ((SGAnimation *) branch->getUserData())->get_animation_type() == 1)
				if( ((SGShadowAnimation *) branch->getUserData())->get_condition_value() )
					return false;
		}
		// recompute range check since the value in the branch is shared by multiple objects
		// we can only have the last value
		if( branch->isA(ssgTypeRangeSelector()) )
			if( dist >= ((ssgRangeSelector *) branch)->getRange(1) ||
				dist < ((ssgRangeSelector *) branch)->getRange(0))
				return false;
		if( branch->isA(ssgTypeSelector()) )
			if( !((ssgSelector *) branch)->isSelected(0) )
				return false;
		branch = branch->getParent(0);
	}
	return true;
}
/*
	trans ----- personality ---- shared object
	perso1 *-----
	             \
	              *--------* shared object
	             /
	perso2 *-----
*/
void SGShadowVolume::ShadowCaster::computeShadows(sgMat4 rotation, sgMat4 rotation_translation,
	OccluderType occluder_type) {
  
	// check the select and range ssgSelector node
	// object can't cast shadow if it is not visible
	sgVec4 trans;
	sgCopyVec4( trans, rotation_translation[3] );
	sgAddVec4( trans, states->CameraViewM[3] );
	float dist = sgLengthVec3( trans );

  	if( first_select && ! isSelected( first_select, dist) )
		return;

		// get the transformations : this comes from animation code for example
		// or static transf
	sgMat4 transf;
 	sgVec3 lightPos;
	int deltaFrame = occluder_type == SGShadowVolume::occluderTypeAircraft ? 0 : 9;
  	if( states->frameNumber - frameNumber > deltaFrame) {
		sgMat4 transform ;
		sgMat4 invTransform;
  		getNetTransform( (ssgBranch *) geometry_leaf, transform );
		sgCopyMat4( last_transform, transform );
		sgPostMultMat4( transform, rotation );
		sgTransposeNegateMat4 ( invTransform, transform ); 

  		sgCopyVec3( lightPos, states->sunPos );
 		sgXformPnt3( lightPos, invTransform );

		sgVec3 lightPosNorm;
		sgNormaliseVec3( lightPosNorm, lightPos );
		float deltaPos = sgAbs(lightPosNorm[0] - last_lightpos[0]) + 
				sgAbs(lightPosNorm[1] - last_lightpos[1]) +
				sgAbs(lightPosNorm[2] - last_lightpos[2]);
		// if the geometry has rotated/moved enought then
		// we need to recompute the silhouette
		// but this computation does not need to be done each frame
   		if( deltaPos > 0.0 ) {
			CalculateSilhouetteEdges( lightPos );
			sgCopyVec3( last_lightpos, lightPosNorm );
			frameNumber = states->frameNumber ;
			statSilhouette ++;
		}
	}
	sgCopyMat4( transf, last_transform );
	sgPostMultMat4( transf, rotation_translation );
  	glLoadMatrixf ( (float *) states->CameraViewM ) ;
   	glMultMatrixf( (float *) transf );

	if( states->shadowsDebug_enabled )
	{
   		glStencilFunc(GL_ALWAYS, 0, ~0);
	  	glDisable( GL_CULL_FACE  );
		glDisable( GL_DEPTH_TEST );
		glDisable(GL_STENCIL_TEST);
		glColorMask(1, 1, 1, 1);
  		glColor4f(0.0, 0.0, 1.0, 1.0);
	  	glBegin(GL_LINES);
		for(int i=0; i<numTriangles; ++i)
		{
			if(!triangles[i].isFacingLight)
				continue;
			int v = i*3;
			//Loop through edges on this face
			sgVec3 vertex1, vertex2, vertex3;
			sgCopyVec3(vertex1, vertices[indices[v+0]]);
			sgCopyVec3(vertex2, vertices[indices[v+1]]);
			sgCopyVec3(vertex3, vertices[indices[v+2]]);

			if(triangles[i].isSilhouetteEdge[0]) {
				glVertex3fv(vertex2);
 				glVertex3fv(vertex1);
			}
			if(triangles[i].isSilhouetteEdge[1]) {
				glVertex3fv(vertex2);
 				glVertex3fv(vertex3);
			}
			if(triangles[i].isSilhouetteEdge[2]) {
				glVertex3fv(vertex3);
 				glVertex3fv(vertex1);
			}
		}
		glEnd();
		glColorMask(0, 0, 0, 0);
 	  	glEnable( GL_CULL_FACE  );
		glEnable( GL_DEPTH_TEST );
		glEnable(GL_STENCIL_TEST);
	}


		// TODO:compute intersection with near clip plane...
 		bool needZFail=false;

		// GL_INCR_WRAP_EXT, GL_DECR_WRAP_EXT

 		if(needZFail)
		{
			//Increment stencil buffer for back face depth fail
			glStencilFunc(GL_ALWAYS, 0, ~0);
			glStencilOp(GL_KEEP, GL_INCR, GL_KEEP);
			glCullFace(GL_FRONT);

			DrawInfiniteShadowVolume( lightPos, true);

			//Decrement stencil buffer for front face depth fail
			glStencilOp(GL_KEEP, GL_DECR, GL_KEEP);
			glCullFace(GL_BACK);

			DrawInfiniteShadowVolume( lightPos, true);
		}
		else	//using zpass
		{
			//Increment stencil buffer for front face depth pass
			if( states->use_alpha ) {
				glBlendEquationPtr( GL_FUNC_ADD );
				glBlendFunc( GL_ONE, GL_ONE );
 			  	glColor4ub(1, 1, 1, 16);
			} else {
			  	glColor4f(1.0f, 1.0f, 0.0f, 0.5f);
				glStencilFunc(GL_ALWAYS, 0, ~0);
				glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
			}
			glCullFace(GL_BACK);

			DrawInfiniteShadowVolume( lightPos, states->shadowsAC_transp_enabled & isTranslucent);

			//Decrement stencil buffer for back face depth pass
			if( states->use_alpha ) {
				glBlendEquationPtr( GL_FUNC_REVERSE_SUBTRACT );
				glBlendFunc( GL_ONE, GL_ONE );
			  	glColor4ub(1, 1, 1, 16);
			} else {
				glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
			}
			glCullFace(GL_FRONT);

			DrawInfiniteShadowVolume( lightPos, states->shadowsAC_transp_enabled & isTranslucent);
		}
}


void SGShadowVolume::SceneryObject::computeShadows(void) {

	// compute intersection with view frustum
	// use pending_object (pointer on obj transform) & tile transform
	// to get position
		if( !scenery_object ) {
			if( states->frameNumber - states->lastTraverseTreeFrame > 5 ) {
				find_trans();
				if( scenery_object )
					traverseTree( pending_object );
					states->lastTraverseTreeFrame = states->frameNumber;
			}
			return;
		}
		sgMat4 rotation, rotation_translation;
		scenery_object->getNetTransform ( rotation_translation );
		// split placement offset into rotation and offset
		// rotation from model inside world
		// we are not interested in translation since the light is very far away
		// without translation we reduce the frequency of updates of the silouhette
		sgCopyMat4( rotation, rotation_translation );
   		sgSetVec4( rotation[3], 0, 0, 0, 1);

		ShadowCaster_list::iterator iShadowCaster;
		for(iShadowCaster = parts.begin() ; iShadowCaster != parts.end() ; iShadowCaster ++ ) {
			(*iShadowCaster)->computeShadows(rotation, rotation_translation, occluder_type);
		}
}

static ssgCullResult cull_test ( ssgEntity *e, sgFrustum *f, sgMat4 m, int test_needed )
{
  if ( ! test_needed )
    return SSG_INSIDE ;

  sgSphere tmp = *(e->getBSphere()) ;

  if ( tmp.isEmpty () )
    return SSG_OUTSIDE ;

  tmp . orthoXform ( m ) ;
  if( tmp.center[2] == 0.0 )
	  return SSG_STRADDLE;
  // cull if too small on screen
  if ( tmp.radius / sgAbs(tmp.center[2]) < 1.0 / 40.0 )
    return SSG_OUTSIDE ;

  return (ssgCullResult) f -> contains ( &tmp ) ;
}


void SGShadowVolume::cull ( ssgBranch *b, sgFrustum *f, sgMat4 m, int test_needed )
{
	int cull_result = cull_test ( (ssgEntity *) b, f, m, test_needed ) ;

	if ( cull_result == SSG_OUTSIDE )
		return ;
	if( b->isA( ssgTypeTransform() ) ) {

		SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( b );
		if( iSceneryObject != sceneryObjects.end() ) {
			SceneryObject *an_occluder = iSceneryObject->second;
			if( shadowsTO_enabled && (an_occluder->occluder_type == occluderTypeTileObject) ||
				shadowsAI_enabled && (an_occluder->occluder_type == occluderTypeAI ) ||
				shadowsAC_enabled && (an_occluder->occluder_type == occluderTypeAircraft ) )
					an_occluder->computeShadows();

			return;
		}
		sgMat4 tmp, transform ;
		sgCopyMat4 ( tmp, m ) ;
		((ssgTransform *)b)->getTransform( transform );
		sgPreMultMat4 ( tmp,  transform ) ;
		glPushMatrix () ;
		glLoadMatrixf ( (float *) tmp ) ;
		for ( ssgEntity *e = b->getKid ( 0 ) ; e != NULL ; e = b->getNextKid() )
			cull ( (ssgBranch *) e, f, tmp, cull_result != SSG_INSIDE ) ;
		glPopMatrix () ;
	} else if( b->isAKindOf( ssgTypeSelector() ) ) {
		int s = ((ssgSelector *) b)->getSelect() ;
		if( b->isA( ssgTypeRangeSelector() ) ) {
			float range = sgLengthVec3 ( m [ 3 ] ) ;
			s = (range < ((ssgRangeSelector *) b)->getRange(1) &&
				range >= ((ssgRangeSelector *) b)->getRange(0) ) ? 1 : 0;
		}
		for ( ssgEntity *e = b->getKid ( 0 ) ; e != NULL ; e = b->getNextKid(), s >>= 1 )
			if ( s & 1 )
				cull ( (ssgBranch *) e, f, m, cull_result != SSG_INSIDE ) ;
	} else if( b->isAKindOf( ssgTypeBranch() ) ) {
		char *name = b->getName();
		// quick exit for the hundreds of ground leafs
		if( name && !strcmp(name, "LocalTerrain") )
			return;
		for ( ssgEntity *e = b->getKid ( 0 ) ; e != NULL ; e = b->getNextKid() )
			if( ! e->isAKindOf( ssgTypeLeaf() ) )
				cull ( (ssgBranch *) e, f, m, cull_result != SSG_INSIDE ) ;
	}
}

/*
	1) starting at the root of a scene object we follow all branch to find vertex leaf.
	each vertex leaf will create a shadow sub object so that the shadow casted by this
	geometry can be correctly rendered according to select or transform nodes.
	2) models are not optimized for shadows because the geometry is cut by
		- select / transform nodes
		- material differences
	since we are not interested in the geometry material we try to merge same level
	leafs. this can divide the number of shadow sub models by a lot (reducing the cpu
	overhead for matrix computation) and at the end this will reduce the number of
	silouhette edge by a lot too.
*/
static bool filterLeaf(ssgLeaf *this_kid) {
	const char *leaf_name = this_kid->getName();
/*	ssgSimpleState *sst = (ssgSimpleState *) this_kid->getState();
	if( sst && sst->isTranslucent() )
		return false;*/
	if( ! leaf_name )
		return true;
	char lname[20];
	unsigned int l = 0;
	char *buff;
	for( buff = lname; *leaf_name && l < (sizeof( lname )-1); ++buff, l++ )
	     *buff = tolower(*leaf_name++);
	*buff = 0;
	if( !strncmp(lname, "noshadow", 8) )
		return false;
	return true;
}
void SGShadowVolume::SceneryObject::traverseTree(ssgBranch *branch) {
	int num_tri = 0;
	int num_leaf = 0;

	if( sgCheckAnimationBranch( (ssgEntity *) branch ) ) {
		if( ((SGAnimation *) branch->getUserData())->get_animation_type() == 1)
			if( ((SGShadowAnimation *) branch->getUserData())->get_condition_value() )
				return;
	}

	for(int i = 0 ; i < branch->getNumKids() ; i++) {
		ssgEntity *this_kid = branch->getKid( i );
		if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
			if( filterLeaf( (ssgLeaf *) this_kid ) ) {
				num_tri += ((ssgLeaf *) this_kid)->getNumTriangles();
				num_leaf ++;
			}
		} else
			traverseTree( (ssgBranch *) this_kid );
	}
	if( num_tri > 0) {
		int tri_idx = 0;
		int ind_idx = 0;
		ShadowCaster *new_part = new ShadowCaster( num_tri, branch);
		new_part->scenery_object = scenery_object;
		new_part->lib_object = lib_object;
		new_part->isTranslucent = false;
		for(int i = 0 ; i < branch->getNumKids() ; i++) {
			ssgEntity *this_kid = branch->getKid( i );
			if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
				if( filterLeaf( (ssgLeaf *) this_kid ) )
					new_part->addLeaf( tri_idx, ind_idx, (ssgLeaf *) this_kid );
			}
		}
		// only do that for aircraft
		if( occluder_type != SGShadowVolume::occluderTypeAircraft )
			new_part->isTranslucent = false;
		new_part->SetConnectivity();
		parts.push_back( new_part );
	}
}

void SGShadowVolume::SceneryObject::find_trans(void) {
	ssgBranch *branch = pending_object;
	// check the existence of the root node
	while( branch && branch->getNumParents() > 0 ) {
		branch = branch->getParent(0);
	}
	// check if we are connected to the scene graph
	if( !branch->isA(ssgTypeRoot() ) )
		return;
	scenery_object = pending_object;
}

SGShadowVolume::SceneryObject::SceneryObject(ssgBranch *_scenery_object, OccluderType _occluder_type) :
        scenery_object ( 0 ),
        pending_object ( _scenery_object ),
        occluder_type ( _occluder_type )
{
	// queue objects, don't do all the work in the first frames because of
	// massive cpu power needed
	statObj++;
	if( occluder_type == SGShadowVolume::occluderTypeAircraft )
		lib_object = _scenery_object;
	else
		lib_object = (ssgBranch *) ((ssgBranch *)_scenery_object->getKid(0))->getKid(0);
}

SGShadowVolume::SceneryObject::~SceneryObject()
{
	ShadowCaster_list::iterator iParts;
	for(iParts = parts.begin() ; iParts != parts.end(); iParts++ ) {
		delete *iParts;
	}
	parts.clear();
}

void SGShadowVolume::computeShadows(void) {

	// intensity = ambient + lights
	// lights = sun_const * (sun_angle . normal)
	double dot_light = cos(sun_angle);
	// do nothing if sun is under horizon
	if( dot_light < 0.2 )
		return;

	//Draw shadow volumes
	glPushAttrib(GL_ALL_ATTRIB_BITS);
 	glPushClientAttrib ( GL_CLIENT_VERTEX_ARRAY_BIT ) ;
	glDisableClientState ( GL_COLOR_ARRAY         ) ;
	glDisableClientState ( GL_NORMAL_ARRAY        ) ;
	glDisableClientState ( GL_TEXTURE_COORD_ARRAY ) ;

	if( use_alpha ) {
		glColorMask(0, 0, 0, 1);
 		glClearColor(0.0, 0.0, 0.0, 0.0 );
		glClear(GL_COLOR_BUFFER_BIT);
 		glDisable(GL_ALPHA);
		glEnable(GL_BLEND);
	} else {
		glClearStencil( 0 );
		glClear(GL_STENCIL_BUFFER_BIT);
		glColorMask(0, 0, 0, 0);
		glEnable(GL_STENCIL_TEST);
		glDisable(GL_ALPHA);
		glDisable(GL_BLEND);
	}
	glDisable( GL_LIGHTING );
	glDisable( GL_FOG );
  	glEnable( GL_CULL_FACE  );
//	glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glPolygonOffset(0.0,2.0);
//    glPolygonOffset(0.0,30.0);
    glEnable(GL_POLYGON_OFFSET_FILL);

 	glShadeModel(GL_FLAT);

	glDepthMask( false );
	glEnable( GL_DEPTH_TEST );
	glDepthFunc(GL_LESS);

	{
		float w, h;
		sgFrustum frustum;
		sgEnviro.getFOV( w, h );
		frustum.setFOV( w, h );
		frustum.setNearFar(0.1f, 5000.0f);
		sgMat4 m;
		ssgGetModelviewMatrix( m );
		cull( ssg_root, &frustum, m, true);
	}


	glMatrixMode   ( GL_PROJECTION ) ;
	glPushMatrix   () ;
	glLoadIdentity () ;
	glOrtho        ( -100, 100, -100, 100, -1, 1 ) ;
	glMatrixMode   ( GL_MODELVIEW ) ;
	glPushMatrix   () ;
	glLoadIdentity () ;

	glDisable(GL_DEPTH_TEST);
	glDisable(GL_CULL_FACE);
//	glBindTexture(GL_TEXTURE_2D, 0);
	glPolygonMode(GL_FRONT, GL_FILL);
	if( use_alpha ) {
		// there is a flaw in the Roettger paper, this does not work for some geometry
		// where we increment (multiply) the buffer a few times then we
		// decrement (divide) a few times. Decrementing more then once will give a
		// non shadowed parts with mask value < 0.25 because the incrementation was
		// clamped
		// Solution : don't use a start value as high as 0.25 but the smallest value
		// posible ie 1/256. This is not a general solution, a stencil buffer will
		// support 255 incrementation before clamping, the alpha mask only 7.
		// => that still does not work with our geometry so use subtractive blend

		// clamp mask = {0,16,32,64,...} => {0,16,16,16,...}
		glBlendEquationPtr( GL_MIN_EXT );
   		glBlendFunc( GL_DST_COLOR, GL_ONE );
 		glColor4ub(1, 1, 1, 16);
 		glRectf(-100,-100,100,100);
		// scale mask = {0,16} => {0,64}
		glBlendEquationPtr( GL_FUNC_ADD );
   		glBlendFunc( GL_DST_COLOR, GL_ONE );
 		glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 		glRectf(-100,-100,100,100);
		glRectf(-100,-100,100,100);
		// negate mask => {0,64} => {255, 191}
		glBlendFunc( GL_ONE_MINUS_DST_COLOR, GL_ZERO );
		glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 		glRectf(-100,-100,100,100);
		// apply mask
		glColorMask(1, 1, 1, 1);
   		glBlendFunc( GL_ZERO, GL_DST_ALPHA );
   		glColor4f(1.0f, 0.5f, 0.2f, 1.0f);
		glRectf(-100,-100,100,100);
	} else {
		// now the stencil contains 0 for scenery in light and != 0 for parts in shadow
		// draw a quad covering the screen, the stencil will be the mask
		// we darken the shadowed parts
		glColorMask(1, 1, 1, 1);
		glStencilFunc(GL_NOTEQUAL, 0, ~0);
		glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
		glEnable(GL_STENCIL_TEST);
		glEnable(GL_ALPHA);
		glAlphaFunc(GL_GREATER, 0.0f);
		glEnable(GL_BLEND);
		glBlendFunc ( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA ) ;
  		glColor4f(0.0, 0.0, 0.0, sgLerp(0.1, 0.3, dot_light) );
		// fixed value is better, the previous line is surely wrong
  		glColor4f(0.0, 0.0, 0.0, 0.3 );
		glRectf(-100,-100,100,100);
	}
	glMatrixMode   ( GL_PROJECTION ) ;
	glPopMatrix    () ;
	glMatrixMode   ( GL_MODELVIEW ) ;
	glPopMatrix    () ;

	glDisable(GL_STENCIL_TEST);
	glPopClientAttrib ( ) ;
	glPopAttrib();
}

SGShadowVolume::SGShadowVolume( ssgBranch *root ) : 
	shadows_enabled( false ),
	frameNumber( 0 ),
	lastTraverseTreeFrame ( 0 ),
	ssg_root( root ),
	shadows_rendered( false )
{
	states = this;
}

SGShadowVolume::~SGShadowVolume() {
	SceneryObject_map::iterator iSceneryObject;
	for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
		delete iSceneryObject->second;
	}
	sceneryObjects.clear();
}

void SGShadowVolume::init(SGPropertyNode *sim_rendering_options) {
	shadows_enabled = true;
	sim_rendering = sim_rendering_options;
	GLint stencilBits = 0, alphaBits = 0;
	glGetIntegerv( GL_STENCIL_BITS, &stencilBits );
	glGetIntegerv( GL_ALPHA_BITS, &alphaBits );
	bool hasSubtractiveBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_subtract");
	bool hasMinMaxBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_minmax");
	if( hasSubtractiveBlend )
		glBlendEquationPtr = (glBlendEquationProc ) SGLookupFunction("glBlendEquationEXT");
	canDoAlpha = (alphaBits >= 8) && hasSubtractiveBlend && hasMinMaxBlend;
	canDoStencil = (stencilBits >= 3);
	if( !canDoStencil )
		if( canDoAlpha )
			SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer, using alpha buffer");
		else
			SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer and no alpha buffer");
}

void SGShadowVolume::startOfFrame(void) {
}
void SGShadowVolume::deleteOccluderFromTile(ssgBranch *tile) {
	SceneryObject_map::iterator iSceneryObject;
	for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); ) {
		SceneryObject_map::iterator iCurrent = iSceneryObject ++;
		if( iCurrent->second->tile == tile ) {
			delete iCurrent->second;
			sceneryObjects.erase( iCurrent );
		}
	}
}

void SGShadowVolume::deleteOccluder(ssgBranch *occluder) {
	// skip first node and go to first transform (placement)
	while( occluder && !occluder->isA(ssgTypeTransform()))
		occluder = (ssgBranch *) occluder->getKid(0);

	// check if we allready know this object
	SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
	if( iSceneryObject != sceneryObjects.end() ) {
		delete iSceneryObject->second;
		sceneryObjects.erase( occluder );
	}
}

void SGShadowVolume::addOccluder(ssgBranch *occluder, OccluderType occluder_type, ssgBranch *tile) {
	// skip first node and go to first transform (placement)
	while( occluder && !occluder->isA(ssgTypeTransform()))
		occluder = (ssgBranch *) occluder->getKid(0);

	// check if we allready know this object
	SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
	if( iSceneryObject == sceneryObjects.end() ) {
//		printf("adding model %x %x\n", occluder, tile);
		SceneryObject *entry = new SceneryObject( occluder, occluder_type );
		entry->tile = tile;
		sceneryObjects[ occluder ] = entry;
	}

}

void SGShadowVolume::setupShadows( double lon, double lat,
		double gst, double SunRightAscension, double SunDeclination, double sunAngle) {

	shadowsAC_enabled = sim_rendering->getBoolValue("shadows-ac", false);
	shadowsAC_transp_enabled = sim_rendering->getBoolValue("shadows-ac-transp", false);
	shadowsAI_enabled = sim_rendering->getBoolValue("shadows-ai", false);
	shadowsTO_enabled = sim_rendering->getBoolValue("shadows-to", false);
	shadowsDebug_enabled = sim_rendering->getBoolValue("shadows-debug", false);
	shadows_enabled = shadowsAC_enabled || shadowsAI_enabled || shadowsTO_enabled;
	shadows_enabled &= canDoAlpha || canDoStencil;
	use_alpha = ((!canDoStencil) || sim_rendering->getBoolValue("shadows-alpha", false)) &&
		canDoAlpha;

	if( ! shadows_enabled )
		return;

	shadows_rendered = false;
	sun_angle = sunAngle;
	{
	sgMat4 GST, RA, DEC;
	sgVec3 axis;


	sgSetVec3( axis, 0.0, 0.0, -1.0 );
	sgMakeRotMat4( GST, (gst) * 15.0, axis );

	sgSetVec3( axis, 0.0, 0.0, 1.0 );
	sgMakeRotMat4( RA, (SunRightAscension * SGD_RADIANS_TO_DEGREES) - 90.0, axis );

	sgSetVec3( axis, 1.0, 0.0, 0.0 );
	sgMakeRotMat4( DEC, SunDeclination * SGD_RADIANS_TO_DEGREES, axis );

	sgMat4 TRANSFORM;
	sgMakeIdentMat4( TRANSFORM );
	sgPreMultMat4( TRANSFORM, GST );
	sgPreMultMat4( TRANSFORM, RA );
	sgPreMultMat4( TRANSFORM, DEC );
   	sgSetVec3( sunPos, 0.0, 9900000.0, 0.0);
	sgXformPnt3( sunPos, TRANSFORM );
	}

	ssgGetModelviewMatrix( CameraViewM );

}

void SGShadowVolume::endOfFrame(void) {
	if( ! shadows_enabled )
		return;
	if( shadows_rendered )
		return;
	glBindTexture(GL_TEXTURE_2D, 0);
	glBindTexture(GL_TEXTURE_1D, 0);

	glMatrixMode(GL_MODELVIEW);
	computeShadows();
	frameNumber ++;
	shadows_rendered = true;
}

int SGShadowVolume::ACpostTravCB( ssgEntity *entity, int traversal_mask ) {
	if( states->shadowsAC_transp_enabled && (SSGTRAV_CULL & traversal_mask) )
		states->endOfFrame();
	return 0;
}

