#include "view.h"

Vertex *liteVertex;

Tree *makeRoot(faceIndex)
int faceIndex;
{
	Tree *t;

	t = Malloc(Tree,1);
	t->faceSet = t->lastFace = 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 addFaceToTree();

static void addFrontFace(tree,facelist,faceIndex)
Tree *tree;
FaceList *facelist;
int faceIndex;
{
	if(tree->frontNode == EMPTYTREE) tree->frontNode = makeRoot(faceIndex);
	else addFaceToTree(tree->frontNode,facelist,faceIndex);
}

static void addBackFace(tree,facelist,faceIndex)
Tree *tree;
FaceList *facelist;
int faceIndex;
{
	if(tree->backNode == EMPTYTREE) tree->backNode = makeRoot(faceIndex);
	else addFaceToTree(tree->backNode,facelist,faceIndex);
}



void addFaceToTree(tree,facelist,faceIndex)
/*filters the new face down the tree*/
Tree *tree;
FaceList *facelist;
int faceIndex;
{
	Face *poly;
	Index *faceSet;
	Tree *frontNode,*backNode;
	PlaneEq *plane;
	Classification c;
	FacePtr frontP,backP;
	int n;

	faceSet = tree->faceSet;
	frontNode = tree->frontNode;
	backNode = tree->backNode;

	plane = PLANEQOfFace(atFaceList(facelist,INDEX(faceSet)));

	c = classifyFace((poly=atFaceList(facelist,faceIndex)),plane,&frontP,&backP);

	if(c==FRONT) addFrontFace(tree,facelist,faceIndex);
	else
	if(c==BACK) addBackFace(tree,facelist,faceIndex);
	else
	if(c == FRONT_BACK || c == BACK_FRONT){
		n = NEXTFreeFaceList(facelist);
		atPutFaceList(facelist,n,frontP);
		addFrontFace(tree,facelist,n);

		n = NEXTFreeFaceList(facelist);
		atPutFaceList(facelist,n,backP);
		addBackFace(tree,facelist,n);
	}
	else /*on*/{
		appendToIndex(&tree->faceSet,faceIndex,&tree->lastFace);
		return;
	}
}

Tree *incrementalMakeTree(facelist,index)
FaceList *facelist;
Index *index;
{
	Tree *tree;
	Index *ind;

	ind = index;
	tree = makeRoot(INDEX(ind));
	ind = NEXT(ind);
	while(ind != NOINDEX){
		addFaceToTree(tree,facelist,INDEX(ind));
		ind = NEXT(ind);
	}
	return(tree);
}


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(")");
}


static int *order;
static int orderno;

void addLiteFaceToTree();

static void addLiteFrontFace(tree,liteFaceList,faceIndex)
Tree *tree;
LiteFaceList *liteFaceList;
int faceIndex;
{
	if(tree->frontNode == EMPTYTREE) tree->frontNode = makeRoot(faceIndex);
	else addLiteFaceToTree(tree->frontNode,liteFaceList,faceIndex);
}

static void addLiteBackFace(tree,liteFaceList,faceIndex)
Tree *tree;
LiteFaceList *liteFaceList;
int faceIndex;
{
	if(tree->backNode == EMPTYTREE) tree->backNode = makeRoot(faceIndex);
	else addLiteFaceToTree(tree->backNode,liteFaceList,faceIndex);
}

void addLiteFaceToTree(tree,liteFaceList,faceIndex)
/*filters the new face down the tree*/
Tree *tree;
LiteFaceList *liteFaceList;
int faceIndex;
{
	LiteFace *poly;
	Index *faceSet;
	Tree *frontNode,*backNode;
	PlaneEq *plane;
	Classification c;
	LiteFacePtr frontP,backP;
	int n;

	faceSet = tree->faceSet;
	frontNode = tree->frontNode;
	backNode = tree->backNode;

	plane = PLANEQOfFace(atLiteFaceList(liteFaceList,INDEX(faceSet)));

	c = classifyLiteFace((poly=atLiteFaceList(liteFaceList,faceIndex)),plane,&frontP,&backP);

	if(c==FRONT) addLiteFrontFace(tree,liteFaceList,faceIndex);
	else
	if(c==BACK) addLiteBackFace(tree,liteFaceList,faceIndex);
	else
	if(c == FRONT_BACK || c == BACK_FRONT){
		n = NEXTFreeFaceList(liteFaceList);
		atPutLiteFaceList(liteFaceList,n,frontP);
		addLiteFrontFace(tree,liteFaceList,n);

		n = NEXTFreeFaceList(liteFaceList);
		atPutLiteFaceList(liteFaceList,n,backP);
		addLiteBackFace(tree,liteFaceList,n);
	}
	else /*on*/{
		appendToIndex(&tree->faceSet,faceIndex,&tree->lastFace);
		return;
	}
}

void addShadowPlanesToTree(tree,face,liteFaceList,light)
Tree **tree;
Face *face;
LiteFaceList *liteFaceList;
Light *light;
{
	register Index *ind,*ind1,*ind2;
	Point3D *p1,*p2,*p,q[3];
	register int n;
	PlaneEq *plane;
	LiteFace *shadowPlane;


	ind = ind1 = face->first;
	ind2 = NEXT(ind1);
	n = 0;
	p = p1 = atVertex(face->vertex,ind1->i);

	while(ind2 != face->first){
		/*make new shadow plane - the light source pos is always between these two*/
		shadowPlane = newLiteFace(face->vertex,ind1->i);
		addToBackLiteFace(shadowPlane,ind2->i);

		/*add this face to the facelist*/
		atPutLiteFaceList(liteFaceList,(n=NEXTFreeFaceList(liteFaceList)),shadowPlane);

		/*find the plane equation*/
		p2 = atVertex(face->vertex,ind2->i);
		q[0] = *p1;
		q[1] = POSITIONOfLight(light);
		q[2] = *p2;
		plane = Malloc(PlaneEq,1);
		normalPoint3D(q,plane);
		plane->d = detFor3Point3D(q);

		/*set the plane equation*/
		shadowPlane->coeff = plane;
		if(*tree == EMPTYTREE)
			*tree = makeRoot(n);
		else
			addLiteFaceToTree(*tree,liteFaceList,n);

		/*onto next edge*/
		p1 = p2;
		ind1 = ind2;
		ind2 = NEXT(ind2);
	}
	/*last edge*/
	shadowPlane = newLiteFace(face->vertex,ind1->i);
	addToBackLiteFace(shadowPlane,ind->i);
	atPutLiteFaceList(liteFaceList,(n=NEXTFreeFaceList(liteFaceList)),shadowPlane);

	q[0] = *p1;
	q[1] = POSITIONOfLight(light);
	q[2] = *p;
	plane = Malloc(PlaneEq,1);
	normalPoint3D(q,plane);
	plane->d = detFor3Point3D(q);
	shadowPlane->coeff = plane;
	addLiteFaceToTree(*tree,liteFaceList,n);
}


#define DELETE

#ifdef DELETE
void filterFaceOnSVBSPTree();

void onFrontFace(tree,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow)
Tree *tree;
Face *targetFace,*face;
FaceList *facelist;
LiteFaceList *liteFaceList;
Light *light;
int lightNo;
BOOLEAN fromShadow;
{
	Face *shadowFace;

	if(tree->frontNode == EMPTYTREE) {
		if(face == targetFace) /*this entire original target face is in shadow*/
			samePolygon(face,&shadowFace);
		else shadowFace = face;
		/*the point being that targetFace and shadowFace should not be the same*/
		setShadowOnFace(targetFace,shadowFace,facelist,light,lightNo);
	}
	else
	filterFaceOnSVBSPTree(tree->frontNode,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow);
}

void onBackFace(tree,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow)
Tree *tree;
Face *targetFace,*face;
FaceList *facelist;
LiteFaceList *liteFaceList;
Light *light;
int lightNo;
BOOLEAN fromShadow;
{
	if(tree->backNode == EMPTYTREE){
		/*this face is visible to the light*/
		if(!fromShadow) addShadowPlanesToTree(&tree,face,liteFaceList,light);
	}
	else
	filterFaceOnSVBSPTree(tree->backNode,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow);
}


void filterFaceOnSVBSPTree(tree,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow)
/*filters the new face down the tree - shadows will be added to this face*/
Tree *tree;
Face *targetFace,*face;
FaceList *facelist;
LiteFaceList *liteFaceList;
Light *light;
int lightNo;
BOOLEAN fromShadow;
{
	Index *faceSet;
	Tree *frontNode,*backNode;
	PlaneEq *plane;
	Classification c;
	FacePtr frontP,backP;
	int n;
	int i;
	Index *ind;
	Vertex *v;

	faceSet = tree->faceSet;
	frontNode = tree->frontNode;
	backNode = tree->backNode;

	plane = PLANEQOfFace(atLiteFaceList(liteFaceList,INDEX(faceSet)));

	c = classifyFace(face,plane,&frontP,&backP);

	if(c==FRONT) onFrontFace(tree,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow);
	else
	if(c==BACK) onBackFace(tree,targetFace,face,facelist,liteFaceList,light,lightNo,fromShadow);
	else
	if(c == FRONT_BACK || c == BACK_FRONT){
		onFrontFace(tree,targetFace,frontP,facelist,liteFaceList,light,lightNo,fromShadow);
		onBackFace(tree,targetFace,backP,facelist,liteFaceList,light,lightNo,fromShadow);
	}
	else /*on*/{
		/*ignore this one*/
		/*
		printf("reached on!!!!!!!\n");
		*/
		return;
	}
}

#endif

void makeSVBSPTree(facelist,liteFaceList,light,lightNo)
FaceList *facelist;
LiteFaceList *liteFaceList;
Light *light;
int lightNo;
{
	register int i;
	Tree *svTree;
	register Face *face;
	Face *targetFace,*shadowOnFace;
	Index *ind;

	/*make an SVBSP tree from the front-most face shadow planes*/
	svTree = EMPTYTREE;
	face = atFaceList(facelist,*(order + orderno - 1));
	addShadowPlanesToTree(&svTree,face,liteFaceList,light);

	/*now process the remaining faces*/
	for(i=orderno-2; i>=0; --i){
		face = atFaceList(facelist,*(order+i));

		/*first deal with any shadows on this face*/
		if(face->noOfShadows > 0){
			ind = face->shadow;
			while(ind != NOINDEX){
				shadowOnFace = atFaceList(facelist,INDEX(ind));
				if(!memberOfIndex(shadowOnFace->lightsAway,lightNo)){
					targetFace = shadowOnFace;
					/*use filterPFaceOnSVBSPTree for polygon version*/
					filterPFaceOnSVBSPTree(svTree,
											targetFace,shadowOnFace,
											facelist,liteFaceList,
											light,lightNo,
											TRUE);  /*from a shadow*/
				}
				ind = NEXT(ind);
			}
		}
		/*now deal with the face itself*/
		targetFace = face;
		/*use filterPFaceOnSVBSPTree for polygon version*/
		filterPFaceOnSVBSPTree(svTree,
								targetFace,face,
								facelist,liteFaceList,
								light,lightNo,
								FALSE);
	}
}


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){
				/*if(orderno > 0) setShadows(face,facelist,light);*/
				*(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;
	LiteFaceList *liteFaceList;

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

	/*make a new face list just to hold the shadow planes*/
	liteFaceList = newLiteFaceList(8000);

	/*make a new vertex list just to hold the shadow plane vertices*/
	liteVertex = newVertex(12000);

	/*for each light*/
	for(i=0; i<NOOfLightsIn(lighting); ++i){
		orderno = 0;
		reinitialiseLiteFaceList(liteFaceList);
		reinitialiseVertex(liteVertex);
		fromLightWalkTree(tree,facelist,&LIGHTOf(lighting,i));
		/*so now the array order[orderno-1] ... order[0] holds the faces in
		  front-to-back order*/

		/*make a SVBSP tree*/
		makeSVBSPTree(facelist,liteFaceList,&LIGHTOf(lighting,i),i);
	}
}


