Polyhedron.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 Polyhedron.h
16 @author Jukka Jyl�nki
17 @brief The Polyhedron geometry object. */
18 #pragma once
19
20 #include "../MathGeoLibFwd.h"
21 #include "../Math/float3.h"
22
23 //#ifdef MATH_ENABLE_STL_SUPPORT
24 #include <vector>
25 #include <string>
26 //#endif
27
28 MATH_BEGIN_NAMESPACE
29
30 /// Represents a three-dimensional closed geometric solid defined by flat polygonal faces.
31 class Polyhedron
32 {
33 public:
34 /// Stores a list of indices of a single face of a Polyhedron.
35 struct Face
36 {
37 /// Specifies the indices of the corner vertices of this polyhedron.
38 /// Indices point to the polyhedron vertex array.
39 /// The face vertices should all lie on the same plane.
40 /// The positive direction of the plane (the direction the face outwards normal points to)
41 /// is the one where the vertices are wound in counter-clockwise order.
42 std::vector<int> v;
43
44 /// Reverses the winding order of this face. This has the effect of reversing the direction
45 /// the normal of this face points to.
46 void FlipWindingOrder();
47
48 /// Returns a string of form "0,1,2,3,4" that refers to the indices of the vertices that this face uses.
49 std::string ToString() const;
50
51 static Face FromString(const char *str);
52 };
53
54 /// Specifies the vertices of this polyhedron.
55 VecArray v;
56
57 /// Specifies the individual faces of this polyhedron. [similarOverload: v]
58 /** Each face is described by a list of indices to the vertex array. The indices define a
59 simple polygon in counter-clockwise winding order. */
60 std::vector<Face> f;
61
62 /// The default constructor creates a null polyhedron.
63 /** A null polyhedron has 0 vertices and 0 faces.
64 @see IsNull(). */
65 Polyhedron() {}
66
67 /// Returns the number of vertices in this polyhedron.
68 /** The running time of this function is O(1).
69 @see NumFaces(), NumEdges(), EulerFormulaHolds(). */
70 int NumVertices() const { return (int)v.size(); }
71
72 /// Returns the number of faces in this polyhedron.
73 /** The running time of this function is O(1).
74 @see NumVertices(), NumEdges(), EulerFormulaHolds(), FacePolygon(), FacePlane(). */
75 int NumFaces() const { return (int)f.size(); }
76
77 /// Returns the number of (unique) edges in this polyhedron.
78 /** This function will enumerate through all faces of this polyhedron to compute the number of unique edges.
79 The running time is linear to the number of faces and vertices in this Polyhedron.
80 @see NumVertices(), NumFaces(), EulerFormulaHolds(), Edge(), Edges(), EdgeIndices(). */
81 int NumEdges() const;
82
83 /// Returns a pointer to an array of vertices of this polyhedron. The array contains NumVertices() elements.
84 /// @note Do NOT hold on to this pointer, since it is an alias to the underlying std::vector owned by this polyhedron. Calling any non-const Polyhedron member function may invalidate the pointer!
85 vec *VertexArrayPtr() { return !v.empty() ? (vec*)&v[0] : 0; }
86 const vec *VertexArrayPtr() const { return !v.empty() ? (vec*)&v[0] : 0; }
87
88 /// Returns the ith vertex of this polyhedron.
89 /** @param vertexIndex The vertex to get, in the range [0, NumVertices()-1].
90 @see NumVertices(). */
91 vec Vertex(int vertexIndex) const;
92
93 /// Returns the ith edge of this polyhedron.
94 /** Performance warning: Use this function only if you are interested in a single edge of this Polyhedron.
95 This function calls the Edges() member function to receive a list of all the edges, so has
96 a complexity of O(|V|log|V|), where |V| is the number of vertices in the polyhedron.
97 @param edgeIndex The index of the edge to get, in the range [0, NumEdges()-1].
98 @see NumEdges(), Edges(), EdgeIndices(). */
99 LineSegment Edge(int edgeIndex) const;
100
101 /// Returns all the (unique) edges of this polyhedron.
102 /** Has complexity of O(|V|log|V|), where |V| is the number of vertices in the polyhedron.
103 @todo Support this in linear time.
104 @see NumEdges(), Edge(), EdgeIndices(). */
105 LineSegmentArray Edges() const;
106
107 std::vector<Polygon> Faces() const;
108
109 /// Returns all the (unique) edges of this polyhedron, as indices to the polyhedron vertex array.
110 /** Has complexity of O(|V|log|V|), where |V| is the number of vertices in the polyhedron.
111 @todo Support this in linear time.
112 @see NumEdges(), Edge(), Edges(). */
113 std::vector<std::pair<int, int> > EdgeIndices() const;
114
115 /// Returns a polygon representing the given face.
116 /** The winding order of the polygon will be the same as in the input. The normal of the polygon
117 points outwards from this polyhedron, i.e. towards the space that is not part of the polyhedron.
118 This function constructs a new Polygon object, so it has a time and space complexity of
119 O(|V|), where |V| is the number of vertices in this polyhedron.
120 @param faceIndex The index of the face to get, in the range [0, NumFaces()-1].
121 @see NumFaces(), FacePlane(). */
122 Polygon FacePolygon(int faceIndex) const;
123
124 /// Returns the plane of the given polyhedron face.
125 /** The normal of the plane points outwards from this polyhedron, i.e. towards the space that
126 is not part of the polyhedron.
127 This function assumes that the given face of the polyhedron is planar, as should be for all
128 well-formed polyhedron.
129 @param faceIndex The index of the face to get, in the range [0, NumFaces()-1].
130 @see NumFaces(), FacePolygon(). */
131 Plane FacePlane(int faceIndex) const;
132
133 /// Returns the normalized normal vector of the given face.
134 vec FaceNormal(int faceIndex) const;
135
136 /// Returns the index of the vertex of this polyhedron that reaches farthest in the given direction.
137 /** @param direction The direction vector to query for. This vector can be unnormalized.
138 @return The supporting point of this polyhedron that reaches farthest in the given direction.
139 The supporting point for a given direction is not necessarily unique, but this function
140 will always return one of the vertices of this polyhedron.
141 @see v, NumVertices(), Vertex(). */
142 int ExtremeVertex(const vec &direction) const;
143 // vec SupportingPoint(const vec &dir) const;
144 // bool IsSupportingPlane(const Plane &plane) const;
145
146 /// Computes an extreme point of this Polyhedron in the given direction.
147 /** An extreme point is a farthest point of this Polyhedron in the given direction. Given a direction,
148 this point is not necessarily unique.
149 @param direction The direction vector of the direction to find the extreme point. This vector may
150 be unnormalized, but may not be null.
151 @return An extreme point of this Polyhedron in the given direction. The returned point is always a
152 corner point of this Polyhedron.
153 @see CornerPoint(). */
154 vec ExtremePoint(const vec &direction) const;
155
156 /// Projects this Polyhedron onto the given 1D axis direction vector.
157 /** This function collapses this Polyhedron onto an 1D axis for the purposes of e.g. separate axis test computations.
158 The function returns a 1D range [outMin, outMax] denoting the interval of the projection.
159 @param direction The 1D axis to project to. This vector may be unnormalized, in which case the output
160 of this function gets scaled by the length of this vector.
161 @param outMin [out] Returns the minimum extent of this object along the projection axis.
162 @param outMax [out] Returns the maximum extent of this object along the projection axis. */
163 void ProjectToAxis(const vec &direction, float &outMin, float &outMax) const;
164
165 /// Returns the exact center of mass of the convex hull of this polyhedron.
166 /** @see SurfaceArea(), Volume(), ApproximateConvexCentroid(). */
167 vec ConvexCentroid() const;
168
169 // Computes the average of all vertices of this Polyhedron.
170 /** If this Polyhedron is a tetrahedron, this is the center of mass for the Polyhedron. Otherwise it
171 is a kind of an approximate enter of mass, biased towards the direction where there are lots of
172 vertices in the Polyhedron.
173 @note This function is considerably faster than ConvexCentroid().
174 @see SurfaceArea(), Volume(), ConvexCentroid(). */
175 vec ApproximateConvexCentroid() const;
176
177 /// Computes the total surface area of the faces of this polyhedron.
178 /** @note When you call this function, none of the faces of this polyhedron may be self-intersecting.
179 @see ConvexCentroid(), Volume(). */
180 float SurfaceArea() const;
181
182 /// Computes the internal volume of this polyhedron.
183 /** @see ConvexCentroid(), SurfaceArea(). */
184 float Volume() const;
185
186 /// Returns the smallest AABB that encloses this polyhedron.
187 /// @todo Add MinimalEnclosingSphere() and MinimalEnclosingOBB().
188 AABB MinimalEnclosingAABB() const;
189
190 #ifdef MATH_CONTAINERLIB_SUPPORT
191 OBB MinimalEnclosingOBB() const;
192 #endif
193
194 void MergeAdjacentPlanarFaces();
195
196 /// Tests if the faces in this polyhedron refer to valid existing vertices.
197 /** This function performs sanity checks on the face indices array.
198 1) Each vertex index for each face must be in the range [0, NumVertices()-1], i.e. refer to a vertex
199 that exists in the array.
200 2) Each face must contain at least three vertices. If a face contains two or one vertex, it is
201 degenerate.
202 3) Each face may refer to a vertex at most once.
203 @return True if the abovementioned conditions hold. Note that this does not guarantee that the
204 polyhedron is completely well-formed, but if false is returned, the polyhedron is definitely
205 ill-formed.
206 @see IsNull(), IsClosed(), IsConvex(). */
207 bool FaceIndicesValid() const;
208
209 /// Flips the winding order of all faces in this polyhedron.
210 void FlipWindingOrder();
211
212 /// Assuming that this polyhedron is convex, reorients all faces of this polyhedron
213 /// so that each face plane has its normal pointing outwards. That is, the "negative" side of the
214 /// polyhedron lies inside the polyhedron, and the positive side of the polyhedron is outside the convex
215 /// shape.
216 void OrientNormalsOutsideConvex();
217
218 /// Removes from the vertex array all vertices that are not referred to by any of the faces of this polyhedron.
219 void RemoveRedundantVertices();
220
221 /// Returns true if this polyhedron has 0 vertices and 0 faces.
222 /** @see FaceIndicesValid(), IsClosed(), IsConvex(). */
223 bool IsNull() const { return v.empty() && f.empty(); }
224
225 /// Returns true if this polyhedron is closed and does not have any gaps.
226 /** \note This function performs a quick check, which might not be complete.
227 @see FaceIndicesValid(), IsClosed(), IsConvex(). */
228 bool IsClosed() const;
229
230 // Returns true if this polyhedron forms a single connected solid volume.
231 // bool IsConnected() const;
232
233 /// Returns true if this polyhedron is convex.
234 /** The running time is O(F*V) ~ O(V^2).
235 @see FaceIndicesValid(), IsClosed(), IsConvex().*/
236 bool IsConvex() const;
237
238 /// Returns true if the Euler formula (V + F - E == 2) holds for this Polyhedron.
239 /** @see NumVertices(), NumEdges(), NumFaces(). */
240 bool EulerFormulaHolds() const;
241
242 /// Tests whether all the faces of this polyhedron are non-degenerate (have at least 3 vertices)
243 /// and in case they have more than 3 vertices, tests that the faces are planar.
244 bool FacesAreNondegeneratePlanar(float epsilon = 1e-2f) const;
245
246 /// Clips the line/ray/line segment specified by L(t) = ptA + t * dir, tFirst <= t <= tLast,
247 /// inside this convex polyhedron.
248 /** The implementation of this function is adapted from Christer Ericson's Real-time Collision Detection, p. 199.
249 @param ptA The first endpoint of the line segment.
250 @param dir The direction of the line segment. This member can be unnormalized.
251 @param tFirst [in, out] As input, takes the parametric distance along the line segment which
252 specifies the starting point of the line segment. As output, the starting point of the line segment
253 after the clipping operation is returned here.
254 @param tLast [in, out] As input, takes the parametric distance along the line segment which
255 specifies the ending point of the line segment. As output, the endingpoint of the line segment
256 after the clipping operation is returned here.
257 @note To clip a line, pass in tFirst=-FLOAT_INF, tLast=FLOAT_INF. To clip a ray, pass in tFirst=0 and tLast = FLOAT_INF.
258 To clip a line segment, pass in tFirst=0, tLast=1, and an unnormalized dir = lineSegment.b-lineSegment.a.
259 @return True if the outputted range [tFirst, tLast] did not become degenerate, and these two variables contain
260 valid data. If false, the whole line segment was clipped away (it was completely outside this polyhedron).
261 @see FLOAT_INF. */
262 bool ClipLineSegmentToConvexPolyhedron(const vec &ptA, const vec &dir, float &tFirst, float &tLast) const;
263
264 /// Returns the index of the nearest vertex to the given point.
265 /** @note In the degenerate case when this Polyhedron is null and does not contain any vertices, this function returns -1. */
266 int NearestVertex(const vec &point) const;
267
268 /// Tests if the given object is fully contained inside this closed polyhedron.
269 /** This function treats this polyhedron as a non-convex object. If you know this polyhedron
270 to be convex, you can use the faster ContainsConvex() function.
271 @note This function assumes that this polyhedron is closed and its edges are not self-intersecting.
272 @see ContainsConvex(), ClosestPoint(), ClosestPointConvex(), Distance(), Intersects(), IntersectsConvex().
273 @todo Add Contains(Circle/Disc/Sphere/Capsule). */
274 bool Contains(const vec &point) const;
275 bool Contains(const LineSegment &lineSegment) const;
276 bool Contains(const Triangle &triangle) const;
277 bool Contains(const Polygon &polygon) const;
278 bool Contains(const AABB &aabb) const;
279 bool Contains(const OBB &obb) const;
280 bool Contains(const Frustum &frustum) const;
281 bool Contains(const Polyhedron &polyhedron) const;
282
283 /// Tests if the given face of this Polyhedron contains the given point.
284 bool FaceContains(int faceIndex, const vec &worldSpacePoint, float polygonThickness = 1e-3f) const;
285
286 /// A helper for Contains() and FaceContains() tests: Returns a positive value if the given point is contained in the given face,
287 /// and a negative value if the given point is outside the face. The magnitude of the return value reports a pseudo-distance
288 /// from the point to the nearest edge of the face polygon. This is used as a robustness/stability criterion to estimate how
289 /// numerically believable the result is.
290 float FaceContainmentDistance2D(int faceIndex, const vec &worldSpacePoint, float polygonThickness = 1e-3f) const;
291
292 /// Tests if the given object is fully contained inside this convex polyhedron.
293 /** This function behaves exactly like Contains(), except this version of the containment test
294 assumes this polyhedron is convex, and uses a faster method of testing containment.
295 @note This function assumes that this polyhedron is closed and its edges are not self-intersecting.
296 @see Contains(), ClosestPoint(), ClosestPointConvex(), Distance(), Intersects(), IntersectsConvex().
297 @todo Add ContainsConvex(Polygon/AABB/OBB/Frustum/Polyhedron/Circle/Disc/Sphere/Capsule). */
298 bool ContainsConvex(const vec &point, float epsilon = 1e-4f) const;
299 bool ContainsConvex(const LineSegment &lineSegment) const;
300 bool ContainsConvex(const Triangle &triangle) const;
301
302 /// Computes the closest point on this polyhedron to the given object.
303 /** If the other object intersects this polyhedron, this function will return an arbitrary point inside
304 the region of intersection.
305 @param lineSegment The line segment to find the closest point to.
306 @param lineSegmentPt [out] If specified, returns the closest point on the line segment to this
307 polyhedron. This pointer may be null.
308 @todo Make lineSegmentPt an out-reference instead of an out-pointer.
309 @note This function assumes that this polyhedron is closed and the edges are not self-intersecting.
310 @see Contains(), ContainsConvex(), ClosestPointConvex(), Distance(), Intersects(), IntersectsConvex().
311 @todo Add ClosestPoint(Line/Ray/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
312 vec ClosestPoint(const LineSegment &lineSegment, vec *lineSegmentPt) const;
313 vec ClosestPoint(const LineSegment &lineSegment) const;
314 /** @param point The point to find the closest point to. */
315 vec ClosestPoint(const vec &point) const;
316
317 /// Returns the closest point on this convex polyhedron to the given point.
318 /** This function behaves exactly like ClosestPoint(), except this version of the test assumes
319 this polyhedron is convex, and uses a faster method of finding the closest point.
320 @note This function assumes that this polyhedron is closed and the edges are not self-intersecting.
321 @see Contains(), ContainsConvex(), ClosestPoint(), Distance(), Intersects(), IntersectsConvex().
322 @todo Add ClosestPointConvex(Line/LineSegment/Ray/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
323 vec ClosestPointConvex(const vec &point) const;
324
325 /// Returns the distance between this polyhedron and the given object.
326 /** This function finds the nearest pair of points on this and the given object, and computes their distance.
327 If the two objects intersect, or one object is contained inside the other, the returned distance is zero.
328 @note This function assumes that this polyhedron is closed and the edges are not self-intersecting.
329 @see Contains(), ContainsConvex(), ClosestPoint(), ClosestPointConvex(), Intersects(), IntersectsConvex().
330 @todo Add Distance(Line/LineSegment/Ray/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
331 float Distance(const vec &point) const;
332
333 /// Tests whether this polyhedron and the given object intersect.
334 /** Both objects are treated as "solid", meaning that if one of the objects is fully contained inside
335 another, this function still returns true. (e.g. in case a line segment is contained inside this polyhedron,
336 or this polyhedron is contained inside a sphere, etc.)
337 @return True if an intersection occurs or one of the objects is contained inside the other, false otherwise.
338 @note This function assumes that this polyhedron is closed and the edges are not self-intersecting.
339 @see Contains(), ContainsConvex(), ClosestPoint(), ClosestPointConvex(), Distance(), IntersectsConvex().
340 @todo Add Intersects(Circle/Disc). */
341 bool Intersects(const LineSegment &lineSegment) const;
342 bool Intersects(const Line &line) const;
343 bool Intersects(const Ray &ray) const;
344 bool Intersects(const Plane &plane) const;
345 bool Intersects(const Polyhedron &polyhedron) const;
346 bool Intersects(const AABB &aabb) const;
347 bool Intersects(const OBB &obb) const;
348 bool Intersects(const Triangle &triangle) const;
349 bool Intersects(const Polygon &polygon) const;
350 bool Intersects(const Frustum &frustum) const;
351 bool Intersects(const Sphere &sphere) const;
352 bool Intersects(const Capsule &capsule) const;
353
354 /// Tests whether this convex polyhedron and the given object intersect.
355 /** This function is exactly like Intersects(), but this version assumes that this polyhedron is convex,
356 and uses a faster method of testing the intersection.
357 @return True if an intersection occurs or one of the objects is contained inside the other, false otherwise.
358 @note This function assumes that this polyhedron is closed and the edges are not self-intersecting.
359 @see Contains(), ContainsConvex(), ClosestPoint(), ClosestPointConvex(), Distance(), Intersects().
360 @todo Add Intersects(Circle/Disc). */
361 bool IntersectsConvex(const Line &line) const;
362 bool IntersectsConvex(const Ray &ray) const;
363 bool IntersectsConvex(const LineSegment &lineSegment) const;
364
365 void MergeConvex(const vec &point);
366
367 /// Translates this Polyhedron in world space.
368 /** @param offset The amount of displacement to apply to this Polyhedron, in world space coordinates.
369 @see Transform(). */
370 void Translate(const vec &offset);
371
372 /// Applies a transformation to this Polyhedron.
373 /** This function operates in-place.
374 @see Translate(), classes float3x3, float3x4, float4x4, Quat. */
375 void Transform(const float3x3 &transform);
376 void Transform(const float3x4 &transform);
377 void Transform(const float4x4 &transform);
378 void Transform(const Quat &transform);
379
380 /// Creates a Polyhedron object that represents the convex hull of the given point array.
381 /// \todo This function is strongly WIP!
382 static Polyhedron ConvexHull(const vec *pointArray, int numPoints);
383
384 static Polyhedron Tetrahedron(const vec &centerPos = POINT_VEC_SCALAR(0.f), float scale = 1.f, bool ccwIsFrontFacing = true);
385 static Polyhedron Octahedron(const vec &centerPos = POINT_VEC_SCALAR(0.f), float scale = 1.f, bool ccwIsFrontFacing = true);
386 static Polyhedron Hexahedron(const vec &centerPos = POINT_VEC_SCALAR(0.f), float scale = 1.f, bool ccwIsFrontFacing = true);
387 static Polyhedron Icosahedron(const vec &centerPos = POINT_VEC_SCALAR(0.f), float scale = 1.f, bool ccwIsFrontFacing = true);
388 static Polyhedron Dodecahedron(const vec &centerPos = POINT_VEC_SCALAR(0.f), float scale = 1.f, bool ccwIsFrontFacing = true);
389
390 /// Tests if these two polyhedrons represent the same set of points.
391 /// @note This function is very slow, and should be used only for debugging purposes.
392 /// @note This function mutates this and the given polyhedron in order to make the test more feasible. The set of space represented
393 /// by the polyhedrons will not change.
394 bool SetEquals(Polyhedron &p2);
395
396 /// Swaps two vertices in the vertex array and updates all faces of this polyhedron so that the volume represented by this polyhedron
397 /// stays the same.
398 void SwapVertices(int i, int j);
399
400 /// Converts the list of faces into a canonical order for easier comparison.
401 void CanonicalizeFaceArray();
402
403 /// Returns true if one of the faces of this Polyhedron has the same ordered of indices as the given Face.
404 bool ContainsFace(const Face &face) const;
405
406 /// Searches each vertex of this polyhedron to find the closest vertex to the given target point.
407 /// @param outDistanceSq [out] Outputs the distance between the target point and the closest vertex, or FLOAT_INF if no such point was found.
408 /// @return An index to the vertex array of this polyhedron denoting the closest vertex to the target point.
409 /// Returns -1 if no such point is found. (no vertices in polyhedron, or all of them contained NaNs/Infs)
410 int FindClosestVertex(const vec &pt, float &outDistanceSq) const;
411
412 TriangleArray Triangulate() const;
413
414 std::string ToString() const;
415
416 #ifdef MATH_GRAPHICSENGINE_INTEROP
417 void Triangulate(VertexBuffer &vb, bool ccwIsFrontFacing, int faceStart = 0, int faceEnd = 0x7FFFFFFF) const;
418 void ToLineList(VertexBuffer &vb) const;
419 #endif
420 };
421
422 Polyhedron operator *(const float3x3 &transform, const Polyhedron &polyhedron);
423 Polyhedron operator *(const float3x4 &transform, const Polyhedron &polyhedron);
424 Polyhedron operator *(const float4x4 &transform, const Polyhedron &polyhedron);
425 Polyhedron operator *(const Quat &transform, const Polyhedron &polyhedron);
426
427 #ifdef MATH_QT_INTEROP
428 Q_DECLARE_METATYPE(Polyhedron)
429 Q_DECLARE_METATYPE(Polyhedron*)
430 #endif
431 /*
432 Polyhedron operator *(const float3x3 &m, const Polyhedron &s);
433 Polyhedron operator *(const float3x4 &m, const Polyhedron &s);
434 Polyhedron operator *(const float4x4 &m, const Polyhedron &s);
435 Polyhedron operator *(const Quat &q, const Polyhedron &s);
436 */
437 // @todo Add this
438 //#ifdef MATH_ENABLE_STL_SUPPORT
439 //std::ostream &operator <<(std::ostream &o, const Polyhedron &polyhedron);
440 //#endif
441
442 MATH_END_NAMESPACE