/*==========================================================================
 *	(C) 2005 Universidad Jaime I de Castellón
 *==========================================================================
 *	PROYECT:	GAME TOOLS
 *==========================================================================*/
/*	CONTENT:	Make triangle strips meshes from triangle list meshes.
 *
 *
 *	@file	GeoMeshStripifier.h
 *==========================================================================*/

#ifndef __GEO_STRIPIFIER__
#define __GEO_STRIPIFIER__

#include "GeoMesh.h"

	typedef int			BOOL;
	typedef void *	PVOID;


namespace Geometry
{

	#define TRIANGLE 3
	#define MAGNITUDE 1000000
	#define MAX_TIE 60
				
	#define	FALSE 0
	#define TRUE  1
	#define	LISTHEAD  0
	#define	LISTTAIL  1

	typedef struct
	{
    void  *Next;
    void  *Previous;
	}
	myNode, * PNODE;

	typedef struct List
	{
		/*  link to the next Listinfo Structure  */
		myNode     ListNode;

	/*  user definable data  */
	}
	ListInfo, *PLISTINFO;

	typedef struct LHead
	{
		PLISTINFO  LHeaders[2];
		int         NumList;
	}
	ListHead, *PLISTHEAD;

	#define PEEKFROMHEAD( lh, ind )     ( PeekList( (lh), LISTHEAD, (ind) ) )
	#define PEEKFROMTAIL( lh, ind )     ( PeekList( (lh), LISTTAIL, (ind) ) )
	#define EMPTYLIST( lh )             ( ( (lh)->LHeaders[LISTHEAD] == NULL ) )
	#define           NumOnList(lh) ( ((lh)->NumList)        )
	#define           GetNextNode(pli) ( ((pli)->ListNode.Next) )
	#define           GetPrevNode(pli) ( ((pli)->ListNode.Previous) )

//-----

	/**	polverts.h
	 */
	typedef struct adjacencies
	{
		myNode ListNode;
		int face_id;
	}ADJACENCIES,*P_ADJACENCIES;

	typedef struct FVerts
	{
		myNode ListNode;
		int *pPolygon;
		int nPolSize;
		int nId;
	} F_VERTS, *PF_VERTS;

	/*Every time we need to use this, cast it ( ListInfo*)*/
	typedef struct FEdges
	{
		myNode ListNode;
		int edge[3];
	}F_EDGES,*PF_EDGES;

	typedef struct FFaces
	{
		myNode ListNode;
		int *pPolygon;
		int *pNorms;
    int seen;
    int seen2;
    int seen3;
		int nPolSize;
    int nOrgSize;
		F_EDGES **VertandId;
		int *marked;
		int *walked;
	}F_FACES,*PF_FACES;
	
	typedef struct FVertices 
  { 
     myNode ListNode;
     PF_FACES face;
  }F_VERTICES, *PF_VERTICES;

	typedef struct Strips
	{
	myNode ListNode;
	int face_id;
	}Strips,*P_STRIPS;


	struct vert_added
  {
		int num;
		int *normal;
	};

	typedef struct face_adjacencies
	{
    P_ADJACENCIES pfNode;
    int bucket;
    ListHead *head;
  }
	FACE_ADJACENCIES, *P_FACE_ADJACENCIES;

	/**	global.h
	 */
	typedef std::vector<int> mi_vector_tipo;
	//std::vector<mi_vector_tipo> mi_vector;
	enum swap_type {ON,OFF};

	#define   VRDATA		double
	#define   MAX1            60
	
	#define   GEO_PI	     	3.1415926573
	#define   ATOI(C)        (C -'0')
	#define   EVEN(x)       (((x) & 1) == 0)
	#define   MAX_BAND      10000

	struct vert_struct
	{
		VRDATA	x, y, z;	/* point coordinates */
	};

	/// Stripifier interface class.
	/** This module implements methods that extract triangle strips from triangle meshes. 
		\n

Inputs:\n
	- This module receives a pointer to a Geometry::Mesh object containing the model to be stripified.
	.

Outputs:\n
	- The stripified mesh, contained also in a Geometry::Mesh object.
	.

	*/
	class MeshStripifier
	{
		public:
			/// Class constructor, receives as a parameter a const pointer to the object that describes a mesh.
			MeshStripifier ();
			MeshStripifier (const Geometry::Mesh *);

			/// virtual class destructor.
			virtual ~MeshStripifier (void);

			/// Copy constructor
			//MeshStripifier(const MeshStripifier&);

			/// Assignment operator
			//MeshStripifier& operator =(const MeshStripifier&);

			/// Starts the stripification process. This is a pure virtual method and must be overloaded in a derived class that implements a stripification algorithm.
			virtual int Stripify()=0;

			/// Returns the stripified mesh.
			Mesh *	GetMesh ();

			// Sets what is the mesh that stores the leaves
			void setSubMeshLeaves(size_t);

		protected:

			//	Progress bar function.
			Geometry::TIPOFUNC mUPB;

			//	Mesh object.
			Geometry::Mesh		*mGeoMesh;

			//	Index of the submesh leaves.
			size_t	mSubMeshLeaves;
	};

	class CustomStripifier : public MeshStripifier
	{
		private:

			/*      Globals */
			int	mError;	//	0	OK.
			//	1	Error:	The mesh is not Manifold.
			int num_faces;
			ListHead **PolFaces;
			ListHead **PolEdges;
			ListHead *array[60];
			P_FACE_ADJACENCIES face_array;  /* Pointers from face_id to face   */
			ListHead **Vertices;            /* Pointers from vertex_id to face */
			ListHead *strips[1];
			int orient;
			int num_tiras;
			int ids[MAX1];
			int norms[MAX1];
			int *vert_norms;
			int *vert_texture;
			int out1;//= -1;			//	static.
			int out2;//= -1;			//	static.
			int ties_array[60];	//	static.
			int last;//= 0;				//	static.
			int out1Ex;// = -1;		//	static.
			int out2Ex;// = -1;		//	static.
			int *vn;
			int *vt;
			int norm;	//	static.
			int text;	//	static.
			BOOL resetting;// = FALSE;		//	static.
			int 	added_quad;// = 0;	//	static.
			BOOL reversed;// = FALSE;		//	static.
			int patch;// = 0;					//	static.

			/**	global.h
			*/
			std::vector<mi_vector_tipo> mi_vector;

			/**	auxiliar.h
			*/
			Geometry::Mesh *MeshGlobal;
			// Structures for the object.
			vert_struct		*vertices;
			vert_struct		*nvertices;
			vert_struct		*pvertices;
			vert_struct		*pnvertices;

			/*   General utility routines   */
			/*        %%s QueRoutines          */
			BOOL    InitList      ( PLISTHEAD );

			/*****************************************************************
InitList :  Initialize a new list structure for use with the List
routines

INPUTS   :  LHead : a pointer to a ListHead structure.
OUTPUT   :  a boolean value TRUE if no errors occured FALSE
otherwise
			 ******************************************************************/


			PLISTINFO  PeekList( PLISTHEAD, int, int   );

			/*****************************************************************
PeekList :  This funciton peeks down a list for the N'th element
from the HEAD or TAIL of the list

INPUTS   :  LHead    :  a pointer to a List head structure.
from     :  can either search from the HEAD or TAIL
of the list
where    :  how many nodes from the begining should the
List routines look.
OUTPUT   :  a pointer to a ListInfo structure identified by
from/where or NULL if an error occurred.
			 ******************************************************************/


			PLISTINFO   RemoveList( PLISTHEAD LHead, PLISTINFO LInfo );


			/*****************************************************************
RemoveList: Remove a ListInfo structure from a List.

INPUTS    : LHead  :  a pointer to a ListHead structure.
LInfo  :  a pointer to the ListInfo structure to remove
from the list.
OUTPUT    : a pointer to the ListInfo structure that was removed or
NULL if an error occurred.
			 ******************************************************************/

			BOOL  InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo );

			/*****************************************************************
InsertNode: add a node to a list after a given node

INPUTS    : LHead : a pointer to a ListHead structure.
nPos  : the position to insert the node into
LInfo : a pointer to the new node to add to the list.
OUTPUT: a boolean value TRUE if all goes well false otherwise
			 *****************************************************************/

			BOOL   AddHead       ( PLISTHEAD, PLISTINFO );

			/*****************************************************************
AddHead   : add a ListInfo structure to the HEAD of a list.

INPUTS    : LHead  : a pointer to a ListHead structure of the list
to add to.
LInfo  : a pointer to the ListInfo structure to add to
the list.
OUTPUT    : A boolean value TRUE if no errors occurred FALSE
otherwise.
			 ******************************************************************/


			BOOL     AddTail       ( PLISTHEAD, PLISTINFO );

			/*****************************************************************
AddTail   : Add a ListInfo structure to the TAIL of a list.

INPUTS    : LHead  : a pointer to a ListHead structure of the List
to add to.
LInfo  : a pointer to the ListInfo structure to add to
the List.
OUTPUT    : a boolean value TRUE if no errors occurred FALSE
otherwise.
			 ******************************************************************/


			PLISTINFO  RemTail       ( PLISTHEAD );

			/*****************************************************************
RemTail   : Remove a ListInfo structure from the TAIL of a List.

INPUTS    : LHead  : a pointer to a ListHead structure of the List
to remove from.
OUTPUT    : a pointer to the ListInfo structure that was removed
or NULL if an error occurred.
			 ******************************************************************/


			PLISTINFO  RemHead       ( PLISTHEAD );

			/*****************************************************************
RemHead   : Remove a ListInfo structure from the Head of a List.

INPUTS    : LHead  : a pointer to a ListHead structure of the List
to remove from.
OUTPUT    : a pointer to the ListInfo structure that was removed or
NULL if an error occurred.
			 ******************************************************************/

			PLISTINFO  SearchList(
					PLISTHEAD lpListHead,
					PVOID lpSKey,
					int ( * CompareCallBack) ( PVOID, PVOID ) );

			/*****************************************************************
SearchList:
Try to find a specific node in the queue whose key matches with
searching key. Return the pointer to that node if found, return NULL
otherwise

Input:
lpHashTbl       => a far pointer to the hash table
lpKey           => a far poniter to searching key
CompareCallBack => comparision function

Output: a far pointer to the node to be found

			 ******************************************************************/

			/**	init.h
			*/
			BOOL InitVertexTable(int nSize);
			BOOL InitFaceTable(int nSize);
			BOOL InitEdgeTable(int nSize);
			void BuildFaceTable(int nSize);
			void BuildVertexTable(int nSize);
			void BuildEdgeTable(int nSize);
			void init_vert_norms(int num_vert);
			void init_vert_texture(int num_vert);
			void InitStripTable();
			void Init_Table_SGI(int numfaces);
			void Start_Vertex_Struct(int numverts);
			void Start_Face_Struct(int numfaces);
			void Start_Edge_Struct(int numverts);

			/**	util.h
			*/
			void switch_lower(int *x, int *y);
			BOOL member(int x , int id1, int id2, int id3);
			BOOL Exist(int face_id, int id1, int id2);
			int Different(	int id1,int id2,int id3,int id4,int id5,
					int id6, int *x, int *y);
			int Return_Other(int *index,int e1,int e2);
			int Get_Other_Vertex(int id1,int id2,int id3,int *index);
			PLISTINFO Done(int face_id,  int *bucket);
			void First_Edge(int *id1,int *id2, int *id3);
			void Last_Edge(int *id1, int *id2, int *id3, BOOL save);

			void preserve_strip_orientation_with_normal(
					int		vertex1,
					int		normal1,
					int		vertex2,
					int		normal2,
					int		vertex3,
					int		normal3);

			void preserve_strip_orientation_with_texture(
					int		vertex1,
					int		texture1,
					int		vertex2,
					int		texture2,
					int		vertex3,
					int texture3);

			void  preserve_strip_orientation_with_texture_and_normal(
					int		vertex1,
					int		texture1,
					int		normal1,
					int		vertex2,
					int		texture2,
					int		normal2,
					int		vertex3,
					int		texture3,
					int		normal3);

			void preserve_strip_orientation(
					int vertex1,
					int vertex2,
					int vertex3);

			void find_triangle_orientation(	int vertex1,
					int vertex2,
					int vertex3,
					int *original_vertex);

			/**	local.h
			*/
			void Find_StripsEx(int *ties, int  tie,	int triangulate, int  swaps, int *next_id);
			void SGI_Strip(int num_faces,int ties,int triangulate);

			/**	outputex.h
			*/
			void Output_TriEx(int id1, int id2, int id3, int flag,int where);
			void Extend_BackwardsEx(int face_id, int *ties, 
					int tie, int triangulate, 
					int swaps,int *next_id);
			void Polygon_OutputEx(P_ADJACENCIES temp,int face_id,int bucket,
					ListHead *pListHead,
					int *ties, int tie,int triangulate, int swaps,
					int *next_id, int where);

			/**	sgi_triang.h
			*/
			int Adjacent(int id2,int id1, int *list, int size);
			void Build_SGI_Table(int num_faces);
			void Non_Blind_Triangulate(	int size,int *index,
					int next_face_id,
					int face_id,int where,
					int color1,int color2,int color3);
			void Blind_Triangulate(int size, int *index, BOOL begin, int where);
			void Rearrange_Index(int *index, int size);	//	static.
			void Delete_From_List(int id,int *list, int *size);	//	static.
			void Triangulate_Quad(int out_edge1,int out_edge2,int in_edge1,
					int in_edge2,int size,int *index,
					int reversed,int where);	//	static.
			void Triangulate_Polygon(	int out_edge1,int out_edge2,
					int in_edge1,	int in_edge2,
					int size,			int *index,
					int reversed,
					int face_id,	int where,
					int color1,		int color2,
					int color3);	//	static.

			void Triangulate(	int out_edge1,int out_edge2,int in_edge1,
					int in_edge2,int size,int *index,
					int reversed,int face_id, int where,
					int color1, int color2,int color3);	//	static.

			/**	struct.h
			*/
			int Get_Edge(	int *edge1,int *edge2,
					int *index,int face_id,
					int size, int id1, int id2);
			int Update_Adjacencies(	int face_id,int *next_bucket,
					int *e1,int *e2,int *ties);
			void Update_Face(	int *next_bucket, int *min_face,
					int face_id, 			int *e1,
					int *e2,					int temp1,
					int temp2,				int *ties);	//	static.
			void Delete_Adj(int id1, int id2,int *next_bucket,
					int *min_face,int current_face,int *e1,
					int *e2,int *ties);	//	static.
			/**	common.h
			*/
			int  Old_Adj(int face_id);
			int Number_Adj(int id1, int id2, int curr_id);
			int Min_Adj(int id);
			void Check_In_Polygon(int face_id, int *min, int size);
			void New_Face (int face_id, int v1, int v2, int v3);
			void New_Size_Face(int face_id);
			void Check_In_Quad(int face_id,int *min);
			int Get_Output_Edge(int face_id, int size, int *index,int id2,int id3);
			void Get_Input_Edge(int *index,int id1,
					int id2,int id3,
					int *new1,int *new2,
					int size,int face_id);
			int Find_Face(int current_face, int id1,
					int id2, int *bucket);
			BOOL Look_Up(int id1,int id2,int face_id);
			void Add_Id_Strips(int id, int where);
			int Num_Adj(int id1, int id2);
			void Add_Sgi_Adj(int bucket,int face_id);
			void Find_Adjacencies(int num_faces);
			void Edge_Least(int *index,int *new1,
					int *new2,int face_id,int size);	//	static.

			/**	ties.h
			*/
			void Clear_Ties();
			void Add_Ties(int id);
			int Get_Next_Face(int t, int face_id, int triangulate);
			int Alternate_Tie();	//	static.
			int Random_Tie();			//	static.
			int Look_Ahead(int id);	//	static.
			int Random_Look(int id[],int count);	//	static.
			int Look_Ahead_Tie();	//	static.
			int Sequential_Tri(int *index);	//	static.
			int Sequential_Quad(int *index,	int triangulate);	//	static.
			void Whole_Output(int in1,	int *index, int size,
					int *out1,int *out2);	//	static.
			int Sequential_Poly(int size,int *index,int triangulate);	//	static.
			int Sequential_Tie(int face_id,int triangulate);	//	static.

			/**	add.h
			*/
			BOOL norm_array(int id,int vertex,
					double normal_difference,
					struct vert_struct *n,int num_vert);
			void add_texture(int id,BOOL vertex);
			int  add_vert_id(int id, int index_count);
			void add_norm_id(int id, int index_count);
			void AddNewFace(int ids[MAX1],int vert_count,
					int face_id,int norms[MAX1]);
			void CopyFace(int ids[MAX1],int vert_count,
					int face_id,int norms[MAX1]);
			void Add_AdjEdge(	int v1,int v2,
					int fnum,int index1);
			BOOL new_vertex(double difference,int id1,
					int id2,struct vert_struct *n);	//	static.
			BOOL Check_VN(int vertex,int normal, struct vert_added *added);	//	static.

			/**	options.h
			*/
			enum file_options {ASCII,BINARY};
			enum tie_options {FIRST, RANDOM, ALTERNA, LOOK, SEQUENTIAL};
			enum triangulation_options {PARTIAL,WHOLE};

			void print_usage(void);
			float get_options(int argc,	char **argv,
					int *f,		int *t,
					int *tr,	int *group,
					int *orientation);
			int power_10(int power);	//	static.
			float power_negative(int power);	//	static.
			float convert_array(int num[],int stack_size);	//	static.

			/**	sgi_triangex.h
			*/
			int AdjacentEx(int id2,int id1, int *list, int size);
			void Delete_From_ListEx(int id,int *list, int size);
			void Triangulate_PolygonEx(	int out_edge1,int out_edge2,int in_edge1,
					int in_edge2,int size,int *index,
					int reversed,int face_id,
					int where);
			void Non_Blind_TriangulateEx(	int size,int *index,
					int next_face_id,
					int face_id,int where);
			void Rearrange_IndexEx(int *index, int size);
			void Blind_TriangulateEx(	int size,		int *index,
					BOOL begin, int where);
			void Triangulate_QuadEx(int out_edge1,int out_edge2,int in_edge1,
					int in_edge2,	int size,			int *index,
					int reversed,	int where);	//	static.
			void TriangulateEx(	int out_edge1,int out_edge2,
					int in_edge1, int in_edge2,
					int size,			int *index,
					int reversed,
					int face_id, 	int where);	//	static.

			/**	structex.h
			*/
			int Get_EdgeEx(	int *edge1,int *edge2,int *index,int face_id,
					int size, int id1, int id2);
			void Delete_AdjEx(int id1, int id2,
					int *next_bucket,int *min_face, 
					int current_face,int *e1,
					int *e2,int *ties);
			int Change_FaceEx(int face_id,int in1,int in2,
					ListHead *pListHead, BOOL no_check);
			int Update_AdjacenciesEx(	int face_id,int *next_bucket,
					int *e1, int *e2,
					int *ties);
			int Min_Face_AdjEx(int face_id,int *next_bucket,int *ties);

			void Update_FaceEx(	int *next_bucket,int *min_face,
					int face_id, int *e1,
					int *e2,int temp1,
					int temp2,int *ties);	//	static.

			void Find_Adj_TallyEx(int id1, 					int id2,
					int *next_bucket,	int *min_face,
					int current_face,	int *ties);	//	static.

			/**	partial.h
			*/
			void Partial_Triangulate(int size,		int *index,
					int next_face_id,
					int face_id,	int *next_id,
					ListHead *pListHead,
					P_ADJACENCIES temp, int where);


			void Inside_Polygon(int size,			int *index,
					int face_id,	ListHead *pListHead,
					int where);

			void P_Triangulate_Quad(int out_edge1,int out_edge2,
					int in_edge1, int in_edge2,
					int size,			int *index,
					int reversed, int face_id,
					ListHead *pListHead, 
					P_ADJACENCIES temp,
					int where);	//	static.
			void P_Triangulate_Polygon(	int out_edge1,int out_edge2,
					int in_edge1, int in_edge2,
					int size,	  	int *index,
					int reversed,
					int face_id,	int *next_id,
					ListHead *pListHead,
					P_ADJACENCIES temp2,
					int where);	//	static.
			void P_Triangulate(	int out_edge1,int out_edge2,int in_edge1,
					int in_edge2,	int size,			int *index,
					int reversed,	int face_id,
					int *next_id,	ListHead *pListHead, 
					P_ADJACENCIES temp,int where);	//	static.
			void Input_Edge(int face_id,	int *index,
					int size, 		int in_edge1,
					int in_edge2, ListHead *pListHead,
					int where);	//	static.

			/**	output.h
			*/
			int Finished(int *swap, int startnewstrip);
			void Output_Tri(int id1, int id2, int id3,BOOL end);
			int Extend_Face(int face_id,int e1,int e2,int *swaps,
					int color1,int color2,int color3,int *vert_norm,
					int normals,int *vert_texture,int texture);
			int Polygon_Output(	P_ADJACENCIES temp,	int face_id,
					int bucket,		  		ListHead *pListHead,
					BOOL first, 				int *swaps,
					int color1,					int color2,					
					int color3,
					BOOL global,		  	BOOL end);	//	static.
			/**	free.h
			*/
			void Free_Strips();
			void End_Face_Struct(int numfaces);
			void End_Edge_Struct(int numverts);
			void ParseAndFreeList( ListHead *pListHead );	//	static.
			void FreeFaceTable(int nSize);	//	static.
			void FreeEdgeTable(int nSize);	//	static.

			/**	newpolve.h
			*/
			void Find_Bands(int numfaces, int *swaps, int *bands, 
					int *cost, int *tri, int norms, int *vert_norms,
					int texture, int *vert_texture);
			void Save_Walks(int numfaces);
			void Save_Rest(int *numfaces);
			int Calculate_Walks(int lastvert,int y, PF_FACES temp2);	//	static.
			BOOL Check_Right(	int last_seen,PF_FACES temp2,
					int y,int face_id);		//	static.
			int Update_and_Test(PF_FACES temp2,int y,
					BOOL first,int distance,
					int lastvert, int val);	//	static.
			int Test_Adj(	PF_FACES temp2,int x,
					int north,int distance,
					int lastvert, int value);	//	static.
			int Find_Max(	PF_FACES temp2,	int lastvert,
					int north,			int left,
					int *lastminup,	int *lastminleft);	//	static.
			void Mark_Face(	PF_FACES temp2, 		int color1,
					int color2,     		int color3,
					BOOL end,
					int *edge1,					int *edge2,
					int *face_id,				int norms,
					int texture);	//	static.
			void Assign_Walk(	int lastvert,		PF_FACES temp2,
					int front_walk,	int y,
					int back_walk);	//	static.
			void Fast_Reset(int x);	//	static.
			void Reset_Max(	PF_FACES temp2,int face_id,
					int north,int last_north,
					int orientation,int last_left,
					int color1,
					int color2,int color3,
					BOOL start);	//	static.
			int Peel_Max(	PF_FACES temp2,int face_id,
					int north,int last_north,
					int orientation,int last_left,
					int color1,
					int color2,int color3,
					BOOL start, int *swaps_added,
					int norms, int texture);	//	static.

			/**	auxiliar.h
			*/
//			FILE *OpenOutputFile(char *fname);
			void AllocateStruct(int num_faces,
					int num_vert,
					int num_nvert,
					int num_texture);
			void miReadFile(char *fname, char *file_open, Geometry::SubMesh *geoSubMesh);
			int stripify(	char						*fname,
										Geometry::Mesh	*geoMesh);

		public:
			/// Class constructor, receives as a parameter a const pointer to the object that describes a mesh.
			CustomStripifier();

			CustomStripifier(const Geometry::Mesh *geoMesh);

			/// Class destructor.
			~CustomStripifier(void);

			/// Copy constructor
			//CustomStripifier(const CustomStripifier&);

			/// Assignment operator
			//CustomStripifier& operator =(const CustomStripifier&);

			/// Starts the stripification process. This is a custom stripification method.
			int Stripify();

			/// Returns the stripified mesh.
			Mesh *	GetMesh();

			//	Set the progress bar function.
			void	SetProgressFunc(Geometry::TIPOFUNC upb);

			// Sets what is the submesh that stores the leaves
			void SetSubMeshLeaves(size_t	submesh);

	};

}

#endif