Triangle.h

1 /* Copyright Jukka Jyl�nki
2
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License. */
14
15 /** @file Triangle.h
16 @author Jukka Jyl�nki
17 @brief The Triangle geometry object. */
18 #pragma once
19
20 #include "../MathGeoLibFwd.h"
21 #include "../Math/float3.h"
22
23 MATH_BEGIN_NAMESPACE
24
25 /// Specifies a triangle through three points in 3D space.
26 /** This class stores three member vertices a, b and c to specify the triangle. */
27 class Triangle
28 {
29 public:
30 /// The first triangle endpoint.
31 vec a;
32 /// The second triangle endpoint.
33 /** [similarOverload: a] */
34 vec b;
35 /// The third triangle endpoint.
36 /** [similarOverload: a]
37 @note The order in which the vertices are stored in this data structure is important. The triangles
38 (a,b,c) and (a,c,b) are otherwise equivalent, but their plane normals point to the opposite directions.
39 @see PlaneCCW(), PlaneCW(). */
40 vec c;
41
42 /// The default constructor does not initialize any members of this class.
43 /** This means that the values of the members a, b and c are undefined after creating a new Triangle using this
44 default constructor. Remember to assign to them before use.
45 @see a, b, c. */
46 Triangle() {}
47
48 /// Constructs a triangle from three given endpoints.
49 /** The normal of the plane will be constructed to point towards the halfspace where
50 the vertices a, b and c wind in counter-clockwise order.
51 @see a, b, c. */
52 Triangle(const vec &a, const vec &b, const vec &c);
53
54 FORCE_INLINE static int NumFaces() { return 1; }
55 FORCE_INLINE static int NumEdges() { return 3; }
56 FORCE_INLINE static int NumVertices() { return 3; }
57
58 /// Translates this Triangle in world space.
59 /** @param offset The amount of displacement to apply to this Triangle, in world space coordinates.
60 @see Transform(). */
61 void Translate(const vec &offset);
62
63 /// Applies a transformation to this Triangle, in-place.
64 /** See Translate(), classes float3x3, float3x4, float4x4, Quat. */
65 void Transform(const float3x3 &transform);
66 void Transform(const float3x4 &transform);
67 void Transform(const float4x4 &transform);
68 void Transform(const Quat &transform);
69
70 /// Expresses the given point in barycentric (u,v,w) coordinates.
71 /** @note There are two different conventions for representing barycentric coordinates. One uses
72 a (u,v,w) triplet with the equation pt == u*a + v*b + w*c, and the other uses a (u,v) pair
73 with the equation pt == a + u*(b-a) + v*(c-a). These two are equivalent. Use the mappings
74 (u,v) -> (1-u-v, u, v) and (u,v,w)->(v,w) to convert between these two representations.
75 @param point The point of the vector space to express in barycentric coordinates. This point should
76 lie in the plane formed by this triangle.
77 @return The factors (u,v,w) that satisfy the weighted sum equation point == u*a + v*b + w*c.
78 @see BarycentricUV(), BarycentricInsideTriangle(), Point(), http://mathworld.wolfram.com/BarycentricCoordinates.html */
79 float3 BarycentricUVW(const vec &point) const;
80
81 /// Expresses the given point in barycentric (u,v) coordinates.
82 /** @note There are two different conventions for representing barycentric coordinates. One uses
83 a (u,v,w) triplet with the equation pt == u*a + v*b + w*c, and the other uses a (u,v) pair
84 with the equation pt == a + u*(b-a) + v*(c-a). These two are equivalent. Use the mappings
85 (u,v) -> (1-u-v, u, v) and (u,v,w)->(v,w) to convert between these two representations.
86 @param point The point to express in barycentric coordinates. This point should lie in the plane
87 formed by this triangle.
88 @return The factors (u,v) that satisfy the weighted sum equation point == a + u*(b-a) + v*(c-a).
89 @see BarycentricUVW(), BarycentricInsideTriangle(), Point(). */
90 float2 BarycentricUV(const vec &point) const;
91
92 /// Tests if the given barycentric UVW coordinates lie inside a triangle.
93 /** A barycentric UVW coordinate represents a point inside a triangle if
94 a) 0 <= u,v,w <= 1 and
95 b) u+v+w == 1.
96 @param uvw The barycentric vector containing the barycentric (u,v,w) coordinates.
97 @return True if the given coordinates lie inside a triangle.
98 @see BarycentricUV(), BarycentricUVW(), Point(). */
99 static bool BarycentricInsideTriangle(const float3 &uvw);
100
101 /// Returns the point at the given barycentric coordinates.
102 /** This function computes the vector space point at the given barycentric coordinates.
103 @param uvw The barycentric UVW coordinate triplet. The condition u+v+w == 1 should hold for the input coordinate.
104 If 0 <= u,v,w <= 1, the returned point lies inside this triangle.
105 @return u*a + v*b + w*c. */
106 vec Point(const float3 &uvw) const;
107 vec Point(float u, float v, float w) const;
108 /** These functions are an alternate form of Point(u,v,w) for the case when the barycentric coordinates are
109 represented as a (u,v) pair and not as a (u,v,w) triplet. This function is provided for convenience
110 and effectively just computes Point(1-u-v, u, v).
111 @param uv The barycentric UV coordinates. If 0 <= u,v <= 1 and u+v <= 1, then the returned point lies inside
112 this triangle.
113 @return a + (b-a)*u + (c-a)*v.
114 @see BarycentricUV(), BarycentricUVW(), BarycentricInsideTriangle(). */
115 vec Point(const float2 &uv) const;
116 vec Point(float u, float v) const;
117
118 /// Computes the center of mass of this triangle.
119 /** @return The point (a+b+c)/3. */
120 vec Centroid() const;
121 /// Identical to CenterPoint(), but provided to enable common signature with Triangle, AABB and OBB to allow them to be used
122 /// in template classes.
123 vec CenterPoint() const { return Centroid(); }
124
125 /// Computes the surface area of this triangle.
126 /** @return The surface area of this triangle.
127 @see Perimeter(), Area2D(), SignedArea(). */
128 float Area() const;
129
130 /// Computes the total edge length of this triangle.
131 /** @return |a-b| + |b-c| + |c-a|.
132 @see Area(), Edge(). */
133 float Perimeter() const;
134
135 /// Returns a pointer to the vertices of this triangle. The array contains three elements.
136 vec *VertexArrayPtr() { return &a; }
137 const vec *VertexArrayPtr() const { return &a; }
138
139 /// Returns a vertex of this triangle.
140 /** @param i The vertex of this triangle to get: 0, 1 or 2.
141 @return Vertex(0) returns the point a, Vertex(1) returns the point b, and Vertex(2) returns the point c.
142 @note If an index outside [0, 2] is passed, an assume() failure occurs and a NaN vector is returned.
143 @see Edge(). */
144 vec Vertex(int i) const;
145 vec CornerPoint(int i) const { return Vertex(i); } // An alias for Vertex() to be able to mash Triangle into templatized algorithms.
146
147 /// Returns an edge of this triangle.
148 /** @param i The index of the edge to generate: 0, 1 or 2.
149 @return A LineSegment representing the given edge of this triangle. Edge(0) returns LineSegment(a,b), Edge(1)
150 returns LineSegment(b,c) and Edge(2) returns LineSegment(c,a).
151 @note If an index outside [0, 2] is passed, an assume() failure occurs and LineSegment(NaN, NaN) is returned.
152 @see Vertex(). */
153 LineSegment Edge(int i) const;
154
155 /// Returns the counterclockwise-oriented plane this triangle lies on.
156 /** The normal of the returned plane points towards the halfspace in which the vertices of this triangle are winded
157 in counter-clockwise direction. */
158 Plane PlaneCCW() const;
159
160 /// Returns the clockwise-oriented plane this triangle lies on.
161 /** The normal of the returned plane points towards the halfspace in which the vertices of this triangle are winded
162 in clockwise direction. [similarOverload: PlaneCCW]
163 @see NormalCCW(), NormalCW(), UnnormalizedNormalCCW(), UnnormalizedNormalCW(). */
164 Plane PlaneCW() const;
165
166 /// Returns the normalized triangle normal pointing to the counter-clockwise direction of this triangle.
167 /** This function computes the normalized triangle normal vector that points towards the halfspace,
168 from which observed, the vertices of this triangle wind in counter-clockwise (CCW) order.
169 @see PlaneCCW(), PlaneCW(), UnnormalizedNormalCCW(), UnnormalizedNormalCW(). */
170 vec NormalCCW() const;
171
172 /// Returns the normalized triangle normal pointing to the clockwise direction of this triangle.
173 /** This function computes the normalized triangle normal vector that points towards the halfspace,
174 from which observed, the vertices of this triangle wind in clockwise (CW) order. [similarOverload: NormalCCW]
175 @see PlaneCCW(), PlaneCW(), UnnormalizedNormalCCW(), UnnormalizedNormalCW(). */
176 vec NormalCW() const;
177
178 /// Computes an unnormalized counter-clockwise oriented triangle normal vector.
179 vec UnnormalizedNormalCCW() const;
180 /// Computes an unnormalized clockwise-oriented triangle normal vector.
181 /** These functions are equivalent to NormalCCW() and NormalCW(), except these functions do not produce
182 a unit-length triangle normal vectors. Use these functions instead of NormalCCW/CW() to obtain a small
183 speed benefit in cases where the normalization step is not required. [similarOverload: UnnormalizedNormalCCW]
184 @see PlaneCCW(), PlaneCW(), NormalCCW(), NormalCW(). */
185 vec UnnormalizedNormalCW() const;
186
187 /// Quickly returns an arbitrary point inside this Triangle. Used in GJK intersection test.
188 inline vec AnyPointFast() const { return a; }
189
190 /// Computes an extreme point of this Triangle in the given direction.
191 /** An extreme point is a farthest point of this Triangle in the given direction. Given a direction,
192 this point is not necessarily unique.
193 @param direction The direction vector of the direction to find the extreme point. This vector may
194 be unnormalized, but may not be null.
195 @return An extreme point of this Triangle in the given direction. The returned point is always a
196 vertex of this Triangle.
197 @see Vertex(). */
198 vec ExtremePoint(const vec &direction) const;
199 vec ExtremePoint(const vec &direction, float &projectionDistance) const;
200
201 /// Returns a Polygon representation of this Triangle.
202 /** The returned polygon is identical to this Triangle. It has three vertices a, b and c which wind in the same
203 direction than in this triangle.
204 @see class Polygon, ToPolyhedron(). */
205 Polygon ToPolygon() const;
206
207 /// Returns a Polyhedron representation of this Triangle.
208 /** The generated polyhedron will be closed and has two triangular faces, and three vertices (a, b and c).
209 The two faces share the same vertices, but in opposite winding orders. This creates a polyhedron with zero
210 volume and the surface area twice of this Triangle.
211 @see class Polyhedron, ToPolygon(). */
212 Polyhedron ToPolyhedron() const;
213
214 /// Returns the tight AABB that encloses this Triangle.
215 AABB BoundingAABB() const;
216
217 /// Computes the surface area of the given 2D triangle.
218 /** This math library does not have a separate class for 2D triangles. To compute the area of a 2D triangle,
219 use this Triangle class and set z=0 for each coordinate, or use this helper function.
220 @see Area(), SignedArea(). */
221 static float Area2D(const float2 &p1, const float2 &p2, const float2 &p3);
222
223 /// Relates the barycentric coordinate of the given point to the surface area of triangle abc.
224 /** This function computes the ratio of the signed area of the triangle (point, b, c) to the signed area of
225 the triangle (a, b, c). This is the same as computing the barycentric u-coordinate of the given point
226 on the triangle (a, b, c).
227 @see Area(), Area2D(), BarycentricUVW(). */
228 static float SignedArea(const vec &point, const vec &a, const vec &b, const vec &c);
229
230 /// Tests if this Triangle is finite.
231 /** A triangle is finite if its vertices a, b and c do not contain floating-point NaNs or +/-infs
232 in them.
233 @return True if each coordinate of each vertex of this triangle has a finite floating-point value.
234 @see a, b, c, IsDegenerate(), ::IsFinite(), IsInf(), IsNan(), IsFinite(), inf, negInf, nan, float3::nan, float3::inf. */
235 bool IsFinite() const;
236
237 /// Returns true if this triangle is degenerate.
238 /** A triangle is degenerate if it is not finite, or if the surface area of the triangle is
239 close to zero.
240 @param epsilon The threshold to test against. If two vertices of this triangle are closer than this, the
241 triangle is considered degenerate.
242 @see a, b, c, IsFinite(). */
243 bool IsDegenerate(float epsilon = 1e-3f) const;
244
245 /// Returns true if the triangle defined by the three given points is degenerate.
246 static bool IsDegenerate(const vec &p1, const vec &p2, const vec &p3, float epsilon = 1e-3f);
247
248 /// Tests if the given object is fully contained inside this triangle.
249 /** @param triangleThickness An epsilon threshold value to use for this test. triangleThicknessSq is the squared version of this parameter.
250 This specifies the maximum distance the given object can lie from the plane defined by this triangle.
251 @see Distance(), Intersects(), ClosestPoint().
252 @todo Add Triangle::Contains(Circle) and Triangle::Contains(Disc). */
253 bool Contains(const vec &point, float triangleThicknessSq = 1e-5f) const;
254 bool Contains(const LineSegment &lineSegment, float triangleThickness = 1e-3f) const;
255 bool Contains(const Triangle &triangle, float triangleThickness = 1e-3f) const;
256
257 /// Computes the distance between this triangle and the given object.
258 /** This function finds the nearest pair of points on this and the given object, and computes their distance.
259 If the two objects intersect, or one object is contained inside the other, the returned distance is zero.
260 @todo Add Triangle::Distance(Line/Ray/LineSegment/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Capsule/Frustum/Polyhedron).
261 @see Contains(), Intersects(), ClosestPoint(). */
262 float Distance(const vec &point) const;
263 float Distance(const Sphere &sphere) const;
264 float Distance(const Capsule &capsule) const;
265
266 float DistanceSq(const vec &point) const;
267
268 /// Tests whether this triangle and the given object intersect.
269 /** Both objects are treated as "solid", meaning that if one of the objects is fully contained inside
270 another, this function still returns true. (e.g. in case a line segment is contained inside this triangle,
271 or this triangle is contained inside a sphere, etc.)
272 @param d [out] If specified, this parameter will receive the parametric distance of
273 the intersection point along the line object. Use the GetPoint(d) function of the line class
274 to get the actual point of intersection. This pointer may be null.
275 @param intersectionPoint [out] If specified, receives the actual point of intersection. This pointer
276 may be null.
277 @return True if an intersection occurs or one of the objects is contained inside the other, false otherwise.
278 @see Contains(), Distance(), ClosestPoint(), LineSegment::GetPoint(). */
279 bool Intersects(const LineSegment &lineSegment, float *d = 0, vec *intersectionPoint = 0) const;
280 bool Intersects(const Line &line, float *d = 0, vec *intersectionPoint = 0) const;
281 bool Intersects(const Ray &ray, float *d = 0, vec *intersectionPoint = 0) const;
282 bool Intersects(const Plane &plane) const;
283 /** @param closestPointOnTriangle [out] If specified, receives the point of intersection between the Sphere
284 and this Triangle. Even if no intersection occurred, this parameter will receive the closest point on
285 the Triangle to the Sphere. This pointer may be null. */
286 bool Intersects(const Sphere &sphere, vec *closestPointOnTriangle) const;
287 bool Intersects(const Sphere &sphere) const;
288 /** @param outLine [out] If specified, receives the line segment of the common points shared by the two
289 intersecting triangles. If the two triangles do not intersect, this pointer is not written to.
290 This pointer may be null. */
291 bool Intersects(const Triangle &triangle, LineSegment *outLine = 0) const;
292 bool Intersects(const AABB &aabb) const;
293 bool Intersects(const OBB &obb) const;
294 bool Intersects(const Polygon &polygon) const;
295 bool Intersects(const Frustum &frustum) const;
296 bool Intersects(const Polyhedron &polyhedron) const;
297 bool Intersects(const Capsule &capsule) const;
298
299 /// A helper function used in line-triangle tests.
300 static float IntersectLineTri(const vec &linePos, const vec &lineDir,
301 const vec &v0, const vec &v1, const vec &v2,
302 float &u, float &v);
303
304 /// Projects this Triangle onto the given axis.
305 /** This function is used in SAT tests (separate axis theorem) to check the interval this triangle
306 lies in on an 1D line.
307 @param axis The axis to project onto. This vector can be unnormalized.
308 @param dMin [out] Returns the minimum extent of this triangle on the given axis.
309 @param dMax [out] Returns the maximum extent of this triangle on the given axis. */
310 void ProjectToAxis(const vec &axis, float &dMin, float &dMax) const;
311
312 int UniqueFaceNormals(vec *out) const;
313 int UniqueEdgeDirections(vec *out) const;
314
315 /// Computes the closest point on this triangle to the given object.
316 /** If the other object intersects this triangle, this function will return an arbitrary point inside
317 the region of intersection.
318 @see Contains(), Distance(), Intersects(), ClosestPointToTriangleEdge(). */
319 vec ClosestPoint(const vec &point) const;
320 /** @param otherPt [out] If specified, receives the closest point on the other object to this triangle.
321 This pointer may be null. */
322 vec ClosestPoint(const LineSegment &lineSegment, vec *otherPt = 0) const;
323 /** @param outU [out] If specified, receives the barycentric U coordinate of the returned point (in the UV convention).
324 This pointer may be null. TODO Add this parameter back.
325 @param outV [out] If specified, receives the barycentric V coordinate of the returned point (in the UV convention).
326 This pointer may be null. TODO Add this parameter back.
327 @param outD [out] If specified, receives the distance along the line of the closest point on the line to this triangle. TODO Add this parameter back.
328 @return The closest point on this triangle to the given object.
329 @todo Add ClosestPoint(Ray/Plane/Polygon/Circle/Disk/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron).
330 @see Distance(), Contains(), Intersects(), ClosestPointToTriangleEdge(), Line::GetPoint. */
331 vec ClosestPoint(const Line &line, vec *otherPt = 0) const;
332 vec ClosestPoint(const Triangle &triangle, vec *otherPt = 0) const;
333
334 /// Computes the closest point on the edge of this triangle to the given object.
335 /** @param outU [out] If specified, receives the barycentric U coordinate of the returned point (in the UV convention).
336 This pointer may be null.
337 @param outV [out] If specified, receives the barycentric V coordinate of the returned point (in the UV convention).
338 This pointer may be null.
339 @param outD [out] If specified, receives the distance along the line of the closest point on the line to the edge of this triangle.
340 @return The closest point on the edge of this triangle to the given object.
341 @todo Add ClosestPointToTriangleEdge(Point/Ray/Triangle/Plane/Polygon/Circle/Disk/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron).
342 @see Distance(), Contains(), Intersects(), ClosestPointToTriangleEdge(), Line::GetPoint. */
343 vec ClosestPointToTriangleEdge(const Line &line, float *outU, float *outV, float *outD) const;
344 vec ClosestPointToTriangleEdge(const LineSegment &lineSegment, float *outU, float *outV, float *outD) const;
345
346 /// Generates a random point inside this Triangle.
347 /** The points are distributed uniformly.
348 The implementation of this function is based on Graphics Gems 1, p. 25:
349 "1.5 Generating random points in triangles. Method 2." The Method 1 presented in the book
350 uses a Sqrt() instead of the if().
351 @param rng A pre-seeded random number generator object that is to be used by this function to generate random values.
352 @see class LCG, RandomPointOnEdge(), RandomVertex(), Point(). */
353 vec RandomPointInside(LCG &rng) const;
354
355 /// Chooses a corner vertex of this Triangle at random.
356 /** This function returns one of the vertices {a, b, c} at uniformly random.
357 @param rng A pre-seeded random number generator object that is to be used by this function to generate random values.
358 @see class LCG, RandomPointInside(), RandomPointOnEdge(), Vertex(). */
359 vec RandomVertex(LCG &rng) const;
360
361 /// Generates a random point on the edge of this Triangle.
362 /** The points are distributed uniformly.
363 This function requires that this triangle is not degenerate. If it is, an assume() error will be printed,
364 and the return value will be undefined.
365 @param rng A pre-seeded random number generator object that is to be used by this function to generate random values.
366 @see class LCG, RandomPointInside(), RandomVertex(), Edge(), class LineSegment, IsDegenerate(). */
367 vec RandomPointOnEdge(LCG &rng) const;
368
369 #ifdef MATH_ENABLE_STL_SUPPORT
370 /// Returns a human-readable representation of this Line. Most useful for debugging purposes.
371 std::string ToString() const;
372 std::string SerializeToString() const;
373
374 /// Returns a string of C++ code that can be used to construct this object. Useful for generating test cases from badly behaving objects.
375 std::string SerializeToCodeString() const;
376 #endif
377
378 static Triangle FromString(const char *str, const char **outEndStr = 0);
379 #ifdef MATH_ENABLE_STL_SUPPORT
380 static Triangle FromString(const std::string &str) { return FromString(str.c_str()); }
381 #endif
382
383 #ifdef MATH_QT_INTEROP
384 operator QString() const { return toString(); }
385 QString toString() const { return QString::fromStdString(ToString()); }
386 #endif
387
388 bool Equals(const Triangle &rhs, float epsilon = 1e-3f) const { return a.Equals(rhs.a, epsilon) && b.Equals(rhs.b, epsilon) && c.Equals(rhs.c, epsilon); }
389
390 /// Compares whether this Triangle and the given Triangle are identical bit-by-bit in the underlying representation.
391 /** @note Prefer using this over e.g. memcmp, since there can be SSE-related padding in the structures. */
392 bool BitEquals(const Triangle &other) const { return a.BitEquals(other.a) && b.BitEquals(other.b) && c.BitEquals(other.c); }
393 };
394
395 Triangle operator *(const float3x3 &transform, const Triangle &t);
396 Triangle operator *(const float3x4 &transform, const Triangle &t);
397 Triangle operator *(const float4x4 &transform, const Triangle &t);
398 Triangle operator *(const Quat &transform, const Triangle &t);
399
400 struct Triangle_storage
401 {
402 vec_storage v0, v1, v2;
403 Triangle_storage(const Triangle &rhs)
404 {
405 *reinterpret_cast<Triangle*>(this) = rhs;
406 }
407 operator Triangle() const { return *reinterpret_cast<const Triangle*>(this); }
408 };
409 #define TRIANGLE(x) (*(Triangle*)&x)
410
411 #ifdef MATH_QT_INTEROP
412 Q_DECLARE_METATYPE(Triangle)
413 Q_DECLARE_METATYPE(Triangle*)
414 #endif
415
416 #ifdef MATH_ENABLE_STL_SUPPORT
417 std::ostream &operator <<(std::ostream &o, const Triangle &triangle);
418 #endif
419
420 bool LineSegment2DLineSegment2DIntersect(const float2 &p0, const float2 &dir0, const float2 &p1, const float2 &dir1, float &s, float &t);
421
422 MATH_END_NAMESPACE