1 /*
2 Open Asset Import Library (assimp)
3 ----------------------------------------------------------------------
4
5 Copyright (c) 2006-2016, assimp team
6 All rights reserved.
7
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:
11
12 * Redistributions of source code must retain the above
13 copyright notice, this list of conditions and the
14 following disclaimer.
15
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.
20
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.
25
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.
37
38 ----------------------------------------------------------------------
39 */
40
41 /** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */
42
43 #ifndef AI_POLYTOOLS_H_INCLUDED
44 #define AI_POLYTOOLS_H_INCLUDED
45
46 #include <assimp/material.h>
47 #include <assimp/ai_assert.h>
48
49 namespace Assimp {
50
51 // -------------------------------------------------------------------------------
52 /** Compute the signed area of a triangle.
53 * The function accepts an unconstrained template parameter for use with
54 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
55 template <typename T>
GetArea2D(const T & v1,const T & v2,const T & v3)56 inline double GetArea2D(const T& v1, const T& v2, const T& v3)
57 {
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));
59 }
60
61 // -------------------------------------------------------------------------------
62 /** Test if a given point p2 is on the left side of the line formed by p0-p1.
63 * The function accepts an unconstrained template parameter for use with
64 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
65 template <typename T>
OnLeftSideOfLine2D(const T & p0,const T & p1,const T & p2)66 inline bool OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2)
67 {
68 return GetArea2D(p0,p2,p1) > 0;
69 }
70
71 // -------------------------------------------------------------------------------
72 /** Test if a given point is inside a given triangle in R2.
73 * The function accepts an unconstrained template parameter for use with
74 * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
75 template <typename T>
PointInTriangle2D(const T & p0,const T & p1,const T & p2,const T & pp)76 inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp)
77 {
78 // Point in triangle test using baryzentric coordinates
79 const aiVector2D v0 = p1 - p0;
80 const aiVector2D v1 = p2 - p0;
81 const aiVector2D v2 = pp - p0;
82
83 double dot00 = v0 * v0;
84 double dot01 = v0 * v1;
85 double dot02 = v0 * v2;
86 double dot11 = v1 * v1;
87 double dot12 = v1 * v2;
88
89 const double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
90 dot11 = (dot11 * dot02 - dot01 * dot12) * invDenom;
91 dot00 = (dot00 * dot12 - dot01 * dot02) * invDenom;
92
93 return (dot11 > 0) && (dot00 > 0) && (dot11 + dot00 < 1);
94 }
95
96
97 // -------------------------------------------------------------------------------
98 /** Check whether the winding order of a given polygon is counter-clockwise.
99 * The function accepts an unconstrained template parameter, but is intended
100 * to be used only with aiVector2D and aiVector3D (z axis is ignored, only
101 * x and y are taken into account).
102 * @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++
103 */
104 template <typename T>
IsCCW(T * in,size_t npoints)105 inline bool IsCCW(T* in, size_t npoints) {
106 double aa, bb, cc, b, c, theta;
107 double convex_turn;
108 double convex_sum = 0;
109
110 ai_assert(npoints >= 3);
111
112 for (size_t i = 0; i < npoints - 2; i++) {
113 aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) +
114 ((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y));
115
116 bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) +
117 ((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y));
118
119 cc = ((in[i+2].x - in[i+1].x) *
120 (in[i+2].x - in[i+1].x)) +
121 ((-in[i+2].y + in[i+1].y) *
122 (-in[i+2].y + in[i+1].y));
123
124 b = std::sqrt(bb);
125 c = std::sqrt(cc);
126 theta = std::acos((bb + cc - aa) / (2 * b * c));
127
128 if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1])) {
129 // if (convex(in[i].x, in[i].y,
130 // in[i+1].x, in[i+1].y,
131 // in[i+2].x, in[i+2].y)) {
132 convex_turn = AI_MATH_PI_F - theta;
133 convex_sum += convex_turn;
134 }
135 else {
136 convex_sum -= AI_MATH_PI_F - theta;
137 }
138 }
139 aa = ((in[1].x - in[npoints-2].x) *
140 (in[1].x - in[npoints-2].x)) +
141 ((-in[1].y + in[npoints-2].y) *
142 (-in[1].y + in[npoints-2].y));
143
144 bb = ((in[0].x - in[npoints-2].x) *
145 (in[0].x - in[npoints-2].x)) +
146 ((-in[0].y + in[npoints-2].y) *
147 (-in[0].y + in[npoints-2].y));
148
149 cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) +
150 ((-in[1].y + in[0].y) * (-in[1].y + in[0].y));
151
152 b = std::sqrt(bb);
153 c = std::sqrt(cc);
154 theta = std::acos((bb + cc - aa) / (2 * b * c));
155
156 //if (convex(in[npoints-2].x, in[npoints-2].y,
157 // in[0].x, in[0].y,
158 // in[1].x, in[1].y)) {
159 if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0])) {
160 convex_turn = AI_MATH_PI_F - theta;
161 convex_sum += convex_turn;
162 }
163 else {
164 convex_sum -= AI_MATH_PI_F - theta;
165 }
166
167 return convex_sum >= (2 * AI_MATH_PI_F);
168 }
169
170
171 // -------------------------------------------------------------------------------
172 /** Compute the normal of an arbitrary polygon in R3.
173 *
174 * The code is based on Newell's formula, that is a polygons normal is the ratio
175 * of its area when projected onto the three coordinate axes.
176 *
177 * @param out Receives the output normal
178 * @param num Number of input vertices
179 * @param x X data source. x[ofs_x*n] is the n'th element.
180 * @param y Y data source. y[ofs_y*n] is the y'th element
181 * @param z Z data source. z[ofs_z*n] is the z'th element
182 *
183 * @note The data arrays must have storage for at least num+2 elements. Using
184 * this method is much faster than the 'other' NewellNormal()
185 */
186 template <int ofs_x, int ofs_y, int ofs_z, typename TReal>
NewellNormal(aiVector3t<TReal> & out,int num,TReal * x,TReal * y,TReal * z)187 inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z)
188 {
189 // Duplicate the first two vertices at the end
190 x[(num+0)*ofs_x] = x[0];
191 x[(num+1)*ofs_x] = x[ofs_x];
192
193 y[(num+0)*ofs_y] = y[0];
194 y[(num+1)*ofs_y] = y[ofs_y];
195
196 z[(num+0)*ofs_z] = z[0];
197 z[(num+1)*ofs_z] = z[ofs_z];
198
199 TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0;
200
201 TReal *xptr = x +ofs_x, *xlow = x, *xhigh = x + ofs_x*2;
202 TReal *yptr = y +ofs_y, *ylow = y, *yhigh = y + ofs_y*2;
203 TReal *zptr = z +ofs_z, *zlow = z, *zhigh = z + ofs_z*2;
204
205 for (int tmp=0; tmp < num; tmp++) {
206 sum_xy += (*xptr) * ( (*yhigh) - (*ylow) );
207 sum_yz += (*yptr) * ( (*zhigh) - (*zlow) );
208 sum_zx += (*zptr) * ( (*xhigh) - (*xlow) );
209
210 xptr += ofs_x;
211 xlow += ofs_x;
212 xhigh += ofs_x;
213
214 yptr += ofs_y;
215 ylow += ofs_y;
216 yhigh += ofs_y;
217
218 zptr += ofs_z;
219 zlow += ofs_z;
220 zhigh += ofs_z;
221 }
222 out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy);
223 }
224
225 } // ! Assimp
226
227 #endif
228