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

		delete node;
		node = NULL;
	}
}


void BspTree::InsertViewCell(ViewCell *viewCell)
{
	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::Copy2PolygonSoup(const ObjectContainer &objects, Mesh &mesh)
{
	ObjectContainer::const_iterator it, it_end = objects.end();

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

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

			Mesh *polys = inst->GetMesh();

			// copy the face data
			for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
			{
				Face *face = new Face((*fi)->mVertexIndices);
				mesh.AddFace(face);
			}
		}
	}
}

void BspTree::Subdivide(const ObjectContainer &objects)
{
	std::stack<BspTraversalData> tStack;
	Mesh 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();
    
		Mesh backPolys;
		Mesh frontPolys;

		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(Mesh *polys) 
{
	// TODO: more sophisticated criteria
	return polys->GetFacePlane(0);
}

BspNode *BspTree::SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
								Mesh *polys, const int depth, 
								Mesh &frontPolys, Mesh &backPolys)
{
	// terminate traversal if no more faces in mesh
	if ((polys->mFaces.size() <= mMaxPolys) || (depth >= mMaxDepth))
	{
		// don't need to store polygon information
		polys->mFaces->clear(); // HACK: faces were deleted before
		DEL_PTR(polys); // we can savely delete mesh

		return leaf;
	}

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

 	FaceContainer::const_iterator fi;

	for (fi = polys->mFaces.begin(); fi != polys->mFaces.end(); ++ fi)
	{
		Face *face = (*fi);

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

		Face *front_piece, *back_piece;

		switch (result)
		{
			case 1:
				frontPolys.AddFace(face);
				break;
			case -1:
				backPolys.AddFace(face);
				break;
			case 0:
				//Split_Polygon (face, tree->partition, front_piece, back_piece);
				backPolys.AddFace(back_piece);
				frontPolys.AddFace(front_piece);

				// face not needed anymore
				DEL_PTR(face);

				break;
			default:
				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);

  	// don't need to store polygon information
	polys->mFaces->clear(); // HACK: faces were deleted before
	DEL_PTR(polys); // we can savely delete mesh

	DEL_PTR(leaf);

	return node;
}

//} // GtpVisibilityPreprocessor