///////////////////////////////////////////////////////////////////////////////
/// @file PrismBrush.cpp
///
/// @brief Creation of a prism
///
/// @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 Jul 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////
#include "deBrush_priv.hpp"
#include "deMath.hpp"

WorldObjectClassImp(dePrismBrush);

static const deBrush::DataQuantity_t s_PrismQuantities = 
{
	deBrush::DataQuantity_t::Quantity_PerCV, 
	2,	//CVNum
	1,	//NumFaces
	5	//CoordsPerFace
};

dePrismBrush::dePrismBrush()
:deBrush(Brush_Prism, s_PrismQuantities)
{
}

dePrismBrush::~dePrismBrush()
{
}

void dePrismBrush::UpdateBrush()
{
	GenerateHull();
}

deBoolean dePrismBrush::PlaneIntersectionPoint(dePlane &p1, dePlane &p2, dePlane &p3, deVec3d &p)
{
	deVec3d &n1 = p1.Norm;
	deVec3d &n2 = p2.Norm;
	deVec3d &n3 = p3.Norm;
	deDouble denom = Vec3d_Dot(n1, Vec3d_Cross(n2, n3));

	if (Compare_Epsilon(denom, 0))
		return deFALSE;

	p = (Vec3d_Cross(n3, n2) * (-p1.Dist));
	p -= (Vec3d_Cross(n3, n1) * (-p2.Dist));
	p -= (Vec3d_Cross(n1, n2) * (-p3.Dist));
	p /= denom;

	return deTRUE;
}

void dePrismBrush::GenerateHull()
{
	int Winding = 1;

	int a,b,c,d, NumPlanes;
	deBoolean Legal;
	deDouble Dist, TempVal;
	deVec3d Vertex;
	deVec3d Vertex2;
	deVec3d Center;
	deVec3d Normal;
	deTexCoord coord;

	if (m_CVNum < 4)
		return;

	m_PolyList.EmptyList();
//	m_Octree->Clear();

	// 1 = CCW, 0 = CW
	Winding = (Winding == 0) ? 0 : 1;
	NumPlanes = m_CVNum/2;
	if (NumPlanes*2 != m_CVNum)
		return;
	m_Planes.Resize(NumPlanes);
	deTArray < deTList<deVec3d> > Faces(NumPlanes);

	// calculate the plane equations from 2 vectors: a normal, and a point on the plane
	for (a = 0; a < NumPlanes; ++a)
	{
		Normal = m_CVList[a*2];
		Vec3d_Normalize(Normal);
		m_Planes[a].Norm = Normal;
		Dist = Vec3d_Dot(m_CVList[a*2+1], m_Planes[a].Norm);
		m_Planes[a].Dist = Dist;
	}

	// cycle through all the planes, testing 3 at a time for collisions against each other
	for (a = 0; a < NumPlanes-2; ++a)
	{
		for (b = a+1; b < NumPlanes-1; ++b)
		{
			for (c = b+1; c < NumPlanes; ++c)
			{
				if (a != b && a != c && b != c)
				{
					// find intersection point of the 3 planes, if there is one
					if (PlaneIntersectionPoint(m_Planes[a], m_Planes[b], m_Planes[c], Vertex))
					{
						Legal = deTRUE;

						// test if the point found is outside of the hull
						for (d = 0; d < NumPlanes; ++d)
						{
							if (d == a || d == b || d == c)
								continue;
							TempVal = Vec3d_Dot(m_Planes[d].Norm, Vertex);
							Dist = m_Planes[d].Dist;
							if (TempVal - Dist < 0)
							{
								Legal = deFALSE;
								break;
							}
						}

						// add the point to all three planes' face entries
						if (Legal)
						{
							Faces[a].AddElement(Vertex);
							Faces[b].AddElement(Vertex);
							Faces[c].AddElement(Vertex);
						}
					}
				}
			}
		}
	}

	// now we have to put the vertices on each face in the correct winding order
	int len, index;
	deDouble lowest;
	deVec3d * pVert;
	void * ptr;
	deTArray <deVec3d> VertArray;
	// cycle through all the faces that we now have, putting each one's vertices in order
	for (a = 0; a < NumPlanes; ++a)
	{
		len = Faces[a].Length();
		if (len == 0)
			continue;

		// resize the vertex array to accomodate the number of vertices on this face
		VertArray.Resize(len);

		// get the vertices out of the linked list and into an array where they are more easily swapped around
		b = 0;
		ptr = Faces[a].GetNext(NULL, pVert);
		while (ptr)
		{
			VertArray[b] = *pVert;
			++b;

			ptr = Faces[a].GetNext(ptr, pVert);
		}

		// calculate the average center of the face
		Center = VertArray[0];
		for (b = 1; b < len; ++b)
			Center += VertArray[b];
		Center /= (deDouble)len;
		// cycle through all the vertices, swapping them as necessary to be "next in line"
		for (b = 0; b < len-1; b++)
		{
			Vertex = VertArray[b]; // current point
			Vertex -= Center; // delta from center to current point
			Vec3d_Normalize(Vertex);
			// depending on the winding, the plane normal goes one way or the other
			if (Winding)
				Normal = Vec3d_Cross(m_Planes[a].Norm, Vertex);
			else
				Normal = Vec3d_Cross(Vertex, m_Planes[a].Norm);
			// splitting plane passing through current point and center, with normal perpendicular to normal of face
			Vec3d_Normalize(Normal);
			Dist = Vec3d_Dot(Normal, Center);

			// -1.0 = 180 degrees. +1.0 = 0 degrees. 0.0 = 90 degrees.
			lowest = -1.0;
			index = b;
			// start at next point and go to last point, looking for closest angle that's in the right geometric order
			for (c = b+1; c < len; ++c)
			{
				// make sure that the vertex we're testing is on the correct side of the splitting plane
				TempVal = Vec3d_Dot(Normal, VertArray[c]) - Dist;
				if (TempVal <= 0)
					continue;
				// calculate the delta from tested point to center, to find angle between it and current point
				Vertex2 = VertArray[c];
				Vertex2 -= Center;
				Vec3d_Normalize(Vertex2);
				// dot product of 2 normalized vectors gives cosine of angle between them
				TempVal = Vec3d_Dot(Vertex, Vertex2);
				// yeah, it's called "lowest" but the dot product is bigger when the angle is smaller
				if (TempVal > lowest)
				{
					// record the new low
					lowest = TempVal;
					index = c;
				}
			}
			// swap em if the one found isn't already in place
			if (index != b+1)
			{
				Vertex = VertArray[b+1];
				VertArray[b+1] = VertArray[index];
				VertArray[index] = Vertex;
			}
		}
		
		// now the vertices are in correct winding order
		// make a temporary polygon
		deBPoly poly(3);
		// go through all the vertices and put them in the polygon list
		for (c = 0; c < len-2; ++c)
		{
			// match this polygon to the texture of this face
			poly.TextureIndex = a;

			// go through the vertices and assign the various values
			for (b = 0; b < 3; ++b)
			{
				// making triangle fans, so the first vertex is the same each time
				if (b == 0)
					Center = VertArray[0];
				else
					Center = VertArray[c+b];
				poly.Verts[b].Pos = Center;

				// this data is recorded in a rather odd way, but it fits into the rest of the brush code
				// we have UNX,VNX,UNY,VNY,UNZ,VNZ (U normal X...)
				coord = m_FaceList[a][0];
				Vertex.x = coord.u;
				Vertex2.x = coord.v;
				coord = m_FaceList[a][1];
				Vertex.y = coord.u;
				Vertex2.y = coord.v;
				coord = m_FaceList[a][2];
				Vertex.z = coord.u;
				Vertex2.z = coord.v;

				// calculate the dot product of the current vertex (Center) and the appropriate texture axis normal
				coord.u = (deFloat)Vec3d_Dot(Center, Vertex);
				coord.v = (deFloat)Vec3d_Dot(Center, Vertex2);

				// divide by scale
				coord.u /= m_FaceList[a][3].u;
				coord.v /= m_FaceList[a][3].v;
				// add offset
				coord.u += m_FaceList[a][4].u;
				coord.v += m_FaceList[a][4].v;

				// record data
				poly.Verts[b].UV = coord;

				// fill in some color
				poly.Verts[b].Color = deMake_Color(0xffffffff);
			}

			// add the polygon to the brush
			m_PolyList.AddElement(poly);
//			m_Octree->AddPoly(poly);

#pragma todo(make this use index buffers to help speed it up some)
		}
	}

//	m_Octree->Generate();
}

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

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

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

