#include "view.h"

#define ATSV(i)			(*(shadowVolume + i))
#define ATSVn(i)		(ATSV(i)->n)
#define ATSVplane(i)	(ATSV(i)->plane)
#define ATSVface(i)		(ATSV(i)->face)

#define MAXSHADOW 	10
#define NOSHADOW 	((ShadowVolume *)0)

typedef struct{
	Face *face; /*face which gave rise to this shadow volume*/
	int n;
	PlaneEq plane[MAXSHADOW];
} ShadowVolume, *ShadowVolumePtr;

static int *order;
static int orderno;
ShadowVolumePtr *shadowVolume;

Tree *makeRoot(faceIndex)
int faceIndex;
{
	Tree *t;
	
	t = Malloc(Tree,1);
	t->faceSet = newIndex(faceIndex);
	FRONTNODEOfTree(t) = EMPTYTREE;
	BACKNODEOfTree(t) = EMPTYTREE;
	
	return(t);
}

Tree *combineTree(frontNode,root,backNode)
Tree *frontNode;
Index *root;
Tree *backNode;
{
	Tree *newtree;
	
	newtree = Malloc(Tree,1);
	newtree->faceSet = root;
	newtree->frontNode = frontNode;
	newtree->backNode = backNode;
	
	return(newtree);
}


Tree *makeTree(facelist,faceset)
FaceList *facelist;
Index *faceset;
{
	int root;
	Index *backlist,*frontlist,*lastback,*lastfront, *ind;
	PlaneEq *plane;
	Classification c;
	Face *poly;
	FacePtr frontP,backP;
	int n;
	Index *rootSet,*lastRoot;
	
	if(faceset == NOINDEX) return(EMPTYTREE);
	
	root = INDEX(faceset);
	rootSet = newIndex(root);
	lastRoot = rootSet;
	
	plane = PLANEQOfFace(atFaceList(facelist,root));
	
	backlist = frontlist = lastback = lastfront = NOINDEX;
	
	ind = faceset;
	while(ind != NOINDEX){
		if(!memberOfIndex(rootSet,INDEX(ind))){
			poly = atFaceList(facelist,INDEX(ind));
			c = classifyFace(poly,plane,&frontP,&backP);
			if(c == FRONT)
				appendToIndex(&frontlist,INDEX(ind),&lastfront);
			else 
			if(c == BACK)
				appendToIndex(&backlist,INDEX(ind),&lastback);
			else
			if(c == FRONT_BACK || c == BACK_FRONT){
				n = NEXTFreeFaceList(facelist);
				atPutFaceList(facelist,n,frontP);
				appendToIndex(&frontlist,n,&lastfront);
				
				n = NEXTFreeFaceList(facelist);
				atPutFaceList(facelist,n,backP);
				appendToIndex(&backlist,n,&lastback);
			}
			else /*ON*/
				appendToIndex(&rootSet,INDEX(ind),&lastRoot);
		}
		ind = NEXT(ind);
	}
	return(
			combineTree(
						makeTree(facelist,frontlist),
						rootSet,
						makeTree(facelist,backlist)
				       )
		  );
}
				

void traverseTree(t,f)
Tree *t;
void (*f)();
{
	if(t == EMPTYTREE) return;
	
	(*f)(FACESETOfTree(t));
	
	traverseTree(FRONTNODEOfTree(t),f);
	traverseTree(BACKNODEOfTree(t),f);
}	

void printTree(t)
Tree *t;
{
	printf("(");
	if(t != EMPTYTREE){
		printTree(FRONTNODEOfTree(t));
		printList(FACESETOfTree(t));
		printTree(BACKNODEOfTree(t));
	}
	printf(")");
}


int findPlaneEquations(face,light,plane)
Face *face;
Light *light;
PlaneEq plane[];
{
	Index *ind1,*ind2;
	Point3D *p1,*p2,*p,q[3];
	int n;
	
	ind1 = face->first;
	ind2 = NEXT(ind1);
	n = 0;
	p = p1 = atVertex(face->vertex,ind1->i);
	while(ind2 != face->first){
		p2 = atVertex(face->vertex,ind2->i);
		
		q[0] = *p1;
		q[1] = POSITIONOfLight(light);
		q[2] = *p2;
		normalPoint3D(q,&plane[n]);
		plane[n++].d = detFor3Point3D(q);
		
		p1 = p2;
		ind2 = NEXT(ind2);
	}
	q[0] = *p1;
	q[1] = POSITIONOfLight(light);
	q[2] = *p;
	normalPoint3D(q,&plane[n]);
	plane[n++].d = detFor3Point3D(q);
	return(n);
}

static ShadowVolume *newShadowVolume(face,light)
Face *face;
Light *light;
{
	ShadowVolume *sv;
	
	sv = Malloc(ShadowVolume,1);
	sv->face = face;
	sv->n = findPlaneEquations(face,light,sv->plane);
	return(sv);
}
	

static void filterFaceOnShadowVolume(poly,i,facelist,light,lightNo,totallyShadowed)
Face *poly;
int i;
FaceList *facelist;
Light *light;
int lightNo;
BOOLEAN *totallyShadowed;
{
	register int n,j;
	register Face *face;
	Classification c;
	BOOLEAN inscribed;
	
	*totallyShadowed = FALSE;
	/*for each shadow volume defined so far*/
	for(j=orderno-1; j>i; --j){
		if(ATSV(j) != NOSHADOW){
			face = ATSVface(j);
			n = ATSVn(j);
			if(!commonVertexWithFace(face,poly)){ 
				/*ignore if it has a common vertex*/
				c = classificationOfFace(poly,PLANEQOfFace(face));
				if((c!=FRONT) && (c!=ON)){ 
					/*only deal with polygons behind the current one*/
					setShadowsFromFace(face,poly,facelist,
										n,ATSVplane(j),
										light,lightNo,
										&inscribed,totallyShadowed);
					if(inscribed) ATSV(j) = NOSHADOW; /*this SV is used up*/
					if(*totallyShadowed) return;
				}
			}
		}
	}
}
		

static void setShadows(facelist,light,lightNo)
FaceList *facelist;
Light *light;
int lightNo;
{
	register int n,i,j;
	register Face *face,*poly,*shadowOnFace;
	Classification c;
	BOOLEAN inscribed,totallyShadowed;
	Index *ind;

	/*make the shadow plane for the nearest face*/
	ATSV(orderno-1) = newShadowVolume(atFaceList(facelist,*(order+orderno-1)),light);
	
	/*for each face after the front-most*/
	for(i=orderno-2; i>=0; --i){
		poly = atFaceList(facelist,*(order+i));
		
		totallyShadowed = FALSE;
		filterFaceOnShadowVolume(poly,i,facelist,light,lightNo,&totallyShadowed);
		
		/*now create new SV for current poly*/
		if(!totallyShadowed) /*if this poly not entirely in shadow*/
			ATSV(i) = newShadowVolume(poly,light);
		else ATSV(i) = NOSHADOW;
	}
}
		

void fromLightWalkTree(tree,facelist,light)
Tree *tree;
FaceList *facelist;
Light *light;
{
	PlaneEq *plane;
	Face *face;
	Classification c;
	REAL d;
	Index *ind;
	
	if(tree == EMPTYTREE) return;
	
	face = atFaceList(facelist,INDEX(FACESETOfTree(tree)));
	plane = PLANEQOfFace(face);
	c = classifyPoint3D(plane,&light->position,&d);
	/*
	CLASSIFYPoint3D(plane,light->position,d,c);
	*/
	if(c == FRONT || c == ON){
		fromLightWalkTree(BACKNODEOfTree(tree),facelist,light);
		ind = FACESETOfTree(tree);
		while(ind != NOINDEX){
			/*check again that the light is in front of this face --
			  this face might be in a list on the same plane as other faces
			  some of which are in front and some behind the light
			*/
			face=atFaceList(facelist,INDEX(ind));
			
			c = classifyPoint3D(PLANEQOfFace(face),&light->position,&d);
			/*
			CLASSIFYPoint3D(PLANEQOfFace(face),light->position,d,c);
			*/
			if(c== FRONT){
				*(order + (orderno++)) = INDEX(ind);
			}
			ind = NEXT(ind);
		}
		fromLightWalkTree(FRONTNODEOfTree(tree),facelist,light);
	}
	else{
		fromLightWalkTree(FRONTNODEOfTree(tree),facelist,light);
		fromLightWalkTree(BACKNODEOfTree(tree),facelist,light);
	}
}
	

void setShadowsOnTree(tree,facelist,lighting)
Tree *tree;
FaceList *facelist;
Lighting *lighting;
{
	register int i;
	
	/*construct an array to hold the index of the faces in order of appearance.
  	  the face at position 0 is therefore the first one encountered
	*/
	order = Malloc(int,NEXTFreeFaceList(facelist));
	
	/*this array is to hold the shadow volumes of the corresponding faces*/
	shadowVolume = Malloc(ShadowVolumePtr,NEXTFreeFaceList(facelist));
	
	
	/*for each light*/
	for(i=0; i<NOOfLightsIn(lighting); ++i){
		orderno = 0;
		fromLightWalkTree(tree,facelist,&LIGHTOf(lighting,i));
		/*now the faces are in back to front list*/
		setShadows(facelist,&LIGHTOf(lighting,i),i);
	}
}
	
		