#include "dllinterface.h"
#include "BSPTree.h"
#include "BufferManager.h"

/*BSPTree::BSPTree(MeshContainer* const pMesh, unsigned iSubset)
{
	m_pRoot = new BSPTreeNode();

	m_pMesh = pMesh;
	m_iSubset = iSubset;

	m_pRoot->TriangleCount = pMesh->GetTriangleCount();
	m_pRoot->pTriangleIndexList = pMesh->GetTriangles();

	SplitNode(m_pRoot);
}*/

BSPTree::BSPTree(LPDIRECT3DVERTEXBUFFER9 pVB, LPDIRECT3DINDEXBUFFER9 pIB, VertexDeclaration* vdecl, const unsigned trianglecount, const unsigned basevertexindex, const unsigned StartIndex)
{
	m_pRoot = new BSPTreeNode();

	m_pRoot->TriangleCount = trianglecount;
	m_pRoot->pTriangleIndexList = new unsigned[trianglecount * 3];

	if (pIB) // copy index data to array
	{
		D3DINDEXBUFFER_DESC desc;
		pIB->GetDesc(&desc);

		void* ibdata;
		pIB->Lock(0, 0, &ibdata, 0);

		if (desc.Format == D3DFMT_INDEX32) //just memcpy array if same bit size
		{
			memcpy(m_pRoot->pTriangleIndexList, ((unsigned*)ibdata) + StartIndex, trianglecount * 3 * sizeof(unsigned));
		}
		else// should be 16 then; convert to 32bit index array if 16bit
		{
			unsigned* pTriangleIndexDst = m_pRoot->pTriangleIndexList;
			unsigned short* pTriangleIndexSrc = ((unsigned short*)ibdata) + StartIndex;

			for (unsigned i = trianglecount * 3; i; --i)
				*pTriangleIndexDst++ = *pTriangleIndexSrc++;
		}

		pIB->Unlock();
	}
	else //build indexlist for triangle list
	{
		unsigned* pTriangleIndexDst = m_pRoot->pTriangleIndexList;

		for (unsigned i = 0; i < trianglecount * 3; ++i)
		{
			*pTriangleIndexDst++ = i;
		}
	}

	pVB->Lock(0, 0, &m_pVertexData, 0);
	m_VertexStride = vdecl->GetVertexSize(0);
	m_BaseVertexIndex = basevertexindex;
	
	SplitNode(m_pRoot);

	pVB->Unlock();
	m_pVertexData = NULL;
}

void BSPTree::SplitNode(BSPTreeNode* const pNode) const
{
	//dont need to be splitted when there are no more than one triangle
	if (!pNode || pNode->TriangleCount <= 1)
		return;

	//block to decrease stack usage
	{
		//find a good splitter plane and count classified triangles
		unsigned pos, neg, slice, planar;
		pNode->Splitter = FindSplitter(pNode, pos, neg, slice, planar);

		//check if splitter plane could be found
		if (pNode->Splitter == DXPlane(0, 0, 0, 0) || (neg == 0 || pos == 0))
			return;

		bool SliceSide = true; //first will be pos

		//remind: first sliced tri is put to pos
		
		if(pos + planar + (slice - slice/2) > 0)
		{
			pNode->pPos = new BSPTreeNode();
			pNode->pPos->pTriangleIndexList = new unsigned[(pos + planar + (slice - slice/2)) * 3]; 
		}

		if((neg + slice/2) > 0)
		{
			pNode->pNeg = new BSPTreeNode();
			pNode->pNeg->pTriangleIndexList = new unsigned[(neg + slice/2) * 3];
		}

		for (unsigned i = 0; i < pNode->TriangleCount; i++)
		{
			unsigned i1 = pNode->pTriangleIndexList[i * 3 + 0];
			unsigned i2 = pNode->pTriangleIndexList[i * 3 + 1];
			unsigned i3 = pNode->pTriangleIndexList[i * 3 + 2];

			BSPTRIANGLECLASS TriClass = ClassifyTriangle(pNode->Splitter, i1, i2, i3);

			if (TriClass == BSP_POS)
			{
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 0] = i1;
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 1] = i2;
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 2] = i3;
				pNode->pPos->TriangleCount++;
			}
			else if (TriClass == BSP_NEG)
			{
				pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 0] = i1;
				pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 1] = i2;
				pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 2] = i3;
				pNode->pNeg->TriangleCount++;
			}
			else if(TriClass == BSP_SLICE) //we dont want to slice so just put it to one side
			{
				if (SliceSide)
				{
					pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 0] = i1;
					pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 1] = i2;
					pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 2] = i3;
					pNode->pPos->TriangleCount++;
				}
				else
				{
					pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 0] = i1;
					pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 1] = i2;
					pNode->pNeg->pTriangleIndexList[pNode->pNeg->TriangleCount * 3 + 2] = i3;
					pNode->pNeg->TriangleCount++;
				}
				SliceSide = !SliceSide;
			}
			else if(TriClass == BSP_PLANAR) // just put it to this side
			{
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 0] = i1;
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 1] = i2;
				pNode->pPos->pTriangleIndexList[pNode->pPos->TriangleCount * 3 + 2] = i3;
				pNode->pPos->TriangleCount++;
			}
		}

		if (pNode->pPos && (pos + planar + (slice - slice/2)) != pNode->pPos->TriangleCount || pNode->pNeg && neg + slice/2 != pNode->pNeg->TriangleCount)
		{
			//holy crap
			wlog("BSPTree: BufferOverflow");
		}
	}

	//it has been splitted, so trianglelist of parent is not needed anymore
	delete pNode->pTriangleIndexList;
	pNode->pTriangleIndexList = NULL;
		
	//recursive split subnodes now
	SplitNode(pNode->pPos);
	SplitNode(pNode->pNeg);
}

void BSPTree::SplitTriangle(const DXPlane& splitter, const unsigned i1, const unsigned i2, const unsigned i3)
{

}

BSPTree::BSPTRIANGLECLASS BSPTree::ClassifyTriangle(const DXPlane& splitter, const unsigned i1, const unsigned i2, const unsigned i3) const
{
	float d[] = {splitter.DotCoord(DXVector3((float*)((char*)m_pVertexData + (m_BaseVertexIndex + i1) * m_VertexStride))),
				splitter.DotCoord(DXVector3((float*)((char*)m_pVertexData + (m_BaseVertexIndex + i2) * m_VertexStride))),
				splitter.DotCoord(DXVector3((float*)((char*)m_pVertexData + (m_BaseVertexIndex + i3) * m_VertexStride)))};

	unsigned pos = 0;
	unsigned neg = 0;

	for (unsigned i = 0; i < 3; i++)
	{
		if (d[i] - 0.0001f > 0)
			pos++;
		else if (d[i] + 0.0001f < 0)
			neg++;
	}

	if(pos > 0 && neg == 0)
		return BSP_POS;
	else if (neg > 0 && pos == 0)
		return BSP_NEG;
	else if (!pos && !neg) // all points are upon the plane
		return BSP_PLANAR;
	else
		return BSP_SLICE;
}

DXPlane BSPTree::FindSplitter(BSPTreeNode* const pNode, unsigned& pos, unsigned& neg, unsigned& slice, unsigned& planar) const
{
	DXPlane BestSplitter(0, 0, 0, 0);
	unsigned BestSplitterRating = 0xffffffff;

	for (unsigned i = 0; i < pNode->TriangleCount; i++) 
	{
		DXVector3 v1((float*)((char*)m_pVertexData + (m_BaseVertexIndex + pNode->pTriangleIndexList[i * 3 + 0]) * m_VertexStride));
		DXVector3 v2((float*)((char*)m_pVertexData + (m_BaseVertexIndex + pNode->pTriangleIndexList[i * 3 + 1]) * m_VertexStride));
		DXVector3 v3((float*)((char*)m_pVertexData + (m_BaseVertexIndex + pNode->pTriangleIndexList[i * 3 + 2]) * m_VertexStride));

		DXPlane splitter = DXPlane::FromPoints(v1, v2, v3);
	
		int curpos = 0;
		int curneg = 0;
		int curslice = 0;
		int curplanar = 0;

		for (unsigned j = 0; j < pNode->TriangleCount; j++) 
		{
			unsigned i1 = pNode->pTriangleIndexList[j * 3 + 0];
			unsigned i2 = pNode->pTriangleIndexList[j * 3 + 1];
			unsigned i3 = pNode->pTriangleIndexList[j * 3 + 2];

			BSPTRIANGLECLASS TriClass = ClassifyTriangle(splitter, i1, i2, i3);

			if (TriClass == BSP_POS)
				curpos++;
			else if (TriClass == BSP_NEG)
				curneg++;			
			else if (TriClass == BSP_SLICE) 
				curslice++;
			else if (TriClass == BSP_PLANAR)
				curplanar++;
        }

		//slicing is bad, therefore give it a higher weight
		unsigned rating = (unsigned)(abs(curpos - curneg) + curslice * 3);

		if(rating < BestSplitterRating)
		{
			BestSplitter = splitter;
			BestSplitterRating = rating;

			pos = curpos;
			neg = curneg;
			slice = curslice;
			planar = curplanar;
		}
	}

   return BestSplitter;
}

void BSPTree::BuildIndexBuffer(void* pIBData, bool bIndex32, const DXVector3& ViewPoint, const DXMatrix& matWorldToMesh)
{
	const DXVector3 vp = matWorldToMesh.TransformCoord(ViewPoint);

	if(bIndex32)
	{
		unsigned* pIBDst = (unsigned*)pIBData;
		BuildIndex32(m_pRoot, pIBDst, vp);
	}
	else
	{
		unsigned short* pIBDst = (unsigned short*)pIBData;
		BuildIndex16(m_pRoot, pIBDst, vp);
	}
}

void BSPTree::BuildIndex16(BSPTreeNode* const pNode, unsigned short* &pIBDst, const DXVector3& ViewPoint)
{
	if (!pNode)
		return;

	// copy indices to indexbuffer
	for (unsigned i = 0; i < pNode->TriangleCount * 3; ++i)
		*pIBDst++ = pNode->pTriangleIndexList[i];
	
	if (pNode->Splitter.DotCoord(ViewPoint) > 0) // point on pos side, render backside first
	{
		BuildIndex16(pNode->pNeg, pIBDst, ViewPoint);
		BuildIndex16(pNode->pPos, pIBDst, ViewPoint);
	}
	else // point on neg side, render pos side first
	{
		BuildIndex16(pNode->pPos, pIBDst, ViewPoint);
		BuildIndex16(pNode->pNeg, pIBDst, ViewPoint);
	}
}

void BSPTree::BuildIndex32(BSPTreeNode* const pNode, unsigned* &pIBDst, const DXVector3& ViewPoint)
{
	if (!pNode)
		return;

	// copy indices to indexbuffer
	if (pNode->pTriangleIndexList)
	{
		memcpy(pIBDst, pNode->pTriangleIndexList, sizeof(unsigned) * pNode->TriangleCount * 3);
		pIBDst += pNode->TriangleCount * 3;
	}
	
	if (pNode->Splitter.DotCoord(ViewPoint) > 0) // point on pos side, render backside first
	{
		BuildIndex32(pNode->pNeg, pIBDst, ViewPoint);
		BuildIndex32(pNode->pPos, pIBDst, ViewPoint);
	}
	else // point on neg side, render pos side first
	{
		BuildIndex32(pNode->pPos, pIBDst, ViewPoint);
		BuildIndex32(pNode->pNeg, pIBDst, ViewPoint);
	}
}