/*
								+----------------------------------+
								|                                  |
								|    ***  Polygon template  ***    |
								|                                  |
								|   Copyright © -tHE SWINe- 2007   |
								|                                  |
								|            Polygon.h             |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __POLYGON_INCLUDED
#define __POLYGON_INCLUDED

/**
 *	@file dev/Polygon.h
 *	@date 2007
 *	@author -tHE SWINe-
 *	@brief polygon template
 *
 *	@date 2007-02-28
 *
 *	removed error in CPolygon2<TVertStruct>::Cut and CPolygon2<TVertStruct>::Split
 *	in cases edge was longer than 1 treshold for adding new edge vertex was bigger
 *	than epsilon so potencial maximal vertex - plane distance deviation was greater
 *	than epsilon. old code also always generated new vertex even in case it was not
 *	going to be used.
 *	fixed unnecessary / double vertices issue in CPolygon2<TVertStruct>::Split
 *
 *	@date 2008-02-01
 *
 *	improved CPolygon2::Split and CPolygon2::Cut, it now gives much nicer outputs
 *	in cases when polygon is almost backside and only single (few) vertices are onplane
 *
 *	@date 2008-06-04
 *
 *	added bool b_MT_RayHit() function for ray-polygon hit testing using Moller-Trumbore
 *	rewritten most of functions so std::vector::size() isn't called so offen
 *
 *	@date 2008-06-24
 *
 *	renamed CPolygon2::r_t_Vertex() and CPolyMesh::r_t_Vertex() to
 *	CPolygon2::r_Vertex() and CPolyMesh::r_Vertex() respectively
 *
 *	@date 2009-04-23
 *
 *	fixed some minor bugs for versions of STL where pointer isn't the same type as
 *	iterator.
 *	fixed major bug in CPolygon::n_Plane_Pos() where position plane_Back was
 *	never detected.
 *
 *	@date 2009-05-03
 *
 *	added explicit epsilon to the most of polygon operations, added some overloads
 *	of ray hit test functions
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2009-10-19
 *
 *	removed exception-specification throw(std::bad_alloc) from TRefVertex constructor
 *	and copy operator, as compilers ignore it 
 *
 *	@date 2010-12-20
 *
 *	fixed error in TRefVertex, m_p_vertex_pool must be a pointer, not a reference,
 *	otherwise TRefVertex::operator =(const TRefVertex&) is flawed.
 *
 *	added comments to where vertex pool throws occur, caught them inside CPolygon2.
 *
 *	changed loop counters from unsigned int to size_t, re-checked boundary conditions.
 *
 *	CPolygon2 copy-constructor and copy-operator now throws std::bad_alloc.
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 */

#include "../NewFix.h"
#include "../Integer.h"
#include "../StlUtils.h"

/*
 *	template <class TBaseVertex>
 *	struct TRefVertex
 *		- template for creating reference vertices for any arbitrary vertices
 */
template <class TBaseVertex>
struct TRefVertex {
	TBaseVertex *m_p_ref; // referenced vertex
	std::vector<TBaseVertex*> *m_p_vertex_pool; // vertex pool (here we're going to add new vertices)

	typedef TBaseVertex TIntermediate;
	// intermediate type for calculations will be TBaseVertex

	/*
	 *	inline TRefVertex(const TBaseVertex &r_t_vertex, std::vector<TBaseVertex*> &r_vertex_pool)
	 *		- default constructor
	 */
	inline TRefVertex(const TBaseVertex &r_t_vertex, std::vector<TBaseVertex*> &r_vertex_pool) /*throw(std::bad_alloc)*/
		:m_p_ref(0), m_p_vertex_pool(&r_vertex_pool)
	{
		m_p_ref = new TBaseVertex(r_t_vertex); // alloc a new TBaseVertex
		m_p_vertex_pool->push_back(m_p_ref); // insert it to the list
	}

	/*
	 *	inline TRefVertex(typename std::vector<TBaseVertex*>::iterator p_vertex,
	 *		std::vector<TBaseVertex*> &r_vertex_pool)
	 *		- reference vertex that is already in the list
	 */
	inline TRefVertex(typename std::vector<TBaseVertex*>::iterator p_vertex,
		std::vector<TBaseVertex*> &r_vertex_pool)
		:m_p_ref(*p_vertex), m_p_vertex_pool(&r_vertex_pool)
	{}

	/*
	 *	inline TRefVertex(const TRefVertex &r_t_vertex)
	 *		- copy constructor
	 */
	inline TRefVertex(const TRefVertex &r_t_vertex)
		:m_p_ref(r_t_vertex.m_p_ref), m_p_vertex_pool(r_t_vertex.m_p_vertex_pool)
	{}

	/*
	 *	inline TRefVertex operator =(const TRefVertex &r_t_vertex)
	 *		- copy operator = (need it to avoid unwanted conversions)
	 */
	inline TRefVertex operator =(const TRefVertex &r_t_vertex)
	{
		m_p_ref = r_t_vertex.m_p_ref;
		m_p_vertex_pool = r_t_vertex.m_p_vertex_pool;

		return *this;
	}

	/*
	 *	inline TRefVertex operator =(const TBaseVertex &r_t_vertex)
	 *		- conversion from TBaseVertex to TRefVertex (conversion
	 *		  is solved by adding vertex to the vertex list)
	 */
	inline TRefVertex operator =(const TBaseVertex &r_t_vertex) /*throw(std::bad_alloc)*/
	{
		m_p_ref = new TBaseVertex(r_t_vertex); // alloc a new TBaseVertex
		m_p_vertex_pool->push_back(m_p_ref); // insert it to the list

		return *this;
	}

	/*
	 *	inline operator TBaseVertex() const
	 *		- now we need means to convert vertex type to intermediate vertex type
	 */
	inline operator TBaseVertex() const
	{
		return *m_p_ref;
	}

	/*
	 *	inline operator Vector3f() const
	 *		- conversion to Vector3f should return vertex position
	 */
	inline operator Vector3f() const
	{
		return (Vector3f)*m_p_ref;
	}

	/*
	 *	inline TRefVertex operator =(const Vector3f &r_v_position)
	 *		- assigning Vector3f should write to vertex position
	 */
	inline TRefVertex operator =(const Vector3f &r_v_position)
	{
		*m_p_ref = r_v_position;
		return *this;
	}

	/*
	 *	inline bool operator ==(const TBaseVertex &r_t_vertex)
	 *		- we might need means to compare two vertices
	 *		- constant f_epsilon is used as maximal coordinate distance tolerance
	 */
	inline bool operator ==(const TBaseVertex &r_t_vertex)
	{
		return *m_p_ref == r_t_vertex;
	}

	/*
	 *	TVertex operator *(float f_scalar) const
	 *		- return vertex, scaled by f_scalar
	 *		- returns a new TBaseVertex because new vertex originated
	 *		  (in case it will need to be converted to TRefVertex, it will be added to the list)
	 */
	TBaseVertex operator *(float f_scalar) const
	{
		return *m_p_ref * f_scalar;
	}

	/*
	 *	TBaseVertex operator +(const TBaseVertex &r_vertex) const
	 *		- return vertex with sum of coordinates of both original vertices
	 *		- returns a new TBaseVertex because new vertex originated
	 *		  (in case it will need to be converted to TRefVertex, it will be added to the list)
	 */
	TBaseVertex operator +(const TBaseVertex &r_vertex) const
	{
		return *m_p_ref + r_vertex;
	}

	/*
	 *	TRefVertex operator *=(float f_scalar) const
	 *		- return vertex, scaled by f_scalar
	 *		- returns this because no new vertex originated
	 *		  (coordinates of some existing vertex were scaled only)
	 */
	TRefVertex operator *=(float f_scalar)
	{
		*m_p_ref *= f_scalar;
		return *this;
	}

	/*
	 *	TRefVertex operator +=(const TBaseVertex &r_vertex) const
	 *		- return vertex with sum of coordinates of both original vertices
	 *		- returns this because no new vertex originated
	 *		  (coordinates of some existing vertex were scaled only)
	 */
	TRefVertex operator +=(const TBaseVertex &r_vertex)
	{
		*m_p_ref += r_vertex;
		return *this;
	}
};

/**
 *	@brief an empty structure (default for polygon's materials and flags)
 */
struct TPolygon2_EmptyType {};

/*
 *	template <class TVertStruct, class TFlags, class TMaterialId>
 *	class CPolygon2
 *		- simple convex polygon template
 */
template <class TVertStruct, class TFlags = TPolygon2_EmptyType, class TMaterialId = TPolygon2_EmptyType>
class CPolygon2 {
protected:
	std::vector<TVertStruct> m_vertex_list;
	Plane3f m_t_normal;
	TFlags m_n_flags;
	TMaterialId m_n_material;

public:
	/*
	 *	inline CPolygon2()
	 *		- default constructor
	 */
	inline CPolygon2()
	{}

	/*
	 *	CPolygon2(const CPolygon2<TVertStruct> &r_other)
	 *		- copy-constructor
	 *		- note in case there's not enough memory, vertex list
	 *		  is left empty (no exception is thrown)
	 */
	CPolygon2(const CPolygon2<TVertStruct> &r_other) /*throw(std::bad_alloc)*/
		:m_t_normal(r_other.m_t_normal), m_n_flags(r_other.m_n_flags)
	{
		if(!stl_ut::Reserve_N(m_vertex_list, r_other.m_vertex_list.size())) {
			throw std::bad_alloc();
			return; // ...
		}
		m_vertex_list.insert(m_vertex_list.begin(),
			r_other.m_vertex_list.begin(), r_other.m_vertex_list.end());
	}

	/*
	 *	bool operator =(const CPolygon2<TVertStruct> &r_other)
	 *		- copy operation. all current vertices are removed, new vertices and normal
	 *		  are copied from r_other polygon
	 *		- returns true on success or false in case there was not enough memory for vertices
	 */
	CPolygon2<TVertStruct> &operator =(const CPolygon2<TVertStruct> &r_other) /*throw(std::bad_alloc)*/
	{
		if(&r_other == this)
			return *this;
		// handle self-assignment

		m_t_normal = r_other.m_t_normal;
		m_n_flags = r_other.m_n_flags;
		// copy normal, flags

		m_vertex_list.clear();
		if(!stl_ut::Reserve_N(m_vertex_list, r_other.m_vertex_list.size())) {
			throw std::bad_alloc();
			return *this;
		}
		// alloc vertex list

		m_vertex_list.insert(m_vertex_list.begin(),
			r_other.m_vertex_list.begin(), r_other.m_vertex_list.end());
		// copy vertex list

		return *this;
	}

	/*
	 *	void Delete()
	 *		- deletes all polygon vertices
	 */
	void Delete()
	{
		m_vertex_list.clear();
	}

	/*
	 *	inline bool Add_Vertex(const TVertStruct &r_t_vertex)
	 *		- adds a single vertex past the last vertex in the array
	 */
	inline bool Add_Vertex(const TVertStruct &r_t_vertex)
	{
		return Add_Vertex(m_vertex_list.size(), &r_t_vertex, 1);
	}

	/*
	 *	inline bool Add_Vertex(unsigned int n_insert_before, const TVertStruct &r_t_vertex)
	 *		- adds a single vertex before the n_insert_before-th vertex in the array
	 */
	inline bool Add_Vertex(size_t n_insert_before, const TVertStruct &r_t_vertex)
	{
		return Add_Vertex(n_insert_before, &r_t_vertex, 1);
	}

	/*
	 *	inline bool Add_Vertex(const TVertStruct *p_vertex, unsigned int n_count)
	 *		- adds array of vertices past the last vertex in the array
	 */
	inline bool Add_Vertex(const TVertStruct *p_vertex, size_t n_count)
	{
		return Add_Vertex(m_vertex_list.size(), p_vertex, n_count);
	}

	/*
	 *	bool Add_Vertex(unsigned int n_insert_before, const TVertStruct *p_vertex, unsigned int n_count)
	 *		- adds array of vertices before the n_insert_before-th vertex in the array
	 */
	bool Add_Vertex(size_t n_insert_before, const TVertStruct *p_vertex, size_t n_count)
	{
		if(!stl_ut::Reserve_NMore(m_vertex_list, n_count))
			return false;
		m_vertex_list.insert(m_vertex_list.begin() + n_insert_before,
			p_vertex, p_vertex + n_count);
		return true;
	}

	/*
	 *	void Delete_Vertices(int n_index, int n_count)
	 *		- deletes n_count vertices, beginning with vertex n_index
	 */
	void Delete_Vertices(size_t n_index, size_t n_count)
	{
		m_vertex_list.erase(m_vertex_list.begin() + n_index, m_vertex_list.begin() + (n_index + n_count));
	}

	/*
	 *	inline int n_Vertex_Num() const
	 *		- returns number of vertices
	 */
	inline size_t n_Vertex_Num() const
	{
		return m_vertex_list.size();
	}

	/*
	 *	inline TFlags n_Flags() const
	 *		- returns polygon flags
	 */
	inline TFlags n_Flags() const
	{
		return m_n_flags;
	}

	/*
	 *	inline void SetFlags(TFlags n_flags)
	 *		- sets polygon material
	 */
	inline void SetFlags(TFlags n_flags)
	{
		m_n_flags = n_flags;
	}

	/*
	 *	inline TMaterialId n_Material() const
	 *		- returns polygon flags
	 */
	inline TMaterialId n_Material() const
	{
		return m_n_material;
	}

	/*
	 *	inline void SetMaterial(TMaterialId n_flags)
	 *		- sets polygon material
	 */
	inline void SetMaterial(TMaterialId n_material)
	{
		m_n_material = n_material;
	}

	/*
	 *	inline TVertStruct &r_Vertex(int n_index) const
	 *		- vertex access function
	 *		- doesn't check array bounds
	 */
	inline TVertStruct &r_Vertex(int n_index)
	{
		return m_vertex_list[n_index];
	}

	/*
	 *	inline TVertStruct &t_Vertex(int n_index) const
	 *		- vertex access function
	 *		- doesn't check array bounds
	 */
	inline const TVertStruct &t_Vertex(int n_index) const
	{
		return m_vertex_list[n_index];
	}

	/*
	 *	const Vector3f v_Center() const
	 *		- return position of center of polygon
	 *		- if polygon has no vertices, return the O vector
	 */
	const Vector3f v_Center() const
	{
		if(m_vertex_list.empty())
			return Vector3f(0, 0, 0);

		Vector3f v_center(0, 0, 0);
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i)
			v_center += m_vertex_list[i];

		return v_center * (1.0f / m_vertex_list.size());
	}

	/*
	 *	const typename TVertStruct::TIntermediate t_Center() const
	 *		- return vertex in center of polygon
	 *		- if polygon has no vertices, return the O vertex
	 */
	const typename TVertStruct::TIntermediate t_Center() const
	{
		TVertStruct::TIntermediate t_center(Vector3f(0, 0, 0));
		if(m_vertex_list.empty())
			return t_center;

		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i)
			t_center += m_vertex_list[i]; // this is TIntermediate, no throw

		return t_center * (1.0f / m_vertex_list.size());
	}

	/*
	 *	bool Calc_Normal()
	 *		- calculate normal, return false if there wasn't trinity
	 *		  of vertices to construct plane from
	 *		- it has to be called explicitly, it is never called by CPolygon2 itself
	 */
	bool Calc_Normal()
	{
		if(m_vertex_list.size() < 3)
			return false;
		// impossible with so little vertices

		for(size_t i = 1, n = m_vertex_list.size(); i < n; ++ i) {
			Vector3f v_u = (Vector3f)m_vertex_list[i - 1] - (Vector3f)m_vertex_list[i];
			if(v_u.f_Length() == 0)
				continue;
			// get non-zero vector

			for(size_t j = 0; j < n; ++ j) {
				if(j == i || j == i - 1)
					continue;
				Vector3f v_v = (Vector3f)m_vertex_list[j] - (Vector3f)m_vertex_list[i];
				if(v_v.f_Length() == 0)
					continue;
				// get another different non-zero vector

				Vector3f v_normal = v_u.v_Cross(v_v);
				if(v_normal.f_Length() == 0)
					continue;
				v_normal.Normalize();
				// colinear vectors would yield zero normal

				m_t_normal = Plane3f(m_vertex_list[0], v_normal);
				return true;
				// create plane
			}
		}

		return false;
	}

	/*
	 *	inline const Plane3f &t_Normal() const
	 *		- normal access function
	 */
	inline const Plane3f &t_Normal() const
	{
		return m_t_normal;
	}

	/*
	 *	inline Plane3f &t_Normal()
	 *		- normal access function
	 */
	inline Plane3f &r_t_Normal()
	{
		return m_t_normal;
	}

	/*
	 *	template <class CFunctionObject>
	 *	inline CFunctionObject for_each_vertex(CFunctionObject t_object)
	 *		- for-each cycle over polygon's vertices
	 */
	template <class CFunctionObject>
	inline CFunctionObject for_each_vertex(CFunctionObject t_object)
	{
		return std::for_each(m_vertex_list.begin(), m_vertex_list.end(), t_object);
	}

	/*
	 *	template <class CFunctionObject>
	 *	inline CFunctionObject for_each_vertex(CFunctionObject t_object) const
	 *		- for-each cycle over polygon's const vertices
	 */
	template <class CFunctionObject>
	inline CFunctionObject for_each_vertex(CFunctionObject t_object) const
	{
		return std::for_each(m_vertex_list.begin(), m_vertex_list.end(), t_object);
	}

	/*
	 *	void Swap_VertexOrder()
	 *		- swap vertex order, flip normal
	 */
	void Swap_VertexOrder()
	{
		m_t_normal.v_normal *= -1;
		m_t_normal.f_dist *= -1;

		if(!m_vertex_list.empty()) {
			for(size_t i = 0, j = m_vertex_list.size() - 1; i < j; ++ i, -- j) {
				TVertStruct t_tmp(m_vertex_list[i]); // this is copy-constructor, no throw
				m_vertex_list[i] = m_vertex_list[j]; // this is copy-operator, no throw
				m_vertex_list[j] = t_tmp; // this is copy-operator, no throw
			}
		}
		// swap vertices
	}

	/*
	 *	inline bool b_IsConvex(float f_epsilon_ex = 1e-3f) const
	 *		- returns true in case polygon is convex, otherwise returns false
	 */
	inline bool b_IsConvex(float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return true;
		// polygon with so little vertices can't be concave

		Vector3f v_u = (Vector3f)m_vertex_list[m_vertex_list.size() - 1] -
			(Vector3f)m_vertex_list[0];
		v_u.Normalize();
		for(size_t i = 0; i < m_vertex_list.size(); ++ i) {
			Vector3f v_v = (Vector3f)m_vertex_list[i] -
				(Vector3f)m_vertex_list[(i + 1) % m_vertex_list.size()];
			v_v.Normalize();
			// get two edge vectors ...

			if(v_u.v_Cross(m_t_normal.v_normal).f_Dot(v_v - v_u) < -f_epsilon_ex)
				return false;
			// see if difference vectors goes to the same side as cross
			// product of first edge vector with normal

			v_u = v_v;
		}

		return true;
	}

protected:
	/*
	 *	class CFindMaxPlaneDeviation
	 *		- simple function object for finding maximal
	 *	      absolute vertex deviation from normal plane
	 */
	class CFindMaxPlaneDeviation {
	protected:
		float m_f_max_deviation;
		const Plane3f &m_r_plane;

	public:
		inline CFindMaxPlaneDeviation(const Plane3f &r_plane)
			:m_r_plane(r_plane), m_f_max_deviation(0)
		{}

		inline void operator ()(const Vector3f &r_v_vertex_pos)
		{
			float f_deviation = (float)fabs(m_r_plane.f_Vector_Dist(r_v_vertex_pos));
			if(m_f_max_deviation < f_deviation)
				m_f_max_deviation = f_deviation;
		}

		inline operator float() const
		{
			return m_f_max_deviation;
		}
	};

public:
	/*
	 *	inline float f_MaxPlaneDeviation() const
	 *		- returns maximal absolute distance of polygon points from polygon plane
	 */
	inline float f_MaxPlaneDeviation() const
	{
		return std::for_each(m_vertex_list.begin(),
			m_vertex_list.end(), CFindMaxPlaneDeviation(m_t_normal));
	}

protected:
	/*
	 *	class CFindLongEdges
	 *		- small function object used to find third edge longer than epsilon
	 *		  (epsilon is explicitly specified in constructor)
	 */
	class CFindLongEdges {
	protected:
		Vector3f m_v_prev;
		float m_f_epsilon;
		int m_n_edge_num;

	public:
		inline CFindLongEdges(Vector3f v_prev, float f_epsilon_ex)
			:m_v_prev(v_prev), m_f_epsilon(f_epsilon_ex), m_n_edge_num(0)
		{}

		inline bool operator ()(Vector3f v_vertex)
		{
			if((m_v_prev - v_vertex).f_Length() >= m_f_epsilon) {
				if(m_n_edge_num == 2)
					return true;
				// in case there are three edges, triangle is not tiny

				++ m_n_edge_num;
			}
			// is the edge longer than epsilon?

			m_v_prev = v_vertex;

			return false;
		}
	};

public:
	/*
	 *	inline bool b_IsTiny(float f_epsilon_ex = 1e-3f) const
	 *		- returns true in case polygon doesn't contain at
	 *		  least three edges longer than epsilon, otherwise false
	 */
	inline bool b_IsTiny(float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return true;
		return std::find_if(m_vertex_list.begin(),
			m_vertex_list.end(), CFindLongEdges(m_vertex_list[m_vertex_list.size() - 1],
			f_epsilon_ex)) == m_vertex_list.end();
	}

protected:
	/*
	 *	class CEvalPlanePos
	 *		- small function object for evaluating polygon position against plane
	 */
	class CEvalPlanePos {
	protected:
		unsigned int m_n_front_num;
		unsigned int m_n_back_num;
		const Plane3f &m_r_t_plane;

	public:
		inline CEvalPlanePos(const Plane3f &r_t_plane)
			:m_r_t_plane(r_t_plane), m_n_front_num(0), m_n_back_num(0)
		{}

		inline void operator ()(const Vector3f &r_v_vertex) const
		{
			EPlanePos n_pos;
			if((n_pos = m_r_t_plane.n_Vector_Pos(r_v_vertex)) == plane_Front)
				++ m_n_front_num;
			else if(n_pos == plane_Back)
				++ m_n_back_num;
			// determine vertex side and increment counters accordingly

			return false;
		}

		inline operator EPlanePos() const
		{
			if(m_n_front_num) {
				if(!m_n_back_num)
					return plane_Front; // front propably occurres more frequently (in this branch)
				else
					return plane_Split;
			} else {
				if(m_n_back_num)
					return plane_Back; // back propably occurres more frequently (in this branch)
				else
					return plane_Onplane;
			}
		}
	};

public:
	/*
	 *	inline EPlanePos n_Plane_Pos(const Plane3f &r_t_plane) const
	 *		- returns relative position of polygon against plane r_t_plane
	 *		  (one of plane_Front, plane_Back, plane_Split or plane_Onplane)
	 *		- note polygons with no vertices will be classified as onplane
	 */
	inline EPlanePos n_Plane_Pos(const Plane3f &r_t_plane) const
	{
		return std::for_each(m_vertex_list.begin(),
			m_vertex_list.end(), CEvalPlanePos(r_t_plane));
	}

	/*
	 *	bool b_PointInside_SumAngles(Vector3f v_point, float f_epsilon_ex = 1e-3f) const
	 *		- returns true in case point v_point is inside the polygon
	 *		- uses method of summing up point-to-edge vector angles
	 */
	bool b_PointInside_SumAngles(Vector3f v_point, float f_epsilon_ex = 1e-3f) const
	{
		float f_angle_sum = 0;
		
		if(m_vertex_list.empty())
			return false;

		Vector3f v_prev = (Vector3f)m_vertex_list[m_vertex_list.size() - 1] - v_point;
		v_prev.Normalize();
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i) {
			Vector3f v_cur = (Vector3f)m_vertex_list[i] - v_point;
			v_cur.Normalize();
			// take two vectors ...

			f_angle_sum += (float)acos(v_prev.f_Dot(v_cur));
			// sum up the angles they hold

			v_prev = v_cur;
		}
		// sum up the angles

		return fabs(f_angle_sum - 2 * f_pi) < f_epsilon_ex;
		// in case difference from 2pi is less than epsilon, the point is inside
	}

	/*
	 *	bool b_PointInside_EdgePlanes(Vector3f v_point) const
	 *		- returns true in case point v_point is inside the polygon
	 *		- uses method of edge planes 'fence'
	 */
	bool b_PointInside_EdgePlanes(Vector3f v_point) const
	{
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i) {
			Vector3f v_u = (Vector3f)m_vertex_list[i] - (Vector3f)m_vertex_list[(i + 1) % n];
			// get an edge vector ...

			Vector3f v_v = v_point - (Vector3f)m_vertex_list[i];
			// get vector to point

			if(v_u.v_Cross(m_t_normal.v_normal).f_Dot(v_v) > 0)
				return false;
			// see if the point lies behind the 'fence' plane
			// (in case it does, it's outside)
		}

		return true;
	}

	/*
	 *	bool b_PointInside_Barycentric(Vector3f v_point) const
	 *		- returns true in case point v_point is inside the polygon
	 *		- uses barycentric coordinates and polygon to triangles decomposition
	 */
	bool b_PointInside_Barycentric(Vector3f v_point) const
	{
		for(size_t i = 1, n = m_vertex_list.size(); i + 1 < n; ++ i) {
			const TVertStruct *p_vert0 = &m_vertex_list[0];
			const TVertStruct *p_vert1 = &m_vertex_list[i];
			const TVertStruct *p_vert2 = &m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = (Vector3f)*p_vert1 - (Vector3f)*p_vert0,
					 v_edge2 = (Vector3f)*p_vert2 - (Vector3f)*p_vert0;
			float f_inv_length2_edge1 = 1.0f / v_edge1.f_Length2();
			Vector3f v_perp = v_edge2 - v_edge1 * (v_edge1.f_Dot(v_edge2) * f_inv_length2_edge1);
			Vector3f v_t = v_point - (Vector3f)*p_vert0;
			float f_u = v_t.f_Dot(v_perp) / v_perp.f_Dot(v_edge2);
			// calculate barycentric coordinates for v_point

			if(f_u < 0)
				continue;
			// first condition failed

			float f_v = (v_t - v_edge2 * f_u).f_Dot(v_edge1) * f_inv_length2_edge1;
			if(f_v >= 0 && f_u + f_v <= 1)
				return true;
			// in case the other conditions are satisfied as well, point lies inside
		}

		return false;
	}

protected:
	/*
	 *	class CTestVertices
	 *		- little function object for finding vertex, lying inside triangle specified
	 *		  by one vertex two of it's edges sharing the vertex, vector perpendicular
	 *		  to edge1 and inverse squared length of edge1 (barrycentric coords method)
	 */
	class CTestVertices {
	protected:
		Vector3f m_v_vert0, m_v_edge1, m_v_edge2, m_v_perp;
		float m_f_inv_length2_edge1;

	public:
		inline CTestVertices(Vector3f v_vert0, Vector3f v_edge1,
			Vector3f v_edge2, Vector3f v_perp, float f_inv_length2_edge1)
			:m_v_vert0(v_vert0), m_v_edge1(v_edge1), m_v_edge2(v_edge2), m_v_perp(v_perp),
			m_f_inv_length2_edge1(f_inv_length2_edge1)
		{}

		inline bool operator ()(const Vector3f &r_v_pos) const
		{
			Vector3f v_t = r_v_pos - m_v_vert0;
			float f_u = v_t.f_Dot(m_v_perp) / m_v_perp.f_Dot(m_v_edge2);
			// calculate barycentric coordinates for v_point

			if(f_u < 0)
				return false;
			// first condition failed

			float f_v = (v_t - m_v_edge2 * f_u).f_Dot(m_v_edge1) * m_f_inv_length2_edge1;
			return f_v >= 0 && f_u + f_v <= 1;
			// in case the other conditions are satisfied as well, point lies inside
		}
	};

public:
	/*
	 *	template <class CPolygon2/*<class TVertStruct2>* / >
	 *	bool b_Overlap_Barycentric(const CPolygon2/*<TVertStruct2>* / &r_poly2) const
	 *		- returns true in case r_poly2 overlaps this polygon, otherwise false
	 *		- uses barycentric coordinates test for determining wheter vertices
	 *		  from one polygon lies in the other one and vice verse
	 *		- note second polygon can be of another vertex type, this comes in handy
	 *		  when dealing with portals
	 *		- !! this is bugged !! (no points need to be inside for polygons to overlap,
	 *		  it's necessary to check polygon-edge intersections)
	 */
	template <class CPolygon2_TVertStruct2_ >
	bool b_Overlap_Barycentric(const CPolygon2_TVertStruct2_ &r_poly2) const
	{
#pragma message "!! this is bugged !!"

		for(size_t i = 1, n = m_vertex_list.size(); i + 1 < n; ++ i) {
			const TVertStruct *p_vert0 = &m_vertex_list[0];
			const TVertStruct *p_vert1 = &m_vertex_list[i];
			const TVertStruct *p_vert2 = &m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = (Vector3f)*p_vert1 - (Vector3f)*p_vert0,
					 v_edge2 = (Vector3f)*p_vert2 - (Vector3f)*p_vert0;
			float f_inv_length2_edge1 = 1.0f / v_edge1.f_Length2();
			Vector3f v_perp = v_edge2 - v_edge1 * (v_edge1.f_Dot(v_edge2) * f_inv_length2_edge1);

			if(std::find_if(r_poly2.m_vertex_list.begin(), r_poly2.m_vertex_list.end(),
			   CTestVertices(*p_vert0, v_edge1, v_edge2, v_perp, f_inv_length2_edge1)) <
			   r_poly2.m_vertex_list.end())
				return true;
			// see if any of those vertices lies in this part of polygon
		}
		// see if any of r_poly2's vertices lies in this polygon

		for(size_t i = 1, n = r_poly2.m_vertex_list.size(); i + 1 < n; ++ i) {
			const TVertStruct *p_vert0 = &r_poly2.m_vertex_list[0];
			const TVertStruct *p_vert1 = &r_poly2.m_vertex_list[i];
			const TVertStruct *p_vert2 = &r_poly2.m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = (Vector3f)*p_vert1 - (Vector3f)*p_vert0,
					 v_edge2 = (Vector3f)*p_vert2 - (Vector3f)*p_vert0;
			float f_inv_length2_edge1 = 1.0f / v_edge1.f_Length2();
			Vector3f v_perp = v_edge2 - v_edge1 * (v_edge1.f_Dot(v_edge2) *
				f_inv_length2_edge1);

			if(std::find_if(m_vertex_list.begin(), m_vertex_list.end(),
			   CTestVertices(*p_vert0, v_edge1, v_edge2, v_perp, f_inv_length2_edge1)) <
			   m_vertex_list.end())
				return true;
			// see if any of those vertices lies in this part of polygon
		}
		// see if any of this polygon's vertices lies in r_poly2

		return false;
	}

	/*
	 *	Vector3f v_NearestPoint(Vector3f &r_v_vector) const
	 *		- returns nearest point to r_v_vector contained by polygon
	 */
	Vector3f v_NearestPoint(Vector3f &r_v_vector) const
	{
		Vector3f v_projection = r_v_vector - m_t_normal.v_normal *
			(m_t_normal.v_normal.f_Dot(r_v_vector) + m_t_normal.f_dist);
		if(b_PointInside_Barycentric(v_projection))
			return v_projection;
		// calculate projection, then in case it's inside, return it

		/*if(b_PointInside_EdgePlanes(r_v_vector)) {
			Vector3f v_projection = r_v_vector - m_t_normal.v_normal *
				(m_t_normal.v_normal.f_Dot(r_v_vector) + m_t_normal.f_dist);
			return v_projection;
		}*/
		// in case it's inside, calculate projection and return it
		// possibly faster version using edge planes 'fence'

		Vector3f v_closest;
		float f_min_dist2 = 1e10f;
		Vector3f v_pt, v_prev_pt = m_vertex_list.back();
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i, v_prev_pt = v_pt) {
			v_pt = m_vertex_list[i];
			Vector3f v_u = v_pt - v_prev_pt;
			// get an edge vector ...

			Vector3f v_v = r_v_vector - v_prev_pt;
			// get vector from edge origin to point

			float f_t = v_u.f_Dot(v_v) / v_u.f_Length2();
			// get projection distance along the edge

			Vector3f v_projection;
			if(f_t <= 0)
				v_projection = v_prev_pt;
			else if(f_t >= 1)
				v_projection = v_pt;
			else
				v_projection = v_prev_pt + v_u * f_t;
			// get projection position

			float f_dist2 = (r_v_vector - v_projection).f_Length2();
			if(f_dist2 < f_min_dist2 || !i) {
				f_min_dist2 = f_dist2;
				v_closest = v_projection;
			}
			// find the closest projection
		}

		return v_closest;
	}

	/*
	 *	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test 
	 *		- v_org and v_dir are ray origin and direction
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);
			Vector3f v_t = r_v_org - v_vert0;
			Vector3f v_q = v_t.v_Cross(v_edge1);

			if(f_det > -f_epsilon_ex && f_det < f_epsilon_ex)
				continue;
			float f_inv_det = 1 / f_det;
			float f_u = v_t.f_Dot(v_p) * f_inv_det;
			if(f_u < 0 || f_u > 1)
				continue;
			float f_v = r_v_dir.f_Dot(v_q) * f_inv_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;
			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test 
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det > -f_epsilon_ex && f_det < f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			float f_u = v_t.f_Dot(v_p) * f_det;
			if(f_u < 0 || f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			float f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test 
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- r_f_u and r_f_v are barycentric coordinates of intersection
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det > -f_epsilon_ex && f_det < f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			r_f_u = v_t.f_Dot(v_p) * f_det;
			if(r_f_u < 0 || r_f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			r_f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(r_f_v < 0 || r_f_u + r_f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with front-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det < f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			float f_u = v_t.f_Dot(v_p) * f_det;
			if(f_u < 0 || f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			float f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with front-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det < f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			float f_u = v_t.f_Dot(v_p) * f_det;
			if(f_u < 0 || f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			float f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with front-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- r_f_u and r_f_v are barycentric coordinates of intersection
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullFF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det < f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			r_f_u = v_t.f_Dot(v_p) * f_det;
			if(r_f_u < 0 || r_f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			r_f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(r_f_v < 0 || r_f_u + r_f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with back-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det > -f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			float f_u = v_t.f_Dot(v_p) * f_det;
			if(f_u < 0 || f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			float f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with back-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det > -f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			float f_u = v_t.f_Dot(v_p) * f_det;
			if(f_u < 0 || f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			float f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(f_v < 0 || f_u + f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
	 *		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	 *		- Moller-Trumbore ray-triangle hit test with back-face culling
	 *		- v_org and v_dir are ray origin and direction
	 *		- r_f_t is time of ray hit (distance from origin in r_v_dir units)
	 *		- r_f_u and r_f_v are barycentric coordinates of intersection
	 *		- returns true if ray hits polygon, otherwise false
	 */
	bool b_RayHit_CullBF(const Vector3f &r_v_org, const Vector3f &r_v_dir,
		float &r_f_t, float &r_f_u, float &r_f_v, float f_epsilon_ex = 1e-3f) const
	{
		if(m_vertex_list.size() < 3)
			return false;
		for(size_t i = 1, n = m_vertex_list.size(); i < n - 1; ++ i) {
			Vector3f v_vert0 = (Vector3f)m_vertex_list[0];
			Vector3f v_vert1 = (Vector3f)m_vertex_list[i];
			Vector3f v_vert2 = (Vector3f)m_vertex_list[(i + 1) % n];

			Vector3f v_edge1 = v_vert1 - v_vert0,
					 v_edge2 = v_vert2 - v_vert0;
			Vector3f v_p = r_v_dir.v_Cross(v_edge2);
			float f_det = v_edge1.f_Dot(v_p);

			if(f_det > -f_epsilon_ex)
				continue;
			f_det = 1 / f_det;

			Vector3f v_t = r_v_org - v_vert0;

			r_f_u = v_t.f_Dot(v_p) * f_det;
			if(r_f_u < 0 || r_f_u > 1)
				continue;

			Vector3f v_q = v_t.v_Cross(v_edge1);

			r_f_v = r_v_dir.f_Dot(v_q) * f_det;
			if(r_f_v < 0 || r_f_u + r_f_v > 1)
				continue;

			r_f_t = v_edge2.f_Dot(v_q) * f_det;

			return true;
		}
		return false;
	}

	/*
	 *	bool Cut(const Plane3f &r_t_plane, EPlanePos n_desired_half = plane_Front,
	 *		float f_epsilon_ex = 1e-3f)
	 *		- cuts polygon by plane r_t_plane so only the half lying on n_desired_half side
	 *		  will remain. note plane_Front and plane_Back are the only allowed values
	 *		- returns true in case of success or false in case there was not enough memory
	 */
	bool Cut(const Plane3f &r_t_plane, EPlanePos n_desired_half = plane_Front,
		float f_epsilon_ex = 1e-3f)
	{
		//assert(n_desired_half == plane_Front || n_desired_half == plane_Back);

		if(m_vertex_list.empty())
			return true;
		// nothing to do here

		EPlanePos n_other_half = (n_desired_half == plane_Front)? plane_Back : plane_Front;
		// the other ('wrong one') position

		TVertStruct t_prev_vertex = m_vertex_list[m_vertex_list.size() - 1];
		bool b_prev_good_side = r_t_plane.n_Vector_Pos(t_prev_vertex) != n_other_half;
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i) {
			TVertStruct t_vertex = m_vertex_list[i];
			bool b_good_side = r_t_plane.n_Vector_Pos(t_vertex) != n_other_half;
			// determine plane sides previous and current vertex lies on

			if(b_good_side == b_prev_good_side) {
				if(b_good_side) {
					// both sides in front, keep vertex in the list 'as is'
				} else {
					// both sides in back, remove current vertex from the list

					m_vertex_list.erase(m_vertex_list.begin() + i);
					-- i;
					-- n;
				}
			} else {
				float f_t = r_t_plane.f_Vector_Dist(t_vertex);
				float f_subdivide_tresh = 1.0f / (f_t - r_t_plane.f_Vector_Dist(t_prev_vertex));
				f_t *= f_subdivide_tresh;
				// calculate distance of subdivision along the edge

				if(f_subdivide_tresh < 0)
					f_subdivide_tresh = -f_subdivide_tresh;
				f_subdivide_tresh *= f_epsilon_ex;
				// calculate treshold distance

				if(f_t > f_subdivide_tresh &&
				   f_t < 1 - f_subdivide_tresh) {
					// new vertex is far enough from existing vertices ...
					// (prevents from creating tiny edges)

					TVertStruct t_split_vertex(t_vertex); // this is copy-constructor, no throw (needs to copy reference to the vertex pool)
					try {
						t_split_vertex = t_vertex * (1 - f_t) + t_prev_vertex * f_t;
					} catch(std::nothrow&) {
						return false; // failed to add new vertex to the pool
					}
					// calculate a new vertex lying on edge in place where it's cut by the plane

					if(b_good_side) {
						// prev side was on the wrong position of plane, we have to insert
						// split vertex before current vertex

						if(!Add_Vertex(i, t_split_vertex)) // this is copy-operator, no throw
							return false;
						++ i;
						++ n;
					} else {
						// this side is on the wrong position, replace the current vertex by
						// split vertex

						m_vertex_list[i] = t_split_vertex; // this is copy-operator, no throw
					}
				} else if(!b_good_side) {
					m_vertex_list.erase(m_vertex_list.begin() + i);
					-- i;
					-- n;
				}
			}

			b_prev_good_side = b_good_side;
			t_prev_vertex = t_vertex; // this is copy-operator, no throw
		}
		// cut polygon

		return true;
	}

	/*
	 *	bool Split(const Plane3f &r_t_plane, CPolygon2<TVertStruct> &r_other,
	 *		EPlanePos n_desired_half = plane_Front, float f_epsilon_ex = 1e-3f)
	 *		- splits polygon by plane r_t_plane so only the half lying on n_desired_half side
	 *		  will remain. the other half is put inside r_other polygon. note plane_Front and
	 *		  plane_Back are the only allowed values
	 *		- returns true in case of success or false in case there was not enough memory
	 *		- note in case this becomes tiny polygon after operation, it's propable that r_other
	 *		  contains double vertex which is looked up and removed (TVertStruct should
	 *		  therefore either not implement operator == at all or it should be taken as vertex
	 *		  identity (no epsilons in it))
	 */
	bool Split(const Plane3f &r_t_plane, CPolygon2<TVertStruct> &r_other,
		EPlanePos n_desired_half = plane_Front, float f_epsilon_ex = 1e-3f)
	{
		_ASSERTE(n_desired_half == plane_Front || n_desired_half == plane_Back);

		r_other.m_t_normal = m_t_normal;
		// copy normal

		r_other.m_vertex_list.clear();
		// erase all the vertices

		if(m_vertex_list.empty())
			return true;
		// nothing to do here

		EPlanePos n_other_half = (n_desired_half == plane_Front)? plane_Back : plane_Front;
		// the other ('wrong one') position

		int n_added_vert = -1;

		TVertStruct t_prev_vertex = m_vertex_list[m_vertex_list.size() - 1];
		bool b_prev_good_side = r_t_plane.n_Vector_Pos(t_prev_vertex) != n_other_half;
		for(size_t i = 0, n = m_vertex_list.size(); i < n; ++ i) {
			TVertStruct t_vertex = m_vertex_list[i];
			int n_side = r_t_plane.n_Vector_Pos(t_vertex);
			bool b_good_side = n_side != n_other_half;
			// determine plane sides previous and current vertex lies on

			if(b_good_side == b_prev_good_side) {
				if(b_good_side) {
					// both sides in front, keep vertex in the list 'as is'

					if(n_side == plane_Onplane && !r_other.Add_Vertex(t_vertex)) // this is copy-operator, no throw
						return false;
					// add onplane vertices to the other one as well
				} else {
					// both sides in back, remove current vertex from the list

					if(!r_other.Add_Vertex(t_vertex)) // this is copy-operator, no throw
						return false;
					m_vertex_list.erase(m_vertex_list.begin() + i);
					-- i;
					-- n;
				}
			} else {
				float f_t = r_t_plane.f_Vector_Dist(t_vertex);
				float f_subdivide_tresh = 1.0f / (f_t - r_t_plane.f_Vector_Dist(t_prev_vertex));
				f_t *= f_subdivide_tresh;
				// calculate distance of subdivision along the edge

				if(f_subdivide_tresh < 0)
					f_subdivide_tresh = -f_subdivide_tresh;
				f_subdivide_tresh *= f_epsilon_ex;
				// calculate treshold distance

				if(f_t > f_subdivide_tresh &&
				   f_t < 1 - f_subdivide_tresh) {
					// new vertex is far enough from existing vertices ...
					// (prevents from creating tiny edges)

					// note these vertices won't be onplane because edge distance
					// is always greater or equal to plane distance

					TVertStruct t_split_vertex(t_vertex); // this is copy-operator, no throw (needs to copy reference to the vertex pool)
					try {
						t_split_vertex = t_vertex * (1 - f_t) + t_prev_vertex * f_t;
					} catch(std::bad_alloc&) {
						return false; // failed to add new vertex to the pool
					}
					// calculate a new vertex lying on edge in place where it's cut by the plane

					if(b_good_side) {
						// prev side was on the wrong position of plane, we have to insert
						// split vertex before current vertex

						if(!Add_Vertex(i, t_split_vertex) || // this is copy-operator, no throw
						   !r_other.Add_Vertex(t_split_vertex)) // this is copy-operator, no throw
							return false;
						++ i;
						++ n;
					} else {
						// this side is on the wrong position, replace the current vertex by
						// split vertex

						if(!r_other.Add_Vertex(t_split_vertex) || // this is copy-operator, no throw
						   !r_other.Add_Vertex(t_vertex)) // this is copy-operator, no throw
							return false;
						m_vertex_list[i] = t_split_vertex;
					}
				} else {
					// vertices with close intersection (not necessarily onplane)

					if(b_good_side) {
						// prev side was on the wrong position of plane, we have to insert
						// current vertex (== onplane-like) to the other poly and keep it in this one

						if(!r_other.Add_Vertex(t_vertex)) // this is copy-operator, no throw
							return false;
					} else {
						// prev side was onplane (if it wasn't we'd be in split section),
						// this side is back

						if(!r_other.Add_Vertex(t_vertex)) // this is copy-operator, no throw
							return false;
						m_vertex_list.erase(m_vertex_list.begin() + i);
						-- i;
						-- n;
					}
				}
			}

			b_prev_good_side = b_good_side;
			t_prev_vertex = t_vertex; // this is copy-operator, no throw
		}
		// cut polygon

		return true;
	}
};

#endif // __POLYGON_INCLUDED
