/*
								+----------------------------------+
								|                                  |
								|  ***  Polygonal mesh class  ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|           PolyMesh.cpp           |
								|                                  |
								+----------------------------------+
*/

/**
 *	@file lml/PolyMesh.cpp
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief polygonal mesh class
 *
 *	@date 2008-06-04
 *
 *	fixed error in CPolyMesh::BoundingBox() (it returned minimal corner coordinates in maximum)
 *
 *	conducted series of experiments to find out what is the most efficient vertex hash
 *	cell size. it was found that for unit sphere with 655362 vertices there is ratio
 *	2:3 between required vertices per cell and real number of vertices / cell. this ratio
 *	is however independent of vertex cell size. timing of vertex hash / vertex merge table
 *	operations is independent as well, aparts from CVertexGroupTable constructor which
 *	runs in linear time proportional to number of vertices / cell. memory trashing
 *	is logarithmic, the bend is approximately at 11 so this value has been chosen as default.
 *
 *	@date 2008-06-24
 *
 *	renamed CPolygon2::r_t_Vertex() and CPolyMesh::r_t_Vertex() to
 *	CPolygon2::r_Vertex() and CPolyMesh::r_Vertex() respectively
 *
 *	added vertex color comparison to CPolyMesh::CVertexGroupTable() and dependent functions
 *	(CPolyMesh::OptimizeVertices(), CPolyMesh::CalcVertexNormals_Thresh())
 *
 *	@date 2008-08-08
 *
 *	added \#ifdef for windows 64, added \#define for GL_GLEXT_LEGACY (for linux builds)
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2009-10-20
 *
 *	fixed some warnings when compiling under VC 2005, implemented "Security
 *	Enhancements in the CRT" for VC 2008. compare against MyProjects_2009-10-19_
 *
 */

#include "../NewFix.h"
#include "../CallStack.h"
#include <math.h>
#include <vector>
#include <algorithm>
#include "../Vector.h"
#include "../MinMax.h"
#include "PolyMesh.h"
#include "../StlUtils.h"

#if defined(_MSC_VER) && !defined(__MWERKS__) && !defined(for) && _MSC_VER <= 1200
#define for if(0) {} else for
#endif // _MSC_VER && !__MWERKS__ && !for && _MSC_VER <= 1200
// msvc 'for' scoping hack

/*
 *								=== CPolyMesh ===
 */

CPolyMesh::CPolyMesh()
{
	__FuncGuard("CPolyMesh::CPolyMesh");
}

CPolyMesh::CPolyMesh(size_t n_vertex_num, size_t n_polygon_num)
{
	__FuncGuard("CPolyMesh::CPolyMesh");

	if(!Alloc(n_vertex_num, n_polygon_num))
		throw std::bad_alloc(); // rethrow
}

CPolyMesh::CPolyMesh(const CPolyMesh &r_mesh)
{
	__FuncGuard("CPolyMesh::CPolyMesh");

	if(!Copy(r_mesh))
		throw std::bad_alloc(); // rethrow
}

CPolyMesh::~CPolyMesh()
{
	__FuncGuard("CPolyMesh::~CPolyMesh");

	DeletePolygons();
	//DeleteVertices(); // no need, called by VertexPool destructor
}

class CReplacePoolRef {
protected:
	CPolyMesh::_TyVertexPool *m_p_pool;

public:
	inline CReplacePoolRef(CPolyMesh::_TyVertexPool *p_pool)
		:m_p_pool(p_pool)
	{}

	inline void operator ()(CPolyMesh::_TyPolygon &r_poly) const
	{
		r_poly.for_each_vertex(*this);
	}

	inline void operator ()(CPolyMesh::_TyRefVertex &r_vertex) const
	{
		r_vertex.m_p_vertex_pool = m_p_pool;
	}
};

void CPolyMesh::Swap(CPolyMesh &r_poly_mesh)
{
	__FuncGuard("CPolyMesh::Swap");

	m_poly_list.Swap(r_poly_mesh.m_poly_list);
	// swap polygons

	m_vertex_list.Swap(r_poly_mesh.m_vertex_list);
	// swap vertices

	m_poly_list.ForEach(0, size_t(-1), CReplacePoolRef(&m_vertex_list));
	r_poly_mesh.m_poly_list.ForEach(0, size_t(-1), CReplacePoolRef(&r_poly_mesh.m_vertex_list));
	// the pool references unfortunately need to change, as the addresses
	// of the pools also change (could allocate pools on the heap)
}

bool CPolyMesh::Alloc(size_t n_vertex_num, size_t n_polygon_num)
{
	__FuncGuard("CPolyMesh::Alloc");

	DeleteVertices();
	//DeletePolygons(); // called from DeleteVertices()
	// delete anything that was here before

	_ASSERTE(m_poly_list.b_Empty());
	try {
		m_vertex_list.Reserve(n_vertex_num);
		m_poly_list.Reserve(n_polygon_num);
	} catch(std::bad_alloc&) {
		DeleteVertices(); // DeletePolygons() called from DeleteVertices()
		return false;
	}
	_ASSERTE(m_vertex_list.n_Size() == n_vertex_num);
	_ASSERTE(m_poly_list.n_Size() == n_polygon_num);
	// allocate vertices and polygons (empty, initialized by default constructors)

	return true;
}

bool CPolyMesh::Copy(const CPolyMesh &r_poly_mesh)
{
	__FuncGuard("CPolyMesh::Copy");

#if 1
	DeleteVertices();
	//DeletePolygons(); // called from DeleteVertices()
	// clear

	return Merge(r_poly_mesh); // just as efficient
#else // 1
	if(!Alloc(r_poly_mesh.m_vertex_list.n_Vertex_Num(), r_poly_mesh.m_poly_list.size()))
		return false;

	for(size_t i = 0, n = m_vertex_list.n_Vertex_Num(); i < n; ++ i)
		m_vertex_list.r_Vertex(i) = r_poly_mesh.r_Vertex(i);
	// copy vertices

	try {
		for(size_t i = 0, n = m_poly_list.size(); i < n; ++ i) {
			*m_poly_list[i] = *r_poly_mesh.m_poly_list[i];
			// copy polygon

			_TyPolygon *p_polygon = m_poly_list[i];
			for(size_t j = 0, m = p_polygon->n_Vertex_Num(); j < m; ++ j) {
				size_t n_index = r_poly_mesh.m_vertex_list.n_Index(p_polygon->t_Vertex(j).m_p_ref);
				_ASSERTE(n_index != -1 /*n_index >= 0*/ && n_index < r_poly_mesh.m_vertex_list.n_Vertex_Num());
				// find index of j-th vertex

				p_polygon->t_Vertex(j) = _TyRefVertex(&m_vertex_list.r_Vertex(n_index), m_vertex_list);
				// create new ref-vertex
			}
			// fix vertex references (may take some time)
		}
		// copy polygons
	} catch(std::bad_alloc&) {
		DeleteVertices();
		DeletePolygons();
		// deletes mesh contents

		return false;
	}

	return true;
#endif // 1
}

bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh)
{
	__FuncGuard("CPolyMesh::Merge");

	size_t n_poly_num = n_Polygon_Num();
	size_t n_vertex_num = n_Vertex_Num();
	try {
		//m_poly_list.Reserve(n_poly_num + r_poly_mesh.n_Poly_Num());
		//m_vertex_list.Reserve(n_vertex_num + r_poly_mesh.n_Vertex_Num());
		m_poly_list.Insert_Back(r_poly_mesh.m_poly_list.p_Begin_it(), r_poly_mesh.m_poly_list.p_End_it());
		m_vertex_list.Insert_Back(r_poly_mesh.m_vertex_list.p_Begin_it(), r_poly_mesh.m_vertex_list.p_End_it());
	} catch(std::bad_alloc&) {
		return false;
	}
	// make space for new polygons and vertices

	for(size_t i = n_poly_num, n = m_poly_list.n_Size(); i < n; ++ i) {
		_TyPolygon &r_poly = m_poly_list[i];
		for(size_t j = 0, m = r_poly.n_Vertex_Num(); j < m; ++ j) {
			size_t n_index = r_poly_mesh.m_vertex_list.n_IndexOf(r_poly.t_Vertex(j).m_p_ref);
			_ASSERTE(n_index != size_t(-1));
			// find index of j-th vertex

			r_poly.t_Vertex(j) = t_RefVertex(n_vertex_num + n_index);
			// create new ref-vertex
		}
		// fix vertex references (may take some time)
	}

	return true;
}

bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh, Matrix4f t_transform)
{
	__FuncGuard("CPolyMesh::Merge");

	size_t n_old_vertex_num = n_Vertex_Num();
	if(!Merge(r_poly_mesh))
		return false;
	m_vertex_list.ForEach(n_old_vertex_num, size_t(-1), CTransform(t_transform));
	/*for(size_t i = n_old_vertex_num, n = n_Vertex_Num(); i < n; ++ i) {
		_TyVertex &r_vertex = m_vertex_list.r_Vertex(i);
		r_vertex.v_position = t_transform.v_Transform_Pos(r_vertex.v_position);
	}*/
	// t_odo - use for-each
	return true;
}

bool CPolyMesh::BoundingBox(Vector3f &r_v_min, Vector3f &r_v_max) const
{
	__FuncGuard("CPolyMesh::BoundingBox");

	if(m_vertex_list.b_Empty()) {
		r_v_min = r_v_max = Vector3f(0, 0, 0);
		return false;
	}

	Vector3f v_min(m_vertex_list.r_Front().v_position);
	Vector3f v_max(m_vertex_list.r_Front().v_position);
	for(size_t i = 1, n = m_vertex_list.n_Size(); i < n; ++ i) {
		Vector3f v_pos = m_vertex_list[i].v_position;
		for(int j = 0; j < 3; ++ j) {
			if(v_min[j] > v_pos[j])
				v_min[j] = v_pos[j];
			if(v_max[j] < v_pos[j])
				v_max[j] = v_pos[j];
		}
	}
	// find bounding box

	r_v_min = v_min;
	r_v_max = v_max;
	// this is supposedly faster

	return true;
}

bool CPolyMesh::OptimizeVertices(bool b_compare_normal,
	bool b_compare_color, size_t n_compare_texcoord_num, float f_epsilon_ex)
{
	__FuncGuard("CPolyMesh::OptimizeVertices");

	CVertexHash::CVertexGroupTable merge_table(*this,
		CVertexHash::CUniformGrid<>(*this, 100, f_epsilon_ex),
		b_compare_normal, b_compare_color, n_compare_texcoord_num,
		f_epsilon_ex, f_epsilon_ex, f_epsilon_ex, f_epsilon_ex);
	if(!merge_table.b_Status())
		return false;
	// create vertex merge table

	const std::vector<size_t> &r_vertex_index = merge_table.r_GroupIndexTable();
	// get vertex group indices (as much as vertices in this object)

	CPolyMesh t_optimized;
	if(!t_optimized.Alloc(merge_table.n_Group_Num(), 0)) // actually no need to realloc the polygons, can simply swap the list
		return false;
	// create object to hold optimized vertices and faces

	for(size_t i = 0, n = merge_table.n_Group_Num(); i < n; ++ i)
		t_optimized.r_Vertex(i) = *merge_table.p_FirstVertex(i);
	// copy the first vertex of each group

	for(size_t i = 0, m = m_poly_list.n_Size(); i < m; ++ i) {
		_TyPolygon &r_face = m_poly_list[i];
		try {
			for(size_t n = 0, nn = r_face.n_Vertex_Num(); n < nn; ++ n) {
				size_t n_index = m_vertex_list.n_IndexOf(r_face.t_Vertex(n).m_p_ref);
				_ASSERTE(n_index != size_t(-1));
				_ASSERTE(r_vertex_index[n_index] < merge_table.n_Group_Num()); // make sure there are no more verts
				r_face.t_Vertex(n) = t_optimized.t_RefVertex(r_vertex_index[n_index]);
			}
		} catch(std::bad_alloc&) {
			return false;
		}
	}
	// copy faces, renew pointers

	t_optimized.m_poly_list.Swap(m_poly_list); // swap the polygon list
	Swap(t_optimized);
	// swap data, now we're optimized

	return true;
}

bool CPolyMesh::ExplodeVertices()
{
	__FuncGuard("CPolyMesh::ExplodeVertices");

	size_t n_vertex_num = 0;
	for(size_t i = 0, n = m_poly_list.n_Size(); i < n; ++ i)
		n_vertex_num += m_poly_list[i].n_Vertex_Num();
	// sum up vertices of all polygons

	CPolyMesh t_exploded;
	if(!t_exploded.Alloc(n_vertex_num, 0)) // no need to realloc polygons, can just swap
		return false;
	// create object to hold exploded vertices and faces

	size_t n_out_vertex = 0;
	for(size_t i = 0, m = m_poly_list.n_Size(); i < m; ++ i) {
		_TyPolygon &r_poly = m_poly_list[i];
		for(size_t n = 0, nn = r_poly.n_Vertex_Num(); n < nn; ++ n, ++ n_out_vertex) {
			_TyVertex *p_src_vertex = r_poly.t_Vertex(n).m_p_ref;
			r_poly.t_Vertex(n) = t_exploded.t_RefVertex(n_out_vertex);
			// set new pointer

			*r_poly.t_Vertex(n).m_p_ref = *p_src_vertex;
			// copy data
		}
	}
	_ASSERTE(n_out_vertex == n_vertex_num);
	// renew vertex pointers, copy vertex data

	t_exploded.m_poly_list.Swap(m_poly_list);
	Swap(t_exploded);
	// swap data, now we're exploded

	return true;
}

#define __POLY_MESH_MAKETRIS_USE_TRIANGLE_STRIP

bool CPolyMesh::MakeTris()
{
	__FuncGuard("CPolyMesh::MakeTris");

	size_t n_tri_num = 0;
	for(size_t i = 0, n = m_poly_list.n_Size(); i < n; ++ i)
		n_tri_num += max(m_poly_list[i].n_Vertex_Num(), size_t(2)) - 2;
	// calculate number of triangles

	CPolyMesh t_tmp;
	if(!t_tmp.Alloc(n_Vertex_Num(), n_tri_num))
		return false;
	// alloc new mesh

	for(size_t i = 0, n = m_vertex_list.n_Size(); i < n; ++ i)
		t_tmp.m_vertex_list[i] = m_vertex_list[i];
	// copy vertices

	try {
		for(size_t i = 0, n_out_face = 0, n = m_poly_list.n_Size(); i < n; ++ i) {
			const _TyPolygon &r_poly = m_poly_list[i];
			if(r_poly.n_Vertex_Num() < 3)
				continue;

			_TyPolygon poly_data = r_poly;
			poly_data.Delete();
			// make initializer for polygon data

#if defined(__POLY_MESH_MAKETRIS_USE_TRIANGLE_FAN)
			size_t n_index_0, n_index_1;
			if((n_index_0 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(0).m_p_ref)) == size_t(-1) ||
			   (n_index_1 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(1).m_p_ref)) == size_t(-1))
				return false;
			// get first two vertex indices

			_TyRefVertex p_tri_verts[3] = {
				t_tmp.t_RefVertex(n_index_0),
				t_tmp.t_RefVertex(n_index_1),
				t_tmp.t_RefVertex(n_index_1) // this actually doesn't have to be initialized
			};
			// ref-vertices for new triangle

			for(size_t j = 2; j < r_poly.n_Vertex_Num();
			   ++ j, ++ n_out_face, p_tri_verts[1] = p_tri_verts[2]) {
				size_t n_index_2;
				if((n_index_2 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(j).m_p_ref)) == size_t(-1))
					return false;
				p_tri_verts[2] = t_tmp.t_RefVertex(n_index_2);
				// get index of third vertex

				_TyPolygon &r_tri = t_tmp.m_poly_list[n_out_face];
				r_tri = poly_data; // copy surface flags and such
				r_tri.Insert_Vertex(p_tri_verts, p_tri_verts + 3);
				// add vertices to face
			}
			// make a triangle fan
#elif defined(__POLY_MESH_MAKETRIS_USE_TRIANGLE_STRIP)
			size_t n_first = 0;
			size_t n_last = r_poly.n_Vertex_Num() - 1;
			size_t n_index_0, n_index_2;
			if((n_index_0 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_first).m_p_ref)) == size_t(-1) ||
			   (n_index_2 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_last).m_p_ref)) == size_t(-1))
				return false;
			// get the first and the last vertex index

			_TyRefVertex p_tri_verts[3] = {
				t_tmp.t_RefVertex(n_index_0),
				t_tmp.t_RefVertex(n_index_2),
				t_tmp.t_RefVertex(n_index_0) // will get overwritten immediately
			};
			// ref-vertices for the new triangle

			for(size_t j = 0, n_triangle_num = n_last - 1; j < n_triangle_num; ++ j, ++ n_out_face) {
				if(j & 1) {
					p_tri_verts[0] = p_tri_verts[1];
					_ASSERTE(n_last > 0);
					size_t n_index = m_vertex_list.n_IndexOf(r_poly.t_Vertex(-- n_last).m_p_ref);
					if(n_index == size_t(-1))
						return false;
					p_tri_verts[1] = t_tmp.t_RefVertex(n_index);
				} else {
					p_tri_verts[2] = p_tri_verts[1];
					_ASSERTE(n_first + 1 < r_poly.n_Vertex_Num());
					size_t n_index = m_vertex_list.n_IndexOf(r_poly.t_Vertex(++ n_first).m_p_ref);
					if(n_index == size_t(-1))
						return false;
					p_tri_verts[1] = t_tmp.t_RefVertex(n_index);
				}
				// progress from the beginning or from the end, zigzag style

				_TyPolygon &r_tri = t_tmp.m_poly_list[n_out_face];
				r_tri = poly_data; // copy surface flags and such
				r_tri.Insert_Vertex(p_tri_verts, p_tri_verts + 3);
				// add vertices to the face
			}
			// make a triangle strip
#else // __POLY_MESH_MAKETRIS_USE_TRIANGLE_FAN
			size_t n_first = 0;
			size_t n_last = r_poly.n_Vertex_Num() - 1;
			size_t n_index_0, n_index_2;
			if((n_index_0 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_first).m_p_ref)) == size_t(-1) ||
			   (n_index_2 = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_last).m_p_ref)) == size_t(-1))
				return false;
			// get the first and the last vertex index

			_TyRefVertex p_tri_verts[3] = {
				t_tmp.t_RefVertex(n_index_0),
				t_tmp.t_RefVertex(n_index_2),
				t_tmp.t_RefVertex(n_index_0) // will get overwritten immediately
			};
			// ref-vertices for the new triangle

			bool b_again = false;
			for(size_t j = 0, n_triangle_num = n_last - 1; j < n_triangle_num; ++ j, ++ n_out_face) {
				_ASSERTE(n_last > 0);
				_ASSERTE(n_first + 1 < r_poly.n_Vertex_Num());
				size_t n_index_l = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_last - 1).m_p_ref);
				size_t n_index_r = m_vertex_list.n_IndexOf(r_poly.t_Vertex(n_first + 1).m_p_ref);
				if(n_index_l == size_t(-1) || n_index_r == size_t(-1))
					return false;
				if(j & 1) {
					if(!b_again) {// we took the same branch?
						// think about how to write this
						// maybe it will not help as it is a greedy approach, the last triangle still might be flat
					} else {
						p_tri_verts[0] = p_tri_verts[1];
						p_tri_verts[1] = t_tmp.t_RefVertex(n_index_l);
					}
					-- n_last;
					b_again = false;
				} else {
					++ n_first;
					if(b_again) { // we took the same branch?
						//p_tri_verts[1] = p_tri_verts[2];
						//p_tri_verts[2] = t_tmp.t_RefVertex(n_index_r); // wrong, // think about how to write this
					} else {
						p_tri_verts[2] = p_tri_verts[1];
						p_tri_verts[1] = t_tmp.t_RefVertex(n_index_r);
					}
					b_again = true;
				}
				// progress from the beginning or from the end, zigzag style

				_TyPolygon &r_tri = t_tmp.m_poly_list[n_out_face];
				r_tri = poly_data; // copy surface flags and such
				r_tri.Insert_Vertex(p_tri_verts, p_tri_verts + 3);
				// add vertices to the face
			}
			// make a triangle strip
#endif // __POLY_MESH_MAKETRIS_USE_TRIANGLE_FAN
		}
	} catch(std::bad_alloc&) {
		return false;
	}
	// break polygons down to triangles

	Swap(t_tmp);
	// swap triangle mesh with this mesh

	return true;
}

bool CPolyMesh::CalcFaceNormals(float f_epsilon_ex /*= f_epsilon*/)
{
	__FuncGuard("CPolyMesh::CalcFaceNormals");

	bool b_result = true;
	for(size_t i = 0, m = m_poly_list.n_Size(); i < m; ++ i) {
		if(!m_poly_list[i].Calc_Normal(f_epsilon_ex))
			b_result = false;
	}
	return b_result;
}

void CPolyMesh::CalcVertexNormals_Simple()
{
	__FuncGuard("CPolyMesh::CalcVertexNormals_Simple");

	const size_t n_vertex_num = n_Vertex_Num();
	for(size_t i = 0, m = n_vertex_num; i < m; ++ i)
		m_vertex_list[i].v_normal = Vector3f(0, 0, 0);
	for(size_t i = 0, m = m_poly_list.n_Size(); i < m; ++ i) {
		_TyPolygon &r_poly = m_poly_list[i];
		for(size_t n = 0, nn = r_poly.n_Vertex_Num(); n < nn; ++ n)
			r_poly.t_Vertex(n).m_p_ref->v_normal += r_poly.t_Normal().v_normal;
	}
	for(size_t i = 0, m = n_vertex_num; i < m; ++ i)
		m_vertex_list[i].v_normal.Normalize();
	// simply average face normals; reflects vertex references
}

bool CPolyMesh::CalcVertexNormals_Thresh(float f_angle_thresh)
{
	__FuncGuard("CPolyMesh::CalcVertexNormals_Thresh");

	if(!ExplodeVertices())
		return false;
	// explode vertices

	CVertexHash::CVertexGroupTable merge_table(*this,
		CVertexHash::CUniformGrid<>(*this, 100, f_epsilon), false, false, 0);
	if(!merge_table.b_Status())
		return false;
	// create vertex merge table

	std::vector<std::vector<_TyPolygon*> > vertex_ref_table;
	if(!merge_table.Build_VertexReference_Table(vertex_ref_table, *this))
		return false;
	// create a table of polygon references

	const std::vector<size_t> &r_group_index = merge_table.r_GroupIndexTable();
	// get vertex group indices (as much as vertices in this object)

	for(size_t i = 0, n = m_vertex_list.n_Size(); i < n; ++ i) {
		size_t n_group = r_group_index[i];
		// determine vertex group

		_TyVertex *p_vertex_i = &m_vertex_list[i];
		// fetch vertex

		const std::vector<_TyPolygon*> &r_referencing_polygons = vertex_ref_table[n_group];
		// get indices of polygons

		_TyPolygon *p_owner = 0;
		for(size_t j = 0, m = r_referencing_polygons.size(); j < m; ++ j) {
			_TyPolygon &r_poly = *r_referencing_polygons[j];
			for(size_t k = 0, o = r_poly.n_Vertex_Num(); k < o; ++ k) { 
				if(r_poly.t_Vertex(k).m_p_ref == p_vertex_i) {
					p_owner = &r_poly;
					break;
				}
			}
		}
		// find face owning this vertex

		_ASSERTE(p_owner);
		if(!p_owner) {
			p_vertex_i->v_normal = Vector3f(0, 0, 0);
			continue;
		}
		// this vertex is not referenced by any face (shouldn't happen after ExplodeVertices())

		p_vertex_i->v_normal = p_owner->t_Normal().v_normal;
		// account owner face normal

		for(size_t j = 0, m = r_referencing_polygons.size(); j < m; ++ j) {
			_TyPolygon *p_face_ptr = r_referencing_polygons[j];
			if(p_face_ptr == p_owner)
				continue;
			// skip owner self

			float f_angle = (float)acos(p_face_ptr->t_Normal().v_normal.f_Dot(
				p_owner->t_Normal().v_normal));
			if(f_angle < 0)
				f_angle += float(f_pi); // back-facing polygons
			if(f_angle > f_angle_thresh)
				continue;
			// check angle against threshold

			p_vertex_i->v_normal += p_face_ptr->t_Normal().v_normal;
		}
		// account other face's normals

		p_vertex_i->v_normal.Normalize();
		// normalize
	}
	// calc vertex normals

	return true;
}

void CPolyMesh::DeleteVertices()
{
	__FuncGuard("CPolyMesh::DeleteVertices");

	m_vertex_list.Clear();
	m_poly_list.Clear(); // !! otherwise leaves reference vertices with invalid pointers
}

void CPolyMesh::DeletePolygons(size_t n_begin, size_t n_end)
{
	__FuncGuard("CPolyMesh::DeletePolygons");

	if(n_end == -1)
		n_end = m_poly_list.n_Size();
	_ASSERTE(n_begin <= n_end);

	if(n_end != m_poly_list.n_Size()) {
		size_t n_delete = n_end - n_begin;
		_ASSERTE(m_poly_list.n_Size() > n_delete); // not equal, strictly larger
		for(size_t i = n_begin, n = m_poly_list.n_Size() - n_delete; i < n; ++ i)
			std::swap(m_poly_list[i], m_poly_list[i + n_delete]);
		// shift range (nothrow)

		m_poly_list.Erase_Back(m_poly_list.p_Begin_it() + m_poly_list.n_Size() - n_delete);
		// delete the required count from the end
	} else
		m_poly_list.Erase_Back(m_poly_list.p_Begin_it() + n_begin);
}

bool CPolyMesh::Build_DrawBuffers(std::vector<uint32_t> &r_index_buffer,
	std::vector<float> &r_vertex_buffer,
	std::vector<std::pair<size_t, std::pair<size_t, size_t> > > &r_material_range_list,
	bool b_use_normals, bool b_use_colors, size_t n_use_texcoord_element_num) const
{
	__FuncGuard("CPolyMesh::BuildDrawBuffers");

	if(!Build_DrawBuffers(r_index_buffer, r_vertex_buffer, b_use_normals,
	   b_use_colors, n_use_texcoord_element_num))
		return false;

	try {
		r_material_range_list.clear();
		for(size_t i = 0, n = m_poly_list.n_Size(), n_index = 0; i < n; ++ i) {
			const _TyPolygon &r_poly = m_poly_list[i];
			_ASSERTE(r_poly.n_Vertex_Num() == 3); // can only draw triangles (but it would already fail in the call to Build_DrawBuffers)

			if(!i || r_poly.n_MaterialId() != r_material_range_list.back().first) {
				r_material_range_list.push_back(std::make_pair(size_t(r_poly.n_MaterialId()),
					std::make_pair(size_t(n_index), size_t(1))));
				// put there a pair of material, first index, number of triangles
			} else
				++ r_material_range_list.back().second.second; // one more with the same mat
			
			n_index += r_poly.n_Vertex_Num();
		}
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

bool CPolyMesh::Build_DrawBuffers(std::vector<uint32_t> &r_index_buffer,
	std::vector<float> &r_vertex_buffer, bool b_use_normals,
	bool b_use_colors, size_t n_use_texcoord_element_num) const
{
	__FuncGuard("CPolyMesh::BuildDrawBuffers");

	try {
		r_index_buffer.resize(m_poly_list.n_Size() * 3);
		// allocate the index buffer

		size_t n_vertex_size = 3;
		if(b_use_normals)
			n_vertex_size += 3;
		if(b_use_colors)
			n_vertex_size += 4;
		if(n_use_texcoord_element_num)
			n_vertex_size += n_use_texcoord_element_num;
		// calculate vertex size

		r_vertex_buffer.resize(m_vertex_list.n_Size() * n_vertex_size);
		// allocate the vertex buffer

		float *p_dest = (r_vertex_buffer.empty())? 0 : &r_vertex_buffer[0];
		for(size_t i = 0, n = m_vertex_list.n_Size(); i < n; ++ i) {
			const _TyVertex &r_vert = m_vertex_list[i];
			*p_dest ++ = r_vert.v_position.x;
			*p_dest ++ = r_vert.v_position.y;
			*p_dest ++ = r_vert.v_position.z;
			if(b_use_normals) {
				*p_dest ++ = r_vert.v_normal.x;
				*p_dest ++ = r_vert.v_normal.y;
				*p_dest ++ = r_vert.v_normal.z;
			}
			if(b_use_colors) {
				*p_dest ++ = r_vert.v_color.x;
				*p_dest ++ = r_vert.v_color.y;
				*p_dest ++ = r_vert.v_color.z;
				*p_dest ++ = r_vert.v_color.w;
			}
			for(size_t j = 0; j < n_use_texcoord_element_num; ++ j)
				*p_dest ++ = r_vert.p_texture_coord[j / 4][j % 4];
		}
		_ASSERTE(r_vertex_buffer.empty() || p_dest == &r_vertex_buffer.back() + 1);
		// make vertices

		uint32_t *p_index = (r_index_buffer.empty())? 0 : &r_index_buffer[0];
		for(size_t i = 0, n = m_poly_list.n_Size(); i < n; ++ i) {
			const _TyPolygon &r_poly = m_poly_list[i];
			if(r_poly.n_Vertex_Num() != 3)
				return false;
			// can only draw triangles

			_ASSERTE(m_vertex_list.n_IndexOf(r_poly.t_Vertex(0).m_p_ref) != size_t(-1));
			_ASSERTE(m_vertex_list.n_IndexOf(r_poly.t_Vertex(1).m_p_ref) != size_t(-1));
			_ASSERTE(m_vertex_list.n_IndexOf(r_poly.t_Vertex(2).m_p_ref) != size_t(-1));
			*p_index ++ = uint32_t(m_vertex_list.n_IndexOf(r_poly.t_Vertex(0).m_p_ref));
			*p_index ++ = uint32_t(m_vertex_list.n_IndexOf(r_poly.t_Vertex(1).m_p_ref));
			*p_index ++ = uint32_t(m_vertex_list.n_IndexOf(r_poly.t_Vertex(2).m_p_ref));
			_ASSERTE(p_index[-1] != size_t(-1) &&
				p_index[-2] != size_t(-1) && p_index[-3] != size_t(-1));
			// save vertices
		}
		_ASSERTE(r_index_buffer.empty() || p_index == &r_index_buffer.back() + 1);
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

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