#include "Plane3.h"
#include "ViewCellBsp.h"
#include "Mesh.h"

#include "ViewCell.h"
#include <stack>

#define DEL_PTR(ptr) while (0) {if (ptr) {delete (ptr); (ptr) = NULL;}}

//namespace GtpVisibilityPreprocessor {
/****************************************************************/
/*                  class BspNode implementation                */
/****************************************************************/
bool BspNode::IsRoot() const 
{
	return mParent == NULL;
}

BspInterior *BspNode::GetParent() 
{ 
	return mParent; 
}
/****************************************************************/
/*              class BspInterior implementation                */
/****************************************************************/


BspInterior::BspInterior(Plane3 plane): mPlane(plane) 
{}

bool BspInterior::IsLeaf() const
{ 
	return false; 
}

BspNode *BspInterior::GetBack() 
{
	return mBack;
}

BspNode *BspInterior::GetFront() 
{
	return mFront;
}

Plane3 *BspInterior::GetPlane()
{
	return &mPlane;
}

void BspInterior::ReplaceChildLink(BspNode *oldChild, BspNode *newChild) 
{
	if (mBack == oldChild)
	{
		mBack = newChild;
	}
    else
	{
		mFront = newChild;
	}
}

void BspInterior::SetupChildLinks(BspNode *b, BspNode *f) 
{
    mBack = b;
    mFront = f;
}

/****************************************************************/
/*                  class BspLeaf implementation                */
/****************************************************************/

BspLeaf::BspLeaf(ViewCell *viewCell): mViewCell(viewCell) 
{
}

ViewCell *BspLeaf::GetViewCell()
{
	return mViewCell;
}

bool BspLeaf::IsLeaf() const 
{ 
	return true; 
}

/****************************************************************/
/*                  class Polygon implementation                */
/****************************************************************/

Polygon::Polygon()
{}

Polygon::Polygon(const VertexContainer &vertices): mVertices(vertices) 
{}

Polygon::Polygon(Face *face, Mesh *parent)
{
	VertexIndexContainer::const_iterator it;

	for (it = face->mVertexIndices.begin(); it != face->mVertexIndices.end(); ++ it)
	{
		mVertices.push_back(parent->mVertices[*it]);
	}
}

Plane3 Polygon::GetSupportingPlane()
{
	return Plane3(mVertices[0], mVertices[1], mVertices[2]);
}

void Polygon::DeletePolygons(PolygonQueue *polys)
{
	// don't need to store polygon information = delete polygons
	while(!polys->empty())
	{
		Polygon *poly = polys->front();
		polys->pop();
		DEL_PTR(poly);
	}

}

void Polygon::Split(Plane3 *partition, Polygon *front, Polygon *back)
{
	Vector3 ptA = mVertices[mVertices.size() - 1];;
	
	int sideA = partition->Side(ptA);
	
	VertexContainer::const_iterator it;

	// find line - plane intersections
	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
	{
		Vector3 ptB = (*it);
		int sideB = partition->Side(ptB);

		// vertices on different sides => split
		if ((sideA != 0) && (sideB != 0) && (sideA != sideB)) 
		{
			Vector3 v = ptB - ptA; // line from A to B
			float dv = DotProd(partition->mNormal, v);
			float t = 0;
			
			if (dv)
			{
				t = - partition->Distance(ptA) / dv;
			}
		}
		if (sideB >= 0)
		{
			back->mVertices.push_back(ptB);
		}
		else if (sideB <= 0)
		{
			front->mVertices.push_back(ptB);
		}

		ptA = ptB;
		sideA = sideB;
	}
}

int Polygon::Side(Plane3 *plane)
{
	VertexContainer::const_iterator it;

	bool onFrontSide = false;
	bool onBackSide = false;

	// find line - plane intersections
	for (it = mVertices.begin(); it != mVertices.end(); ++ it)
	{
		int side = plane->Side(*it);
		
		if (side > 0)
		{
			onFrontSide = true;
		}
		else if (side < 0)
		{
			onBackSide = true;
		}

		if (onFrontSide && onBackSide) // splits
			return SPLIT;
	}

	if (onBackSide)
	{
		return BACK_SIDE;
	}
	else if (onFrontSide)
	{
		return FRONT_SIDE;
	}

	return COINCIDENT;
}

/****************************************************************/
/*                  class BspTree implementation                */
/****************************************************************/

BspTree::BspTree(const ViewCellContainer &viewCells): 
mMaxPolys(0), mMaxDepth(0), mRoot(NULL)
{
	//mRootCell = cell;
	Subdivide(viewCells);
}

BspTree::BspTree(const ObjectContainer &objects, int maxPolys, int maxDepth):
mMaxPolys(maxPolys), mMaxDepth(maxDepth)
{
	mRoot = new BspLeaf();

	Subdivide(objects);
}
 
BspTree::~BspTree()
{
	std::stack<BspNode *> tStack;

	tStack.push(mRoot);

	while (!tStack.empty())
	{
		BspNode *node = tStack.top();

	    tStack.pop();
	
		if (!node->IsLeaf())
		{
			BspInterior *interior = dynamic_cast<BspInterior *>(node);

			// push the children on the stack (there are always two children)
			interior->GetBack()->mParent = NULL;
			interior->GetFront()->mParent = NULL;

			tStack.push(interior->GetBack());
			tStack.push(interior->GetFront());
		}

		DEL_PTR(node);
	}
}


void BspTree::InsertViewCell(ViewCell *viewCell)
{
	std::stack<BspTraversalData> tStack;
	
	PolygonQueue polys;
	// copy polygon information to guide the split process
	CopyMesh2Polygon(viewCell->GetMesh(), polys);

	tStack.push(BspTraversalData(mRoot, NULL, &polys, 0));

	while (!tStack.empty())
	{
		/*BspNode *node = tStack.top();

	    tStack.pop();
	
		if (!node->IsLeaf())
		{
			BspInterior *interior = dynamic_cast<BspInterior *>(node);

			// push the children on the stack (there are always two children)
			interior->GetBack()->mParent = NULL;
			interior->GetFront()->mParent = NULL;

			tStack.push(interior->GetBack());
			tStack.push(interior->GetFront());
		}

		DEL_PTR(node);*/
	}
/*	BspNode *currentNode = mRoot;
  
	std::stack<BspTraversalData> tStack;
	//  stack<STraversalData> tStack;

	//tStack.push(tdata);

	while (!tStack.empty()) 
	{
	    BspTraversalData data = tStack.top();

	    tStack.pop();
    
		Mesh backPolys;
		Mesh frontPolys;

		if (data.mNode->IsLeaf()) // if we have a leaf => subdivide
		{
			BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
										  data.mParent,
										  data.mPolys,
									      data.mDepth,
										  backPolys,
										  frontPolys);
	
			if (!node->IsLeaf()) // node was subdivided
			{
				BspInterior *interior = dynamic_cast<BspInterior *>(node);

				// push the children on the stack (there are always two children)
				//tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
				//tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
			}
		}
	}*/
}

void BspTree::Subdivide(const ViewCellContainer &viewCells)
{
}

void BspTree::CopyMesh2Polygon(Mesh *mesh, PolygonQueue &polys)
{
	FaceContainer::const_iterator fi;
	// copy the face data to polygons
	for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
	{
		Polygon *poly = new Polygon((*fi), mesh);
		polys.push(poly);
	}
}

void BspTree::Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys)
{
	ObjectContainer::const_iterator it, it_end = objects.end();

	for (it = objects.begin(); it != it_end; ++ it)
	{
		Intersectable *object = *it;

		// extract the mesh instances
		if (object->Type() == Intersectable::MESH_INSTANCE)
		{
			MeshInstance *inst = dynamic_cast<MeshInstance *>(object);

			Mesh *mesh = inst->GetMesh();

			// copy the mesh data to polygons
			CopyMesh2Polygon(mesh, polys);
		}
	}
}

void BspTree::Subdivide(const ObjectContainer &objects)
{
	std::stack<BspTraversalData> tStack;
	PolygonQueue polys;
	
	// copy mesh instance polygons into one big polygon soup
	Copy2PolygonSoup(objects, polys);

	BspTraversalData tdata(mRoot, mRoot->GetParent(), &polys, 0);
	tStack.push(tdata);

	while (!tStack.empty()) 
	{
	    BspTraversalData data = tStack.top();

	    tStack.pop();
    
		PolygonQueue *backPolys = new PolygonQueue();
		PolygonQueue *frontPolys = new PolygonQueue();

		BspNode *node = SubdivideNode(dynamic_cast<BspLeaf *>(data.mNode),
									  data.mParent,
									  data.mPolys,
								      data.mDepth,
									  backPolys,
									  frontPolys);
	
		if (!node->IsLeaf()) // node was subdivided
		{
			BspInterior *interior = dynamic_cast<BspInterior *>(node);

			// push the children on the stack (there are always two children)
			tStack.push(BspTraversalData(interior->GetBack(), interior, backPolys, data.mDepth + 1));
			tStack.push(BspTraversalData(interior->GetFront(), interior, frontPolys, data.mDepth + 1));
		}
	}
}

Plane3 BspTree::SelectPlane(PolygonQueue *polyQueue) 
{
	// TODO: more sophisticated criteria
	return polyQueue->front()->GetSupportingPlane();
}

BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
								PolygonQueue *polys, const int depth, 
								PolygonQueue *frontPolys, PolygonQueue *backPolys)
{
	// terminate traversal if no more faces in mesh
	if ((polys->size() <= mMaxPolys) || (depth >= mMaxDepth))
	{
		// don't need to store polygon information = delete polygons
		Polygon::DeletePolygons(polys);
		
		return leaf;
	}

	// add the new nodes to the tree + select subdivision plane
	BspInterior *node = new BspInterior(SelectPlane(polys)); 

 	while (!polys->empty())
	{
		Polygon *poly = polys->front();

		polys->pop();

		int  result = 0;// = node->GetPlane()->Side(node->GetPlane());

		Polygon *front_piece = NULL;
		Polygon *back_piece = NULL;

		switch (result)
		{
			case Polygon::COINCIDENT:
			case Polygon::FRONT_SIDE:
				frontPolys->push(poly);
				break;
			case Polygon::BACK_SIDE:
				backPolys->push(poly);
				break;
			case Polygon::SPLIT:
				front_piece = new Polygon();
				back_piece = new Polygon();

				//-- split polygon
                poly->Split(node->GetPlane(), front_piece, back_piece);


				backPolys->push(back_piece);
				frontPolys->push(front_piece);

				// don't need polygon anymore
				DEL_PTR(poly);
				break;
			default:
				frontPolys->push(poly);
				break;
		}
	}

	// backside of convex view cell polygon => outside
	BspLeaf *back = new BspLeaf();
	BspLeaf *front = new BspLeaf();

	// replace a link from node's parent
	if (parent)
	{
		parent->ReplaceChildLink(leaf, node);
	}

	// and setup child links
	node->SetupChildLinks(back, front);

	DEL_PTR(leaf);

	return node;
}

//} // GtpVisibilityPreprocessor