//////////////////////////////////////////////////////////////////////////////
//
// NvTriStripObjects.h
//
// By: Nvidia.
//
//////////////////////////////////////////////////////////////////////////////

// B E G I N   F I L E   W R A P P E R ///////////////////////////////////////

#ifdef ASURA_USE_PRAGMA_ONCE
    #pragma once
#endif

#ifndef ___NVTRISTRIPOBJECTS_H___
#define ___NVTRISTRIPOBJECTS_H___ 1

// I N C L U D E S ///////////////////////////////////////////////////////////

// Standard headers.
#include "Core/Asura_MemoryManagement_DebugOff.h" // Std headers define their own new and delete operators and our macros break them.
#pragma warning( push, 1 )                        // Std headers spew a ton of (internal) warnings otherwise.
#pragma warning( disable: 4530 )
#pragma warning( disable: 4702 )
#include <list>
#include <vector>
#pragma warning( pop )
#include "Core/Asura_MemoryManagement_DebugOn.h"
#include <windows.h>

// F O R W A R D   D E C L A R A T I O N S ///////////////////////////////////

class PS2Strip_Tri;

// B E G I N   N A M E S P A C E /////////////////////////////////////////////

namespace NVTriStrip
{

// F O R W A R D   D E C L A R A T I O N S ///////////////////////////////////

class NvEdgeInfo;
class NvFaceInfo;
class NvStripInfo;
class VertexCache;

// T Y P E S /////////////////////////////////////////////////////////////////

struct Vertex
{
    // Indices into Asura data.
    unsigned uPolygonIdx;
    unsigned uVertexIdx;
};

struct Face
{
    // Indices into vertex lists.
	int v1, v2, v3;

    // Face normal.
	float nx, ny, nz;
};

typedef std::vector<NvFaceInfo*>    NvFaceInfoVec;
typedef std::list  <NvFaceInfo*>    NvFaceInfoList;
typedef std::list  <NvFaceInfoVec*> NvStripList;
typedef std::vector<NvEdgeInfo*>    NvEdgeInfoVec;
typedef std::vector<NvStripInfo*>   NvStripInfoVec;

typedef std::vector<int>    IndexVec;
typedef std::vector<Vertex> VertexVec;
typedef std::vector<Face>   FaceVec;

// C L A S S E S /////////////////////////////////////////////////////////////

class NvFaceInfo {
public:
	
    NvFaceInfo( void ) { }
    
	// vertex indices
	NvFaceInfo(int v0, int v1, int v2){
		m_v0 = v0; m_v1 = v1; m_v2 = v2;
		m_stripId      = -1;
		m_testStripId  = -1;
		m_experimentId = -1;
	}
	
	// data members are left public
    
    union
    {
        struct { int m_v0, m_v1, m_v2; };

        int m_av[3];
    };

	int   m_stripId;      // real strip Id
	int   m_testStripId;  // strip Id in an experiment
	int   m_experimentId; // in what experiment was it given an experiment Id?
};

// nice and dumb edge class that points knows its
// indices, the two faces, and the next edge using
// the lesser of the indices
class NvEdgeInfo {
public:
	
	// constructor puts 1 ref on us
	NvEdgeInfo (int v0, int v1){
		m_v0       = v0;
		m_v1       = v1;
		m_face0    = NULL;
		m_face1    = NULL;
		m_nextV0   = NULL;
		m_nextV1   = NULL;
		
		// we will appear in 2 lists.  this is a good
		// way to make sure we delete it the second time
		// we hit it in the edge infos
		m_refCount = 2;    
		
	}
	
	// ref and unref
	void Unref () { if (--m_refCount == 0) delete this; }
	
	// data members are left public
	UINT         m_refCount;
	NvFaceInfo  *m_face0, *m_face1;
	int          m_v0, m_v1;
	NvEdgeInfo  *m_nextV0, *m_nextV1;
};


// This class is a quick summary of parameters used
// to begin a triangle strip.  Some operations may
// want to create lists of such items, so they were
// pulled out into a class
class NvStripStartInfo {
public:
	NvStripStartInfo(NvFaceInfo *startFace, NvEdgeInfo *startEdge, bool toV1){
		m_startFace    = startFace;
		m_startEdge    = startEdge;
		m_toV1         = toV1;
	}
	NvFaceInfo    *m_startFace;
	NvEdgeInfo    *m_startEdge;
	bool           m_toV1;      
};

// This is a summary of a strip that has been built
class NvStripInfo {
public:
	
	// A little information about the creation of the triangle strips
	NvStripInfo(const NvStripStartInfo &startInfo, int stripId, int experimentId = -1) :
	  m_startInfo(startInfo)
	{
		m_stripId      = stripId;
		m_experimentId = experimentId;
		visited = false;
	}
	  
	// This is an experiment if the experiment id is >= 0
	inline bool IsExperiment () const { return m_experimentId >= 0; }
	  
	inline bool IsInStrip (const NvFaceInfo *faceInfo) const 
	{
		if(faceInfo == NULL)
			return false;
		  
		return (m_experimentId >= 0 ? faceInfo->m_testStripId == m_stripId : faceInfo->m_stripId == m_stripId);
	}
	  
	bool SharesEdge(const NvFaceInfo* faceInfo, NvEdgeInfoVec &edgeInfos) const;
	  
	// take the given forward and backward strips and combine them together
	void Combine(const NvFaceInfoVec &forward, const NvFaceInfoVec &backward);
	  
	//returns true if the face is "unique", i.e. has a vertex which doesn't exist in the faceVec
	bool Unique( NvFaceInfoVec& faceVec, const NvFaceInfo* face ) const;
	  
	// mark the triangle as taken by this strip
	bool IsMarked( const NvFaceInfo* faceInfo) const;
	void MarkTriangle(NvFaceInfo *faceInfo) const;
	  
	// build the strip
	void Build( NvEdgeInfoVec& edgeInfos, const NvFaceInfoVec& faceInfos );
	  
	// public data members
	NvStripStartInfo m_startInfo;
	NvFaceInfoVec    m_faces;
	int              m_stripId;
	int              m_experimentId;
	  
	bool visited;
};

//The actual stripifier
class NvStripifier {
public:
	
	// Constructor
    NvStripifier() { }
    ~NvStripifier() { }
	
	//the target vertex cache size, the structure to place the strips in, and the input indices
	void Stripify( const ::PS2Strip_Tri* in_pxTris,
                   u_int in_uNumTris,
                   u_int in_uMaxStripLength,
                   u_int in_uMaxVertexIndex,
                   bool in_bReorderFirstFaceOfStrips,
                   NvStripInfoVec* out_pxStrips,
                   u_int* out_puTotalVerts );
	
	static int GetUniqueVertexInB( const NvFaceInfo* faceA, const NvFaceInfo* faceB );
	static int GetSharedVertex( const NvFaceInfo* faceA, const NvFaceInfo* faceB );

	u_int GetNumberOfEdgesWithTooManyTriangles() const {return m_uEdgesWithTooManyTriangles;}

    void ReorderFirstFaceOfStrips( NvStripInfoVec* pxStrips ) const;
    
protected:
	
    const ::PS2Strip_Tri* m_pxSrcTris;
    unsigned m_uNumTris;

//	int cacheSize;
//	int minStripLength;
	float meshJump;
	bool bFirstTimeResetPoint;
	u_int m_uEdgesWithTooManyTriangles;
	
	/////////////////////////////////////////////////////////////////////////////////
	//
	// Big mess of functions called during stripification
	//
	/////////////////////////////////////////////////////////////////////////////////
	
	static int GetNextIndex( const IndexVec &indices, const NvFaceInfo* face );
	static NvEdgeInfo *FindEdgeInfo(NvEdgeInfoVec &edgeInfos, int v0, int v1);
	static NvFaceInfo* FindOtherFace(NvEdgeInfoVec &edgeInfos, int v0, int v1, const NvFaceInfo* faceInfo);
	NvFaceInfo *FindGoodResetPoint(NvFaceInfoVec &faceInfos, NvEdgeInfoVec &edgeInfos);
	
	void FindAllStrips(NvStripInfoVec &allStrips, NvFaceInfoVec &allFaceInfos, NvEdgeInfoVec &allEdgeInfos, int numSamples);
//	void SplitUpStripsAndOptimize(NvStripInfoVec &allStrips, NvStripInfoVec &outStrips, NvEdgeInfoVec& edgeInfos, NvFaceInfoVec& outFaceList);
    u_int SplitUpStripsIfNecessary( const NvStripInfoVec& in_xStrips, unsigned in_uMaxStripFaces, NvStripInfoVec* out_pxSplitStrips ) const;
//	void RemoveSmallStrips(NvStripInfoVec& allStrips, NvStripInfoVec& allBigStrips, NvFaceInfoVec& faceList);
	
	bool FindTraversal( const NvFaceInfoVec& faceInfos, NvEdgeInfoVec& edgeInfos, const NvStripInfo* strip, NvStripStartInfo& startInfo ) const;
	
	void CommitStrips(NvStripInfoVec &allStrips, const NvStripInfoVec &strips) const;
	
	float AvgStripSize( const NvStripInfoVec& strips ) const;
	int FindStartPoint(NvFaceInfoVec &faceInfos, NvEdgeInfoVec &edgeInfos) const;
	
	void UpdateCacheStrip( VertexCache* vcache, NvStripInfo* strip ) const;
	void UpdateCacheFace( VertexCache* vcache, const NvFaceInfo* face ) const;
	float CalcNumHitsStrip( const VertexCache* vcache, const NvStripInfo* strip) const;
	int CalcNumHitsFace( const VertexCache* vcache, const NvFaceInfo* face) const;
	int NumNeighbors( const NvFaceInfo* face, NvEdgeInfoVec& edgeInfoVec ) const;
	
	void BuildStripifyInfo( NvFaceInfoVec& faceInfos, NvEdgeInfoVec& edgeInfos, u_int uMaxVertexIndex );
	bool AlreadyExists( const NvFaceInfo* faceInfo, NvFaceInfoVec& faceInfos) const;
	
	// let our strip info classes and the other classes get
	// to these protected stripificaton methods if they want
	friend NvStripInfo;
};

// E N D   N A M E S P A C E /////////////////////////////////////////////////

} // namespace NVTriStrip.

// E N D   F I L E   W R A P P E R ///////////////////////////////////////////

#endif // #ifndef ___NVTRISTRIPOBJECTS_H___


