///////////////////////////////////////////////////////////////////////////////
/// @file BrushOctree.hpp
///
/// @brief Brush Octree header
///
/// @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 Nov 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks January Release
///
/// @date Dec 2002
/// @author Assassin
/// @remarks Rewrite for new scenegraph code
///
///////////////////////////////////////////////////////////////////////////////

#ifndef BRUSH_OCTREE_HPP
#define BRUSH_OCTREE_HPP

#include "deGlobalTypes.hpp"
#include "deList.hpp"
#include "deArray.hpp"
#include "deBrush_priv.hpp"

#include "deHash.hpp"
#include "deFunctors.hpp"

class deBrushOctree
{
public:
	class deIndexedPoly
	{
	public:
		//deBoolean	CanRemove;
		s32			NumVerts;
		long		PolyIndex;
		long		TextureIndex;
		u16 *		PosIndices;
		u16 *		NormIndices;
		u16 *		MatIndices;
		deDouble	Dist;
		deVec3d		Normal;
		~deIndexedPoly()
		{ delete[] PosIndices; }
		deIndexedPoly(s32 vertnum = 3)
		{
			//CanRemove = deFALSE;
			NumVerts = vertnum;
			PosIndices = new u16[NumVerts*3];
			NormIndices= &PosIndices[NumVerts];
			MatIndices = &PosIndices[NumVerts*2];
			TextureIndex = -1;
			PolyIndex = -1;
		}
		deIndexedPoly(const deIndexedPoly & ref) 
		{	
			//CanRemove = deFALSE;
			Normal = ref.Normal;
			Dist = ref.Dist;
			NumVerts = ref.NumVerts;
			TextureIndex = ref.TextureIndex;
			PosIndices = new u16[NumVerts*3];
			NormIndices= &PosIndices[NumVerts];
			MatIndices = &PosIndices[NumVerts*2];
			memcpy(PosIndices, ref.PosIndices, NumVerts*sizeof(u16)*3);
			PolyIndex = -1;
		}
		deIndexedPoly & operator=(const deIndexedPoly & ref)
		{	
			Normal = ref.Normal;
			Dist = ref.Dist;
			TextureIndex = ref.TextureIndex;
			NumVerts = ref.NumVerts;
			if (NumVerts != ref.NumVerts)
			{
				delete[] PosIndices;
				PosIndices = new u16[NumVerts*3];
				NormIndices= &PosIndices[NumVerts];
				MatIndices = &PosIndices[NumVerts*2];
			}
			memcpy(PosIndices, ref.PosIndices, NumVerts*sizeof(u16)*3);
			PolyIndex = -1;
			return *this;
		}
		void Resize(s32 vertnum)
		{	
			if (vertnum == NumVerts) return;
			u16* pTemp;
			NumVerts = vertnum;

			pTemp = new u16[NumVerts*3];
			memcpy(pTemp, PosIndices, NumVerts*sizeof(u16)*3);
			delete[] PosIndices;
			PosIndices = pTemp;
			NormIndices= &PosIndices[NumVerts];
			MatIndices = &PosIndices[NumVerts*2];
		}
	};

	struct deVertMat
	{
		deARGB Diffuse;
		deTexCoord UV;
	};

private:
	struct OctNode
	{
		long Depth;
		DWORD Contents;
		deVec3d Min, Max;
		struct OctNode* Children[9];
		deTArray <long> PolyIndexList;
	};

public:
	deBrushOctree();
	~deBrushOctree();

	deBoolean AddPositions(deVec3d *VertArray, u16 NumVerts, u16 &Offset);
	deBoolean AddNormals(deVec3d *VertArray, u16 NumVerts, u16 &Offset);
	deBoolean AddVertMats(deVertMat *VertArray, u16 NumVerts, u16 &Offset);
	deBoolean AddPolyGetRef(deIndexedPoly* & poly);
	deBoolean AddPoly(deIndexedPoly * poly, u16 PosOffset, u16 NormOffset, u16 MatOffset);

	deBoolean GetPoly(deIndexedPoly* & poly, long PolyIndex);

	deBoolean RemovePoly(const deIndexedPoly * poly);

	deBoolean Generate();
	deBoolean Clear();

	deBoolean GetPolysInBox(const deVec3d & Min, const deVec3d & Max, deTArray <deIndexedPoly*> &PolyArray, OctNode * node = NULL);
	deBoolean GetAllPolys(deTArray <deIndexedPoly*>* &PolyArray);
	deBoolean GetPolyInfo(deIndexedPoly* poly, deVec3d* &PosArray, deVec3d* &NormArray, deVertMat* &VertMatArray);
/*	deBoolean RayTrace(const deVec3d & start, const deVec3d & end, deIndexedPoly * & HitPoly, deVec3d & intersect);
	
	deBoolean AddMesh(deBrushOctree & adder);
	deBoolean SubtractMesh(deBrushOctree & cutter);
	deBoolean IntersectMesh(deBrushOctree & brush);

	deBoolean Copy(deBrushOctree & target);
*/
private:
	OctNode *m_Root;
	deTList	 <long>					m_PolyAddList;	// list of polygons that haven't been put into the array yet
	deTList	 <long>				m_PolyRemoveList;	// list of polygons that have been invalidated and can be replaced
	deTArray <deIndexedPoly*>		m_PolyArray;	// all the polygons that are inserted into the octree
	deTArray <deTArray<OctNode*> >	m_PolyNodes;	// lists of which nodes a polygon is "in"
	deTArray <deVec3d>				m_Positions;	// positions buffer
	deTArray <deVec3d>				m_Normals;		// normals buffer
	deTArray <deVertMat>			m_VertMats;		// materials buffer
	// for splitting polygons
	dePlane		m_SplittingPlane;
	deTHashFunctor<u16,HashEdge>	m_SplitPosHash;
	deTHashFunctor<u16,HashEdge>	m_SplitNormHash;
	deTHashFunctor<u16,HashEdge>	m_SplitMatHash;
	
//	void CopyNode(OctNode * source, OctNode * & target);
	void DestroyNode(OctNode * node);

	deBoolean	InsertPolyIntoTree(long PolyIndex);
	u8		DecideChildNodes(long PolyIndex, OctNode* Node);
	OctNode*	GetSmallestNodeForAABB(const deAABB & bbox);
	deBoolean	InsertPolyIntoNode(long PolyIndex, OctNode* Node);

/*
	void SubdivideNode(OctNode * node);
	void Optimize(OctNode * node);
	void InsertPoly(long index);
	bool InsertPoly(PolyPointer * p, OctNode * node);
	void RemovePoly(PolyPointer * p);
	bool PolyInNode(long poly, OctNode * node);
	long PolysIntersecting(deBPoly & tri, deTList <PolyPointer*> & polylist, bool CheckIntersection = false);
	long GetAllPolys(deTList <PolyPointer*> & polylist, OctNode * node);
	void Split(deBrushOctree & In1, deBrushOctree & In2, deBrushOctree & Out1, deBrushOctree & Out2);
*/

	static char      FrontmostOctNodeCorner(const deVec3d & norm);
	static void      OctNodeCorner(const OctNode* node, const char Corner, deVec3d & vec);
	static void      OctNodeMidPoint(const OctNode* node, const char MidPoint, deVec3d & vec);
	static deBoolean OctNodeIntersectsPlane(OctNode *node, const dePlane & plane);
	static inline void OctNodeCenter(const OctNode* node, deVec3d & vec)
	{
		vec = node->Min; vec += node->Max; vec *= 0.5;
	}

	// not static because they depend on the current octree's vertices
	// mostly polygon stuff
	char		TriLineIntersect(	const deIndexedPoly * T, u16 VertNum,
									const deVec3d & LinePt1, const deVec3d & LinePt2, 
									deVec3d & Res, deBoolean & HitEdge); // not implemented
	deBoolean	PolyPlaneIntersect(const deVec3d & norm, const deDouble & dist, const deIndexedPoly * poly, deVec3d* & ResPair);
	deBoolean	PolyPolyIntersect(const deIndexedPoly * p1, const deIndexedPoly * p2);
	deBoolean	MakePlane(long PolyIndex);
	deBoolean	MakePlane(deIndexedPoly * input);
	deBoolean	SplitPoly(const deIndexedPoly * input, deIndexedPoly* & out1, deIndexedPoly* & out2);
	u16			SplitEdgePos(const HashEdge & Edge, deDouble & Percent);
	u16			SplitEdgeNorm(const HashEdge & Edge, const deDouble & Percent);
	u16			SplitEdgeMat(const HashEdge & Edge, const deDouble & Percent);

	deBoolean	SplitAllPolys(deIndexedPoly* splitter);

	deBoolean	AssembleVertexBuffer(IdeVertexBuffer * pVB);
	deBoolean	AssembleVertexBufferNoNormals(IdeVertexBuffer * pVB);
	deBoolean	TriangulateIndices(const deIndexedPoly * Poly, u16 LastVertIndex, u16 * IndexArray3);

	void TEST();
};

/*
	    ________Max
	   / 6 / 7 /|
	  /___/___/7|		Y+  Z+
	 / 2 / 3 /| |		|  /
	/___/___/3|/|		| /
	|   |   | /5|		|/____X+
4=>	| 2 | 3 |/| |
	|-------|1|/
	| 0 | 1 | /
	|___|___|/
  Min

  mins:
  X: i%2 == 0
  Y: i%4 <  2
  Z: i   <  4

*/

#endif