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