vrshoot

annotate libs/assimp/PolyTools.h @ 0:b2f14e535253

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 01 Feb 2014 19:58:19 +0200
parents
children
rev   line source
nuclear@0 1 /*
nuclear@0 2 Open Asset Import Library (assimp)
nuclear@0 3 ----------------------------------------------------------------------
nuclear@0 4
nuclear@0 5 Copyright (c) 2006-2012, assimp team
nuclear@0 6 All rights reserved.
nuclear@0 7
nuclear@0 8 Redistribution and use of this software in source and binary forms,
nuclear@0 9 with or without modification, are permitted provided that the
nuclear@0 10 following conditions are met:
nuclear@0 11
nuclear@0 12 * Redistributions of source code must retain the above
nuclear@0 13 copyright notice, this list of conditions and the
nuclear@0 14 following disclaimer.
nuclear@0 15
nuclear@0 16 * Redistributions in binary form must reproduce the above
nuclear@0 17 copyright notice, this list of conditions and the
nuclear@0 18 following disclaimer in the documentation and/or other
nuclear@0 19 materials provided with the distribution.
nuclear@0 20
nuclear@0 21 * Neither the name of the assimp team, nor the names of its
nuclear@0 22 contributors may be used to endorse or promote products
nuclear@0 23 derived from this software without specific prior
nuclear@0 24 written permission of the assimp team.
nuclear@0 25
nuclear@0 26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
nuclear@0 27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
nuclear@0 28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0 29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
nuclear@0 30 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0 31 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
nuclear@0 32 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0 33 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
nuclear@0 34 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
nuclear@0 35 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
nuclear@0 36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0 37
nuclear@0 38 ----------------------------------------------------------------------
nuclear@0 39 */
nuclear@0 40
nuclear@0 41 /** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */
nuclear@0 42
nuclear@0 43 #ifndef AI_POLYTOOLS_H_INCLUDED
nuclear@0 44 #define AI_POLYTOOLS_H_INCLUDED
nuclear@0 45
nuclear@0 46 namespace Assimp {
nuclear@0 47
nuclear@0 48 // -------------------------------------------------------------------------------
nuclear@0 49 /** Compute the signed area of a triangle.
nuclear@0 50 * The function accepts an unconstrained template parameter for use with
nuclear@0 51 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
nuclear@0 52 template <typename T>
nuclear@0 53 inline double GetArea2D(const T& v1, const T& v2, const T& v3)
nuclear@0 54 {
nuclear@0 55 return 0.5 * (v1.x * ((double)v3.y - v2.y) + v2.x * ((double)v1.y - v3.y) + v3.x * ((double)v2.y - v1.y));
nuclear@0 56 }
nuclear@0 57
nuclear@0 58 // -------------------------------------------------------------------------------
nuclear@0 59 /** Test if a given point p2 is on the left side of the line formed by p0-p1.
nuclear@0 60 * The function accepts an unconstrained template parameter for use with
nuclear@0 61 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
nuclear@0 62 template <typename T>
nuclear@0 63 inline bool OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2)
nuclear@0 64 {
nuclear@0 65 return GetArea2D(p0,p2,p1) > 0;
nuclear@0 66 }
nuclear@0 67
nuclear@0 68 // -------------------------------------------------------------------------------
nuclear@0 69 /** Test if a given point is inside a given triangle in R2.
nuclear@0 70 * The function accepts an unconstrained template parameter for use with
nuclear@0 71 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
nuclear@0 72 template <typename T>
nuclear@0 73 inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp)
nuclear@0 74 {
nuclear@0 75 // Point in triangle test using baryzentric coordinates
nuclear@0 76 const aiVector2D v0 = p1 - p0;
nuclear@0 77 const aiVector2D v1 = p2 - p0;
nuclear@0 78 const aiVector2D v2 = pp - p0;
nuclear@0 79
nuclear@0 80 double dot00 = v0 * v0;
nuclear@0 81 double dot01 = v0 * v1;
nuclear@0 82 double dot02 = v0 * v2;
nuclear@0 83 double dot11 = v1 * v1;
nuclear@0 84 double dot12 = v1 * v2;
nuclear@0 85
nuclear@0 86 const double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
nuclear@0 87 dot11 = (dot11 * dot02 - dot01 * dot12) * invDenom;
nuclear@0 88 dot00 = (dot00 * dot12 - dot01 * dot02) * invDenom;
nuclear@0 89
nuclear@0 90 return (dot11 > 0) && (dot00 > 0) && (dot11 + dot00 < 1);
nuclear@0 91 }
nuclear@0 92
nuclear@0 93
nuclear@0 94 // -------------------------------------------------------------------------------
nuclear@0 95 /** Check whether the winding order of a given polygon is counter-clockwise.
nuclear@0 96 * The function accepts an unconstrained template parameter, but is intended
nuclear@0 97 * to be used only with aiVector2D and aiVector3D (z axis is ignored, only
nuclear@0 98 * x and y are taken into account).
nuclear@0 99 * @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++
nuclear@0 100 */
nuclear@0 101 template <typename T>
nuclear@0 102 inline bool IsCCW(T* in, size_t npoints) {
nuclear@0 103 double aa, bb, cc, b, c, theta;
nuclear@0 104 double convex_turn;
nuclear@0 105 double convex_sum = 0;
nuclear@0 106
nuclear@0 107 ai_assert(npoints >= 3);
nuclear@0 108
nuclear@0 109 for (size_t i = 0; i < npoints - 2; i++) {
nuclear@0 110 aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) +
nuclear@0 111 ((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y));
nuclear@0 112
nuclear@0 113 bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) +
nuclear@0 114 ((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y));
nuclear@0 115
nuclear@0 116 cc = ((in[i+2].x - in[i+1].x) *
nuclear@0 117 (in[i+2].x - in[i+1].x)) +
nuclear@0 118 ((-in[i+2].y + in[i+1].y) *
nuclear@0 119 (-in[i+2].y + in[i+1].y));
nuclear@0 120
nuclear@0 121 b = sqrt(bb);
nuclear@0 122 c = sqrt(cc);
nuclear@0 123 theta = acos((bb + cc - aa) / (2 * b * c));
nuclear@0 124
nuclear@0 125 if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1])) {
nuclear@0 126 // if (convex(in[i].x, in[i].y,
nuclear@0 127 // in[i+1].x, in[i+1].y,
nuclear@0 128 // in[i+2].x, in[i+2].y)) {
nuclear@0 129 convex_turn = AI_MATH_PI_F - theta;
nuclear@0 130 convex_sum += convex_turn;
nuclear@0 131 }
nuclear@0 132 else {
nuclear@0 133 convex_sum -= AI_MATH_PI_F - theta;
nuclear@0 134 }
nuclear@0 135 }
nuclear@0 136 aa = ((in[1].x - in[npoints-2].x) *
nuclear@0 137 (in[1].x - in[npoints-2].x)) +
nuclear@0 138 ((-in[1].y + in[npoints-2].y) *
nuclear@0 139 (-in[1].y + in[npoints-2].y));
nuclear@0 140
nuclear@0 141 bb = ((in[0].x - in[npoints-2].x) *
nuclear@0 142 (in[0].x - in[npoints-2].x)) +
nuclear@0 143 ((-in[0].y + in[npoints-2].y) *
nuclear@0 144 (-in[0].y + in[npoints-2].y));
nuclear@0 145
nuclear@0 146 cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) +
nuclear@0 147 ((-in[1].y + in[0].y) * (-in[1].y + in[0].y));
nuclear@0 148
nuclear@0 149 b = sqrt(bb);
nuclear@0 150 c = sqrt(cc);
nuclear@0 151 theta = acos((bb + cc - aa) / (2 * b * c));
nuclear@0 152
nuclear@0 153 //if (convex(in[npoints-2].x, in[npoints-2].y,
nuclear@0 154 // in[0].x, in[0].y,
nuclear@0 155 // in[1].x, in[1].y)) {
nuclear@0 156 if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0])) {
nuclear@0 157 convex_turn = AI_MATH_PI_F - theta;
nuclear@0 158 convex_sum += convex_turn;
nuclear@0 159 }
nuclear@0 160 else {
nuclear@0 161 convex_sum -= AI_MATH_PI_F - theta;
nuclear@0 162 }
nuclear@0 163
nuclear@0 164 return convex_sum >= (2 * AI_MATH_PI_F);
nuclear@0 165 }
nuclear@0 166
nuclear@0 167
nuclear@0 168 // -------------------------------------------------------------------------------
nuclear@0 169 /** Compute the normal of an arbitrary polygon in R3.
nuclear@0 170 *
nuclear@0 171 * The code is based on Newell's formula, that is a polygons normal is the ratio
nuclear@0 172 * of its area when projected onto the three coordinate axes.
nuclear@0 173 *
nuclear@0 174 * @param out Receives the output normal
nuclear@0 175 * @param num Number of input vertices
nuclear@0 176 * @param x X data source. x[ofs_x*n] is the n'th element.
nuclear@0 177 * @param y Y data source. y[ofs_y*n] is the y'th element
nuclear@0 178 * @param z Z data source. z[ofs_z*n] is the z'th element
nuclear@0 179 *
nuclear@0 180 * @note The data arrays must have storage for at least num+2 elements. Using
nuclear@0 181 * this method is much faster than the 'other' NewellNormal()
nuclear@0 182 */
nuclear@0 183 template <int ofs_x, int ofs_y, int ofs_z, typename TReal>
nuclear@0 184 inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z)
nuclear@0 185 {
nuclear@0 186 // Duplicate the first two vertices at the end
nuclear@0 187 x[(num+0)*ofs_x] = x[0];
nuclear@0 188 x[(num+1)*ofs_x] = x[ofs_x];
nuclear@0 189
nuclear@0 190 y[(num+0)*ofs_y] = y[0];
nuclear@0 191 y[(num+1)*ofs_y] = y[ofs_y];
nuclear@0 192
nuclear@0 193 z[(num+0)*ofs_z] = z[0];
nuclear@0 194 z[(num+1)*ofs_z] = z[ofs_z];
nuclear@0 195
nuclear@0 196 TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0;
nuclear@0 197
nuclear@0 198 TReal *xptr = x +ofs_x, *xlow = x, *xhigh = x + ofs_x*2;
nuclear@0 199 TReal *yptr = y +ofs_y, *ylow = y, *yhigh = y + ofs_y*2;
nuclear@0 200 TReal *zptr = z +ofs_z, *zlow = z, *zhigh = z + ofs_z*2;
nuclear@0 201
nuclear@0 202 for (int tmp=0; tmp < num; tmp++) {
nuclear@0 203 sum_xy += (*xptr) * ( (*yhigh) - (*ylow) );
nuclear@0 204 sum_yz += (*yptr) * ( (*zhigh) - (*zlow) );
nuclear@0 205 sum_zx += (*zptr) * ( (*xhigh) - (*xlow) );
nuclear@0 206
nuclear@0 207 xptr += ofs_x;
nuclear@0 208 xlow += ofs_x;
nuclear@0 209 xhigh += ofs_x;
nuclear@0 210
nuclear@0 211 yptr += ofs_y;
nuclear@0 212 ylow += ofs_y;
nuclear@0 213 yhigh += ofs_y;
nuclear@0 214
nuclear@0 215 zptr += ofs_z;
nuclear@0 216 zlow += ofs_z;
nuclear@0 217 zhigh += ofs_z;
nuclear@0 218 }
nuclear@0 219 out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy);
nuclear@0 220 }
nuclear@0 221
nuclear@0 222 } // ! Assimp
nuclear@0 223
nuclear@0 224 #endif