/*
								+----------------------------------+
								|                                  |
								| ***  Triangle strip builder  *** |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|            Stripify.h            |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __TRI_STRIP_BUILDER_INCLUDED
#define __TRI_STRIP_BUILDER_INCLUDED

/**
 *	@file dev/Stripify.h
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief Triangle strip builder
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 */

#include "TinyVector.h"

/*
 *	class CStripBuilder
 *		- triangle strip builder (quads strip might be handled in future as well)
 */
class CStripBuilder {
public:
	/*
	 *	struct CStripBuilder::TEdge
	 *		- polygon edge
	 */
	struct TEdge {
		int p_vertex[2]; // vertex group
		int n_polygon; // source polygon
		int n_side; // side of polygon (side n = vertex[n] and vertex[(n + 1) % polygon.size()])

		/*
		 *	inline CStripBuilder::TEdge::TEdge()
		 *		- default constructor, has no effect
		 */
		inline TEdge()
		{}

		/*
		 *	inline CStripBuilder::TEdge::TEdge(int n_vertex_a,
		 *		int n_vertex_b, int _n_polygon, int _n_side)
		 *		- constructor; fills edge structure
		 *		- n_vertex_a and n_vertex_b are vertex group id's,
		 *		  _n_polygon is polygon index and _n_side is index of edge
		 *		  on that particular polygon (side n is edge formed by vertices
		 *		  vertex[n] and vertex[(n + 1) % polygon.size()])
		 */
		inline TEdge(int n_vertex_a, int n_vertex_b, int _n_polygon, int _n_side)
			:n_polygon(_n_polygon), n_side(_n_side)
		{
			p_vertex[0] = n_vertex_a;
			p_vertex[1] = n_vertex_b;
		}

		/*
		 *	inline bool CStripBuilder::TEdge::operator <(const TEdge &r_t_edge) const
		 *		- less-than operator for sorting
		 */
		inline bool operator <(const TEdge &r_t_edge) const
		{
			return p_vertex[0] < r_t_edge.p_vertex[0] ||
				(p_vertex[0] == r_t_edge.p_vertex[0] && p_vertex[1] < r_t_edge.p_vertex[1]);
		}
	};

	/*
	 *	static bool CStripBuilder::MakeEdgeList(std::vector<TEdge> &r_edge_list,
	 *		const CPolyMesh &r_mesh, const int *p_vertex_merge_table)
	 *		- creates list of polygon edges, stores results in r_edge_list
	 *		  (note r_edge_list is erased upon beginning)
	 *		- r_mesh is polygon mesh and p_vertex_merge_table is array,
	 *		  containing group id for each vertex in r_mesh (can be obtained
	 *		  by calling CPolyMesh::CVertexMergeTable::p_VertexIndexTable())
	 *		- returns true on success, false on failure
	 */
	static bool MakeEdgeList(std::vector<TEdge> &r_edge_list,
		const CPolyMesh &r_mesh, const int *p_vertex_merge_table);

	/*
	 *	struct CStripBuilder::TNeighbour
	 *		- information about neighbour on some particular edge
	 *		- contains polygon index and index of shared edge
	 */
	struct TNeighbour {
		int n_polygon, n_side;

		/*
		 *	inline CStripBuilder::TNeighbour::TNeighbour()
		 *		- default constructor; has no effect
		 */
		inline TNeighbour()
		{}

		/*
		 *	inline CStripBuilder::TNeighbour::TNeighbour(int n_poly, int _n_side)
		 *		- constructor
		 *		- n_poly is polygon inex, _n_side is shared edge index
		 */
		inline TNeighbour(int n_poly, int _n_side)
			:n_polygon(n_poly), n_side(_n_side)
		{}

		/*
		 *	inline bool CStripBuilder::TNeighbour::operator ==(
		 *		const TNeighbour &r_t_neighbour) const
		 *		- equality comparison operator
		 */
		inline bool operator ==(const TNeighbour &r_t_neighbour) const
		{
			return n_polygon == r_t_neighbour.n_polygon && n_side == r_t_neighbour.n_side;
		}

		/*
		 *	inline bool CStripBuilder::TNeighbour::operator !=(
		 *		const TNeighbour &r_t_neighbour) const
		 *		- inequality comparison operator
		 */
		inline bool operator !=(const TNeighbour &r_t_neighbour) const
		{
			return !(*this == r_t_neighbour);
		}
	};

	/*
	 *	struct CStripBuilder::TNeighbourInfo
	 *		- information about all neighbours on all polygon edges
	 */
	struct TNeighbourInfo {
		/*
		 *	CStripBuilder::TNeighbourInfo::<unnamed_0>
		 *		- names for edge direction
		 *		- affects which edges neighbours are found by
		 */
		enum {
			edge_Parallel = 1,
			edge_AntiParallel,
			edge_Any
		};

		int n_side_num;
		tiny_vector<TNeighbour> *p_neighbour_list; // todo - see memory and speed effect of chaging this to std::vector

		static const TNeighbour t_terminator; // = TNeighbour(-1, -1)

		/*
		 *	CStripBuilder::TNeighbourInfo::TNeighbourInfo()
		 *		- default constructor; sets p_neighbour_list to null
		 */
		TNeighbourInfo();

		/*
		 *	CStripBuilder::TNeighbourInfo::~TNeighbourInfo()
		 *		- destructor; deletes p_neighbour_list if not null
		 */
		~TNeighbourInfo();

		/*
		 *	bool CStripBuilder::TNeighbourInfo::Alloc(int _n_side_num)
		 *		- allocates list of neighbour lists to _n_side_num
		 *		- returns true on success, false on failure (n_side_num is set to 0)
		 */
		bool Alloc(int _n_side_num);

		/*
		 *	bool CStripBuilder::TNeighbourInfo::Create(const std::vector<TEdge> &r_edge_list,
		 *		const CPolyMesh &r_mesh, const int *p_vertex_merge_table, int n_polygon,
		 *		int n_edge_flags = edge_Any, bool b_material_separation = false)
		 *		- allocates and fills neighbour lists
		 *		- r_edge_list is sorted edge list (result of CStripBuilder::MakeEdgeList())
		 *		- r_mesh is polygon mesh and p_vertex_merge_table is array,
		 *		  containing group id for each vertex in r_mesh (can be obtained
		 *		  by calling CPolyMesh::CVertexMergeTable::p_VertexIndexTable())
		 *		- n_polygon is polygon index in r_mesh
		 *		- n_edge_flags is one of edge_Parallel, edge_AntiParallel or edge_Any
		 *		  (vertex order of found edges)
		 *		- setting b_material_separation causes no polygons with different material
		 *		  can be neighbors
		 *		- returns true on success, false on failure
		 *		- note this is not very effective because polygon neighbourhood is the
		 *		  same information for each polygon sharing the edge and it could be exploited
		 */
		bool Create(const std::vector<TEdge> &r_edge_list, const CPolyMesh &r_mesh,
			const int *p_vertex_merge_table, int n_polygon,
			int n_edge_flags = edge_Any, bool b_material_separation = false);

		/*
		 *	static CStripBuilder::TNeighbourInfo *CStripBuilder::TNeighbourInfo::p_CreateAll(
		 *		const std::vector<TEdge> &r_edge_list, const CPolyMesh &r_mesh,
		 *		const int *p_vertex_merge_table, int n_edge_flags = edge_Any,,
		 *		bool b_material_separation = false)
		 *		- creates neighbour information for all polygons in the mesh
		 *		- r_edge_list is sorted edge list (result of CStripBuilder::MakeEdgeList())
		 *		- r_mesh is polygon mesh and p_vertex_merge_table is array,
		 *		  containing group id for each vertex in r_mesh (can be obtained
		 *		  by calling CPolyMesh::CVertexMergeTable::p_VertexIndexTable())
		 *		- n_edge_flags is one of edge_Parallel, edge_AntiParallel or edge_Any
		 *		  (vertex order of found edges)
		 *		- setting b_material_separation causes no polygons with different material
		 *		  can be neighbors
		 *		- returns array of TNeighbourInfo as long as r_mesh.n_Poly_Num(), 0 on failure
		 *		- note this is about twice as fast as calling Create() for each
		 *		  polygon's neighbour info (on meshes where every polygon has a single
		 *		  neighbour on each of it's edges).
		 */
		static TNeighbourInfo *p_CreateAll(const std::vector<TEdge> &r_edge_list,
			const CPolyMesh &r_mesh, const int *p_vertex_merge_table,
			int n_edge_flags = edge_Any, bool b_material_separation = false);
	};

	/*
	 *	struct CStripBuilder::TPrimBatch
	 *		- primitive batch description; contains type (GL_TRIANGLE_STRIP, GL_TRIANGLES,
	 *		  etc ...), id of material used to draw the triangles and list of vertex indices
	 */
	struct TPrimBatch {
		int n_material;
		int n_type; // GL_TRIANGLE_STRIP
		int n_vertex_num;
		int *p_vertex;
	};

	/*
	 *	static bool Greedy_Strips(std::vector<TPrimBatch> &r_strip_list,
	 *		const CPolyMesh &r_mesh, const TNeighbourInfo *p_neighbour_info)
	 *		- the most basic tri-stripify function (begins with triangle with least
	 *		  neighbours and makes strip as long as possible)
	 *		- note this works with triangular meshes only
	 *		- r_mesh is polygon mesh (containing triangles), p_neighbour_info is triangle
	 *		  connectivity info
	 *		- resulting triangle strips are stored to r_strip_list (cleared on the beginning)
	 *		- returns true on success, false on failure
	 */
	static bool Greedy_Strips(std::vector<TPrimBatch> &r_strip_list,
		const CPolyMesh &r_mesh, const TNeighbourInfo *p_neighbour_info); // todo
};

#endif // __TRI_STRIP_BUILDER_INCLUDED
