/* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
*
* This software is provided 'as-is', without any express or implied
* warranty. In no event will the authors be held liable for any damages
* arising from the use of this software.
*
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
*
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
*
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
*
* 3. This notice may not be removed or altered from any source distribution.
*/

#ifndef __dgPolyhedra__
#define __dgPolyhedra__

#include "dgStdafx.h"
#include "dgList.h"
#include "dgTree.h"
#include "dgHeap.h"
#include "dgDebug.h"




class dgEdge;
class dgPlane;
class dgSphere;
class dgMatrix;
class dgPolyhedra;


typedef dgInt64 dgEdgeKey;

/*
class dgPolyhedraDescriptor
{
    public:

     dgPolyhedraDescriptor (const dgPolyhedra& polyhedra);
     ~dgPolyhedraDescriptor ();
     void Update (const dgPolyhedra& polyhedra);

    dgInt32 m_faceCount;                             // total face count including openfaces
    dgInt32 m_edgeCount;                             // total edge count count including openfaces
    dgInt32 m_vertexCount;                       // total vertex count including openfaces
    dgInt32 m_maxVertexIndex;
    dgList<dgEdge*> m_unboundedLoops;
};
*/

DG_MSC_VECTOR_ALIGMENT
class dgEdge {
public:
	dgEdge();
	dgEdge(dgInt32 vertex, dgInt32 face, dgUnsigned64 userdata = 0);

	dgInt32 m_incidentVertex;
	dgInt32 m_incidentFace;
	dgUnsigned64 m_userData;
	dgEdge *m_next;
	dgEdge *m_prev;
	dgEdge *m_twin;
	dgInt32 m_mark;
} DG_GCC_VECTOR_ALIGMENT;


class dgPolyhedra: public dgTree <dgEdge, dgEdgeKey> {
public:

	struct dgPairKey {
		dgPairKey();
		dgPairKey(dgInt64 val);
		dgPairKey(dgInt32 v0, dgInt32 v1);
		dgInt64 GetVal() const;
		dgInt32 GetLowKey() const;
		dgInt32 GetHighKey() const;

	private:
		dgUnsigned64 m_key;
	};

	dgPolyhedra(dgMemoryAllocator *const allocator);
	dgPolyhedra(const dgPolyhedra &polyhedra);
	virtual ~dgPolyhedra();

	void BeginFace();
	dgEdge *AddFace(dgInt32 v0, dgInt32 v1, dgInt32 v2);
	dgEdge *AddFace(dgInt32 count, const dgInt32 *const index);
	dgEdge *AddFace(dgInt32 count, const dgInt32 *const index, const dgInt64 *const userdata);
	void EndFace();
	void DeleteFace(dgEdge *const edge);

	dgInt32 GetFaceCount() const;
	dgInt32 GetEdgeCount() const;
	dgInt32 GetLastVertexIndex() const;

	dgInt32 IncLRU() const;
	void SetLRU(dgInt32 lru) const;

	dgEdge *FindEdge(dgInt32 v0, dgInt32 v1) const;
	dgTreeNode *FindEdgeNode(dgInt32 v0, dgInt32 v1) const;

	dgEdge *AddHalfEdge(dgInt32 v0, dgInt32 v1);
	void DeleteEdge(dgEdge *const edge);
	void DeleteEdge(dgInt32 v0, dgInt32 v1);

	bool FlipEdge(dgEdge *const edge);
	dgEdge *SpliteEdge(dgInt32 newIndex, dgEdge *const edge);
	dgBigVector FaceNormal(dgEdge *const face, const dgFloat64 *const vertex, dgInt32 strideInBytes) const;

	void BeginConectedSurface() const;
	bool GetConectedSurface(dgPolyhedra &polyhedra) const;
	void EndConectedSurface() const;

	dgSphere CalculateSphere(const dgFloat64 *const vertex, dgInt32 strideInBytes, const dgMatrix *const basis = NULL) const;
	void ChangeEdgeIncidentVertex(dgEdge *const edge, dgInt32 newIndex);
	void DeleteDegenerateFaces(const dgFloat64 *const pool, dgInt32 dstStrideInBytes, dgFloat64 minArea);

	void Optimize(const dgFloat64 *const pool, dgInt32 strideInBytes, dgFloat64 tol);
	void Triangulate(const dgFloat64 *const vertex, dgInt32 strideInBytes, dgPolyhedra *const leftOversOut);
	void ConvexPartition(const dgFloat64 *const vertex, dgInt32 strideInBytes, dgPolyhedra *const leftOversOut);

	/*
	    bool SanityCheck() const;


	    // create an edge and add it to the tree.
	    // the edge is not linked to the existing edge list


	    // create a complete edge and add it to the tree
	    //  the new edge is linked to the existing edge list
	//  dgEdge* AddEdge (dgInt32 v0, dgInt32 v1);

	    void DeleteEdge (dgInt32 v0, dgInt32 v1);
	    void DeleteEdge (dgEdge* const edge);

	    void DeleteAllFace();



	    dgInt32 GetMaxIndex() const;

	    dgInt32 GetUnboundedFaceCount() const;

	    dgBigVector BigFaceNormal (dgEdge* const face, const dgFloat64* const pool, dgInt32 strideInBytes) const;




	    dgEdge* SpliteEdgeAndTriangulate (dgInt32 newIndex, dgEdge* const edge);

	    dgEdge* FindVertexNode (dgInt32 v0) const;

	    dgInt32 PackVertex (dgFloat64* const destArray, const dgFloat64* const unpackArray, dgInt32 strideInBytes);
	    void DeleteOverlapingFaces (const dgFloat64* const pool, dgInt32 strideInBytes, dgFloat64 distTol);
	    void InvertWinding ();

	    // find edges edge shared by two or more non adjacent faces
	    // this make impossible to triangulate the polyhedra
	    void GetBadEdges (dgList<dgEdge*>& faceList, const dgFloat64* const pool, dgInt32 strideInBytes) const;


	    void GetCoplanarFaces (dgList<dgEdge*>& faceList, dgEdge* startFace, const dgFloat64* const pool, dgInt32 hisStrideInBytes, dgFloat64 normalDeviation) const;
	    void GetOpenFaces (dgList<dgEdge*>& faceList) const;
	    void CollapseDegenerateFaces (dgPolyhedraDescriptor &desc, const dgFloat64* const pool, dgInt32 strideInBytes, dgFloat64 area);



	    // this function assume the mesh is a legal mesh;
	    dgInt32 TriangleList (dgUnsigned32 outputBuffer[], dgInt32 maxBufferSize, dgInt32 vertexCacheSize = 12) const;
	    void SwapInfo (dgPolyhedra& source);


	*/

	// this function ayend to create a better triangulation of a mesh
	// by first calling the calling quadrangular and then triangulate
	// all quad strips.
	// this function assume the mesh is a legal mesh;
	// note1: recommend a call to Triangulate or OptimalTriangulation
	//           before using this function
	// note2: a index set to 0xffffffff indicate a run start
	// return index count
	//  dgInt32 TriangleStrips (dgUnsigned32 outputBuffer[], dgInt32 maxBufferSize, dgInt32 vertexCacheSize = 12) const;
	//  void OptimalTriangulation (const dgFloat64* const vertex, dgInt32 strideInBytes);
	//  void CombineOpenFaces (const dgFloat64* const pool, dgInt32 strideInBytes, dgFloat64 distTol);
	//  bool TriangulateFace (dgEdge* const face, const dgFloat64* const vertex, dgInt32 strideInBytes, dgBigVector& normalOut);
	//  void OptimizeTriangulation (const dgFloat64* const vertex, dgInt32 strideInBytes);
	//  void Quadrangulate (const dgFloat64* const vertex, dgInt32 strideInBytes);
	//  dgEdge* GetBadEdge (dgList<dgEdge*>& faceList  const dgFloat64* const pool, dgInt32 strideInBytes) const;

private:

	void RefineTriangulation(const dgFloat64 *const vertex, dgInt32 stride);
	void RefineTriangulation(const dgFloat64 *const vertex, dgInt32 stride, dgBigVector *const normal, dgInt32 perimeterCount, dgEdge **const perimeter);
	void OptimizeTriangulation(const dgFloat64 *const vertex, dgInt32 strideInBytes);
	void MarkAdjacentCoplanarFaces(dgPolyhedra &polyhedraOut, dgEdge *const face, const dgFloat64 *const pool, dgInt32 strideInBytes);
	dgEdge *FindEarTip(dgEdge *const face, const dgFloat64 *const pool, dgInt32 stride, dgDownHeap<dgEdge *, dgFloat64> &heap, const dgBigVector &normal) const;
	dgEdge *TriangulateFace(dgEdge *face, const dgFloat64 *const pool, dgInt32 stride, dgDownHeap<dgEdge *, dgFloat64> &heap, dgBigVector *const faceNormalOut);

	dgFloat64 EdgePenalty(const dgBigVector *const pool, dgEdge *const edge) const;

	mutable dgInt32 m_baseMark;
	mutable dgInt32 m_edgeMark;
	mutable dgInt32 m_faceSecuence;

	friend class dgPolyhedraDescriptor;

};



inline dgEdge::dgEdge() {
}

inline dgEdge::dgEdge(dgInt32 vertex, dgInt32 face, dgUnsigned64 userdata)
	: m_incidentVertex(vertex)
	, m_incidentFace(face)
	, m_userData(userdata)
	, m_next(NULL)
	, m_prev(NULL)
	, m_twin(NULL)
	, m_mark(0) {
}


inline dgPolyhedra::dgPairKey::dgPairKey() {
}

inline dgPolyhedra::dgPairKey::dgPairKey(dgInt64 val)
	: m_key(dgUnsigned64(val)) {
}

inline dgPolyhedra::dgPairKey::dgPairKey(dgInt32 v0, dgInt32 v1)
	: m_key(dgUnsigned64((dgInt64(v0) << 32) | v1)) {
}

inline dgInt64 dgPolyhedra::dgPairKey::GetVal() const {
	return dgInt64(m_key);
}

inline dgInt32 dgPolyhedra::dgPairKey::GetLowKey() const {
	return dgInt32(m_key >> 32);
}

inline dgInt32 dgPolyhedra::dgPairKey::GetHighKey() const {
	return dgInt32(m_key & 0xffffffff);
}

inline void dgPolyhedra::BeginFace() {
}

inline dgEdge *dgPolyhedra::AddFace(dgInt32 count, const dgInt32 *const index) {
	return AddFace(count, index, NULL);
}

inline dgEdge *dgPolyhedra::AddFace(dgInt32 v0, dgInt32 v1, dgInt32 v2) {
	dgInt32 vertex[3];

	vertex [0] = v0;
	vertex [1] = v1;
	vertex [2] = v2;
	return AddFace(3, vertex, NULL);
}

inline dgInt32 dgPolyhedra::GetEdgeCount() const {
#ifdef _DEBUG
	dgInt32 edgeCount = 0;
	Iterator iter(*this);
	for (iter.Begin(); iter; iter ++) {
		edgeCount ++;
	}
	NEWTON_ASSERT(edgeCount == GetCount());;
#endif
	return GetCount();
}

inline dgInt32 dgPolyhedra::GetLastVertexIndex() const {
	dgInt32 maxVertexIndex = -1;
	Iterator iter(*this);
	for (iter.Begin(); iter; iter ++) {
		const dgEdge *const edge = &(*iter);
		if (edge->m_incidentVertex > maxVertexIndex) {
			maxVertexIndex = edge->m_incidentVertex;
		}
	}
	return maxVertexIndex + 1;
}


inline dgInt32 dgPolyhedra::IncLRU() const {
	m_edgeMark ++;
	NEWTON_ASSERT(m_edgeMark < 0x7fffffff);
	return m_edgeMark;
}

inline void dgPolyhedra::SetLRU(dgInt32 lru) const {
	if (lru > m_edgeMark) {
		m_edgeMark = lru;
	}
}

inline void dgPolyhedra::BeginConectedSurface() const {
	m_baseMark = IncLRU();
}

inline void dgPolyhedra::EndConectedSurface() const {
}


inline dgPolyhedra::dgTreeNode *dgPolyhedra::FindEdgeNode(dgInt32 i0, dgInt32 i1) const {
	dgPairKey key(i0, i1);
	return Find(key.GetVal());
}


inline dgEdge *dgPolyhedra::FindEdge(dgInt32 i0, dgInt32 i1) const {
	//  dgTreeNode *node;
	//  dgPairKey key (i0, i1);
	//  node = Find (key.GetVal());
	//  return node ? &node->GetInfo() : NULL;
	dgTreeNode *const node = FindEdgeNode(i0, i1);
	return node ? &node->GetInfo() : NULL;
}

inline void dgPolyhedra::DeleteEdge(dgInt32 v0, dgInt32 v1) {
	dgPairKey pairKey(v0, v1);
	dgTreeNode *const node = Find(pairKey.GetVal());
	dgEdge *const edge = node ? &node->GetInfo() : NULL;
	if (!edge) {
		return;
	}
	DeleteEdge(edge);
}


#endif