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

/**
 *	@file dev/Stripify.cpp
 *	@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 "../NewFix.h"

#include "../CallStack.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include "../Vector.h"
#include "PolyMesh.h"
#include "TinyVector.h"
#include "Stripify.h"
#include "../StlUtils.h"

/*
 *								=== CStripBuilder ===
 */

/*
 *	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
 */
bool CStripBuilder::MakeEdgeList(std::vector<TEdge> &r_edge_list,
	const CPolyMesh &r_mesh, const int *p_vertex_merge_table)
{
	r_edge_list.clear();
	// make sure edge list is empty

	stl_ut::Reserve_N(r_edge_list, r_mesh.n_Poly_Num() * 3);
	// reserve space for some edges (minimum; polygons may have more than 3 edges)

	const CVertexPool<CPolyMesh::TVertex> &r_vertex_pool = r_mesh.Vertex_Pool();
	// get vertex pool

	for(int i = 0, n = r_mesh.n_Poly_Num(); i < n; ++ i) {
		const CPolyMesh::CPolygon &r_poly = r_mesh.r_Polygon(i);
		// get polygon

		_ASSERTE(r_poly.n_Vertex_Num());
		if(!r_poly.n_Vertex_Num())
			continue;
		// skip empty polygons (shouldn't be there anyway)

		if(!stl_ut::Reserve_NMore(r_edge_list, r_poly.n_Vertex_Num()))
			return false;
		// make sure there's enough space in the list

		int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex(0).m_p_ref);
		_ASSERTE(n_index_1 != -1);
		int n_vertex_1 = p_vertex_merge_table[n_index_1];
		for(int j = 0, m = r_poly.n_Vertex_Num(); j < m; ++ j) {
			int n_vertex_0 = n_vertex_1;
			int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex((j + 1) % m).m_p_ref);
			_ASSERTE(n_index_1 != -1);
			n_vertex_1 = p_vertex_merge_table[n_index_1];
			// get group id's for edge vertices

			r_edge_list.push_back(TEdge(n_vertex_0, n_vertex_1, i, j));
			// create edge
		}
		// add all polygon edges
	}

	std::sort(r_edge_list.begin(), r_edge_list.end());
	// sort edges so it's possible to do binary searches in them

	return true;
}

/*
 *								=== ~CStripBuilder ===
 */

/*
 *								=== CStripBuilder::TNeighbourInfo ===
 */

const CStripBuilder::TNeighbour CStripBuilder::TNeighbourInfo::t_terminator(-1, -1);

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

/*
 *	CStripBuilder::TNeighbourInfo::~TNeighbourInfo()
 *		- destructor; deletes p_neighbour_list if not null
 */
CStripBuilder::TNeighbourInfo::~TNeighbourInfo()
{
	if(p_neighbour_list)
		delete[] p_neighbour_list;
}

/*
 *	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 CStripBuilder::TNeighbourInfo::Alloc(int _n_side_num)
{
	if(p_neighbour_list)
		delete[] p_neighbour_list;
	// cleanup old lists

	if(!(p_neighbour_list = new(std::nothrow) tiny_vector<TNeighbour>[n_side_num = _n_side_num])) {
		n_side_num = 0;
		return false;
	}
	// alloc new lists

	return true;
}

/*
 *	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 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, bool b_material_separation)
{
	const CVertexPool<CPolyMesh::TVertex> &r_vertex_pool = r_mesh.Vertex_Pool();
	// get vertex pool

	const CPolyMesh::CPolygon &r_poly = r_mesh.r_Polygon(n_polygon);
	// get polygon

	int n_material = r_poly.n_Material();
	// get polygon material

	if(!Alloc(r_poly.n_Vertex_Num()))
		return false;
	// alloc (and clear) neighbour lists

	int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex(0).m_p_ref);
	_ASSERTE(n_index_1 != -1);
	int n_vertex_1 = p_vertex_merge_table[n_index_1];
	for(int i = 0, n = r_poly.n_Vertex_Num(); i < n; ++ i) {
		int n_vertex_0 = n_vertex_1;
		int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex((i + 1) % n).m_p_ref);
		_ASSERTE(n_index_1 != -1);
		n_vertex_1 = p_vertex_merge_table[n_index_1];
		// get group id's for edge vertices

		if(n_edge_flags == edge_Parallel || n_edge_flags == edge_Any) {
			std::vector<TEdge>::const_iterator p_edge_it = std::lower_bound(r_edge_list.begin(),
				r_edge_list.end(), TEdge(n_vertex_0, n_vertex_1, n_polygon, i));
			// find edge with the same vertices

			for(; p_edge_it != r_edge_list.end() && (*p_edge_it).p_vertex[0] == n_vertex_1 &&
			   (*p_edge_it).p_vertex[1] == n_vertex_0; ++ p_edge_it) {
				if(b_material_separation &&
				   n_material != r_mesh.r_Polygon((*p_edge_it).n_polygon).n_Material())
					continue;
				// material separation

				p_neighbour_list[i].push_back(
					TNeighbour((*p_edge_it).n_polygon, (*p_edge_it).n_side), t_terminator);
				if(!p_neighbour_list[i].empty()) // this is tiny_vector, not std::vector
					return false;
				// add neighbour to the list
			}
			// find all polygons, sharing this edge, and their indices of this edge
		}
		if(n_edge_flags == edge_AntiParallel || n_edge_flags == edge_Any) {
			std::vector<TEdge>::const_iterator p_edge_it = std::lower_bound(r_edge_list.begin(),
				r_edge_list.end(), TEdge(n_vertex_1, n_vertex_0, n_polygon, i));
			// find edge with swapped vertices

			for(; p_edge_it != r_edge_list.end() && (*p_edge_it).p_vertex[0] == n_vertex_1 &&
			   (*p_edge_it).p_vertex[1] == n_vertex_0; ++ p_edge_it) {
				if(b_material_separation &&
				   n_material != r_mesh.r_Polygon((*p_edge_it).n_polygon).n_Material())
					continue;
				// material separation

				p_neighbour_list[i].push_back(
					TNeighbour((*p_edge_it).n_polygon, (*p_edge_it).n_side), t_terminator);
				if(p_neighbour_list[i].empty()) // this is tiny_vector, not std::vector
					return false;
				// add neighbour to the list
			}
			// find all polygons, sharing this edge, and their indices of this edge
		}
	}

	return true;
}

/*
 *	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).
 */
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, bool b_material_separation)
{
	TNeighbourInfo *p_info_list;
	if(!(p_info_list = new(std::nothrow) TNeighbourInfo[r_mesh.n_Poly_Num()]))
		return 0;
	// alloc neighbour info's

	for(int i = 0, n = r_mesh.n_Poly_Num(); i < n; ++ i) {
		const CPolyMesh::CPolygon &r_poly = r_mesh.r_Polygon(i);
		if(!p_info_list[i].Alloc(r_poly.n_Vertex_Num())) {
			delete[] p_info_list;
			return 0;
		}
	}
	// alloc individual lists

	const CVertexPool<CPolyMesh::TVertex> &r_vertex_pool = r_mesh.Vertex_Pool();
	// get vertex pool

	TNeighbourInfo *p_neigh_info = p_info_list;
	for(int i = 0, n = r_mesh.n_Poly_Num(); i < n; ++ i, ++ p_neigh_info) {
		const CPolyMesh::CPolygon &r_poly = r_mesh.r_Polygon(i);
		// get polygon

		int n_material = r_poly.n_Material();
		// get polygon material

		int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex(0).m_p_ref);
		_ASSERTE(n_index_1 != -1);
		int n_vertex_1 = p_vertex_merge_table[n_index_1];
		for(int j = 0, m = r_poly.n_Vertex_Num(); j < m; ++ j) {
			int n_vertex_0 = n_vertex_1;
			int n_index_1 = r_vertex_pool.n_Index(r_poly.t_Vertex((j + 1) % m).m_p_ref);
			_ASSERTE(n_index_1 != -1);
			n_vertex_1 = p_vertex_merge_table[n_index_1];
			// get group id's for edge vertices

			if(n_edge_flags == edge_Parallel || n_edge_flags == edge_Any) {
				std::vector<TEdge>::const_iterator p_edge_it = std::lower_bound(r_edge_list.begin(),
					r_edge_list.end(), TEdge(n_vertex_0, n_vertex_1, i, j));
				// find edge with the same vertices

				for(; p_edge_it != r_edge_list.end() && (*p_edge_it).p_vertex[0] == n_vertex_1 &&
				   (*p_edge_it).p_vertex[1] == n_vertex_0; ++ p_edge_it) {
					if(b_material_separation &&
					   n_material != r_mesh.r_Polygon((*p_edge_it).n_polygon).n_Material())
						continue;
					// material separation

					p_neigh_info->p_neighbour_list[j].push_back(
						TNeighbour((*p_edge_it).n_polygon, (*p_edge_it).n_side), t_terminator);
					if(p_neigh_info->p_neighbour_list[j].empty()) // this is tiny_vector, not std::vector
						return false;
					// add neighbour to the list
				}
				// find all polygons, sharing this edge, and their indices of this edge
			}
			if(n_edge_flags == edge_AntiParallel || n_edge_flags == edge_Any) {
				std::vector<TEdge>::const_iterator p_edge_it = std::lower_bound(r_edge_list.begin(),
					r_edge_list.end(), TEdge(n_vertex_1, n_vertex_0, i, j));
				// find edge with swapped vertices

				for(; p_edge_it != r_edge_list.end() && (*p_edge_it).p_vertex[0] == n_vertex_1 &&
				   (*p_edge_it).p_vertex[1] == n_vertex_0; ++ p_edge_it) {
					if(b_material_separation &&
					   n_material != r_mesh.r_Polygon((*p_edge_it).n_polygon).n_Material())
						continue;
					// material separation

					p_neigh_info->p_neighbour_list[j].push_back(
						TNeighbour((*p_edge_it).n_polygon, (*p_edge_it).n_side), t_terminator);
					if(p_neigh_info->p_neighbour_list[j].empty()) // this is tiny_vector, not std::vector
						return false;
					// add neighbour to the list
				}
				// find all polygons, sharing this edge, and their indices of this edge
			}
		}
	}

	// todo - optimize

	return p_info_list;
}

/*
 *								=== ~CStripBuilder::TNeighbourInfo ===
 */

/*
 *								===  ===
 */

/*
 *								=== ~ ===
 */
