1 | /* |
---|---|

2 | Open Asset Import Library (assimp) |

3 | ---------------------------------------------------------------------- |

4 | |

5 | Copyright (c) 2006-2017, assimp team |

6 | |

7 | All rights reserved. |

8 | |

9 | Redistribution and use of this software in source and binary forms, |

10 | with or without modification, are permitted provided that the |

11 | following conditions are met: |

12 | |

13 | * Redistributions of source code must retain the above |

14 | copyright notice, this list of conditions and the |

15 | following disclaimer. |

16 | |

17 | * Redistributions in binary form must reproduce the above |

18 | copyright notice, this list of conditions and the |

19 | following disclaimer in the documentation and/or other |

20 | materials provided with the distribution. |

21 | |

22 | * Neither the name of the assimp team, nor the names of its |

23 | contributors may be used to endorse or promote products |

24 | derived from this software without specific prior |

25 | written permission of the assimp team. |

26 | |

27 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |

28 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |

29 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |

30 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |

31 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |

32 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |

33 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |

34 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |

35 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |

36 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |

37 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |

38 | |

39 | ---------------------------------------------------------------------- |

40 | */ |

41 | |

42 | /** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */ |

43 | |

44 | #ifndef AI_POLYTOOLS_H_INCLUDED |

45 | #define AI_POLYTOOLS_H_INCLUDED |

46 | |

47 | #include <assimp/material.h> |

48 | #include <assimp/ai_assert.h> |

49 | |

50 | namespace Assimp { |

51 | |

52 | // ------------------------------------------------------------------------------- |

53 | /** Compute the signed area of a triangle. |

54 | * The function accepts an unconstrained template parameter for use with |

55 | * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/ |

56 | template <typename T> |

57 | inline double GetArea2D(const T& v1, const T& v2, const T& v3) |

58 | { |

59 | return 0.5 * (v1.x * ((double)v3.y - v2.y) + v2.x * ((double)v1.y - v3.y) + v3.x * ((double)v2.y - v1.y)); |

60 | } |

61 | |

62 | // ------------------------------------------------------------------------------- |

63 | /** Test if a given point p2 is on the left side of the line formed by p0-p1. |

64 | * The function accepts an unconstrained template parameter for use with |

65 | * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/ |

66 | template <typename T> |

67 | inline bool OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2) |

68 | { |

69 | return GetArea2D(p0,p2,p1) > 0; |

70 | } |

71 | |

72 | // ------------------------------------------------------------------------------- |

73 | /** Test if a given point is inside a given triangle in R2. |

74 | * The function accepts an unconstrained template parameter for use with |

75 | * both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/ |

76 | template <typename T> |

77 | inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp) |

78 | { |

79 | // Point in triangle test using baryzentric coordinates |

80 | const aiVector2D v0 = p1 - p0; |

81 | const aiVector2D v1 = p2 - p0; |

82 | const aiVector2D v2 = pp - p0; |

83 | |

84 | double dot00 = v0 * v0; |

85 | double dot01 = v0 * v1; |

86 | double dot02 = v0 * v2; |

87 | double dot11 = v1 * v1; |

88 | double dot12 = v1 * v2; |

89 | |

90 | const double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); |

91 | dot11 = (dot11 * dot02 - dot01 * dot12) * invDenom; |

92 | dot00 = (dot00 * dot12 - dot01 * dot02) * invDenom; |

93 | |

94 | return (dot11 > 0) && (dot00 > 0) && (dot11 + dot00 < 1); |

95 | } |

96 | |

97 | |

98 | // ------------------------------------------------------------------------------- |

99 | /** Check whether the winding order of a given polygon is counter-clockwise. |

100 | * The function accepts an unconstrained template parameter, but is intended |

101 | * to be used only with aiVector2D and aiVector3D (z axis is ignored, only |

102 | * x and y are taken into account). |

103 | * @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++ |

104 | */ |

105 | template <typename T> |

106 | inline bool IsCCW(T* in, size_t npoints) { |

107 | double aa, bb, cc, b, c, theta; |

108 | double convex_turn; |

109 | double convex_sum = 0; |

110 | |

111 | ai_assert(npoints >= 3); |

112 | |

113 | for (size_t i = 0; i < npoints - 2; i++) { |

114 | aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) + |

115 | ((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y)); |

116 | |

117 | bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) + |

118 | ((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y)); |

119 | |

120 | cc = ((in[i+2].x - in[i+1].x) * |

121 | (in[i+2].x - in[i+1].x)) + |

122 | ((-in[i+2].y + in[i+1].y) * |

123 | (-in[i+2].y + in[i+1].y)); |

124 | |

125 | b = std::sqrt(bb); |

126 | c = std::sqrt(cc); |

127 | theta = std::acos((bb + cc - aa) / (2 * b * c)); |

128 | |

129 | if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1])) { |

130 | // if (convex(in[i].x, in[i].y, |

131 | // in[i+1].x, in[i+1].y, |

132 | // in[i+2].x, in[i+2].y)) { |

133 | convex_turn = AI_MATH_PI_F - theta; |

134 | convex_sum += convex_turn; |

135 | } |

136 | else { |

137 | convex_sum -= AI_MATH_PI_F - theta; |

138 | } |

139 | } |

140 | aa = ((in[1].x - in[npoints-2].x) * |

141 | (in[1].x - in[npoints-2].x)) + |

142 | ((-in[1].y + in[npoints-2].y) * |

143 | (-in[1].y + in[npoints-2].y)); |

144 | |

145 | bb = ((in[0].x - in[npoints-2].x) * |

146 | (in[0].x - in[npoints-2].x)) + |

147 | ((-in[0].y + in[npoints-2].y) * |

148 | (-in[0].y + in[npoints-2].y)); |

149 | |

150 | cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) + |

151 | ((-in[1].y + in[0].y) * (-in[1].y + in[0].y)); |

152 | |

153 | b = std::sqrt(bb); |

154 | c = std::sqrt(cc); |

155 | theta = std::acos((bb + cc - aa) / (2 * b * c)); |

156 | |

157 | //if (convex(in[npoints-2].x, in[npoints-2].y, |

158 | // in[0].x, in[0].y, |

159 | // in[1].x, in[1].y)) { |

160 | if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0])) { |

161 | convex_turn = AI_MATH_PI_F - theta; |

162 | convex_sum += convex_turn; |

163 | } |

164 | else { |

165 | convex_sum -= AI_MATH_PI_F - theta; |

166 | } |

167 | |

168 | return convex_sum >= (2 * AI_MATH_PI_F); |

169 | } |

170 | |

171 | |

172 | // ------------------------------------------------------------------------------- |

173 | /** Compute the normal of an arbitrary polygon in R3. |

174 | * |

175 | * The code is based on Newell's formula, that is a polygons normal is the ratio |

176 | * of its area when projected onto the three coordinate axes. |

177 | * |

178 | * @param out Receives the output normal |

179 | * @param num Number of input vertices |

180 | * @param x X data source. x[ofs_x*n] is the n'th element. |

181 | * @param y Y data source. y[ofs_y*n] is the y'th element |

182 | * @param z Z data source. z[ofs_z*n] is the z'th element |

183 | * |

184 | * @note The data arrays must have storage for at least num+2 elements. Using |

185 | * this method is much faster than the 'other' NewellNormal() |

186 | */ |

187 | template <int ofs_x, int ofs_y, int ofs_z, typename TReal> |

188 | inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z) |

189 | { |

190 | // Duplicate the first two vertices at the end |

191 | x[(num+0)*ofs_x] = x[0]; |

192 | x[(num+1)*ofs_x] = x[ofs_x]; |

193 | |

194 | y[(num+0)*ofs_y] = y[0]; |

195 | y[(num+1)*ofs_y] = y[ofs_y]; |

196 | |

197 | z[(num+0)*ofs_z] = z[0]; |

198 | z[(num+1)*ofs_z] = z[ofs_z]; |

199 | |

200 | TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0; |

201 | |

202 | TReal *xptr = x +ofs_x, *xlow = x, *xhigh = x + ofs_x*2; |

203 | TReal *yptr = y +ofs_y, *ylow = y, *yhigh = y + ofs_y*2; |

204 | TReal *zptr = z +ofs_z, *zlow = z, *zhigh = z + ofs_z*2; |

205 | |

206 | for (int tmp=0; tmp < num; tmp++) { |

207 | sum_xy += (*xptr) * ( (*yhigh) - (*ylow) ); |

208 | sum_yz += (*yptr) * ( (*zhigh) - (*zlow) ); |

209 | sum_zx += (*zptr) * ( (*xhigh) - (*xlow) ); |

210 | |

211 | xptr += ofs_x; |

212 | xlow += ofs_x; |

213 | xhigh += ofs_x; |

214 | |

215 | yptr += ofs_y; |

216 | ylow += ofs_y; |

217 | yhigh += ofs_y; |

218 | |

219 | zptr += ofs_z; |

220 | zlow += ofs_z; |

221 | zhigh += ofs_z; |

222 | } |

223 | out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy); |

224 | } |

225 | |

226 | } // ! Assimp |

227 | |

228 | #endif |

229 |