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

/**
 *	@file dev/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 CVertexMergeTable 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::CVertexMergeTable() 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_
 *
 */

#if defined(_MSC_VER) && !defined(_MWERKS)
#pragma warning(disable:4786)
#endif

#include "../NewFix.h"

#include "../CallStack.h"
//#include "../OpenGL20.h"
#include <math.h>
#include <vector>
#include <algorithm>
#include "../Vector.h"
#include "../BitArray.h"
//#include "../OpenGL20.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()
 *		- default constructor, creates empty mesh
 */
CPolyMesh::CPolyMesh()
{
	__FuncGuard("CPolyMesh::CPolyMesh");
}

/*
 *	CPolyMesh::CPolyMesh(int n_vertex_num, int n_polygon_num)
 *		- allocates clear mesh with n_vertex_num vertices and n_polygon_num polygons
 *		- if it fails, it's guaranteed there are no vertices nor polygons
 */
CPolyMesh::CPolyMesh(size_t n_vertex_num, size_t n_polygon_num)
{
	__FuncGuard("CPolyMesh::CPolyMesh");

	Alloc(n_vertex_num, n_polygon_num);
}

/*
 *	CPolyMesh::CPolyMesh(int n_vertex_num, int n_polygon_num)
 *		- copy-constructor
 *		- if it fails, it's guaranteed there are no vertices nor polygons
 */
CPolyMesh::CPolyMesh(const CPolyMesh &r_t_mesh)
{
	__FuncGuard("CPolyMesh::CPolyMesh");

	Copy(r_t_mesh);
}

/*
 *	CPolyMesh::~CPolyMesh()
 *		- destructor
 */
CPolyMesh::~CPolyMesh()
{
	__FuncGuard("CPolyMesh::~CPolyMesh");

	DeletePolygons();
}

/*
 *	void CPolyMesh::Swap(CPolyMesh &r_poly_mesh)
 *		- swap contents of this mesh and r_poly_mesh
 */
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
}

/*
 *	bool CPolyMesh::Alloc(int n_vertex_num, int n_polygon_num)
 *		- allocates clear mesh with n_vertex_num vertices and n_polygon_num polygons,
 *		  if there were any vertices or polygons before calling this, they will be deleted
 *		- returns true on success, false on failure
 *		- if it fails, it's guaranteed there are no vertices nor polygons
 */
bool CPolyMesh::Alloc(size_t n_vertex_num, size_t n_polygon_num)
{
	__FuncGuard("CPolyMesh::Alloc");

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

	try {
		if(!m_vertex_list.Reserve(n_vertex_num))
			return false;
	} catch(std::bad_alloc&) {
		return false;
	}
	_ASSERTE(m_vertex_list.n_Vertex_Num() == n_vertex_num);
	// allocate vertices (with random contents)

	_ASSERTE(m_poly_list.empty());
	if(!stl_ut::Reserve_N(m_poly_list, n_polygon_num)) {
		DeleteVertices();
		return false;
	}
	for(size_t i = 0; i < n_polygon_num; ++ i) {
		CPolygon *p_poly;
		if(!(p_poly = new(std::nothrow) CPolygon)) {
			DeleteVertices();
			DeletePolygons();
			return false;
		}
		m_poly_list.push_back(p_poly);
	}
	// alloc empty polygons

	return true;
}

/*
 *	bool CPolyMesh::Copy(const CPolyMesh &r_poly_mesh)
 *		- copies contents of r_poly_mesh
 *		- returns true on success, false on failure
 *		- if it fails, it's guaranteed there are no vertices nor polygons
 */
bool CPolyMesh::Copy(const CPolyMesh &r_poly_mesh)
{
	__FuncGuard("CPolyMesh::Copy");

	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.p_Vertex(i) = *r_poly_mesh.p_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

			CPolygon *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->r_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->r_Vertex(j) = TRefVertex(m_vertex_list.p_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;
}

/*
 *	bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh)
 *		- adds contents of r_poly_mesh to this mesh
 *		- returns true on success, false on failure
 *		- if it fails, this mesh might contain some of r_poly_mesh
 *		  vertices and polygon (but not all of them)
 */
bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh)
{
	__FuncGuard("CPolyMesh::Merge");

	if(!stl_ut::Reserve_NMore(m_poly_list, r_poly_mesh.m_poly_list.size()))
		return false;
	size_t n_vertex_num = n_Vertex_Num();
	if(!m_vertex_list.Reserve(n_vertex_num + r_poly_mesh.n_Vertex_Num()))
		return false;
	// make space for new polygons and vertices

	for(size_t i = 0, j = n_vertex_num, n = r_poly_mesh.m_vertex_list.n_Vertex_Num();
	   i < n; ++ i, ++ j)
		*m_vertex_list.p_Vertex(j) = *r_poly_mesh.m_vertex_list.p_Vertex(i);
	// copy new vertices

	for(size_t i = 0, n = r_poly_mesh.m_poly_list.size(); i < n; ++ i) {
		CPolygon *p_poly;
		if(!(p_poly = new(std::nothrow) CPolygon))
			return false;
		try {
			*p_poly = *r_poly_mesh.m_poly_list[i];
		} catch(std::bad_alloc&) {
			delete p_poly;
			return false;
		}
		// create a new polygon and copy it

		try {
			for(size_t j = 0, m = p_poly->n_Vertex_Num(); j < m; ++ j) {
				int n_index = r_poly_mesh.m_vertex_list.n_Index(p_poly->r_Vertex(j).m_p_ref);
				_ASSERTE(n_index >= 0 && n_index < r_poly_mesh.m_vertex_list.n_Vertex_Num());
				// find index of j-th vertex

				p_poly->r_Vertex(j) = TRefVertex(m_vertex_list.p_Vertex(n_vertex_num + n_index), m_vertex_list);
				// create new ref-vertex
			}
			// fix vertex references (may take some time)
		} catch(std::bad_alloc&) {
			delete p_poly;
			return false;
		}

		m_poly_list.push_back(p_poly);
	}
	// copy new polygons

	return true;
}

/*
 *	bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh, Matrix4f t_transform)
 *		- adds contents of r_poly_mesh to this mesh,
 *		  with transformation given by t_transform
 *		- returns true on success, false on failure
 *		- if it fails, this mesh might contain some of r_poly_mesh
 *		  vertices and polygon (but not all of them)
 */
bool CPolyMesh::Merge(const CPolyMesh &r_poly_mesh, Matrix4f t_transform)
{
	int n_old_vertex_num = n_Vertex_Num();
	if(!Merge(r_poly_mesh))
		return false;
	for(size_t i = n_old_vertex_num, n = n_Vertex_Num(); i < n; ++ i) {
		TVertex *p_vertex = m_vertex_list.p_Vertex(i);
		p_vertex->v_position = t_transform.v_Transform_Pos(p_vertex->v_position);
	}
	// todo - use for-each
	return true;
}

/*
 *	bool CPolyMesh::BoundingBox(Vector3f &r_v_min, Vector3f &r_v_max) const
 *		- finds mesh bounding box, output is in r_v_min and r_v_max
 *		- in case there are no vertices, both r_v_min and r_v_max are set to (0, 0, 0)
 *		  and function returns false; otherwise returns true.
 */
bool CPolyMesh::BoundingBox(Vector3f &r_v_min, Vector3f &r_v_max) const
{
	__FuncGuard("CPolyMesh::BoundingBox");

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

	Vector3f v_min(m_vertex_list[0]->v_position);
	Vector3f v_max(m_vertex_list[0]->v_position);
	for(size_t i = 1, n = m_vertex_list.n_Vertex_Num(); 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;
}

/*
 *	const CVertexPool<CPolyMesh::TVertex> &CPolyMesh::Vertex_Pool() const
 *		- returns const reference to vertex list
 */
const CVertexPool<CPolyMesh::TVertex> &CPolyMesh::Vertex_Pool() const
{
	return m_vertex_list;
}

/*
 *	CVertexPool<CPolyMesh::TVertex> &CPolyMesh::Vertex_Pool()
 *		- returns const reference to vertex list
 */
CVertexPool<CPolyMesh::TVertex> &CPolyMesh::Vertex_Pool()
{
	return m_vertex_list;
}

/*
 *	std::vector<int> *CPolyMesh::p_VertexReference_Table(int *p_vertex_index_table,
 *		const CVertexMergeTable &r_merge_table) const
 *		- create table of vertex references
 *		- table has same length as number of vertex groups
 *		  (number of distinct vertex positions) and contains indices of all polygons
 *		  referencing vertices in this group
 *		- returns pointer to vertex reference table on success or 0 on failure
 */
std::vector<size_t> *CPolyMesh::p_VertexReference_Table(size_t *p_vertex_index_table,
	const CVertexMergeTable &r_merge_table) const
{
	if(!r_merge_table.b_Status() || !p_vertex_index_table)
		return 0;
	// see if merge table is ready

	std::vector<size_t> *p_ref_table;
	if(!(p_ref_table = new(std::nothrow) std::vector<size_t>[r_merge_table.n_Group_Num()]))
		return 0;
	for(size_t i = 0, m = m_poly_list.size(); i < m; ++ i) {
		CPolygon *p_poly = m_poly_list[i];
		for(size_t n = 0, nn = p_poly->n_Vertex_Num(); n < nn; ++ n) {
			size_t n_index_n = m_vertex_list.n_Index(p_poly->t_Vertex(n).m_p_ref);
			_ASSERTE(n_index_n != -1);
			size_t n_group = p_vertex_index_table[n_index_n];
			// determine vertex group (vertex position id)

			if(!stl_ut::Reserve_1More(p_ref_table[n_group])) {
				delete[] p_ref_table;
				return 0;
			}
			p_ref_table[n_group].push_back(i);
			// add face index to the group
		}
	}
	// create table of polygon references

	return p_ref_table;
}

/*
 *	bool CPolyMesh::OptimizeVertices(bool b_compare_normal = false,
 *		bool b_compare_color = false, bool b_compare_texcoord = true)
 *		- optimizes vertices (ie. merges all equivalent vertices)
 *		- b_compare_normal is normal comparison flag
 *		- b_compare_color is color comparison flag
 *		- b_compare_texcoord is texcoord comparison flag
 *		  (note all coords of all texture units are compared!)
 *		- note all epsilons are equal to f_epsilon from Vector.cpp
 *		- returns true on success, false on failure
 */
bool CPolyMesh::OptimizeVertices(bool b_compare_normal,
	bool b_compare_color, bool b_compare_texcoord)
{
	CVertexHash vertex_hash(*this);
	if(!vertex_hash.b_Status())
		return false;
	CVertexMergeTable merge_table(*this, vertex_hash,
		b_compare_normal, b_compare_color, b_compare_texcoord);
	if(!merge_table.b_Status())
		return false;
	// create vertex merge table

	size_t *p_vertex_index;
	if(!(p_vertex_index = merge_table.p_VertexIndexTable()))
		return false;
	// create vertex indices (as much as vertices in this object)

	CPolyMesh t_optimized;
	if(!t_optimized.Alloc(merge_table.n_Group_Num(), m_poly_list.size())) {
		delete[] p_vertex_index;
		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 first vertex of each group

	for(size_t i = 0, m = m_poly_list.size(); i < m; ++ i) {
		CPolygon &r_face = t_optimized.r_Polygon(i);
		CPolygon *p_src_face = m_poly_list[i];
		try {
			r_face = *p_src_face;
			for(size_t n = 0, nn = r_face.n_Vertex_Num(); n < nn; ++ n) {
				int n_index = m_vertex_list.n_Index(p_src_face->t_Vertex(n).m_p_ref);
				_ASSERTE(n_index != -1);
				r_face.r_Vertex(n) = t_optimized.t_RefVertex(p_vertex_index[n_index]);
			}
		} catch(std::bad_alloc&) {
			delete[] p_vertex_index;
			return false;
		}
	}
	// copy faces, renew pointers

	Swap(t_optimized);
	// swap data, now we're optimized

	delete[] p_vertex_index;

	return true;
}

/*
 *	bool CPolyMesh::ExplodeVertices()
 *		- explodes vertices (ie. makes sure every face has three unique vertices)
 *		- returns true on success, false on failure
 */
bool CPolyMesh::ExplodeVertices()
{
	size_t n_vertex_num = 0;
	for(size_t i = 0, n = m_poly_list.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, m_poly_list.size()))
		return false;
	// create object to hold exploded vertices and faces

	try {
		for(size_t i = 0, n_out_vertex = 0, m = m_poly_list.size(); i < m; ++ i) {
			CPolygon *p_src_poly = m_poly_list[i];
			CPolygon *p_poly = t_exploded.m_poly_list[i];
			*p_poly = *p_src_poly;
			// copies all members like material, ...

			for(size_t n = 0, nn = p_poly->n_Vertex_Num(); n < nn; ++ n, ++ n_out_vertex) {
				TVertex *p_src_vertex = p_poly->t_Vertex(n).m_p_ref;
				p_poly->r_Vertex(n) = t_exploded.t_RefVertex(n_out_vertex);
				// set new pointer

				*p_poly->r_Vertex(n).m_p_ref = *p_src_vertex;
				// copy data
			}
		}
		// copy faces, renew pointers, copy vertex data
	} catch(std::bad_alloc&) {
		return false;
	}

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

	return true;
}

/*
 *	bool CPolyMesh::MakeTris()
 *		- break down polygons to triangles
 *		- returns true on success, false on failure
 *		- note this removes degenerate polygons with < 3 vertices
 */
bool CPolyMesh::MakeTris()
{
	size_t n_tri_num = 0;
	for(size_t i = 0, n = m_poly_list.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_Vertex_Num(); i < n; ++ i)
		*t_tmp.m_vertex_list[i] = *m_vertex_list[i];
	// copy vertices

	for(size_t i = 0, n_out_face = 0, n = m_poly_list.size(); i < n; ++ i) {
		const CPolygon *p_poly = m_poly_list[i];
		if(p_poly->n_Vertex_Num() < 3)
			continue;

		int n_index_0, n_index_1;
		if((n_index_0 = m_vertex_list.n_Index(p_poly->t_Vertex(0).m_p_ref)) < 0 ||
		   (n_index_1 = m_vertex_list.n_Index(p_poly->t_Vertex(1).m_p_ref)) < 0)
			return false;
		// get first two vertex indices

		TRefVertex 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 < p_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_Index(p_poly->t_Vertex(j).m_p_ref)) == -1)
				return false;
			p_tri_verts[2] = t_tmp.t_RefVertex(n_index_2);
			// get index of third vertex

			CPolygon *p_tri = t_tmp.m_poly_list[n_out_face];
			p_tri->Delete_Vertices(0, p_tri->n_Vertex_Num());
			if(!p_tri->Add_Vertex(0, p_tri_verts, 3))
				return false;
			// add vertices to face

			p_tri->SetFlags(p_poly->n_Flags());
			// inherit flags

			p_tri->r_t_Normal() = p_poly->t_Normal();
			// inherit normal
		}
	}
	// break polygons down to triangles

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

	return true;
}

/*
 *	bool CPolyMesh::CalcFaceNormals()
 *		- calculates face normals
 *		- returns false in case some polygons failed to
 *		  calculate their normal (it is set to zero),
 *		  otherwise returns true
 */
bool CPolyMesh::CalcFaceNormals()
{
	bool b_result = true;
	for(size_t i = 0, m = m_poly_list.size(); i < m; ++ i) {
		if(!m_poly_list[i]->Calc_Normal()) {
			b_result = false;
			m_poly_list[i]->r_t_Normal() = Plane3f(Vector3f(0, 0, 0), 0);
		}
	}
	return b_result;
}

/*
 *	void CPolyMesh::CalcVertexNormals_Simple()
 *		- calculates vertex normals by averaging normals
 *		  of faces which references the vertex
 *		- note this does not make any changes to mesh topology
 */
void 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.size(); i < m; ++ i) {
		CPolygon *p_poly = m_poly_list[i];
		for(size_t n = 0, nn = p_poly->n_Vertex_Num(); n < nn; ++ n)
			p_poly->t_Vertex(n).m_p_ref->v_normal += p_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 = 30 * f_pi / 180)
 *		- calculates vertex normals, normals of faces holding angle under
 *		  f_angle_thresh are averaged only
 *		- note this explodes vertices
 */
bool CPolyMesh::CalcVertexNormals_Thresh(float f_angle_thresh)
{
	if(!ExplodeVertices())
		return false;
	// explode vertices

	size_t *p_vertex_index;
	std::vector<size_t> *p_ref_table;

	{
		CVertexHash vertex_hash(*this);
		if(!vertex_hash.b_Status())
			return false;
		CVertexMergeTable merge_table(*this, vertex_hash, false, false, false);
		if(!merge_table.b_Status())
			return false;
		// create vertex merge table

		if(!(p_vertex_index = merge_table.p_VertexIndexTable()))
			return false;
		// create vertex indices (as much as vertices in this object)

		if(!(p_ref_table = p_VertexReference_Table(p_vertex_index, merge_table))) {
			delete[] p_vertex_index;
			return false;
		}
		// create table of polygon references
	}
	// make sure vertex hash and merge table is deleted as soon as tables are created

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

		TVertex *p_vertex_i = m_vertex_list.p_Vertex(i);
		// fetch vertex

		CPolygon *p_owner = 0;
		for(size_t j = 0, m = p_ref_table[n_group].size(); j < m; ++ j) {
			CPolygon *p_poly = m_poly_list[p_ref_table[n_group][j]];
			for(size_t k = 0, o = p_poly->n_Vertex_Num(); k < o; ++ k) { 
				if(p_poly->r_Vertex(k).m_p_ref == p_vertex_i) {
					p_owner = p_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 = p_ref_table[n_group].size(); j < m; ++ j) {
			CPolygon *p_face_ptr = m_poly_list[p_ref_table[n_group][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 += 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

	delete[] p_vertex_index;
	delete[] p_ref_table;
	// don't need this anymore

	return true;
}

/*
 *	void CPolyMesh::DeleteVertices()
 *		- helper func, deletes all vertices
 */
void CPolyMesh::DeleteVertices()
{
	__FuncGuard("CPolyMesh::DeleteVertices");

	m_vertex_list.Clear();
}

/*
 *	void CPolyMesh::DeletePolygons(int n_begin = 0, int n_end = -1)
 *		- helper func, deletes polygons in range n_begin to n_end
 */
void CPolyMesh::DeletePolygons(size_t n_begin, size_t n_end)
{
	__FuncGuard("CPolyMesh::DeletePolygons");

	if(n_end == -1)
		n_end = m_poly_list.size();
	if(n_begin >= n_end)
		return;

	std::for_each(m_poly_list.begin() + n_begin, m_poly_list.begin() + n_end, DeletePolygon);
	m_poly_list.erase(m_poly_list.begin() + n_begin, m_poly_list.begin() + n_end);
}

/*
 *	static inline void CPolyMesh::DeletePolygon(CPolygon *p_polygon)
 *		- helper func, deletes polygon p_vertex (but doesn't remove it from list)
 */
inline void CPolyMesh::DeletePolygon(CPolygon *p_polygon)
{
	delete p_polygon;
}

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

/*
 *								=== CPolyMesh::CVertexHash ===
 */

/*
 *	CPolyMesh::CVertexHash::CVertexHash(CPolyMesh &r_object, int n_vertices_per_node = 11)
 *		- default constructor
 *		- r_object is object to be hashed
 *		- n_vertices_per_node is desired number of vertices per node
 *		  (to determine uniform grid size)
 *		- call b_Status() to determine wheter constructor was successful
 *		- note default of 11 vertices / node was chosen to be memory efficient
 *		  while reasonably fast
 */
CPolyMesh::CVertexHash::CVertexHash(CPolyMesh &r_object, size_t n_vertices_per_node)
{
	Vector3f v_min, v_max;
	r_object.BoundingBox(v_min, v_max);
	// calculate bounding box

	size_t n_node_num = r_object.n_Vertex_Num() / n_vertices_per_node;
	if(!n_node_num)
		n_node_num = 1;
	Vector3f v_cell_size = v_max - v_min;
	m_f_cell_side = (float)pow(v_cell_size.x *
		v_cell_size.y * v_cell_size.z / n_node_num, 1.0f / 3);
	if(m_f_cell_side < .01f)
		m_f_cell_side = .01f; // not too small
	m_n_cells_x = (int)(v_cell_size.x / m_f_cell_side + .5f);
	if(!m_n_cells_x)
		m_n_cells_x = 1;
	m_n_cells_y = (int)(v_cell_size.y / m_f_cell_side + .5f);
	if(!m_n_cells_y)
		m_n_cells_y = 1;
	m_n_cells_z = (int)(v_cell_size.z / m_f_cell_side + .5f);
	if(!m_n_cells_z)
		m_n_cells_z = 1;
	// calculate grid dimensions

	if(!(m_p_vertex_hash = new(std::nothrow) std::vector<TVertex*>[m_n_cells_x * m_n_cells_y * m_n_cells_z]))
		return;
	// create new hash

	float p_cell_overlap[2] = {-m_f_cell_side * .1f, m_f_cell_side * .1f};
	// cell overlap

	m_f_inv_cell_side = 1 / m_f_cell_side;
	// inverse cell size

	size_t p_table_size[3] = {m_n_cells_x, m_n_cells_y, m_n_cells_z};
	for(size_t i = 0, m = r_object.n_Vertex_Num(); i < m; ++ i) {
		const TVertex &r_vertex = r_object.t_Vertex(i);

		long p_index[3][2];
		for(int j = 0; j < 2; j ++) {
			for(int n = 0; n < 3; n ++) {
				p_index[n][j] = size_t((r_vertex.v_position[n] + p_cell_overlap[j]) * 
					m_f_inv_cell_side) % p_table_size[n];
				while(p_index[n][j] < 0)
					p_index[n][j] += p_table_size[n];
			}
		}
		// calc indices

		for(int x = 0; x < 2; x ++) {
			for(int y = 0; y < 2; y ++) {
				for(int z = 0; z < 2; z ++) {
					size_t n_cell = p_index[0][x] + (p_index[1][y] +
						p_index[2][z] * m_n_cells_y) * m_n_cells_x;
					// calc cell index

					if(!stl_ut::Reserve_1More(m_p_vertex_hash[n_cell])) {
						delete[] m_p_vertex_hash;
						m_p_vertex_hash = 0;
						return;
					}
					m_p_vertex_hash[n_cell].push_back(&r_object.r_Vertex(i));
					// add reference into a cell

					if(p_index[2][0] == p_index[2][1])
						break;
				}
				if(p_index[1][0] == p_index[1][1])
					break;
			}
			if(p_index[0][0] == p_index[0][1])
				break;
		}
		// add references to a vertex to all cells it hit
	}
}

/*
 *	CPolyMesh::CVertexHash::~CVertexHash()
 *		- default destructor
 */
CPolyMesh::CVertexHash::~CVertexHash()
{
	if(m_p_vertex_hash)
		delete[] m_p_vertex_hash;
}

/*
 *	bool CPolyMesh::CVertexHash::b_Status() const
 *		- returns true in case constructor succeeded and vertex hash
 *		  is ready to be used, otherwise returns false
 */
bool CPolyMesh::CVertexHash::b_Status() const
{
	return m_p_vertex_hash != 0;
}

/*
 *	const std::vector<TVertex*> &CPolyMesh::CVertexHash::r_Hash(Vector3f v_pos)
 *		- returns list of vertices in cell corresponding to position v_pos
 */
const std::vector<CPolyMesh::TVertex*> &CPolyMesh::CVertexHash::r_Hash(Vector3f v_pos)
{
	size_t p_table_size[3] = {m_n_cells_x, m_n_cells_y, m_n_cells_z};
	long p_index[3];
	for(int n = 0; n < 3; n ++) {
		p_index[n] = long(v_pos[n] * m_f_inv_cell_side) % p_table_size[n];
		while(p_index[n] < 0)
			p_index[n] += p_table_size[n];
	}
	size_t n_cell = p_index[0] + (p_index[1] + p_index[2] * m_n_cells_y) * m_n_cells_x;
	return m_p_vertex_hash[n_cell];
}

/*
 *	float CPolyMesh::CVertexHash::f_Avg_CellOccupation() const
 *		- returns average cell occupation
 *		- returns -1 if there's too much vertices so they can't be counted
 */
float CPolyMesh::CVertexHash::f_Avg_CellOccupation() const
{
	size_t n_vertex_num = 0;
	std::vector<TVertex*> *p_cell = m_p_vertex_hash;
	for(size_t i = 0, n = m_n_cells_x * m_n_cells_y * m_n_cells_z; i < n; ++ i, ++ p_cell) {
		if(n_vertex_num > UINT_MAX - p_cell->size())
			return -1;
		n_vertex_num += p_cell->size();
	}
	return float(n_vertex_num) / (m_n_cells_x * m_n_cells_y * m_n_cells_z);
}

/*
 *								=== ~CPolyMesh::CVertexHash ===
 */

/*
 *								=== CPolyMesh::CVertexMergeTable ===
 */

class CPolyMesh::CVertexMergeTable::CGroupVertices {
protected:
	std::vector<TVertex*> *m_p_group;
	const CVertexPool<TVertex> &m_vertex_pool;
	CBitArray &m_r_vertex_flags;
	bool m_b_result;

public:
	CGroupVertices(std::vector<TVertex*> *p_group,
		const CVertexPool<TVertex> &r_vertex_pool, CBitArray &r_vertex_flags)
		:m_p_group(p_group), m_vertex_pool(r_vertex_pool),
		m_r_vertex_flags(r_vertex_flags), m_b_result(true)
	{}

	inline void operator ()(TVertex *p_vertex)
	{
		size_t n_index = m_vertex_pool.n_Index(p_vertex);
		_ASSERTE(n_index != -1);
		//_ASSERTE(!m_r_vertex_flags[n_index]);
		if(m_r_vertex_flags[n_index])
			return; // one vertex can be close to two others
		m_r_vertex_flags.Raise(n_index);
		if(!stl_ut::Reserve_1More(*m_p_group)) {
			m_b_result = false;
			return;
		}
		m_p_group->push_back(p_vertex);
	}

	inline operator bool() const
	{
		return m_b_result;
	}
};

class CPolyMesh::CVertexMergeTable::CCreateIndexTable {
protected:
	size_t *m_p_vertex_index;
	const CVertexPool<TVertex> &m_vertex_pool;
	size_t m_n_index;

	class CFillIndices {
	protected:
		size_t *m_p_vertex_index;
		const CVertexPool<TVertex> &m_vertex_pool;
		size_t m_n_index;

	public:
		CFillIndices(size_t *p_vertex_index,
			const CVertexPool<TVertex> &r_vertex_pool, size_t n_index)
			:m_p_vertex_index(p_vertex_index), m_vertex_pool(r_vertex_pool), m_n_index(n_index)
		{}

		inline void operator ()(const TVertex *p_vertex)
		{
			m_p_vertex_index[m_vertex_pool.n_Index(p_vertex)] = m_n_index;
		}
	};

public:
	CCreateIndexTable(size_t *p_vertex_index, const CVertexPool<TVertex> &r_vertex_pool)
		:m_p_vertex_index(p_vertex_index), m_vertex_pool(r_vertex_pool), m_n_index(0)
	{}

	inline void operator ()(std::vector<TVertex*> *p_equal_vertex_list)
	{
		std::for_each(p_equal_vertex_list->begin(), p_equal_vertex_list->end(),
			CFillIndices(m_p_vertex_index, m_vertex_pool, m_n_index));
		++ m_n_index;
	}
};

/*
 *	CPolyMesh::CVertexMergeTable::CVertexMergeTable(CPolyMesh &r_object,
 *		CVertexHash &r_vertex_hash, bool b_compare_normal = false,
 *		bool b_compare_color = false, bool b_compare_texcoord = true,
 *		float f_epsilon_ex = f_epsilon, float f_normal_epsilon = f_epsilon,
 *		float f_color_epsilon = f_epsilon, float f_texcoord_epsilon = f_epsilon)
 *		- default constructor
 *		- r_object is object for which this merge table is constructed
 *		- r_vertex_hash is current vertex hash for the same object
 *		- b_compare_normal is normal comparison flag
 *		- b_compare_color is color comparison flag
 *		- b_compare_texcoord is texture coordinate comparison flag
 *		  (compares all coords of all texture units!)
 *		- f_epsilon_ex is maximal allowed distance (note the grid cell overlap of
 *		  vertex hash is limit to this distance)
 *		- f_normal_epsilon is maximal allowed normal distance
 *		- f_color_epsilon is maximal allowed color distance (euclidean)
 *		- f_texcoord_epsilon is maximal allowed texcoord distance
 *		- call b_Status() to see wheter constructor succeeded
 */
CPolyMesh::CVertexMergeTable::CVertexMergeTable(CPolyMesh &r_object,
	CVertexHash &r_vertex_hash, bool b_compare_normal, bool b_compare_color,
	bool b_compare_texcoord, float f_epsilon_ex, float f_normal_epsilon,
	float f_color_epsilon, float f_texcoord_epsilon)
	:m_r_object(r_object)
{
	m_b_status = Create(r_object, r_vertex_hash, b_compare_normal, b_compare_color,
		b_compare_texcoord, f_epsilon_ex, f_normal_epsilon, f_color_epsilon, f_texcoord_epsilon);
}

/*
 *	CPolyMesh::CVertexMergeTable::~CVertexMergeTable
 *		- default destructor
 */
CPolyMesh::CVertexMergeTable::~CVertexMergeTable()
{
	std::for_each(m_table.begin(), m_table.end(), DeleteVector);
}

/*
 *	bool CPolyMesh::CVertexMergeTable::b_Status() const
 *		- returns true in case constructor succeeded and
 *		  table is ready to use, otherwise returns false
 */
bool CPolyMesh::CVertexMergeTable::b_Status() const
{
	return m_b_status;
}

/*
 *	int *CPolyMesh::CVertexMergeTable::p_VertexIndexTable() const
 *		- generates list of indices as long as vertex list
 *		- contains indices of vertex groups for each vertex in object
 *		- returns pointer to index list or 0 in case there was not enough memory
 */
size_t *CPolyMesh::CVertexMergeTable::p_VertexIndexTable() const
{
	size_t n_vert_num = m_r_object.n_Vertex_Num();
	size_t *p_vertex_index;
	p_vertex_index = new(std::nothrow) size_t[n_vert_num];
	if(!p_vertex_index)
		return 0;
	// alloc index table (note this is written on separate lines because
	// it's causing internal compiller error in MSVC 6.0 otherwise)

	std::for_each(m_table.begin(), m_table.end(),
		CCreateIndexTable(p_vertex_index, m_r_object.Vertex_Pool())); // O(n)
	// fill vertex indices

	return p_vertex_index;
}

bool CPolyMesh::CVertexMergeTable::Create(CPolyMesh &r_object, CVertexHash &r_vertex_hash,
	bool b_compare_normal, bool b_compare_color, bool b_compare_texcoord, float f_epsilon_ex,
	float f_normal_epsilon, float f_color_epsilon, float f_texcoord_epsilon)
{
	if(!r_vertex_hash.b_Status())
		return false;

	CBitArray vertex_flags(r_object.n_Vertex_Num());
	if(vertex_flags.n_Length() < r_object.n_Vertex_Num())
		return false;
	vertex_flags = false;
	// clear vertex flags

	_ASSERTE(m_table.empty());
	stl_ut::Reserve_N(m_table, r_object.n_Vertex_Num() / 2);
	// roughly estimate to avoid resizing later

	for(size_t i = 0, n = r_object.n_Vertex_Num(); i < n; ++ i) {
		if(vertex_flags[i])
			continue;
		// we've already added this one

		std::vector<TVertex*> *p_group;
		if(!stl_ut::Reserve_1More(m_table) ||
		   !(p_group = new(std::nothrow) std::vector<TVertex*>))
			return false;
		m_table.push_back(p_group);
		// create a new vertex group & add it to group table

		if(!r_vertex_hash.ForEachVertexNear(r_object.t_Vertex(i).v_position,
		   CVertexHash::CVertexGenPredicate(r_object.t_Vertex(i), b_compare_normal,
		   b_compare_color, b_compare_texcoord, f_epsilon_ex, f_normal_epsilon,
		   f_color_epsilon, f_texcoord_epsilon),
		   CGroupVertices(p_group, r_object.Vertex_Pool(), vertex_flags))) // O(n)
			return false;
		// other vertices include current vertex as well so we don't need to explicitly add it

		if(!p_group->size()) {
			m_table.erase(m_table.end() - 1);
			delete p_group;
		} else {
			_ASSERTE(vertex_flags[i]);
			// otherwise it should mark itself as well
		}
		// when there's vertex with NAN / INF coordinate, it can't be compared with the other
		// ones, neither with itself so it's not included in table
	}

	return true;
}

inline void CPolyMesh::CVertexMergeTable::DeleteVector(std::vector<TVertex*> *p_vector)
{
	delete p_vector;
}

/*
 *								=== ~CPolyMesh::CVertexMergeTable ===
 */
