1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/PolyTools.h	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,224 @@
     1.4 +/*
     1.5 +Open Asset Import Library (assimp)
     1.6 +----------------------------------------------------------------------
     1.7 +
     1.8 +Copyright (c) 2006-2012, assimp team
     1.9 +All rights reserved.
    1.10 +
    1.11 +Redistribution and use of this software in source and binary forms, 
    1.12 +with or without modification, are permitted provided that the 
    1.13 +following conditions are met:
    1.14 +
    1.15 +* Redistributions of source code must retain the above
    1.16 +  copyright notice, this list of conditions and the
    1.17 +  following disclaimer.
    1.18 +
    1.19 +* Redistributions in binary form must reproduce the above
    1.20 +  copyright notice, this list of conditions and the
    1.21 +  following disclaimer in the documentation and/or other
    1.22 +  materials provided with the distribution.
    1.23 +
    1.24 +* Neither the name of the assimp team, nor the names of its
    1.25 +  contributors may be used to endorse or promote products
    1.26 +  derived from this software without specific prior
    1.27 +  written permission of the assimp team.
    1.28 +
    1.29 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.30 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.31 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.32 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.33 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.34 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.35 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.36 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.37 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.38 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.39 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.40 +
    1.41 +----------------------------------------------------------------------
    1.42 +*/
    1.43 +
    1.44 +/** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */
    1.45 +
    1.46 +#ifndef AI_POLYTOOLS_H_INCLUDED
    1.47 +#define AI_POLYTOOLS_H_INCLUDED
    1.48 +
    1.49 +namespace Assimp {
    1.50 +
    1.51 +// -------------------------------------------------------------------------------
    1.52 +/** Compute the signed area of a triangle.
    1.53 + *  The function accepts an unconstrained template parameter for use with
    1.54 + *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
    1.55 +template <typename T>
    1.56 +inline double GetArea2D(const T& v1, const T& v2, const T& v3) 
    1.57 +{
    1.58 +	return 0.5 * (v1.x * ((double)v3.y - v2.y) + v2.x * ((double)v1.y - v3.y) + v3.x * ((double)v2.y - v1.y));
    1.59 +}
    1.60 +
    1.61 +// -------------------------------------------------------------------------------
    1.62 +/** Test if a given point p2 is on the left side of the line formed by p0-p1.
    1.63 + *  The function accepts an unconstrained template parameter for use with
    1.64 + *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
    1.65 +template <typename T>
    1.66 +inline bool OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2)
    1.67 +{
    1.68 +	return GetArea2D(p0,p2,p1) > 0;
    1.69 +}
    1.70 +
    1.71 +// -------------------------------------------------------------------------------
    1.72 +/** Test if a given point is inside a given triangle in R2.
    1.73 + * The function accepts an unconstrained template parameter for use with
    1.74 + *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
    1.75 +template <typename T>
    1.76 +inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp)
    1.77 +{
    1.78 +	// Point in triangle test using baryzentric coordinates
    1.79 +	const aiVector2D v0 = p1 - p0;
    1.80 +	const aiVector2D v1 = p2 - p0;
    1.81 +	const aiVector2D v2 = pp - p0;
    1.82 +
    1.83 +	double dot00 = v0 * v0;
    1.84 +	double dot01 = v0 * v1;
    1.85 +	double dot02 = v0 * v2;
    1.86 +	double dot11 = v1 * v1;
    1.87 +	double dot12 = v1 * v2;
    1.88 +
    1.89 +	const double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    1.90 +	dot11 = (dot11 * dot02 - dot01 * dot12) * invDenom;
    1.91 +	dot00 = (dot00 * dot12 - dot01 * dot02) * invDenom;
    1.92 +
    1.93 +	return (dot11 > 0) && (dot00 > 0) && (dot11 + dot00 < 1);
    1.94 +}
    1.95 +
    1.96 +
    1.97 +// -------------------------------------------------------------------------------
    1.98 +/** Check whether the winding order of a given polygon is counter-clockwise.
    1.99 + *  The function accepts an unconstrained template parameter, but is intended 
   1.100 + *  to be used only with aiVector2D and aiVector3D (z axis is ignored, only
   1.101 + *  x and y are taken into account).
   1.102 + * @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++
   1.103 + */
   1.104 +template <typename T>
   1.105 +inline bool IsCCW(T* in, size_t npoints) {
   1.106 +	double aa, bb, cc, b, c, theta;
   1.107 +	double convex_turn;
   1.108 +	double convex_sum = 0;
   1.109 +
   1.110 +	ai_assert(npoints >= 3);
   1.111 +
   1.112 +	for (size_t i = 0; i < npoints - 2; i++) {		
   1.113 +		aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) +
   1.114 +			((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y));
   1.115 +
   1.116 +		bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) +
   1.117 +			((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y));
   1.118 +
   1.119 +		cc = ((in[i+2].x - in[i+1].x) * 
   1.120 +			(in[i+2].x - in[i+1].x)) +
   1.121 +			((-in[i+2].y + in[i+1].y) *
   1.122 +			(-in[i+2].y + in[i+1].y));
   1.123 +
   1.124 +		b = sqrt(bb);
   1.125 +		c = sqrt(cc);
   1.126 +		theta = acos((bb + cc - aa) / (2 * b * c));
   1.127 +
   1.128 +		if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1])) {
   1.129 +			//	if (convex(in[i].x, in[i].y,
   1.130 +			//		in[i+1].x, in[i+1].y,
   1.131 +			//		in[i+2].x, in[i+2].y)) {
   1.132 +			convex_turn = AI_MATH_PI_F - theta;
   1.133 +			convex_sum += convex_turn;
   1.134 +		}
   1.135 +		else {
   1.136 +			convex_sum -= AI_MATH_PI_F - theta;
   1.137 +		}
   1.138 +	}
   1.139 +	aa = ((in[1].x - in[npoints-2].x) * 
   1.140 +		(in[1].x - in[npoints-2].x)) +
   1.141 +		((-in[1].y + in[npoints-2].y) * 
   1.142 +		(-in[1].y + in[npoints-2].y));
   1.143 +
   1.144 +	bb = ((in[0].x - in[npoints-2].x) * 
   1.145 +		(in[0].x - in[npoints-2].x)) +
   1.146 +		((-in[0].y + in[npoints-2].y) * 
   1.147 +		(-in[0].y + in[npoints-2].y));
   1.148 +
   1.149 +	cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) +
   1.150 +		((-in[1].y + in[0].y) * (-in[1].y + in[0].y));
   1.151 +
   1.152 +	b = sqrt(bb);
   1.153 +	c = sqrt(cc);
   1.154 +	theta = acos((bb + cc - aa) / (2 * b * c));
   1.155 +
   1.156 +	//if (convex(in[npoints-2].x, in[npoints-2].y,
   1.157 +	//	in[0].x, in[0].y,
   1.158 +	//	in[1].x, in[1].y)) {
   1.159 +	if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0])) {
   1.160 +		convex_turn = AI_MATH_PI_F - theta;
   1.161 +		convex_sum += convex_turn;
   1.162 +	}
   1.163 +	else { 
   1.164 +		convex_sum -= AI_MATH_PI_F - theta;
   1.165 +	}
   1.166 +
   1.167 +	return convex_sum >= (2 * AI_MATH_PI_F);
   1.168 +}
   1.169 +
   1.170 +
   1.171 +// -------------------------------------------------------------------------------
   1.172 +/** Compute the normal of an arbitrary polygon in R3.
   1.173 + *
   1.174 + *  The code is based on Newell's formula, that is a polygons normal is the ratio
   1.175 + *  of its area when projected onto the three coordinate axes.
   1.176 + *
   1.177 + *  @param out Receives the output normal
   1.178 + *  @param num Number of input vertices
   1.179 + *  @param x X data source. x[ofs_x*n] is the n'th element. 
   1.180 + *  @param y Y data source. y[ofs_y*n] is the y'th element 
   1.181 + *  @param z Z data source. z[ofs_z*n] is the z'th element 
   1.182 + *
   1.183 + *  @note The data arrays must have storage for at least num+2 elements. Using
   1.184 + *  this method is much faster than the 'other' NewellNormal()
   1.185 + */
   1.186 +template <int ofs_x, int ofs_y, int ofs_z, typename TReal>
   1.187 +inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z)
   1.188 +{
   1.189 +	// Duplicate the first two vertices at the end
   1.190 +	x[(num+0)*ofs_x] = x[0]; 
   1.191 +	x[(num+1)*ofs_x] = x[ofs_x]; 
   1.192 +
   1.193 +	y[(num+0)*ofs_y] = y[0]; 
   1.194 +	y[(num+1)*ofs_y] = y[ofs_y]; 
   1.195 +
   1.196 +	z[(num+0)*ofs_z] = z[0]; 
   1.197 +	z[(num+1)*ofs_z] = z[ofs_z]; 
   1.198 +
   1.199 +	TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0;
   1.200 +
   1.201 +	TReal *xptr = x +ofs_x, *xlow = x, *xhigh = x + ofs_x*2;
   1.202 +	TReal *yptr = y +ofs_y, *ylow = y, *yhigh = y + ofs_y*2;
   1.203 +	TReal *zptr = z +ofs_z, *zlow = z, *zhigh = z + ofs_z*2;
   1.204 +
   1.205 +	for (int tmp=0; tmp < num; tmp++) {
   1.206 +		sum_xy += (*xptr) * ( (*yhigh) - (*ylow) );
   1.207 +		sum_yz += (*yptr) * ( (*zhigh) - (*zlow) );
   1.208 +		sum_zx += (*zptr) * ( (*xhigh) - (*xlow) );
   1.209 +
   1.210 +		xptr  += ofs_x;
   1.211 +		xlow  += ofs_x;
   1.212 +		xhigh += ofs_x;
   1.213 +
   1.214 +		yptr  += ofs_y;
   1.215 +		ylow  += ofs_y;
   1.216 +		yhigh += ofs_y;
   1.217 +
   1.218 +		zptr  += ofs_z;
   1.219 +		zlow  += ofs_z;
   1.220 +		zhigh += ofs_z;
   1.221 +	}
   1.222 +	out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy);
   1.223 +}
   1.224 +
   1.225 +} // ! Assimp
   1.226 +
   1.227 +#endif