///////////////////////////////////////////////////////////////////////////////
/// @file BlockBrush.cpp
///
/// @brief Block creation
///
/// @author Assassin 
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Feb 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deBrush_priv.hpp"
#include "deStack.hpp"
//#include <cstdarg>
#include "deMath.hpp"
//#include "octree.hpp"
#include "deCamera.hpp"

WorldObjectClassImp(deBlockBrush);

static const deBrush::DataQuantity_t s_BlockQuantities = 
{
	deBrush::DataQuantity_t::Quantity_PerCV, 
	1,	//CVNum
	0,	//NumFaces
	0	//CoordsPerFace
};

deBlockBrush::deBlockBrush()
:deBrush(Brush_Block, s_BlockQuantities)
{
	ResizeLists(1);
	m_EdgesUpdated = deFALSE;
}

deBlockBrush::~deBlockBrush()
{
}

void deBlockBrush::UpdateBrush()
{
	GiftWrap();
	m_EdgesUpdated = deFALSE;
}

static bool operator==(edge e1, edge e2)
{
	if (e1.p1 == e2.p1 && e1.p2 == e2.p2)
		return true;
	if (e1.p1 == e2.p2 && e1.p2 == e2.p1)
		return true;
	return false;
}
/*
static bool EdgeHasVert(edge e1, int pt)
{
	return (e1.p1 == pt || e1.p2 == pt);
}
*/
static int EdgeOtherVert(edge e, int i)
{
	return (e.p1 == i) ? e.p2 : e.p1;
}

void deBlockBrush::GiftWrap()
{
	m_PolyList.EmptyList();
//	m_Octree->Clear();
	if (m_CVNum < 4)
		return;
	int i;
	edge e;
	deTStack <edge> UnComputed;
	deTList <edge> Computed;
	m_TotallyUsed.Resize(m_CVNum);
	m_EdgesOnVert.Resize(m_CVNum);
	for (i = 0; i < m_CVNum; i++)
	{
		m_TotallyUsed[i] = false;
		m_EdgesOnVert[i].EmptyList();
	}
	short a = FindA();
	short b = FindB(a);
	short c = FindC(a,b,-1);
	deBPoly face;
	MakeTri(a,b,c,face);
	m_PolyList.AddElement(face);
//	m_Octree->AddPoly(face);
	// we now have our base triangle
	e.p1 = a;
	e.p2 = c;
	e.p_opp = b;
	UnComputed.Push(e);
	m_EdgesOnVert[a].AddElement(e);
	m_EdgesOnVert[c].AddElement(e);
	e.p1 = b;
	e.p2 = a;
	e.p_opp = c;
	UnComputed.Push(e);
	m_EdgesOnVert[b].AddElement(e);
	m_EdgesOnVert[a].AddElement(e);
	e.p1 = c;
	e.p2 = b;
	e.p_opp = a;
	UnComputed.Push(e);
	m_EdgesOnVert[c].AddElement(e);
	m_EdgesOnVert[b].AddElement(e);
	while(!UnComputed.isEmpty())
	{
		UnComputed.Pop(e);
		if (Computed.FindData(NULL, e) != NULL)
			continue;
		if (UnComputed.HasData(e))
			continue;
		Computed.AddElement(e);
		a = e.p1;
		b = e.p2;
		c = FindC(a,b,e.p_opp);
		if (c >= m_CVNum)
			continue;
		m_EdgesOnVert[a].AddElement(e);
		m_EdgesOnVert[b].AddElement(e);
		MakeTri(a,b,c,face);
		m_PolyList.AddElement(face);
		// record that this face has been made
		e.p_opp = c;
		deTArray<edge>::iterator it = m_FaceList.IncrementSizeQuick(deFALSE);
		*it = e;
//		m_Octree->AddPoly(face);
		e.p1 = c;
		e.p2 = b;
		e.p_opp = a;
		UnComputed.Push(e);
		m_EdgesOnVert[c].AddElement(e);
		m_EdgesOnVert[b].AddElement(e);
		e.p1 = a;
		e.p2 = c;
		e.p_opp = b;
		UnComputed.Push(e);
		m_EdgesOnVert[c].AddElement(e);
		m_EdgesOnVert[a].AddElement(e);

		/* evaluate whether a point has been totally used
		 ****************/
		if (PointTotallyUsed(a))
			m_TotallyUsed[a] = true;
		if (PointTotallyUsed(b))
			m_TotallyUsed[b] = true;
		if (PointTotallyUsed(c))
			m_TotallyUsed[c] = true;
	}
	// free up some memory...
	m_TotallyUsed.Resize(0);
	m_EdgesOnVert.Resize(0);

//	m_Octree->Generate();
}

bool deBlockBrush::PointTotallyUsed(short p)
{
	deTArray <int> PointsFound(m_CVNum,0);
	edge e;
	int i;
	void * ptr = m_EdgesOnVert[p].GetNext(NULL,e);
	while (ptr)
	{
		PointsFound[EdgeOtherVert(e, p)]++;
		ptr = m_EdgesOnVert[p].GetNext(ptr,e);
	}
	for (i = 0; i < m_CVNum; i++)
	{
		int found = PointsFound[i];
		if (found == 1)
			return false;
		if (found == 2 || found == 0)
			continue;
		return false;
	}
	return true;
}

short deBlockBrush::FindA()
{
	short i;
	deDouble lowestval = m_CVList[0].y;
	short lowest = 0;
	for (i = 1; i < m_CVNum; i++)
	{
		if (m_CVList[i].y < lowestval)
		{
			lowestval = m_CVList[i].y;
			lowest = i;
		}
	}
	return lowest;
}

short deBlockBrush::FindB(short A)
{
	/*
	|a  b  c|
	|d  e  f| = aei + bfg + cdh - ceg - afh - bdi
	|g  h  i|
						  p0 p1 p2
						| x0 x1 x2 |
	Area of triangle =	| y0 y1 y2 | * 1/2
						| 1  1  1  |

	*/
	deVec3d p0, p1, p2;
	short i,k;


	p0 = m_CVList[A];

	for (i = 0; i < m_CVNum; i++)
	{
		if (i == A)
			continue;
		p1 = m_CVList[i];
		if (p1.x == p0.x && p1.y == p0.y)
			continue;
		//int ToLeft = 0;
		for (k = 0; k < m_CVNum; k++)
		{
			if (k == A || k == i)
				continue;
			p2 = m_CVList[k];
			if (p1.x == p2.x && p1.y == p2.y)
				continue;
			if (p0.x == p2.x && p0.y == p2.y)
				continue;
			deDouble Area = p0.x*p1.y + p1.x*p2.y + p2.x*p0.y 
							- p2.x*p1.y - p0.x*p2.y - p1.x*p0.y;
			// positive if to left
			if (Area < 0)
				break;
		}
		if (k == m_CVNum)
			break;
	}
	return i;
}

// the DontUse param is to prevent it form making the same poly
// as on the other side of the edge
short deBlockBrush::FindC(short A, short B, short DontUse)
{
	short i,k;
	deVec3d p0, p1, p2;
	deBPoly poly(3);

	p0 = m_CVList[A];
	p1 = m_CVList[B];

	for (i = 0; i < m_CVNum; i++)
	{
		if (i == A || i == B || DontUse == i || m_TotallyUsed[i])
			continue;
		p2 = m_CVList[i];

		MakeTri(A,B,i,poly);
		for (k = 0; k < m_CVNum; k++)
		{
			if (k == i || k == A || k == B)
				continue;
			deDouble d = Dist(poly, m_CVList[k]);
			//if (DontUse == k && d == 0)
			//	break;
			if (d > 0)
				break;
		}
		if (k == m_CVNum)
			break;
	}
	return i;
}

deDouble deBlockBrush::Dist(deBPoly & Poly, deVec3d Point)
{
	/*
	From	Pt (u.v.w)
	To		Plane (Ax+By+Cz=D)
	Distance is
			|Au + Bv + Cw - D|
			------------------
		   sqrt(A^2 + B^2 + C^2)

	sqrt(A^2+B^2+C^2) = 1 on normal
	Distance is |Au + Bv + Cw - D| = uvw dot ABC - D
	*/

	return	Vec3d_Dot(Poly.Normal, Point) - Poly.Dist;
}			

void deBlockBrush::MakeTri(long v1, long v2, long v3, deBPoly & face)
{
	deVec3d vec1, vec2;
	face.Resize(3);
	face.Verts[0].Pos = m_CVList[v1];
	face.Verts[1].Pos = m_CVList[v2];
	face.Verts[2].Pos = m_CVList[v3];

	vec1 = face.Verts[0].Pos - face.Verts[1].Pos;
	vec2 = face.Verts[0].Pos - face.Verts[2].Pos;
	face.Normal = Vec3d_Cross(vec1,vec2);
	Vec3d_Normalize(face.Normal);
	face.Dist = Vec3d_Dot(face.Normal, face.Verts[0].Pos);
}

deBoolean deBlockBrush::GetProjectedEdgePlanes(const deVec3d & Position, const deTransformInfo & transform, IdePlaneFrustum* pFrustum)
{
#pragma todo (test me)

	if (!pFrustum)
		return deFALSE;

	if (!m_EdgesUpdated)
		RecalcEdgeConnectivity();

	deVec3d invposition;

	{
		// transform the position by the "inverse" of the brush's transform
		DE_ASSERT(((deTransform*)(&transform))->IsOrthoNormal());
		deTransform invtform;
		((deTransform*)(&transform))->GetTranspose(invtform);
		invtform.Transform(Position, invposition);
	}

	{
		deVec3d Delta1, Delta2, Center, Delta3;
		deDouble Dot1, Dot2;
		dePlane plane;
		int i, len;

		// could change this to only loop through 4 points
		Center = m_CVList[0];
		len = m_CVList.Length();
		for (i = 0; i < len; ++i)
		{
			Center += m_CVList[i];
		}
		Center *= 1.0/len;

		len = m_EdgeNormals.Length();
		for (i = 0; i < len; ++i)
		{
			Delta1 = m_CVList[m_EdgeNormals[i].CV1];
			Delta1 -= invposition;
			Dot1 = Vec3d_Dot(Delta1, m_EdgeNormals[i].Norm1);
			Dot2 = Vec3d_Dot(Delta1, m_EdgeNormals[i].Norm2);
			if ((Dot1 < 0 && Dot2 > 0) || (Dot1 > 0 && Dot2 < 0))
			{
				// if the dot-products are opposing, this edge is a peripheral edge
				// so let's generate a plane
				Delta2 = m_CVList[m_EdgeNormals[i].CV1];
				Delta3 = Delta2;
				Delta2 -=m_CVList[m_EdgeNormals[i].CV2];
				Delta3 -= Center;
				Vec3d_Cross(Delta1, Delta2, plane.Norm);
				Vec3d_Normalize(plane.Norm);
				// if this normal faces out, the dot of it and the "center delta" will be negative
				// we want inward-facing normals, so reverse any out-facing normals
				if (Vec3d_Dot(plane.Norm, Delta3) < 0)
					plane.Norm *= -1;
				((deTransform*)(&transform))->Transform(plane.Norm, plane.Norm);
				plane.Dist = Vec3d_Dot(plane.Norm, Position);
				pFrustum->AddPlane(plane);
			}
		}
	}		

	return deTRUE;
}

void deBlockBrush::RecalcEdgeConnectivity()
{
#pragma todo (test me)

	deTHashFunctor<edge_normals,HashEdge> EdgeList(m_CVList.Length() * 2);
	int i, len;

	{
		// construct the hash-table of all the edges
		edge_normals CurrEdge, *pEdge;
		deVec3d vec0, vec1, vec2;
		len = m_FaceList.Length();
		for (i = 0; i < len; ++i)
		{
			HashEdge hash(m_FaceList[i].p1,m_FaceList[i].p2);
			pEdge = EdgeList.FindElement(hash);
			if (!pEdge)
			{
				CurrEdge.PairedFaces = false;
				CurrEdge.CV1 = m_FaceList[i].p1;
				CurrEdge.CV2 = m_FaceList[i].p2;
				vec0 = m_CVList[m_FaceList[i].p_opp];
				vec1 = m_CVList[CurrEdge.CV1];
				vec1 -= vec0;
				vec2 = m_CVList[CurrEdge.CV2];
				vec2 -= vec0;
				Vec3d_Cross(vec1, vec2, CurrEdge.Norm1);
				EdgeList.AddElement(CurrEdge, hash);
			}
			else
			{
				DE_ASSERT(!(pEdge->PairedFaces));

				pEdge->PairedFaces = true;
				vec0 = m_CVList[m_FaceList[i].p_opp];
				vec1 = m_CVList[pEdge->CV1];
				vec1 -= vec0;
				vec2 = m_CVList[pEdge->CV2];
				vec2 -= vec0;
				Vec3d_Cross(vec1, vec2, pEdge->Norm2);
			}
		}
	}

	{
		deTArray <edge_normals*> EdgeArray;
		EdgeList.GetAllElements(EdgeArray);
		len = EdgeArray.Length();
		m_EdgeNormals.ResizeQuick(0);
		m_EdgeNormals.ResizeQuick(len);
		for (i = 0; i < len; ++i)
		{
			DE_ASSERT(EdgeArray[i]->PairedFaces);
			m_EdgeNormals[i] = *(EdgeArray[i]);
		}
	}

	m_EdgesUpdated = deTRUE;
}

deBrush * deBlockBrush::CopyBrush()
{
	deBlockBrush * b = NULL;
	b = new deBlockBrush;
//	*b = *this;
	return b;
}

deBoolean deBlockBrush::Serialize(IdeFile* FS)
{
	if (!deBrush::Serialize(FS))
		return deFALSE;
	return deTRUE;
}

deBoolean deBlockBrush::DeSerialize(IdeFile* FS, long DataLength)
{
	if (!deBrush::DeSerialize(FS, DataLength))
		return deFALSE;
	return deTRUE;
}

