1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2 /**
3 * Contains a handy triangle class.
4 * \file IceTriangle.cpp
5 * \author Pierre Terdiman
6 * \date January, 17, 2000
7 */
8 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
9
10 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
11 // Precompiled Header
12 #include "Stdafx.h"
13
14 using namespace IceMaths;
15
16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17 /**
18 * Contains a triangle class.
19 *
20 * \class Tri
21 * \author Pierre Terdiman
22 * \version 1.0
23 * \date 08.15.98
24 */
25 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
26
VPlaneSideEps(const Point & v,const Plane & plane,float epsilon)27 static sdword VPlaneSideEps(const Point& v, const Plane& plane, float epsilon)
28 {
29 // Compute distance from current vertex to the plane
30 float Dist = plane.Distance(v);
31 // Compute side:
32 // 1 = the vertex is on the positive side of the plane
33 // -1 = the vertex is on the negative side of the plane
34 // 0 = the vertex is on the plane (within epsilon)
35 return Dist > epsilon ? 1 : Dist < -epsilon ? -1 : 0;
36 }
37
38 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
39 /**
40 * Flips the winding order.
41 */
42 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Flip()43 void Triangle::Flip()
44 {
45 Point Tmp = mVerts[1];
46 mVerts[1] = mVerts[2];
47 mVerts[2] = Tmp;
48 }
49
50 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
51 /**
52 * Computes the triangle area.
53 * \return the area
54 */
55 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Area() const56 float Triangle::Area() const
57 {
58 const Point& p0 = mVerts[0];
59 const Point& p1 = mVerts[1];
60 const Point& p2 = mVerts[2];
61 return ((p0 - p1)^(p0 - p2)).Magnitude() * 0.5f;
62 }
63
64 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
65 /**
66 * Computes the triangle perimeter.
67 * \return the perimeter
68 */
69 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Perimeter() const70 float Triangle::Perimeter() const
71 {
72 const Point& p0 = mVerts[0];
73 const Point& p1 = mVerts[1];
74 const Point& p2 = mVerts[2];
75 return p0.Distance(p1)
76 + p0.Distance(p2)
77 + p1.Distance(p2);
78 }
79
80 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
81 /**
82 * Computes the triangle compacity.
83 * \return the compacity
84 */
85 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Compacity() const86 float Triangle::Compacity() const
87 {
88 float P = Perimeter();
89 if(P==0.0f) return 0.0f;
90 return (4.0f*PI*Area()/(P*P));
91 }
92
93 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
94 /**
95 * Computes the triangle normal.
96 * \param normal [out] the computed normal
97 */
98 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Normal(Point & normal) const99 void Triangle::Normal(Point& normal) const
100 {
101 const Point& p0 = mVerts[0];
102 const Point& p1 = mVerts[1];
103 const Point& p2 = mVerts[2];
104 normal = ((p0 - p1)^(p0 - p2)).Normalize();
105 }
106
107 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
108 /**
109 * Computes the triangle denormalized normal.
110 * \param normal [out] the computed normal
111 */
112 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
DenormalizedNormal(Point & normal) const113 void Triangle::DenormalizedNormal(Point& normal) const
114 {
115 const Point& p0 = mVerts[0];
116 const Point& p1 = mVerts[1];
117 const Point& p2 = mVerts[2];
118 normal = ((p0 - p1)^(p0 - p2));
119 }
120
121 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
122 /**
123 * Computes the triangle center.
124 * \param center [out] the computed center
125 */
126 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Center(Point & center) const127 void Triangle::Center(Point& center) const
128 {
129 const Point& p0 = mVerts[0];
130 const Point& p1 = mVerts[1];
131 const Point& p2 = mVerts[2];
132 center = (p0 + p1 + p2)*INV3;
133 }
134
TestAgainstPlane(const Plane & plane,float epsilon) const135 PartVal Triangle::TestAgainstPlane(const Plane& plane, float epsilon) const
136 {
137 bool Pos = false, Neg = false;
138
139 // Loop through all vertices
140 for(udword i=0;i<3;i++)
141 {
142 // Compute side:
143 sdword Side = VPlaneSideEps(mVerts[i], plane, epsilon);
144
145 if (Side < 0) Neg = true;
146 else if (Side > 0) Pos = true;
147 }
148
149 if (!Pos && !Neg) return TRI_ON_PLANE;
150 else if (Pos && Neg) return TRI_INTERSECT;
151 else if (Pos && !Neg) return TRI_PLUS_SPACE;
152 else if (!Pos && Neg) return TRI_MINUS_SPACE;
153
154 // What?!
155 return TRI_FORCEDWORD;
156 }
157
158 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
159 /**
160 * Computes the triangle moment.
161 * \param m [out] the moment
162 */
163 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
164 /*
165 void Triangle::ComputeMoment(Moment& m)
166 {
167 // Compute the area of the triangle
168 m.mArea = Area();
169
170 // Compute the centroid
171 Center(m.mCentroid);
172
173 // Second-order components. Handle zero-area faces.
174 Point& p = mVerts[0];
175 Point& q = mVerts[1];
176 Point& r = mVerts[2];
177 if(m.mArea==0.0f)
178 {
179 // This triangle has zero area. The second order components would be eliminated with the usual formula, so, for the
180 // sake of robustness we use an alternative form. These are the centroid and second-order components of the triangle's vertices.
181 m.mCovariance.m[0][0] = (p.x*p.x + q.x*q.x + r.x*r.x);
182 m.mCovariance.m[0][1] = (p.x*p.y + q.x*q.y + r.x*r.y);
183 m.mCovariance.m[0][2] = (p.x*p.z + q.x*q.z + r.x*r.z);
184 m.mCovariance.m[1][1] = (p.y*p.y + q.y*q.y + r.y*r.y);
185 m.mCovariance.m[1][2] = (p.y*p.z + q.y*q.z + r.y*r.z);
186 m.mCovariance.m[2][2] = (p.z*p.z + q.z*q.z + r.z*r.z);
187 m.mCovariance.m[2][1] = m.mCovariance.m[1][2];
188 m.mCovariance.m[1][0] = m.mCovariance.m[0][1];
189 m.mCovariance.m[2][0] = m.mCovariance.m[0][2];
190 }
191 else
192 {
193 const float OneOverTwelve = 1.0f / 12.0f;
194 m.mCovariance.m[0][0] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.x + p.x*p.x + q.x*q.x + r.x*r.x) * OneOverTwelve;
195 m.mCovariance.m[0][1] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.y + p.x*p.y + q.x*q.y + r.x*r.y) * OneOverTwelve;
196 m.mCovariance.m[1][1] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.y + p.y*p.y + q.y*q.y + r.y*r.y) * OneOverTwelve;
197 m.mCovariance.m[0][2] = m.mArea * (9.0f * m.mCentroid.x*m.mCentroid.z + p.x*p.z + q.x*q.z + r.x*r.z) * OneOverTwelve;
198 m.mCovariance.m[1][2] = m.mArea * (9.0f * m.mCentroid.y*m.mCentroid.z + p.y*p.z + q.y*q.z + r.y*r.z) * OneOverTwelve;
199 m.mCovariance.m[2][2] = m.mArea * (9.0f * m.mCentroid.z*m.mCentroid.z + p.z*p.z + q.z*q.z + r.z*r.z) * OneOverTwelve;
200 m.mCovariance.m[2][1] = m.mCovariance.m[1][2];
201 m.mCovariance.m[1][0] = m.mCovariance.m[0][1];
202 m.mCovariance.m[2][0] = m.mCovariance.m[0][2];
203 }
204 }
205 */
206
207 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
208 /**
209 * Computes the triangle's smallest edge length.
210 * \return the smallest edge length
211 */
212 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
MinEdgeLength() const213 float Triangle::MinEdgeLength() const
214 {
215 float Min = MAX_FLOAT;
216 float Length01 = mVerts[0].Distance(mVerts[1]);
217 float Length02 = mVerts[0].Distance(mVerts[2]);
218 float Length12 = mVerts[1].Distance(mVerts[2]);
219 if(Length01 < Min) Min = Length01;
220 if(Length02 < Min) Min = Length02;
221 if(Length12 < Min) Min = Length12;
222 return Min;
223 }
224
225 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
226 /**
227 * Computes the triangle's largest edge length.
228 * \return the largest edge length
229 */
230 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
MaxEdgeLength() const231 float Triangle::MaxEdgeLength() const
232 {
233 float Max = MIN_FLOAT;
234 float Length01 = mVerts[0].Distance(mVerts[1]);
235 float Length02 = mVerts[0].Distance(mVerts[2]);
236 float Length12 = mVerts[1].Distance(mVerts[2]);
237 if(Length01 > Max) Max = Length01;
238 if(Length02 > Max) Max = Length02;
239 if(Length12 > Max) Max = Length12;
240 return Max;
241 }
242
243 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
244 /**
245 * Computes a point on the triangle according to the stabbing information.
246 * \param u,v [in] point's barycentric coordinates
247 * \param pt [out] point on triangle
248 * \param nearvtx [out] index of nearest vertex
249 */
250 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ComputePoint(float u,float v,Point & pt,udword * nearvtx) const251 void Triangle::ComputePoint(float u, float v, Point& pt, udword* nearvtx) const
252 {
253 // Compute point coordinates
254 pt = (1.0f - u - v)*mVerts[0] + u*mVerts[1] + v*mVerts[2];
255
256 // Compute nearest vertex if needed
257 if(nearvtx)
258 {
259 // Compute distance vector
260 Point d(mVerts[0].SquareDistance(pt), // Distance^2 from vertex 0 to point on the face
261 mVerts[1].SquareDistance(pt), // Distance^2 from vertex 1 to point on the face
262 mVerts[2].SquareDistance(pt)); // Distance^2 from vertex 2 to point on the face
263
264 // Get smallest distance
265 *nearvtx = d.SmallestAxis();
266 }
267 }
268
Inflate(float fat_coeff,bool constant_border)269 void Triangle::Inflate(float fat_coeff, bool constant_border)
270 {
271 // Compute triangle center
272 Point TriangleCenter;
273 Center(TriangleCenter);
274
275 // Don't normalize?
276 // Normalize => add a constant border, regardless of triangle size
277 // Don't => add more to big triangles
278 for(udword i=0;i<3;i++)
279 {
280 Point v = mVerts[i] - TriangleCenter;
281
282 if(constant_border) v.Normalize();
283
284 mVerts[i] += v * fat_coeff;
285 }
286 }
287