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

/**
 *	@file dev/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 ===
 */

/*
 *	static bool CSplineSurf::MakeExtrudeSurf(CPolyMesh &r_t_mesh,
 *		const CSpline<Vector3f> &r_spline, Vector3f v_extrude, int n_tess_spline,
 *		int n_tess_extrusion = 1, bool b_flip = false)
 *		- creates surface of spline r_spline extruded in direction v_extrude
 *		- n_tess_spline is number of points on spline and n_tess_extrusion is
 *		  number of points along extrusion direction (over-tesselation)
 *		- setting b_flip flips surface faces
 *		- returns true on success, false on failure
 */
bool CSplineSurf::MakeExtrudeSurf(CPolyMesh &r_t_mesh, const CSpline<Vector3f> &r_spline,
	Vector3f v_extrude, int n_tess_spline, int n_tess_extrusion, bool b_flip)
{
	if(n_tess_spline < 1)
		n_tess_spline = 1;
	if(n_tess_extrusion < 1)
		n_tess_extrusion = 1;
	// min tesselation check

	int n_vertex_num = (n_tess_spline + 1) * (n_tess_extrusion + 1);
	int n_poly_num = n_tess_spline * n_tess_extrusion;
	if(!r_t_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;
	for(int j = 0, n_out_vertex = 0; j <= n_tess_spline; ++ j, f_t += f_t_step) {
		Vector3f v_point = r_spline.v_Position_SCS(f_t);
		Vector3f v_tangent = r_spline.v_Derivative_SCS(f_t);
		Vector3f v_normal = v_extrude_step.v_Cross(v_tangent);
		v_normal.Normalize();
		for(int i = 0; i <= n_tess_extrusion; ++ i, ++ n_out_vertex, v_point += v_extrude_step) {
			CPolyMesh::TVertex 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_t_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	// create vertices

	if(!CPlatonicPrimitives::WindGrid(r_t_mesh, 0, 0, n_tess_extrusion, n_tess_spline, b_flip))
		return false;
	// create polygons

	return true;
}

/*
 *	static bool CSplineSurf::MakeRuledSurf(CPolyMesh &r_t_mesh,
 *		const CSpline<Vector3f> &r_left_spline, const CSpline<Vector3f> &r_right_spline,
 *		int n_tess_left_spline, int n_tess_right_spline, int n_tess_cross_section = 1,
 *		bool b_flip = false)
 *		- creates surface of moving line connecting points of r_left_spline with
 *		  corrseponding points of r_right_spline (points at the same position on the spline)
 *		- n_tess_left_spline is number of points on left spline, n_tess_right_spline
 *		  is number of points on right spline and n_tess_cross_section is
 *		  number of points along the line between splines (over-tesselation)
 *		- setting b_flip flips surface faces
 *		- returns true on success, false on failure
 */
bool CSplineSurf::MakeRuledSurf(CPolyMesh &r_t_mesh, const CSpline<Vector3f> &r_left_spline,
	const CSpline<Vector3f> &r_right_spline, int n_tess_left_spline, int n_tess_right_spline,
	int n_tess_cross_section, bool b_flip)
{
	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

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

	if(!r_t_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;
	for(int j = 0, n_out_vertex = 0; j <= n_tess_cross_section; ++ j, f_t += f_t_step) {
		int n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(int i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_left(r_left_spline.v_Position_SCS(f_s));
			Vector3f v_right(r_right_spline.v_Position_SCS(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_SCS(f_s));
			Vector3f v_right_n(r_right_spline.v_Derivative_SCS(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::TVertex 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_t_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}

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

	return true;
}

/*
 *	static bool CSplineSurf::MakeRevolutionSurf(CPolyMesh &r_t_mesh,
 *		const CSpline<Vector2f> &r_spline, int n_tess_spline, int n_tess_radius,
 *		bool b_bottom_cap, bool b_top_cap, bool b_weld_top_vertex = false,
 *		bool b_weld_bottom_vertex = false, bool b_flip = false)
 *		- creates surface of spline r_spline revolution arround
 *		  y-axis and stores it to r_t_mesh
 *		- n_tess_spline is number of points on spline and
 *		  n_tess_radius is number of revolution steps
 *		- b_bottom_cap or b_top_cap enables construction of flat
 *		  cap on bottom or top end of spline, respectively
 *		  (cap is triangle fan, perpendicular to y-axis)
 *		- b_weld_top_vertex or b_weld_bottom_vertex tells the function
 *		  spline top or bottom vertex, respectively, lies at y-axis
 *		  and therefore is identical for all revolution steps, so
 *		  top or bottom part of mesh, respectively, is triangle fan.
 *		  note these options can not be used with b_bottom_cap
 *		  or b_top_cap, respectively
 *		- note 'bottom' refers to starting point of spline and 'top' to endpoint
 *		- setting b_flip flips surface faces
 *		- returns true on success, false on failure
 */
bool CSplineSurf::MakeRevolutionSurf(CPolyMesh &r_t_mesh, const CSpline<Vector2f> &r_spline,
	int n_tess_spline, int n_tess_radius, bool b_bottom_cap, bool b_top_cap,
	bool b_weld_top_vertex, bool b_weld_bottom_vertex, bool b_flip)
{
	if(b_weld_bottom_vertex) {
		-- n_tess_spline;
		b_bottom_cap = true;
	}
	if(b_weld_top_vertex) {
		-- 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;
	// min tesselation check

	int n_coat_vertex_num = (n_tess_spline + 1) * (n_tess_radius + 1);
	int n_coat_face_num = n_tess_spline * n_tess_radius;
	int n_cap_num = ((b_bottom_cap)? 1 : 0) + ((b_top_cap)? 1 : 0);
	int n_cap_vertex_num = n_cap_num; // in both caps
	int n_cap_face_num = n_tess_radius * n_cap_num; // in both caps
	if(!r_t_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 = (2 * f_pi) / n_tess_radius;
	int n_out_vertex = 0;
	for(int j = 0; j <= n_tess_spline; ++ j, f_y += f_y_step) {
		float f_angle_r = 0;
		for(int i = 0; i <= n_tess_radius; ++ i, f_angle_r += f_r_step, ++ n_out_vertex) {
			Vector2f v_spline(r_spline.v_Position_SCS(f_y));
			Vector2f v_normal(r_spline.v_Derivative_SCS(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::TVertex 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_t_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}
	// generate coat vertices

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

	if(!CPlatonicPrimitives::WindGrid(r_t_mesh, 0, 0, n_tess_radius, n_tess_spline, b_flip))
		return false;
	if(b_bottom_cap && !CPlatonicPrimitives::WindFan(r_t_mesh, n_coat_face_num,
	   n_bottom_vertex, 0, n_tess_radius + 1, false, !b_flip))
		return false;
	if(b_top_cap && !CPlatonicPrimitives::WindFan(r_t_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))
		return false;
	// create windings

	return true;
}

/*
 *	static void CSplineSurf::RailBases(const CSpline<Vector3f> &r_left_spline,
 *		const CSpline<Vector3f> &r_right_spline, float f_t, bool b_dist_scaling,
 *		bool b_unskew, Matrix4f &r_t_left_basis, Matrix4f &r_t_right_basis)
 *		- calculates two basis matrices for point on r_left_spline and on r_right_spline,
 *		  both on position f_t on the splines. bases are aligned with spline tangents and
 *		  with line connecting the points. setting b_dist_scaling scales matrices with
 *		  distance between points, setting b_unskew assures both matrices define orthogonal
 *		  coordinate bases.
 *		- note the bases cannot be constructed if the points are identical and
 *		  spline tangents on them are collinear (but that should be rather rare)
 */
void CSplineSurf::RailBases(const CSpline<Vector3f> &r_left_spline,
	const CSpline<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_SCS(f_t));
	Vector3f v_right(r_right_spline.v_Position_SCS(f_t));
	// calc positions

	Vector3f v_left_t(r_left_spline.v_Derivative_SCS(f_t));
	v_left_t.Normalize();
	Vector3f v_right_t(r_right_spline.v_Derivative_SCS(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);
	v_normal.Normalize();
	// calc normal

	Vector3f v_left_b = v_normal.v_Cross(v_left_t);
	v_left_b.Normalize();
	Vector3f v_left_n = (b_unskew)? v_left_b.v_Cross(v_left_t) : v_normal;
	Vector3f v_right_b = v_normal.v_Cross(v_right_t);
	v_right_b.Normalize();
	Vector3f v_right_n = (b_unskew)? v_right_b.v_Cross(v_right_t) : v_normal;
	// create 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
}

/*
 *	static bool CSplineSurf::MakeRailSweep(CPolyMesh &r_t_mesh,
 *		const CSpline<Vector3f> &r_left_rail, const CSpline<Vector3f> &r_right_rail,
 *		const CSpline<Vector3f> &r_connect_spline, float f_connect_spline_position,
 *		int n_tess_rail, int n_tess_connect_spline_begin, int n_tess_connect_spline_end,
 *		bool b_flip = false, bool b_scale = true, bool b_unskew = false)
 *		- creates surface by sweeping spline r_connect_spline connecting corresponding points
 *		  on the left and the right spline (points at the same position on the spline)
 *		- f_connect_spline_position is position where connection spline is attached to rails
 *		- n_tess_rail is number of points on left and right spline (rails),
 *		  n_tess_connect_spline_begin and n_tess_connect_spline_end is number of points
 *		  on the connecting spline on the beginning and on the end of rails, respectively
 *		- setting b_flip flips surface faces
 *		- setting b_scale scales connection spline depending on distance it connects
 *		- setting b_unskew forces orthogonal matrices for transforming spline position
 *		  which may lead to some unexpected surface shapes
 *		- returns true on success, false on failure
 *		- note this doesn't calculate normals (lot of blending involved, it's cheaper
 *		  to use CPolyMesh::CalcVertexNormals_Simple())
 */
bool CSplineSurf::MakeRailSweep(CPolyMesh &r_t_mesh, const CSpline<Vector3f> &r_left_rail,
	const CSpline<Vector3f> &r_right_rail, const CSpline<Vector3f> &r_connect_spline,
	float f_connect_spline_position, int n_tess_rail, int n_tess_connect_spline_begin,
	int n_tess_connect_spline_end, bool b_flip, bool b_scale, bool b_unskew)
{
	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_t_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_SCS(0));
	t_left_basis0.FullInvert();
	t_left_basis0 *= -1;
	t_right_basis0.Offset(r_connect_spline.v_Position_SCS(1));
	t_right_basis0.FullInvert();
	t_right_basis0 *= -1;
	// calculate inverse of bases where connecting spline is defined

	float f_t_step = 1.0f / n_tess_rail, f_t = 0;
	for(int j = 0, n_out_vertex = 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

		int n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(int i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_pos = r_connect_spline.v_Position_SCS(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::TVertex t_tmp(v_position);
			t_tmp.v_normal = Vector3f(0, (b_flip)? -1.0f : 1.0f, 0); // cheap (and rather bizarre) normal approximation
#ifdef SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // SPLINE_SURF_GENERATE_TEXCOORDS
			r_t_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}

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

	return true;
}

/*
 *	static bool CSplineSurf::MakeRailSweep2(CPolyMesh &r_t_mesh,
 *		const CSpline<Vector3f> &r_left_rail, const CSpline<Vector3f> &r_right_rail,
 *		const CSpline<Vector3f> &r_conn_spline_0, const CSpline<Vector3f> &r_conn_spline_1,
 *		int n_tess_rail, int n_tess_connect_spline_begin, int n_tess_connect_spline_end,
 *		bool b_flip = false, bool b_scale = true, bool b_unskew = false)
 *		- creates surface by sweeping spline connecting corresponding points on left
 *		  and right spline (points at the same position on the spline)
 *		- r_conn_spline_0 and r_conn_spline_1 are morph targets of connection spline
 *		  on the beginning and on the end of rails
 *		- n_tess_rail is number of points on left and right spline (rails),
 *		  n_tess_connect_spline_begin and n_tess_connect_spline_end is number of points
 *		  on the connecting spline on the beginning and on the end of rails, respectively
 *		- setting b_flip flips surface faces
 *		- setting b_scale scales connection spline depending on distance it connects
 *		- setting b_unskew forces orthogonal matrices for transforming spline position
 *		  which may lead to some unexpected surface shapes
 *		- returns true on success, false on failure
 *		- note this doesn't calculate normals (lot of blending involved, it's cheaper
 *		  to use CPolyMesh::CalcVertexNormals_Simple())
 */
bool CSplineSurf::MakeRailSweep2(CPolyMesh &r_t_mesh, const CSpline<Vector3f> &r_left_rail,
	const CSpline<Vector3f> &r_right_rail, const CSpline<Vector3f> &r_conn_spline_0,
	const CSpline<Vector3f> &r_conn_spline_1, int n_tess_rail, int n_tess_connect_spline_begin,
	int n_tess_connect_spline_end, bool b_flip, bool b_scale, bool b_unskew)
{
	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_t_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_SCS(0));
	t_left_basis0.FullInvert();
	t_left_basis0 *= -1;
	t_right_basis0.Offset(r_conn_spline_0.v_Position_SCS(1));
	t_right_basis0.FullInvert();
	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_SCS(0));
	t_left_basis1.FullInvert();
	t_left_basis1 *= -1;
	t_right_basis1.Offset(r_conn_spline_1.v_Position_SCS(1));
	t_right_basis1.FullInvert();
	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;
	for(int j = 0, n_out_vertex = 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

		int n_col_num = subdivision.n_Width(j);
		float f_s_step = 1.0f / n_col_num, f_s = 0;
		for(int i = 0; i <= n_col_num; ++ i, f_s += f_s_step, ++ n_out_vertex) {
			Vector3f v_pos0 = r_conn_spline_0.v_Position_SCS(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_SCS(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::TVertex t_tmp(v_position);
			t_tmp.v_normal = Vector3f(0, (b_flip)? -1.0f : 1.0f, 0); // cheap (and rather bizarre) normal approximation
#ifdef SPLINE_SURF_GENERATE_TEXCOORDS
			t_tmp.p_texture_coord[0] = Vector4f(f_s, f_t, 0, 1);
#endif // SPLINE_SURF_GENERATE_TEXCOORDS
			r_t_mesh.r_Vertex(n_out_vertex) = t_tmp;
			// generate vertex
		}
	}

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

	return true;
}

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

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

/*
 *	CSplineSurf::CSkewGridSubdivision::CSkewGridSubdivision(int n_height,
 *		int n_bottom_width, int n_top_width)
 *		- default constructor; n_height is number of grid lines,
 *		  n_bottom_width is number of columns in the first line
 *		  and n_top_width is number of columns in the last line
 *		- calculates total vertex and polygon num for later use
 */
CSplineSurf::CSkewGridSubdivision::CSkewGridSubdivision(int n_height,
	int n_bottom_width, int 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(int i = 0, n_tess = n_Width(i); i <= m_n_height; ++ i) {
		int 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
}

/*
 *	int CSplineSurf::CSkewGridSubdivision::n_Width(int n_row) const
 *		- returns number of grid columns at line with zero-based index n_row
 *		  (equals to number of vertices - 1 in that line)
 *		- note this is just linear interpolation
 */
int CSplineSurf::CSkewGridSubdivision::n_Width(int n_row) const
{
	return m_n_bottom_width - ((m_n_bottom_width - m_n_top_width) * n_row) / m_n_height;
}

/*
 *	bool CSplineSurf::CSkewGridSubdivision::CreateWinding(CPolyMesh &r_t_mesh,
 *		int n_face, int n_vertex, bool b_flip = false)
 *		- creates grid winding in mesh r_t_mesh (must have allocated sufficient number
 *		  of vertices and polygons), n_face is index of first face to be used, n_vertex
 *		  is index of first grid vertex
 *		- setting b_flip reverses face vertex order
 *		- returns true on success, false on failure
 */
bool CSplineSurf::CSkewGridSubdivision::CreateWinding(CPolyMesh &r_t_mesh,
	int n_face, int n_vertex, bool b_flip)
{
	int n_width = n_Width(0);
	for(int j = 0; j < m_n_height; ++ j) {
		int n_width1 = n_Width(j + 1); // calculate number of edges at the next line
		int n_vertex1 = n_vertex + n_width + 1; // calculate vertex pointer to the next line
		for(int i = 0, n = max(n_width, n_width1); i < n; ++ i) {
			int 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

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

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

			int n_face_num;
			if(n_vertex_num == 3)
				n_face_num = 1;
			else {
				n_face_num = 2;
				if((r_t_mesh.t_Vertex(p_vertex_idx[0]).v_position -
				   r_t_mesh.t_Vertex(p_vertex_idx[2]).v_position).f_Length2() <
				   (r_t_mesh.t_Vertex(p_vertex_idx[1]).v_position -
				   r_t_mesh.t_Vertex(p_vertex_idx[3]).v_position).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 int *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::CPolygon &r_face = r_t_mesh.r_Polygon(n_face);
				r_face.Delete_Vertices(0, r_face.n_Vertex_Num());
				// clear face
			
				CPolyMesh::TRefVertex p_vertex_ptr[3] = {
					r_t_mesh.t_RefVertex(p_idx_ptr[0]),
					r_t_mesh.t_RefVertex(p_idx_ptr[1]),
					r_t_mesh.t_RefVertex(p_idx_ptr[2])
				};
				if(!r_face.Add_Vertex(0, p_vertex_ptr, 3))
					return false;
				// add vertices

				r_face.SetFlags(0);
				r_face.SetMaterial(-1);
				// 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

	return true;
}

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