/*
								+----------------------------------+
								|                                  |
								|  ***  Geo-Sphere primitive  ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2007   |
								|                                  |
								|          GeoSphere.cpp           |
								|                                  |
								+----------------------------------+
*/

/**
 *	@file dev/GeoSphere.cpp
 *	@date 2007
 *	@author -tHE SWINe-
 *	@brief Geo-Sphere primitive
 *
 *	@date 2008-06-24
 *
 *	renamed CPolygon2::r_t_Vertex() and CPolyMesh::r_t_Vertex() to
 *	CPolygon2::r_Vertex() and CPolyMesh::r_Vertex() respectively
 *
 */

#if defined(_MSC_VER) && !defined(__MWERKS__)
#pragma warning(disable:4786)
#endif
// disable warning C4786 "identifier was truncated to '255' characters in the debug information"

#include "../NewFix.h"

#include "../CallStack.h"
#include <algorithm>
#include <vector>
#include <math.h>
#include "../Vector.h"
#include "../BitArray.h"
#include "PolyMesh.h"
#include "GeoSphere.h"

/*
 *								=== CTesselate ===
 */

/*
 *	static bool CTesselate::Tesselate(CPolyMesh &r_t_mesh, bool b_force_quads = false)
 *		- tesselates r_t_mesh by turning each of it's triangles to four triangles
 *		- returns true on success, false on failure
 */
bool CTesselate::Tesselate(CPolyMesh &r_t_mesh, bool b_force_quads)
{
	size_t n_new_vertex_num = r_t_mesh.n_Vertex_Num();
	size_t n_new_face_num = 0;
	for(size_t i = 0, n = r_t_mesh.n_Poly_Num(); i < n; ++ i) {
		const CPolyMesh::CPolygon *p_poly = r_t_mesh.p_Polygon(i);
		if(p_poly->n_Vertex_Num() == 3 && !b_force_quads) {
			n_new_face_num += 4;
			n_new_vertex_num += 3;
		} else {
			n_new_face_num += p_poly->n_Vertex_Num();
			n_new_vertex_num += p_poly->n_Vertex_Num() + 1;
		}
	}
	// count how much polygons do we need

	CPolyMesh t_tesselated;
	if(!t_tesselated.Alloc(n_new_vertex_num, n_new_face_num))
		return false;

	for(size_t i = 0, n = r_t_mesh.n_Vertex_Num(); i < n; ++ i)
		t_tesselated.r_Vertex(i) = r_t_mesh.t_Vertex(i);
	// copy original vertices

	size_t n_tess_vertex = r_t_mesh.n_Vertex_Num();
	size_t n_out_face = 0;
	for(size_t i = 0, n = r_t_mesh.n_Poly_Num(); i < n; ++ i) {
		const CPolyMesh::CPolygon *p_poly = r_t_mesh.p_Polygon(i);
		// polygon i

		if(p_poly->n_Vertex_Num() == 3 && !b_force_quads) {
			/*

					  *0
					 /\
					/  \
				   /    \
			   t20*------*t01
				 /\     /\  
				/  \   /  \ 
			   /    \ /    \
			 2*------*------*1
					t12

				0-t01-t20
				1-t12-t01
				2-t20-t12
				t01-t12-t20

			 */

			try {
				t_tesselated.r_Vertex(n_tess_vertex) =
					(*p_poly->t_Vertex(0).m_p_ref + *p_poly->t_Vertex(1).m_p_ref) * .5f;
				t_tesselated.r_Vertex(n_tess_vertex + 1) =
					(*p_poly->t_Vertex(1).m_p_ref + *p_poly->t_Vertex(2).m_p_ref) * .5f;
				t_tesselated.r_Vertex(n_tess_vertex + 2) =
					(*p_poly->t_Vertex(2).m_p_ref + *p_poly->t_Vertex(0).m_p_ref) * .5f;
				// create three more vertices on triangle edges

				for(int j = 0; j < 4; ++ j, ++ n_out_face) {
					CPolyMesh::CPolygon &r_face = t_tesselated.r_Polygon(n_out_face);
					r_face = *p_poly;
					// copy any properties polygon might hold (material, surfaceflags, ...)

					if(j != 3) {
						int n_index_j = r_t_mesh.Vertex_Pool().n_Index(p_poly->t_Vertex(j).m_p_ref);
						_ASSERTE(n_index_j != -1);
						r_face.r_Vertex(0) = t_tesselated.t_RefVertex(n_index_j);
						r_face.r_Vertex(1) = t_tesselated.t_RefVertex(n_tess_vertex + j);
						r_face.r_Vertex(2) = t_tesselated.t_RefVertex(n_tess_vertex + (j + 2) % 3);
					} else {
						r_face.r_Vertex(0) = t_tesselated.t_RefVertex(n_tess_vertex + 0);
						r_face.r_Vertex(1) = t_tesselated.t_RefVertex(n_tess_vertex + 1);
						r_face.r_Vertex(2) = t_tesselated.t_RefVertex(n_tess_vertex + 2);
					}
					// modify vertices
				}
			} catch(std::bad_alloc&) {
				return false;
			}

			n_tess_vertex += 3;
			// created three new vertices
		} else if(p_poly->n_Vertex_Num()) {
			/*

					  *0
					 /\
					/  \
				   /    \
			   t20*,   ,-*t01
				 /  \,/   \  
				/    | c   \ 
			   /     |      \
			 2*------*------*1
					t12

				0-t01-c-t20
				1-t12-c-t01
				2-t20-c-t12

			 */

			try {
				size_t n_edge_num = p_poly->n_Vertex_Num();
				for(size_t j = 0, n_prev_j = n_edge_num - 1; j < n_edge_num; n_prev_j = j ++) {
					t_tesselated.r_Vertex(n_tess_vertex + j) =
						(*p_poly->t_Vertex(n_prev_j).m_p_ref +
						*p_poly->t_Vertex(j).m_p_ref) * .5f;
				}
				t_tesselated.r_Vertex(n_tess_vertex + n_edge_num) = p_poly->t_Center();
				// create some more vertices on polygon edges and one in the center

				for(int j = 0; j < n_edge_num; ++ j, ++ n_out_face) {
					CPolyMesh::CPolygon &r_face = t_tesselated.r_Polygon(n_out_face);
					r_face = *p_poly;
					r_face.Delete_Vertices(0, n_edge_num);
					// copy any properties polygon might hold (material, surfaceflags, ...)

					int n_index_j = r_t_mesh.Vertex_Pool().n_Index(p_poly->t_Vertex(j).m_p_ref);
					_ASSERTE(n_index_j != -1);

					CPolyMesh::TRefVertex p_vertex_ptr[4] = {
						t_tesselated.t_RefVertex(n_index_j),
						t_tesselated.t_RefVertex(n_tess_vertex + (j + 1) % n_edge_num),
						t_tesselated.t_RefVertex(n_tess_vertex + n_edge_num),
						t_tesselated.t_RefVertex(n_tess_vertex + j)
					};
					// vertices of a single quad

					if(!r_face.Add_Vertex(0, p_vertex_ptr, 4))
						return false;
					// wind new quad
				}
				// create new faces

				n_tess_vertex += n_edge_num + 1;
				// created some new vertices
			} catch(std::bad_alloc&) {
				return false;
			}
		}
	}

	r_t_mesh.Swap(t_tesselated);

	return true;
}

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

/*
 *								=== CSpherify ===
 */

class CSpherifyOp {
protected:
	Vector3f m_v_center;
	float m_f_radius;

public:
	CSpherifyOp(Vector3f v_center, float f_radius)
		:m_v_center(v_center), m_f_radius(f_radius)
	{}

	inline void operator ()(CPolyMesh::TVertex *p_vertex) const
	{
		Vector3f v_vec = p_vertex->v_position - m_v_center;
		v_vec.Normalize(m_f_radius);
		p_vertex->v_position = m_v_center + v_vec;
	}
};

/*
 *	static void CSpherify::Spherify(CPolyMesh &r_t_mesh, Vector3f v_center, float f_radius)
 *		- moves all vertices of r_t_mesh to sphere with
 *		  center at v_center and radius f_radius
 */
void CSpherify::Spherify(CPolyMesh &r_t_mesh, Vector3f v_center, float f_radius)
{
	r_t_mesh.Vertex_Pool().ForEach(0, -1, CSpherifyOp(v_center, f_radius));
	// apply spherify operator on each vertex
}

/*
 *	static void CSpherify::Spherify(CPolyMesh &r_t_mesh)
 *		- automatic spherify; radius and center are chosen based on bounding box
 */
void CSpherify::Spherify(CPolyMesh &r_t_mesh)
{
	Vector3f v_min, v_max;
	r_t_mesh.BoundingBox(v_min, v_max);
	Spherify(r_t_mesh, (v_min + v_max) * .5f, (v_min - v_max).f_Length() * .5f);
}
/*
 *								=== ~CSpherify ===
 */

/*
 *								=== CMakeGeoSphere ===
 */

const float CMakeGeoSphere::m_p_vertex[12][3] = {
	{ 0.000f,  0.000f,  1.000f},
	{ 0.894f,  0.000f,  0.447f},
	{ 0.276f,  0.851f,  0.447f},
	{-0.724f,  0.526f,  0.447f},
	{-0.724f, -0.526f,  0.447f},
	{ 0.276f, -0.851f,  0.447f},
	{ 0.724f,  0.526f, -0.447f},
	{-0.276f,  0.851f, -0.447f},
	{-0.894f,  0.000f, -0.447f},
	{-0.276f, -0.851f, -0.447f},
	{ 0.724f, -0.526f, -0.447f},
	{ 0.000f,  0.000f, -1.000f}
};

const int CMakeGeoSphere::m_p_face[20][3] = {
	{ 0,  1,  2},
	{ 0,  2,  3},
	{ 0,  3,  4},
	{ 0,  4,  5},
	{ 0,  5,  1},
	{ 6, 11,  7},
	{ 7, 11,  8},
	{ 8, 11,  9},
	{ 9, 11, 10},
	{10, 11,  6},
	{ 2,  1,  6},
	{ 3,  2,  7},
	{ 4,  3,  8},
	{ 5,  4,  9},
	{ 1,  5, 10},
	{ 6,  7,  2},
	{ 7,  8,  3},
	{ 8,  9,  4},
	{ 9, 10,  5},
	{10,  6,  1}
};

/*
 *	static bool CMakeGeoSphere::MakeGeoSphere(CPolyMesh &r_t_mesh,
 *		int n_tesselation, bool b_force_quads = false, float f_radius = 1)
 *		- creates geodesic sphere with center at origin, radius f_radius
 *		  and tesselation n_tesselation (tesselation 0 yields icosahedron)
 *		- if b_force_quads is true, tesselated mesh will contain quadriliterals,
 *		  otherwise triangles; non-tesselated mesh is always made of triangles
 *		- r_t_mesh is filled with sphere data; any original contents are deleted
 *		- returns true on success, false on failure
 */
bool CMakeGeoSphere::MakeGeoSphere(CPolyMesh &r_t_mesh,
	int n_tesselation, bool b_force_quads, float f_radius)
{
	CPolyMesh t_mesh;
	if(!t_mesh.Alloc(12, 20))
		return false;
	for(int i = 0; i < 12; ++ i) {
		t_mesh.r_Vertex(i) = CPolyMesh::TVertex(m_p_vertex[i][0],
			m_p_vertex[i][1], m_p_vertex[i][2]);
	}
	for(int i = 0; i < 20; ++ i) {
		CPolyMesh::TRefVertex p_vertex_ptr[3] = {
			t_mesh.t_RefVertex(m_p_face[i][0]),
			t_mesh.t_RefVertex(m_p_face[i][1]),
			t_mesh.t_RefVertex(m_p_face[i][2])
		};

		CPolyMesh::CPolygon &r_face = t_mesh.r_Polygon(i);
		_ASSERTE(!r_face.n_Vertex_Num());
		if(!r_face.Add_Vertex(0, p_vertex_ptr, 3))
			return false;
		// creates a new polygon

		r_face.SetFlags(0);
		r_face.SetMaterial(-1);
		// set no material
	}
	// creates an icosahedron mesh

#if 0 // more precise, nicer output (more uniform polygons)
	CSpherify::Spherify(t_mesh, Vector3f(0, 0, 0), f_radius);
	// spherify the result, make the right radius

	for(int i = 0; i < n_tesselation; ++ i) {
		if(!CTesselate::Tesselate(t_mesh, b_force_quads))
			return false;
		// apply tesselation modifier

		CSpherify::Spherify(t_mesh, Vector3f(0, 0, 0), f_radius);
		// spherify the result and make the right radius again
	}
#else // less precise, faster
	for(int i = 0; i < n_tesselation; ++ i) {
		if(!CTesselate::Tesselate(t_mesh, b_force_quads))
			return false;
	}
	// apply tesselation modifier

	CSpherify::Spherify(t_mesh, Vector3f(0, 0, 0), f_radius);
	// spherify the result, make the right radius
#endif

	if(!t_mesh.OptimizeVertices(false, false, false))
		return false;
	// optimize vertices, tesselation generates double edges

	t_mesh.CalcFaceNormals();
	t_mesh.CalcVertexNormals_Simple();
	// calculate normals

	r_t_mesh.Swap(t_mesh);

	return true;
}

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