///////////////////////////////////////////////////////////////////////////////
/// @file dePolyABT.hpp
///
/// @brief Adaptive Binary Tree for polygons
///
/// @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 Mar 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DE_POLYABT_HPP
#define DE_POLYABT_HPP

#include "deGlobalTypes.hpp"
#include "deArray.hpp"
#include "deSurface.hpp"
#include "deScene.hpp"
#include "deMath.hpp"
#include "deWorld_Helper.hpp"

class IdeVertexBuffer;
class IdeSceneObject;

const int deABT_TexCoords = 4;

class dePolyABT
{
public:
	// all vertices stored in the ABT structure will store this information only
	struct ABTVertex
	{
		deVec3d		Position;
		deVec3f		Normal;
		deTexCoord2	TexCoords[deABT_TexCoords];
		deARGB		Diffuse;
	};
	// all ABT faces are triangles, and each knows its surface ID
	struct ABTFace
	{
		long Indices[3];
		long SurfaceID;
	};
	enum ABTSplitMethod
	{
		Split_NoMethod,
		Split_SuccessiveApprox,
		Split_AllVerts,
		Split_MultiSample,
		Split_Statistical,
		Split_Count,
		Split_Force32Bit = 0x7fffffff
	};

	dePolyABT();
	~dePolyABT();

	/// surface state machine setting
	deBoolean SetCurrentSurface(IdeSurface* CurrSurface);

	/// add vertices that will be indexed by faces
	deBoolean AddVertices(ABTVertex* VertexArray, long NumVerts, long & BaseVertexIndex, const deTransformInfo & worldpos);
	/// add indices for faces, offset by a value obtained from AddVertices
	deBoolean AddTriangleIndices(long* IndexArray, long BaseVertexIndex, long NumIndices);
	/// handles an entire sceneobject without decomposing it into geometry
	deBoolean AddSceneObject(IdeSceneObject* pObject);
	/// add raw geometry from a vertex buffer - can be just vertices, just indices, or both
	deBoolean AddIndexedVBuffer(IdeVertexBuffer* VBuffer, long & BaseVertexIndex, const deTransformInfo & worldpos);
	/// add the geometry from an IdeMesh object
	deBoolean AddMeshGeometry(IdeMesh* pMesh, const deTransformInfo & worldpos);

	/// set the threshold for maximum triangles in a leaf node. defaults to 50.
	deBoolean SetMaxLeafTris(long MaxTris);
	/// set the threshold for maximum triangles in a renderable vertex buffer. defaults to 2000.
	deBoolean SetMaxVBufferTris(long MaxTris);
	/// set the weighting values for determining split plane locations.
	/// sum of all weights should be 1.0, and will be normalized if it is not.
	/// recommended to put most weight into FaceBalance to get more adaptive splits,
	/// but leave some weight in the others to avoid degenerate splits.
	/// @param Axis weight towards largest axis
	/// @param Volume weight towards center of chunk volume
	/// @param FaceBalance weight towards equal number of faces on each side of split
	/// @param NumSplit weight away from inducing splits of faces in a node
	deBoolean SetSplitWeights(deFloat Axis, deFloat Volume, deFloat FaceBalance, deFloat NumSplit);

	/// compile the entire ABT geometry into renderable VBs and leaf nodes
	deBoolean CompileABT();

	/// render the currently visible geometry, according to the input Params.
	deBoolean RenderVisibleGeometry(IdeSceneGraph::deSceneTraversal* Params);

	/// get the AABB extents of the ABT
	void GetVisibleAABB(deAABB& bbox);

	// serialization stuff
	deBoolean Serialize(IdeFile * File);
	deBoolean DeSerialize(IdeFile * File, u32 DataLength, u32 & AmtRead);
	deBoolean DeSerializeLoad();

private:
	/// a split in an ABT node, along an axis (0,1,2) at a certain percentage
	struct ABTSplit
	{
		long		Axis;
		deDouble	Percent;
	};
	/// a chunk of geometry that can be rendered independently.
	/// chunks should generally be 2000 faces or more
	struct ABTRenderChunk
	{
		IdeVertexBuffer*	VBuffer;
		u32					Surface;
	};
	/// a partition within the ABT.
	/// either has children or renderables, never both.
	/// non-leaf nodes can have faces if in limbo while compiling.
	struct ABTPartition
	{
		deAABB BBox;
		ABTSplit Split;
		deTArray <long> SceneObjectList;
		deTArray<ABTFace>	Faces;
		deTArray<ABTRenderChunk> Renderables;
		ABTPartition* Children[2]; // 0 = minside, 1 = maxside
		ABTPartition* Parent;
		deBoolean RenderableBuilt;
	};
	/// information about a split - most important being the score.
	/// used only while partitioning a box, to score the various sampled splits
	struct ABTSplitStat
	{
		ABTSplit Split;
		dePlane Plane;
		long FrontBackDiff;
		long NumOn;
		deFloat	Score;
	};

	deTArray<ABTVertex>		m_Vertices;
	deTArray<ABTFace>		m_AllFaces;
	deTArray<IdeSurface*>	m_Surfaces;
	deTArray<IdeSceneObject*>	m_SceneObjects;
	deAABB					m_TotalBBox;
	deVec3d					m_WorldOffset;
	ABTPartition*			m_RootPartition;
	u32						m_CurrSurfaceIndex;
	u32						m_OriginalVertNum;
	u32						m_MaxLeafTris;
	u32						m_MaxVBTris;
	deFloat					m_SplitWeights[4];

	// setup
	void			DestroyABT();
	// building the ABT
	ABTPartition*	CreateABTPartition(ABTPartition * Parent, int ChildNum);
	deBoolean		DestroyABTPartition(ABTPartition* &pPart);
	deBoolean		ShrinkPartitionBBoxes(ABTPartition * Parent);
	deBoolean		ProcessABTPartition(ABTPartition * pPart);
	void			PickBestSplit(const ABTPartition* pPart, ABTSplitStat & best, ABTSplitMethod method) const;
	deBoolean		ScorePartitionSplit(const ABTPartition* pPart, ABTSplitStat * pStat, deFloat AxisScores[3]) const;
	deBoolean		InterpolateCutEdge(ABTVertex * NewVert, long Index1, long Index2, dePlane& SplitPlane);
	deBoolean		BuildPartitionVBuffer(ABTPartition* pPart);

	// using the ABT
	deBoolean		RenderVisibleABTPartitions(IdeSceneGraph::deSceneTraversal* Params, ABTPartition* CurrentPart, deBoolean AllVisible);
	deBoolean		RenderABTPartition(IdeSceneGraph::deSceneTraversal* Params, ABTPartition* pPart);

	// stuff for serialization
	deTArray<deIDPair> m_SerialSurfaces, m_SerialObjects;
	struct ABTFilePartition_01
	{
		deAABB BBox;
		ABTSplit Split;
		u32 childPart[2]; u32 parentPart;
		u32 numFaces, faceIndexStart;
		u32 numObjects, objectIndexStart;
	};
	static u32 AppendFilePartition(deTArray<ABTFilePartition_01> & fileparts, const ABTPartition* current, u32 parentIdx, u32 & TotalFaces, u32 & TotalObjects);
	ABTPartition* DecomposeFilePartition(const deTArray<ABTFilePartition_01> & fileparts, u32 currentIdx, ABTPartition* parent, const deTArray<u32> objectIndices, const deTArray<ABTFace> faces);
	struct readWriteObject_t
	{
		IdeFile * m_File;
		deBoolean m_Write;
		u32 m_DataLength, *m_AmtRead;
		deBoolean operator()(IdeWorldObject* obj);
	};
	struct readWriteVertex_t
	{
		IdeFile * m_File;
		deBoolean m_Write;
		u32 m_DataLength, *m_AmtRead;
		deBoolean operator()(ABTVertex& vert);
	};
	struct readWriteFace_t
	{
		IdeFile * m_File;
		deBoolean m_Write;
		u32 m_DataLength, *m_AmtRead;
		deBoolean operator()(ABTFace& face);
	};
	struct readWritePartition_t
	{
		IdeFile * m_File;
		deBoolean m_Write;
		u32 m_DataLength, *m_AmtRead;
		deBoolean operator()(ABTFilePartition_01& part);
	};
	struct grabPartitionData_t
	{
		deTArray<u32> objects;
		deTArray<ABTFace> faces;
		deBoolean operator()(ABTFilePartition_01& part);
	};
};

#endif // DE_POLYABT_HPP