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 Polygon.h
16         @author Jukka Jyl�nki
17         @brief The Polygon 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 //#endif
26
27 MATH_BEGIN_NAMESPACE
28
29 /// Represents a two-dimensional closed surface in 3D space.
30 /** A polygon is defined by N endpoints, or corner vertices. To be a valid polygon, there must be
31    at least 3 vertices (a triangle).
32
33    Well-formed polygons are always planar, i.e. all the vertices lie on the same plane. It is possible
34    to store non-planar Polygons in this structure, but their representation is ambiguous, and for all practical
35    purposes, should be avoided. */
36 class Polygon
37 {
38 public:
39         /// The default constructor creates a null polygon.
40         /** A null polygon has 0 vertices.
41                 @see IsNull(). */
42         Polygon() {}
43
44         /// Stores the vertices of this polygon.
45         VecArray p;
46
47         FORCE_INLINE static int NumFaces() { return 1; }
48
49         /// Returns the number of edges in this polygon.
50         /** Since the polygon is always closed and connected, the number of edges is equal to the number of vertices.
51                 @see Edge(), NumVertices(). */
52         int NumEdges() const;
53
54         /// Returns the number of vertices in this polygon.
55         /** Since the polygon is always closed and connected, the number of edges is equal to the number of vertices.
56                 @see p, Vertex(), NumVertices(). */
57         int NumVertices() const;
58
59         /// Returns a pointer to an array of vertices of this polygon. The array contains NumVertices() elements.
60         /// @note Do NOT hold on to this pointer, since it is an alias to the underlying std::vector owned by this polygon. Calling any non-const Polygon member function may invalidate the pointer!
61         vec *VertexArrayPtr() { return !p.empty() ? (vec*)&p[0] : 0; }
62         const vec *VertexArrayPtr() const { return !p.empty() ? (vec*)&p[0] : 0; }
63
64         /// Quickly returns an arbitrary point inside this AABB. Used in GJK intersection test.
65         vec AnyPointFast() const { return !p.empty() ? p[0] : vec::nan; }
66
67         /// Returns a vertex of this polygon.
68         /** @param vertexIndex The index of the vertex to get, in the range [0, NumVertices()-1].
69                 @see p, NumVertices(), Edge(). */
70         vec Vertex(int vertexIndex) const;
71
72         /// Returns a line segment between two adjacent vertices of this polygon.
73         /** @param edgeIndex The index of the edge line segment to construct, in the range [0, NumEdges()-1].
74                 @return LineSegment(Vertex(edgeIndex), Vertex((edgeIndex+1)%NumVertices()).
75                 @see NumEdges(), Vertex(), Edge2D(), EdgeNormal(), EdgePlane(). */
76         LineSegment Edge(int edgeIndex) const;
77
78         /// Returns a line segment between two adjacent vertices of this polygon, in the local space of this polygon.
79         /** In the local space of the polygon, the z-coordinate is always zero, and the polygon lies in the XY-plane, with
80                 the first vertex of the polygon being in the origin, and the x-axis running in the direction given by BasisU() and
81                 the y-axis running in the direction given by BasisV().
82                 @param edgeIndex The index of the edge line segment to construct, in the range [0, NumEdges()-1].
83                 @see NumEdges(), Vertex(), Edge2D(), EdgeNormal(), EdgePlane(), BasisU(), BasisV(). */
84         LineSegment Edge2D(int edgeIndex) const;
85
86         /// Returns the normal vector of the given edge.
87         /** The normal vector is perpendicular to the normal of the plane the polygon lies in, and the direction the given edge
88                 is pointing towards. The vector points outwards from the polygon.
89                 @param edgeIndex The index of the edge line segment to construct, in the range [0, NumEdges()-1].
90                 @return A normalized direction vector perpendicular to the normal of the polygon, and the given edge.
91                 @see NumEdges(), Edge(), Edge2D(), EdgePlane(). */
92         vec EdgeNormal(int edgeIndex) const;
93
94         /// Returns the normal plane of the given edge.
95         /** The normal vector of the returned plane points towards the direction specified by EdgeNormal(), and the given edge
96                 lies inside the returned plane.
97                 @param edgeIndex The index of the edge line segment to construct, in the range [0, NumEdges()-1]. */
98         Plane EdgePlane(int edgeIndex) const;
99
100         /// Computes an extreme point of this Polygon in the given direction.
101         /** An extreme point is a farthest point of this Polygon in the given direction. Given a direction,
102                 this point is not necessarily unique.
103                 @param direction The direction vector of the direction to find the extreme point. This vector may
104                         be unnormalized, but may not be null.
105                 @return An extreme point of this Polygon in the given direction. The returned point is always a
106                         vertex of this Polygon.
107                 @see Vertex(). */
108         vec ExtremePoint(const vec &direction) const;
109         vec ExtremePoint(const vec &direction, float &projectionDistance) const;
110
111         /// Projects this Polygon onto the given 1D axis direction vector.
112         /** This function collapses this Polygon onto an 1D axis for the purposes of e.g. separate axis test computations.
113                 The function returns a 1D range [outMin, outMax] denoting the interval of the projection.
114                 @param direction The 1D axis to project to. This vector may be unnormalized, in which case the output
115                         of this function gets scaled by the length of this vector.
116                 @param outMin [out] Returns the minimum extent of this object along the projection axis.
117                 @param outMax [out] Returns the maximum extent of this object along the projection axis. */
118         void ProjectToAxis(const vec &direction, float &outMin, float &outMax) const;
119
120         /// Tests if the given diagonal exists.
121         /** This function tests whether the diagonal that joins the two given vertices lies inside this polygon and is not intersected
122                 by the edges of this polygon.
123                 This function may only be called if this Polygon is planar.
124                 @param i Index of the first endpoint of the diagonal LineSegment, in the range [0, NumVertices-1].
125                 @param j Index of the second endpoint of the diagonal LineSegment, in the range [0, NumVertices-1]. Do not pass in i==j
126                         or |i-j| == 1.
127                 @note If |i-j| <= 1, then assume() failure is generated and false is returned.
128                 @return True if Diagonal(vertexIndex1, vertexIndex2) exists and does not intersect the edges of this polygon.
129                 @see Diagonal(), Vertex(), Edge(). */
130         bool DiagonalExists(int i, int j) const;
131
132         /// Returns the diagonal that joins the two given vertices.
133         /** If |i-j| == 1, then this returns an edge of this Polygon.
134                 If i==j, then a degenerate line segment of zero length is returned.
135                 Otherwise, the line segment that joins the two given vertices is returned. Note that if the polygon is not planar or convex,
136                 this line segment might not lie inside the polygon. Use the DiagonalExists() function to test whether the returned
137                 LineSegment actually is a diagonal of this polygon.
138                 @param i Index of the first endpoint of the diagonal LineSegment, in the range [0, NumVertices-1].
139                 @param j Index of the second endpoint of the diagonal LineSegment, in the range [0, NumVertices-1].
140                 @note Whereas it is invalid to call DiagonalExists() with values |i-j|<=1, it is acceptable for this function. This is to
141                         simplify generation of code that iterates over diagonal vertex pairs.   
142                 @return LineSegment(Vertex(i), Vertex(j)) without checking if this actually is a valid diagonal of this polygon. If
143                         indices outside the valid range are passed, LineSegment(nan, nan) is returned.
144                 @see Vertex(), NumVertices(), DiagonalExists(). */
145         LineSegment Diagonal(int i, int j) const;
146
147         /// Tests if this polygon is convex.
148         /** A polygon is convex, if for each pair of points inside the polygon, also the line segment joining those points is
149                 inside the polygon.
150                 @note This data structure can be used with both convex and non-convex polygons. In general, using convex polygons
151                         allows more efficient algorithms to be used with some operations. These more efficient variants are of form
152                         xxxConvex() in this class. Do not call those functions unless you know that the polygon is convex.
153                 @see IsPlanar(), IsSimple(), IsNull(), IsFinite(), IsDegenerate(). */
154         bool IsConvex() const;
155
156         /// Tests if this polygon is planar.
157         /** A polygon is planar if all its vertices lie on the same plane.
158                 @note Almost all functions in this class require that the polygon is planar. While you can store vertices of
159                         non-planar polygons in this class, they are better avoided. Read the member function documentation carefully
160                         to avoid calling for non-planar polygons any functions which assume planarity.
161                 @see IsConvex(), IsSimple(), IsNull(), IsFinite(), IsDegenerate(). */
162         bool IsPlanar(float epsilonSq = 1e-4f) const;
163
164         /** Tests if this polygon is simple.
165                 A polygon is simple if no two nonconsecutive edges have a point in common.
166                 In other words, a planar polygon is simple if its edges do not self-intersect, and if each vertex is joined by
167                 exactly two edges.
168                 @note This function assumes that the polygon is planar.
169                 @see IsConvex(), IsPlanar(), IsNull(), IsFinite(), IsDegenerate(). */
170         bool IsSimple() const;
171
172         /// Tests if this polygon is null.
173         /** A polygon is null if it has zero vertices.
174                 @note The null polygon is degenerate and finite.
175                 @see p, IsConvex(), IsPlanar(), IsSimple(), IsFinite(), IsDegenerate(). */
176         bool IsNull() const;
177
178         /// Tests if this polygon is finite.
179         /** A polygon is finite if each of its vertices have finite floating point coordinates (no nans or infs).
180                 @note The null polygon is finite.
181                 @see p, IsConvex(), IsPlanar(), IsSimple(), IsNull(), IsDegenerate(), ::IsFinite(), IsInf(), IsNan(), IsFinite(), inf, negInf, nan, float3::nan, float3::inf. */
182         bool IsFinite() const;
183
184         /// Tests if this polygon is degenerate.
185         /** A polygon is degenerate if it has two or less vertices, or if its surface area is less or equal than the given epsilon.
186                 @note The null polygon is degenerate and finite.
187                 @see p, IsConvex(), IsPlanar(), IsSimple(), IsNull(), IsDegenerate(), Area(). */
188         bool IsDegenerate(float epsilon = 1e-4f) const;
189
190         /// Generates the U vector of the local space of this polygon.
191         /** This vector specifies in global (world) space the direction of the local X axis of this polygon.
192                 @note This function assumes that the first two points (p[0] and p[1]) of this polygon are finite and inequal. */
193         vec BasisU() const;
194         /// Generates the V vector of the local space of this polygon. [similarOverload: BasisU]
195         /** This vector specifies in global (world) space the direction of the local Y axis of this polygon.
196                 @note This function assumes that the first two points (p[0] and p[1]) of this polygon are finite and inequal.
197                 @see MapTo2D(), MapFrom2D(), Edge2D(), BasisU(), BasisV(). */
198         vec BasisV() const;
199
200         /// Returns the given vertex of this polygon mapped to a local 2D space on this polygon.
201         /** In the local space of the polygon, the z-coordinate is always zero, and the polygon lies in the XY-plane, with
202                 the first vertex of the polygon being in the origin, and the x-axis running in the direction given by BasisU() and
203                 the y-axis running in the direction given by BasisV().
204                 @param i The index of the vertices of this polygon to generate, in the range [0, NumVertices()-1].
205                 @see NumVertices(), MapFrom2D(), Edge2D(), BasisU(), BasisV(). */
206         float2 MapTo2D(int i) const;
207
208         /// Maps the given global (world) space point to the local 2D space of this polygon.
209         /// @todo Return a float3 to be able to read the distance of the point from the plane of the polygon? (or add an overload for that)
210         /// @todo Add MapTo2D(Line/LineSegment/Ray/Triangle/Polygon).
211         float2 MapTo2D(const vec &point) const;
212
213         /// Given a 2D point in the local space, returns the corresponding 3D point in the global (world) space.
214         /** @see MapTo2D(), BasisU(), BasisV(). */
215         vec MapFrom2D(const float2 &point) const;
216
217         /// Computes the normal of this polygon.
218         /** @return The normal of this polygon. This vector is normalized and points to the direction from which observed the
219                 vertices of this polygon wind in counter-clockwise order.
220                 @note Only call this function if this Polygon is planar. */
221         vec NormalCCW() const;
222         /// Computes the normal of this polygon in clockwise direction. [similarOverload: NormalCCW]
223         /** @return The normal of this polygon in clockwise direction. This vector is normalized and points to the direction
224                 from which observed the vertices of this polygon wind in clockwise order.
225                 @note Only call this function if this Polygon is planar.
226                 @note These two functions follow the relation NormalCCW() == -NormalCW().
227                 @see PlaneCW(), PlaneCCW(). */
228         vec NormalCW() const;
229
230         /// Computes the plane this polygon is contained in.
231         /** @note Only call this function if this Polygon is planar.
232                 @return The plane equation of this polygon. This normal vector of the plane points to the direction from which observed the
233                 vertices of this polygon wind in counter-clockwise order. */
234         Plane PlaneCCW() const;
235         /// Computes the plane this polygon is contained in, with a normal vector that points in the clockwise direction. [similarOverload: PlaneCCW]
236         /** @note Only call this function if this Polygon is planar.
237                 @note The functions PlaneCCW() and PlaneCW() return the same plane, except the normals of the planes point in opposite directions.
238                 @see NormalCCW(), NormalCW(). */
239         Plane PlaneCW() const;
240
241         /// Translates this Polygon in world space.
242         /** @param offset The amount of displacement to apply to this Polygon, in world space coordinates.
243                 @see Transform(). */
244         void Translate(const vec &offset);
245
246         /// Applies a transformation to this Polygon.
247         /** This function operates in-place.
248                 @see Translate(), classes float3x3, float3x4, float4x4, Quat. */
249         void Transform(const float3x3 &transform);
250         void Transform(const float3x4 &transform);
251         void Transform(const float4x4 &transform);
252         void Transform(const Quat &transform);
253
254         // Returns true if the edges of this polygon self-intersect.
255 //      bool IsSelfIntersecting() const;
256
257         // Projects all vertices of this polygon to the given plane.
258 //      void ProjectToPlane(const Plane &plane);
259
260         // Returns true if the edges of this polygon self-intersect when viewed from the given direction.
261 //      bool IsSelfIntersecting(const vec &viewDirection) const;
262
263         // Returns true if there exists edges (p_{i-1}, p_i) and (p_i, p_{i+1}) which are collinear.
264 //      bool HasCollinearEdges() const;
265
266         /// Tests if the given object, expressed in global (world) space, is fully contained inside this polygon.
267         /** Only call this function if the polygon is planar.
268                 This test is performed in global space of this polygon, i.e. by specifying the other object in global (world)
269                 space coordinates.
270                 @param point The point to test for containment.
271                 @param polygonThickness Since a polygon is a 2D object in a 3D space, a threshold value is used to
272                         allow floating-point inaccuracies. This parameter defines how much "thickness" to give to the polygon
273                         for the purposes of the test. polygonThicknessSq is this parameter squared.
274                 @return True if the given object is fully contained inside this polygon (and the plane of this polygon).
275                 @todo Add ContainsConvex(vec/etc.). See RTCD p. 202.
276                 @todo Add Contains(Circle/Disc). */
277         bool Contains(const vec &point, float polygonThicknessSq = 1e-5f) const;
278         bool Contains(const LineSegment &lineSegment, float polygonThickness = 1e-3f) const;
279         bool Contains(const Triangle &triangle, float polygonThickness = 1e-3f) const;
280         bool Contains(const Polygon &polygon, float polygonThickness = 1e-3f) const;
281         //todo Add RTCD, p. 202.
282         //bool ContainsConvex(const vec &worldSpacePoint, float polygonThickness = 1e-3f) const;
283
284         /// Tests if the given object, expressed in the local space of this polygon, is fully contained inside this polyhedron.
285         /** This test is exactly like in Contains(), except it is performed in 2D in the local space of this polygon.
286                 @see Contains(), MapTo2D().
287                 @todo Add Contains2D(Circle/Disc/Triangle/Polygon). */
288         bool Contains2D(const LineSegment &localSpaceLineSegment) const;
289
290         /// Tests whether this polygon and the given object intersect.
291         /** Both objects are treated as "solid", meaning that if one of the objects is fully contained inside
292                 another, this function still returns true.
293                 This test is performed in the global (world) space of this polygon.
294                 @note These functions assume that this polygon might be concave, which requires a significantly slower test. If
295                         you know ahead of time that this polygon is convex, you can instead use one of the faster ConvexIntersects()
296                         functions.
297                 @return True if an intersection occurs or one of the objects is contained inside the other, false otherwise.
298                 @see ConvexIntersects(), Contains(), ClosestPoint(), Distance().
299                 @todo Add Intersects(Circle/Disc). */
300         bool Intersects(const Line &line) const;
301         bool Intersects(const Ray &ray) const;
302         bool Intersects(const LineSegment &lineSegment) const;
303         bool Intersects(const Plane &plane) const;
304         bool Intersects(const AABB &aabb) const;
305         bool Intersects(const OBB &obb) const;
306         bool Intersects(const Triangle &triangle, float polygonThickness = 1e-3f) const;
307         bool Intersects(const Polygon &polygon, float polygonThickness = 1e-3f) const;
308         bool Intersects(const Frustum &frustum) const;
309         bool Intersects(const Polyhedron &polyhedron) const;
310         bool Intersects(const Sphere &sphere) const;
311         bool Intersects(const Capsule &capsule) const;
312
313         /// Tests whether this convex polygon and the given object intersect.
314         /** @note These functions make an implicit assumption that this polygon is convex. If you call these functions on
315                 a convex polygon, the intersection test is effectively performed on the convex hull of this polygon, meaning
316                 that it can result in false positives, so these functions can still be useful as an approximate or an early-out 
317                 test for concave polygons. */
318         bool ConvexIntersects(const AABB &aabb) const;
319         bool ConvexIntersects(const OBB &obb) const;
320         bool ConvexIntersects(const Frustum &frustum) const;
321
322         /// Computes the closest point on this polygon to the given object.
323         /** If the other object intersects this polygon, this function will return an arbitrary point inside
324                 the region of intersection.
325                 @param lineSegment The line segment to find the closest point to.
326                 @param lineSegmentPt [out] If specified, receives the closest point on the line segment to this polygon. This
327                         pointer may be null.
328                 @see Contains(), Distance(), Intersects().
329                 @todo Add ClosestPoint(Line/Ray/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
330         vec ClosestPoint(const LineSegment &lineSegment, vec *lineSegmentPt) const;
331         vec ClosestPoint(const LineSegment &lineSegment) const;
332         vec ClosestPoint(const vec &point) const;
333
334         /// Returns the distance between this polygon and the given point.
335         /** @see Contains(), ClosestPoint(), Intersects(). */
336         float Distance(const vec &point) const;
337
338         /// Returns the surface area of this polygon.
339         /** @see Perimeter(), Centroid(). */
340         float Area() const;
341
342         /// Returns the total edge length of this polygon.
343         /** @see Area(), Centroid(). */
344         float Perimeter() const;
345
346         /// Returns the center of mass of this polygon.
347         /** @see Area(), Perimeter(). */
348         vec Centroid() const;
349         /// Identical to CenterPoint(), but provided to enable common signature with Triangle, AABB and OBB to allow them to be used
350         /// in template classes.
351         vec CenterPoint() const { return Centroid(); }
352
353         /// Computes a point on the perimeter of this polygon.
354         /** @param normalizedDistance A value in the range [0,1[ specifying the distance along the polygon edge to travel.
355                 The polygon perimeter forms a closed loop, so PointOnEdge(0.f) == PointOnEdge(1.f) and is equal to the point p[0] of this
356                 polygon. As another example, PointOnEdge(0.5f) returns the point half-way around the polygon edge (but not necessarily the farthest
357                 point from p[0]).
358                 @see p, RandomPointOnEdge(). */
359         vec PointOnEdge(float normalizedDistance) const;
360
361         /// Computes a random point on the perimeter of this polygon.
362         /** This function generates points with uniform distribution.
363                 @see PointOnEdge(). */
364         vec RandomPointOnEdge(LCG &rng) const;
365
366         vec FastRandomPointInside(LCG &rng) const;
367
368         /// Converts this Polygon to a Polyhedron representation.
369         /** This function will create a Polyhedron with two faces, one for the front face of this Polygon,
370                 and one for the back face.
371                 @todo Add ToPolyhedron(float polygonThickness)
372                 @see Triangulate(), MinimalEnclosingAABB(). */
373         Polyhedron ToPolyhedron() const;
374
375         // These faces will be extruded along the Polygon normal so that they lie polygonThickness units apart from each other.
376 //      Polyhedron ToPolyhedron(float polygonThickness = 0.f) const; ///@todo Add support for this form.
377
378         /// Triangulates this Polygon using the ear-clipping method.
379         /** @see ToPolyhedron(), MinimalEnclosingAABB(). */
380         TriangleArray Triangulate() const;
381
382         /// Returns the smallest AABB that encloses this polygon.
383         /** @todo Add MinimalEnclosingSphere() and MinimalEnclosingOBB().
384                 @see ToPolyhedron(), Triangulate(). */
385         AABB MinimalEnclosingAABB() const;
386
387         std::string ToString() const;
388
389         std::string SerializeToString() const;
390
391         static Polygon FromString(const char *str, const char **outEndStr = 0);
392         static Polygon FromString(const std::string &str) { return FromString(str.c_str()); }
393
394         bool Equals(const Polygon &other) const;
395         bool BitEquals(const Polygon &other) const;
396
397         // Returns true if the given vertex is a concave vertex. Otherwise the vertex is a convex vertex.
398 //      bool IsConcaveVertex(int i) const;
399
400         // Computes the conves hull of this polygon.
401 //      Polygon ConvexHull() const;
402
403 //      bool IsSupportingPoint(int i) const;
404
405 //      bool IsSupportingPoint(const vec &point) const;
406
407         // Returns true if the quadrilateral defined by the four points is convex (and not concave or bowtie).
408 //      static bool IsConvexQuad(const vec &pointA, const vec &pointB, const vec &pointC, const vec &pointD);
409 };
410
411 Polygon operator *(const float3x3 &transform, const Polygon &polygon);
412 Polygon operator *(const float3x4 &transform, const Polygon &polygon);
413 Polygon operator *(const float4x4 &transform, const Polygon &polygon);
414 Polygon operator *(const Quat &transform, const Polygon &polygon);
415
416 #ifdef MATH_QT_INTEROP
417 Q_DECLARE_METATYPE(Polygon)
418 Q_DECLARE_METATYPE(Polygon*)
419 #endif
420
421 // @todo Add this.
422 //#ifdef MATH_ENABLE_STL_SUPPORT
423 //std::ostream &operator <<(std::ostream &o, const Polygon &polygon);
424 //#endif
425
426 MATH_END_NAMESPACE