/*
								+----------------------------------+
								|                                  |
								| ***  Simple spline surfaces  *** |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|          SplineSurf.cpp          |
								|                                  |
								+----------------------------------+
*/

/**
 *	@file lml/SplineSurf.cpp
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief simple spline surfaces
 *
 *	@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
// disable warning C4786 "identifier was truncated to '255' characters in the debug information"

#include "../NewFix.h"

#include "../CallStack.h"
#include <algorithm>
#include <math.h>
#include "../Vector.h"
#include "../BitArray.h"
#include "../MinMax.h"
#include "PolyMesh.h"
#include "PlatPrim.h"
#include "SplineSurf.h"

/*
 *								=== CSplineSurf ===
 */

bool CSplineSurf::MakeExtrudeSurf(CPolyMesh &r_mesh, const CSplineSampler<Vector3f> &r_spline,
	Vector3f v_extrude, size_t n_tess_spline, size_t n_tess_extrusion,
	CPolyMesh::TMaterialId n_material, bool b_flip)
{
	_ASSERTE(n_tess_spline < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_extrusion < SIZE_MAX); // otherwise loops
	if(n_tess_spline < 1)
		n_tess_spline = 1;
	if(n_tess_extrusion < 1)
		n_tess_extrusion = 1;
	// min tesselation check

	size_t n_vertex_num = (n_tess_spline + 1) * (n_tess_extrusion + 1);
	size_t n_poly_num = n_tess_spline * n_tess_extrusion;
	if(!r_mesh.Alloc(n_vertex_num, n_poly_num))
		return false;
	// allocate mesh

	Vector3f v_extrude_step = v_extrude * (1.0f / n_tess_extrusion);
	float f_t_step = 1.0f / n_tess_spline;
	float f_t = 0;
	size_t n_out_vertex = 0;
	for(size_t j = 0; j <= n_tess_spline; ++ j, f_t += f_t_step) {
		Vector3f v_point = r_spline.v_Position(f_t);
		Vector3f v_tangent = r_spline.v_Derivative(f_t);
		Vector3f v_normal = v_extrude_step.v_Cross(v_tangent);
		v_normal.Normalize();
		for(size_t i = 0; i <= n_tess_extrusion; ++ i, ++ n_out_vertex, v_point += v_extrude_step) {
			CPolyMesh::_TyVertex t_tmp(v_point);
			t_tmp.v_normal = (b_flip)? -v_normal : v_normal;
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_t, float(i) / n_tess_extrusion, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());
	// create vertices

	if(!CPlatonicPrimitives::WindGrid(r_mesh, 0, 0, n_tess_extrusion,
	   n_tess_spline, b_flip, n_material)) // todo - revise code, add materials
		return false;
	// create polygons

	return true;
}

bool CSplineSurf::MakeRuledSurf(CPolyMesh &r_mesh,
	const CSplineSampler<Vector3f> &r_left_spline,
	const CSplineSampler<Vector3f> &r_right_spline,
	size_t n_tess_left_spline, size_t n_tess_right_spline,
	size_t n_tess_cross_section, CPolyMesh::TMaterialId n_material, bool b_flip)
{
	_ASSERTE(n_tess_left_spline < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_right_spline < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_cross_section < SIZE_MAX); // otherwise loops
	if(n_tess_left_spline < 1)
		n_tess_left_spline = 1;
	if(n_tess_right_spline < 1)
		n_tess_right_spline = 1;
	if(n_tess_cross_section < 1)
		n_tess_cross_section = 1;
	// min tesselation check

	if(n_tess_left_spline == n_tess_right_spline) {
		return MakeRuledSurf2(r_mesh, r_left_spline, r_right_spline, n_tess_left_spline,
			n_tess_cross_section, n_tess_cross_section, n_material, b_flip);
	}
	// in cases where tesselation on both splines is the same, MakeRuledSurf2() is faster
	// as it evaluates spline points fewer times

	CSkewGridSubdivision subdivision(n_tess_cross_section,
		n_tess_left_spline, n_tess_right_spline);
	// create subdivision scheme

	if(!r_mesh.Alloc(subdivision.n_Vertex_Num(), subdivision.n_Triangle_Num()))
		return false;
	// alloc mesh

	float f_t_step = 1.0f / n_tess_cross_section, f_t = 0;
	size_t n_out_vertex = 0;
	for(size_t j = 0; j <= n_tess_cross_section; ++ j, f_t += f_t_step) {
		size_t n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(size_t i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_left(r_left_spline.v_Position(f_s));
			Vector3f v_right(r_right_spline.v_Position(f_s)); // calc positions
			v_right -= v_left; // calc distance
			Vector3f v_point = v_left + v_right * f_t; // lerp position
			// calculate vertex position

			Vector3f v_normal;
			Vector3f v_left_n(r_left_spline.v_Derivative(f_s));
			Vector3f v_right_n(r_right_spline.v_Derivative(f_s)); // calc tangents
			if(v_right.f_Length() > f_epsilon) {
				v_left_n.Cross(-v_right);
				v_left_n.Normalize();
				v_right_n.Cross(-v_right);
				v_right_n.Normalize(); // cross with distance yields normal, normalize result
				v_right_n -= v_left_n; // calc normal distance
				v_normal = v_left_n + v_right_n * f_t; // lerp normal
			} else {
				v_normal = v_left_n.v_Cross(v_right_n);
				if(!i)
					v_normal *= -1; // hack - think of better sollution
				// points are identical. use cross-product of tangents instead
			}
			v_normal.Normalize(); // renormalize one last time
			// calculate vertex normal

			CPolyMesh::_TyVertex t_tmp(v_point);
			t_tmp.v_normal = (b_flip)? -v_normal : v_normal;
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());

	if(!subdivision.CreateWinding(r_mesh, 0, 0, b_flip, n_material))
		return false;
	// create winding

	return true;
}

bool CSplineSurf::MakeRuledSurf2(CPolyMesh &r_mesh,
	const CSplineSampler<Vector3f> &r_left_spline,
	const CSplineSampler<Vector3f> &r_right_spline,
	size_t n_tess_splines, size_t n_tess_cross_section_begin,
	size_t n_tess_cross_section_end, CPolyMesh::TMaterialId n_material, bool b_flip)
{
	_ASSERTE(n_tess_splines < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_cross_section_begin < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_cross_section_end < SIZE_MAX); // otherwise loops
	if(n_tess_splines < 1)
		n_tess_splines = 1;
	if(n_tess_cross_section_begin < 1)
		n_tess_cross_section_begin = 1;
	if(n_tess_cross_section_end < 1)
		n_tess_cross_section_end = 1;
	// min tesselation check

	CSkewGridSubdivision subdivision(n_tess_splines,
		n_tess_cross_section_begin, n_tess_cross_section_end);
	// create subdivision scheme

	if(!r_mesh.Alloc(subdivision.n_Vertex_Num(), subdivision.n_Triangle_Num()))
		return false;
	// alloc mesh

	// todo - transpose the loops
	float f_s_step = 1.0f / n_tess_splines, f_s = 0;
	size_t n_out_vertex = 0;
	for(size_t j = 0; j <= n_tess_splines; ++ j, f_s += f_s_step) {
		Vector3f v_left(r_left_spline.v_Position(f_s));
		Vector3f v_right(r_right_spline.v_Position(f_s)); // calc positions
		v_right -= v_left; // calc distance
		Vector3f v_left_n(r_left_spline.v_Derivative(f_s));
		Vector3f v_right_n(r_right_spline.v_Derivative(f_s)); // calc tangents

		size_t n_col_num = subdivision.n_Width(j);
		float f_t_step = 1.0f / n_col_num, f_t = 0;
		for(size_t i = 0; i <= n_col_num; ++ i, f_t += f_t_step, ++ n_out_vertex) {
			Vector3f v_point = v_left + v_right * f_t; // lerp position
			// calculate vertex position

			Vector3f v_normal;
			if(v_right.f_Length() > f_epsilon) {
				v_left_n.Cross(-v_right);
				v_left_n.Normalize();
				v_right_n.Cross(-v_right);
				v_right_n.Normalize(); // cross with distance yields normal, normalize result
				v_right_n -= v_left_n; // calc normal distance
				v_normal = v_left_n + v_right_n * f_t; // lerp normal
			} else {
				v_normal = v_left_n.v_Cross(v_right_n);
				if(!i)
					v_normal *= -1; // hack - think of better sollution
				// points are identical. use cross-product of tangents instead
			}
			v_normal.Normalize(); // renormalize one last time
			// calculate vertex normal

			CPolyMesh::_TyVertex t_tmp(v_point);
			t_tmp.v_normal = (b_flip)? -v_normal : v_normal;
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());

	if(!subdivision.CreateWinding(r_mesh, 0, 0, b_flip, n_material))
		return false;
	// create winding

	return true;
}

bool CSplineSurf::MakeRevolutionSurf(CPolyMesh &r_mesh,
	const CSplineSampler<Vector2f> &r_spline, size_t n_tess_spline,
	size_t n_tess_radius, bool b_bottom_cap, bool b_top_cap,
	CPolyMesh::TMaterialId n_material, bool b_weld_bottom_vertex,
	bool b_weld_top_vertex, bool b_flip)
{
	_ASSERTE(!b_weld_bottom_vertex || !b_bottom_cap); // can't be used together
	_ASSERTE(!b_weld_top_vertex || !b_top_cap); // can't be used together

	if(b_weld_bottom_vertex) {
		if(n_tess_spline > 0)
			-- n_tess_spline;
		b_bottom_cap = true;
	}
	if(b_weld_top_vertex) {
		if(n_tess_spline > 0)
			-- n_tess_spline;
		b_top_cap = true;
	}
	// take care of bottom / top vertex welding

	if(n_tess_spline < 1)
		n_tess_spline = 1;
	if(n_tess_radius < 3)
		n_tess_radius = 3;
	_ASSERTE(n_tess_spline < SIZE_MAX); // otherwise loops
	_ASSERTE(n_tess_radius < SIZE_MAX); // otherwise loops
	// min tesselation check

	size_t n_coat_vertex_num = (n_tess_spline + 1) * (n_tess_radius + 1);
	size_t n_coat_face_num = n_tess_spline * n_tess_radius;
	size_t n_cap_num = ((b_bottom_cap)? 1 : 0) + ((b_top_cap)? 1 : 0);
	size_t n_cap_vertex_num = n_cap_num; // in both caps
	size_t n_cap_face_num = n_tess_radius * n_cap_num; // in both caps
	if(!r_mesh.Alloc(n_coat_vertex_num + n_cap_vertex_num, n_coat_face_num + n_cap_face_num))
		return false;
	// alloc vertices and faces

	float f_y_step = 1.0f / (n_tess_spline + ((b_weld_bottom_vertex)? 1 : 0) + ((b_weld_top_vertex)? 1 : 0));
	float f_y = (b_weld_bottom_vertex)? f_y_step : 0;
	float f_r_step = float((2 * f_pi) / n_tess_radius);
	size_t n_out_vertex = 0;
	for(size_t j = 0; j <= n_tess_spline; ++ j, f_y += f_y_step) {
		float f_angle_r = 0;
		for(size_t i = 0; i <= n_tess_radius; ++ i, f_angle_r += f_r_step, ++ n_out_vertex) {
			Vector2f v_spline(r_spline.v_Position(f_y));
			Vector2f v_normal(r_spline.v_Derivative(f_y).v_yx() * Vector2f(1, -1));
			v_normal.Normalize();
			// calculate spline point and surface normal at that point

			Vector3f v_x(float(-sin(f_angle_r)), 0, float(cos(f_angle_r)));
			Vector3f v_y(0, 1, 0);
			//Vector3f v_z(float(cos(f_angle_r)), 0, float(sin(f_angle_r)));
			// calculate (partial) rotation matrix

			Vector3f v_spline_rot(v_x * v_spline.x + v_y * v_spline.y);
			Vector3f v_normal_rot(v_x * v_normal.x + v_y * v_normal.y);
			// rotate

			CPolyMesh::_TyVertex t_tmp(v_spline_rot);
			t_tmp.v_normal = (b_flip)? -v_normal_rot : v_normal_rot;
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(float(i) / n_tess_radius, f_y, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	// generate coat vertices

	size_t n_bottom_vertex = n_out_vertex;
	if(b_bottom_cap) {
		r_mesh.r_Vertex(n_bottom_vertex) = CPolyMesh::_TyVertex(0, r_spline.v_Position(0).y, 0);
		r_mesh.r_Vertex(n_bottom_vertex).v_normal = Vector3f(0, (b_flip)? 1.0f : -1.0f, 0);
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
		r_mesh.r_Vertex(n_bottom_vertex).p_texture_coord[0] = Vector4f(0, 0, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
		++ n_out_vertex;
	}
	size_t n_top_vertex = n_out_vertex;
	if(b_top_cap) {
		r_mesh.r_Vertex(n_top_vertex) = CPolyMesh::_TyVertex(0, r_spline.v_Position(1).y, 0);
		r_mesh.r_Vertex(n_top_vertex).v_normal = Vector3f(0, (b_flip)? -1.0f : 1.0f, 0);
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
		r_mesh.r_Vertex(n_top_vertex).p_texture_coord[0] = Vector4f(0, 1, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
		++ n_out_vertex;
	}
	// generate bottom-most top-most and vertices if necessary

	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());
	// makes sure all the vertices are used

	if(!CPlatonicPrimitives::WindGrid(r_mesh, 0, 0, n_tess_radius, n_tess_spline, b_flip, n_material))
		return false;
	if(b_bottom_cap && !CPlatonicPrimitives::WindFan(r_mesh, n_coat_face_num,
	   n_bottom_vertex, 0, n_tess_radius + 1, false, !b_flip, n_material))
		return false;
	if(b_top_cap && !CPlatonicPrimitives::WindFan(r_mesh, n_coat_face_num +
	   ((b_bottom_cap)? n_tess_radius : 0), n_top_vertex, n_coat_vertex_num -
	   n_tess_radius - 1, n_tess_radius + 1, false, b_flip, n_material))
		return false;
	// create windings

	return true;
}

void CSplineSurf::RailBases(const CSplineSampler<Vector3f> &r_left_spline,
	const CSplineSampler<Vector3f> &r_right_spline, float f_t, bool b_dist_scaling,
	bool b_unskew, Matrix4f &r_t_left_basis, Matrix4f &r_t_right_basis)
{
	Vector3f v_left(r_left_spline.v_Position(f_t));
	Vector3f v_right(r_right_spline.v_Position(f_t));
	// calc positions

	Vector3f v_left_t(r_left_spline.v_Derivative(f_t));
	v_left_t.Normalize();
	Vector3f v_right_t(r_right_spline.v_Derivative(f_t));
	v_right_t.Normalize();
	// calc tangents

	Vector3f v_normal = v_right - v_left;
	float f_dist = v_normal.f_Length();
	if(f_dist < f_epsilon)
		v_normal = v_left_t.v_Orthogonal(v_right_t); // already normalized; what does it do?
	else
		v_normal /= f_dist; // normalize
	// calc normal

	Vector3f v_left_b = v_normal.v_Cross(v_left_t);
	Vector3f v_right_b = v_normal.v_Cross(v_right_t);
	v_left_b.Normalize();
	v_right_b.Normalize();
	Vector3f v_right_n = (b_unskew)? v_right_b.v_Cross(v_right_t) : v_normal;
	Vector3f v_left_n = (b_unskew)? v_left_b.v_Cross(v_left_t) : v_normal;
	if(b_unskew) {
		v_left_n.Normalize();
		v_right_n.Normalize();
	}
	// create the coordinate bases

	r_t_left_basis.Identity();
	if(b_dist_scaling) {
		r_t_left_basis.Right(v_left_t * f_dist);
		r_t_left_basis.Up(v_left_b * f_dist);
	} else {
		r_t_left_basis.Right(v_left_t);
		r_t_left_basis.Up(v_left_b);
	}
	r_t_left_basis.Dir(v_left_n * f_dist);
	r_t_left_basis.Offset(v_left);
	r_t_right_basis.Identity();
	if(b_dist_scaling) {
		r_t_right_basis.Right(v_right_t * f_dist);
		r_t_right_basis.Up(v_right_b * f_dist);
	} else {
		r_t_right_basis.Right(v_right_t);
		r_t_right_basis.Up(v_right_b);
	}
	r_t_right_basis.Dir(v_right_n * f_dist);
	r_t_right_basis.Offset(v_right);
	// convert them to matrices
}

bool CSplineSurf::MakeRailSweep(CPolyMesh &r_mesh, const CSplineSampler<Vector3f> &r_left_rail,
	const CSplineSampler<Vector3f> &r_right_rail, const CSplineSampler<Vector3f> &r_connect_spline,
	float f_connect_spline_position, size_t n_tess_rail, size_t n_tess_connect_spline_begin,
	size_t n_tess_connect_spline_end, CPolyMesh::TMaterialId n_material, bool b_flip,
	bool b_scale, bool b_unskew)
{
	_ASSERTE(n_tess_rail < SIZE_MAX); // loops otherwise
	_ASSERTE(n_tess_connect_spline_begin < SIZE_MAX); // loops otherwise
	_ASSERTE(n_tess_connect_spline_end < SIZE_MAX); // loops otherwise
	if(n_tess_rail < 1)
		n_tess_rail = 1;
	if(n_tess_connect_spline_begin < 1)
		n_tess_connect_spline_begin = 1;
	if(n_tess_connect_spline_end < 1)
		n_tess_connect_spline_end = 1;
	// min tesselation check

	CSkewGridSubdivision subdivision(n_tess_rail,
		n_tess_connect_spline_begin, n_tess_connect_spline_end);
	// create subdivision scheme

	if(!r_mesh.Alloc(subdivision.n_Vertex_Num(), subdivision.n_Triangle_Num()))
		return false;
	// alloc mesh

	Matrix4f t_left_basis0, t_right_basis0;
	RailBases(r_left_rail, r_right_rail, f_connect_spline_position,
		b_scale, b_unskew, t_left_basis0, t_right_basis0);
	t_left_basis0.Offset(r_connect_spline.v_Position(0));
	t_left_basis0.Invert_Inplace();
	//t_left_basis0 *= -1;
	t_right_basis0.Offset(r_connect_spline.v_Position(1));
	t_right_basis0.Invert_Inplace();
	//t_right_basis0 *= -1;
	// calculate inverse of bases where connecting spline is defined

	size_t n_out_vertex = 0;
	float f_t_step = 1.0f / n_tess_rail, f_t = 0;
	for(size_t j = 0; j <= n_tess_rail; ++ j, f_t += f_t_step) {
		Matrix4f t_left_basis, t_right_basis;
		RailBases(r_left_rail, r_right_rail, f_t, b_scale, b_unskew, t_left_basis, t_right_basis);
		t_left_basis = t_left_basis * t_left_basis0;
		t_right_basis = t_right_basis * t_right_basis0;
		// calculate rotation / scaling matrices

		size_t n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(size_t i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_pos = r_connect_spline.v_Position(f_s);
			Vector3f v_pos_l = t_left_basis.v_Transform_Pos(v_pos);
			Vector3f v_pos_r = t_right_basis.v_Transform_Pos(v_pos);
			Vector3f v_position = v_pos_l + (v_pos_r - v_pos_l) * f_s;
			// calculate position

			CPolyMesh::_TyVertex t_tmp(v_position);
			t_tmp.v_normal = Vector3f(0, (b_flip)? -1.0f : 1.0f, 0); // cheap normal "approximation" // todo - generate proper normals
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());

	if(!subdivision.CreateWinding(r_mesh, 0, 0, b_flip, n_material))
		return false;
	// create winding

	return true;
}

bool CSplineSurf::MakeRailSweep2(CPolyMesh &r_mesh,
	const CSplineSampler<Vector3f> &r_left_rail,
	const CSplineSampler<Vector3f> &r_right_rail,
	const CSplineSampler<Vector3f> &r_conn_spline_0,
	const CSplineSampler<Vector3f> &r_conn_spline_1,
	size_t n_tess_rail, size_t n_tess_connect_spline_begin,
	size_t n_tess_connect_spline_end, CPolyMesh::TMaterialId n_material,
	bool b_flip, bool b_scale, bool b_unskew)
{
	_ASSERTE(n_tess_rail < SIZE_MAX); // loops otherwise
	_ASSERTE(n_tess_connect_spline_begin < SIZE_MAX); // loops otherwise
	_ASSERTE(n_tess_connect_spline_end < SIZE_MAX); // loops otherwise
	if(n_tess_rail < 1)
		n_tess_rail = 1;
	if(n_tess_connect_spline_begin < 1)
		n_tess_connect_spline_begin = 1;
	if(n_tess_connect_spline_end < 1)
		n_tess_connect_spline_end = 1;
	// min tesselation check

	CSkewGridSubdivision subdivision(n_tess_rail,
		n_tess_connect_spline_begin, n_tess_connect_spline_end);
	// create subdivision scheme

	if(!r_mesh.Alloc(subdivision.n_Vertex_Num(), subdivision.n_Triangle_Num()))
		return false;
	// alloc mesh

	Matrix4f t_left_basis0, t_right_basis0;
	RailBases(r_left_rail, r_right_rail, 0,
		b_scale, b_unskew, t_left_basis0, t_right_basis0);
	t_left_basis0.Offset(r_conn_spline_0.v_Position(0));
	t_left_basis0.Invert_Inplace();
	//t_left_basis0 *= -1;
	t_right_basis0.Offset(r_conn_spline_0.v_Position(1));
	t_right_basis0.Invert_Inplace();
	//t_right_basis0 *= -1;
	Matrix4f t_left_basis1, t_right_basis1;
	RailBases(r_left_rail, r_right_rail, 1,
		b_scale, b_unskew, t_left_basis1, t_right_basis1);
	t_left_basis1.Offset(r_conn_spline_1.v_Position(0));
	t_left_basis1.Invert_Inplace();
	//t_left_basis1 *= -1;
	t_right_basis1.Offset(r_conn_spline_1.v_Position(1));
	t_right_basis1.Invert_Inplace();
	//t_right_basis1 *= -1;
	// calculate inverse of bases where connecting splines are defined

	float f_t_step = 1.0f / n_tess_rail, f_t = 0;
	size_t n_out_vertex = 0;
	for(size_t j = 0; j <= n_tess_rail; ++ j, f_t += f_t_step) {
		Matrix4f t_left_basis_a, t_right_basis_a, t_left_basis_b, t_right_basis_b;
		RailBases(r_left_rail, r_right_rail, f_t, b_scale, b_unskew,
			t_left_basis_b, t_right_basis_b);
		t_left_basis_a = t_left_basis_b * t_left_basis0;
		t_right_basis_a = t_right_basis_b * t_right_basis0;
		t_left_basis_b *= t_left_basis1;
		t_right_basis_b *= t_right_basis1;
		// calculate rotation / scaling matrices

		size_t n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(size_t i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_pos0 = r_conn_spline_0.v_Position(f_s);
			Vector3f v_pos_l0 = t_left_basis_a.v_Transform_Pos(v_pos0);
			Vector3f v_pos_r0 = t_right_basis_a.v_Transform_Pos(v_pos0);
			Vector3f v_position0 = v_pos_l0 + (v_pos_r0 - v_pos_l0) * f_s;
			Vector3f v_pos1 = r_conn_spline_1.v_Position(f_s);
			Vector3f v_pos_l1 = t_left_basis_b.v_Transform_Pos(v_pos1);
			Vector3f v_pos_r1 = t_right_basis_b.v_Transform_Pos(v_pos1);
			Vector3f v_position1 = v_pos_l1 + (v_pos_r1 - v_pos_l1) * f_s;
			Vector3f v_position = v_position0 + (v_position1 - v_position0) * f_t;
			// calculate position (even more blending here)

			CPolyMesh::_TyVertex t_tmp(v_position);
			t_tmp.v_normal = Vector3f(0, (b_flip)? -1.0f : 1.0f, 0); // cheap normal "approximation" // todo - generate proper normals
#ifdef __SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // __SPLINE_SURF_GENERATE_TEXCOORDS
			r_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	_ASSERTE(n_out_vertex == r_mesh.n_Vertex_Num());

	if(!subdivision.CreateWinding(r_mesh, 0, 0, b_flip, n_material))
		return false;
	// create winding

	return true;
}

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

/*
 *								=== CSplineSurf::CSkewGridSubdivision ===
 */

CSplineSurf::CSkewGridSubdivision::CSkewGridSubdivision(size_t n_height,
	size_t n_bottom_width, size_t n_top_width)
	:m_n_height(n_height), m_n_bottom_width(n_bottom_width), m_n_top_width(n_top_width)
{
	m_n_vertex_num = 0;
	m_n_triangle_num = 0;
	for(size_t i = 0, n_tess = n_Width(i); i <= m_n_height; ++ i) {
		size_t n_next_tess = n_Width(i + 1);
		m_n_vertex_num += n_tess + 1;
		if(i < m_n_height) {
			m_n_triangle_num += n_tess + n_next_tess; // triangles
			//m_n_polygon_num += max(n_tess, n_next_tess); // mixed quads and triangles
		}
		n_tess = n_next_tess;
	}
	// count polygons and vertices
}

size_t CSplineSurf::CSkewGridSubdivision::n_Width(size_t n_row) const
{
	return (m_n_bottom_width >= m_n_top_width)?
		m_n_bottom_width - ((m_n_bottom_width - m_n_top_width) * n_row) / m_n_height :
		m_n_bottom_width + ((m_n_top_width - m_n_bottom_width) * n_row) / m_n_height;
}

bool CSplineSurf::CSkewGridSubdivision::CreateWinding(CPolyMesh &r_mesh,
	size_t n_face, size_t n_vertex, bool b_flip, CPolyMesh::TMaterialId n_material)
{
	try {
		size_t n_width = n_Width(0);
		for(size_t j = 0; j < m_n_height; ++ j) {
			size_t n_width1 = n_Width(j + 1); // calculate number of edges at the next line
			size_t n_vertex1 = n_vertex + n_width + 1; // calculate vertex pointer to the next line
			for(size_t i = 0, n = max(n_width, n_width1); i < n; ++ i) {
				size_t p_vertex_idx[6], *p_vertex = p_vertex_idx;
				// buffer for vertex indices

				*p_vertex = n_vertex + (n_width * i + (n / 2)) / n;
				*(p_vertex + 1) = n_vertex + (n_width * (i + 1) + (n / 2)) / n;
				if(*p_vertex != *(p_vertex + 1))
					++ p_vertex;
				++ p_vertex;
				*p_vertex = n_vertex1 + (n_width1 * (i + 1) + (n / 2)) / n;
				*(p_vertex + 1) = n_vertex1 + (n_width1 * i + (n / 2)) / n;
				if(*p_vertex != *(p_vertex + 1))
					++ p_vertex;
				++ p_vertex;
				// generate 3 or 4 different vertex indices

				size_t n_vertex_num = p_vertex - p_vertex_idx;
				_ASSERTE(n_vertex_num >= 3);
				// calculate number of vertices

				if(b_flip) {
					for(size_t k = 0, l = n_vertex_num - 1; k < l; ++ k, -- l)
						std::swap(p_vertex_idx[k], p_vertex_idx[l]);
				}
				// flip indices if necessary

				int n_face_num;
				if(n_vertex_num == 3)
					n_face_num = 1;
				else {
					n_face_num = 2;
					if(((Vector3f)r_mesh.r_Vertex(p_vertex_idx[0]) -
					   (Vector3f)r_mesh.r_Vertex(p_vertex_idx[2])).f_Length2() <
					   ((Vector3f)r_mesh.r_Vertex(p_vertex_idx[1]) -
					   (Vector3f)r_mesh.r_Vertex(p_vertex_idx[3])).f_Length2()) {
						p_vertex_idx[4] = p_vertex_idx[3];
						p_vertex_idx[3] = p_vertex_idx[2];
						p_vertex_idx[5] = p_vertex_idx[0];
						// split quad by shorter edge between vertices 0 and 2 (012, 230)
					} else {
						p_vertex_idx[4] = p_vertex_idx[2];
						p_vertex_idx[2] = p_vertex_idx[5] = p_vertex_idx[3];
						p_vertex_idx[3] = p_vertex_idx[1];
						// split quad by shorter edge between vertices 1 and 3 (013, 123)
					}
				}
				// decide number of faces, permutate indices

				const size_t *p_idx_ptr = p_vertex_idx;
				for(int k = 0; k < n_face_num; ++ k, p_idx_ptr += 3, ++ n_face) {
					_ASSERTE(n_face <= m_n_triangle_num);
					CPolyMesh::_TyPolygon &r_face = r_mesh.r_Polygon(n_face);
					r_face.Delete_Vertices(0, r_face.n_Vertex_Num());
					// clear face
				
					CPolyMesh::_TyRefVertex p_vertex_ptr[3] = {
						r_mesh.t_RefVertex(p_idx_ptr[0]),
						r_mesh.t_RefVertex(p_idx_ptr[1]),
						r_mesh.t_RefVertex(p_idx_ptr[2])
					};
					r_face.Insert_Vertex(0, p_vertex_ptr, p_vertex_ptr + 3);
					// add vertices

					r_face.Set_SurfaceFlags(0);
					r_face.Set_MaterialId(n_material);
					// set no material
				}
				// create 1 or 2 faces
			}
			n_width = n_width1;
			n_vertex = n_vertex1;
		}
		// create winding

		_ASSERTE(n_face == m_n_triangle_num);
		// make sure we used all faces
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

/*
 *								=== ~CSplineSurf::CSkewGridSubdivision ===
 */
