Cafu Engine
Polygon.hpp
1 /*
2 Cafu Engine, http://www.cafu.de/
3 Copyright (c) Carsten Fuchs and other contributors.
4 This project is licensed under the terms of the MIT license.
5 */
6 
7 /***************/
8 /*** Polygon ***/
9 /***************/
10 
11 #ifndef CAFU_MATH_POLYGON_HPP_INCLUDED
12 #define CAFU_MATH_POLYGON_HPP_INCLUDED
13 
14 #include "Plane3.hpp"
15 #include "Templates/Array.hpp"
16 
17 
18 /// This class implements convex polygons.
19 ///
20 /// Properties / invariants of polygons:
21 /// 1. Polygons are always convex.
22 /// 2. Polygons are always on the "front" side of their plane.
23 /// 3. The vertices of a polygon are always ordered in clockwise (CW) order,
24 /// as seen from the front half-space (against the normal vectors direction) of the polygons plane.
25 /// 4. A polygon has at least three vertices and its plane is not degenerate, or it is the "null" polygon.
26 /// 5. There are no coincident vertices, that is, V[n]!=V[n+1] for all n.
27 template<class T>
28 class Polygon3T
29 {
30  public:
31 
32  ArrayT< Vector3T<T> > Vertices; ///< Vertices of this polygon.
33  Plane3T<T> Plane; ///< Plane of this polygon.
34 
35 
36  /// Describes on which side of a plane the polygon is.
37  enum SideT
38  {
39  Empty =0, ///< The polygon is empty (it has no vertices).
40  On =1, ///< The polygon has vertices in the plane. Note that this value alone is never returned by WhatSide().
41  Front =2, ///< The polygon has vertices on the front-side of the plane.
42  FrontAndOn =3, ///< The polygon has vertices on the front-side of and in the plane.
43  Back =4, ///< The polygon has vertices on the back-side of the plane.
44  BackAndOn =5, ///< The polygon has vertices on the back-side of and in the plane.
45  Both =6, ///< The polygon has vertices on both sides of the plane.
46  BothAndOn =7, ///< The polygon has vertices on both sides of and in the plane.
47  InIdentical=8, ///< The polygon is in the plane.
48  InMirrored =9 ///< The polygon is in the mirrored version of the plane (opposite normal vectors).
49  };
50 
51 
52  /// This methods returns whether a polygon is valid wrt. the above stipulated properties/terms.
53  /// @param RoundEpsilon The epsilon tolerance that is acceptable for rounding errors.
54  /// @param MinVertexDist The minimum distance that vertices must be apart.
55  /// The MinVertexDist value should be a good deal larger than the RoundEpsilon value, because *very* subtle problems
56  /// can easily arise whenever the "structural object size" is as small as the maximally permitted rounding error!
57  /// @returns true if the polygon is valid, false otherwise.
58  bool IsValid(const double RoundEpsilon, const double MinVertexDist) const;
59 
60  /// Returns the plane that contains the polygon edge defined by (VertexNr, VertexNr+1), that is orthogonal to the polygons
61  /// plane and whose normal vector points towards the polygon center.
62  ///
63  /// @param VertexNr The edge defined by (VertexNr, VertexNr+1) for which a plane should be created.
64  /// @param Epsilon Maximum error value.
65  /// @throws DivisionByZeroE if the edge is shorter than accounted for by Epsilon.
66  Plane3T<T> GetEdgePlane(unsigned long VertexNr, const T Epsilon) const
67  {
68  return Plane3T<T>(Vertices[VertexNr],
69  Vertices[VertexNr+1<Vertices.Size() ? VertexNr+1 : 0],
70  Vertices[VertexNr]-Plane.Normal, Epsilon);
71  }
72 
73  /// Returns a mirrored copy of this polygon, with reversed plane and reversed order.
74  /// (If this polygon was valid, the mirrored polygon is valid, too.)
75  Polygon3T<T> GetMirror() const;
76 
77  /// Determines the spatial area (Fl√§cheninhalt) of this polygon.
78  T GetArea() const;
79 
80  /// Determines whether this polygon has a vertex A, within Epsilon tolerance of the existing vertices.
81  bool HasVertex(const Vector3T<T>& A, const T Epsilon) const;
82 
83  /// Determines on what side of plane P this polygon is.
84  /// @param P The plane to check with.
85  /// @param HalfPlaneThickness DOCTODO
86  /// @returns one of the values of SideT. Note however that SideT::On is never returned in favour of either SideT::InIdentical or SideT::InMirrored.
87  /// If this polygon has edges that are shorter than the plane thickness (==2*HalfPlaneThickness) and SideT::InIdentical or SideT::InMirrored
88  /// is returned, the result is inreliable and should not be trusted. (The polygon should then be considered as invalid and be discarded.)
89  SideT WhatSide(const Plane3T<T>& P, const T HalfPlaneThickness) const;
90 
91  /// Like WhatSide(), but it integrates the "...AndOn" answers with the non-"AndOn" answers.
92  /// That is, instead of FrontAndOn only Front is returned, instead of BackAndOn Back, and instead of BothAndOn Both is returned.
93  /// @param P The plane to check with.
94  /// @param HalfPlaneThickness DOCTODO
95  /// @see WhatSide()
96  SideT WhatSideSimple(const Plane3T<T>& P, const T HalfPlaneThickness) const;
97 
98  /// Determines whether this polygon overlaps OtherPoly (in the same plane).
99  ///
100  /// @param OtherPoly The polygon for which is determined whether it is overlapped by this polygon.
101  /// @param ReportTouchesAsOverlaps If true, an overlap is reported even if it has zero area, that is, even if the two polygons merely "touch"
102  /// within the thickness of the edges. If false, an overlap is only reported if it has a positive, non-zero area.
103  /// @param EdgeThickness describes both the "thickness" of the edges within which small gaps (i.e. non-overlaps)
104  /// are tolerated, *and* the minimum length of the edges of this polygon and OtherPoly.
105  /// @throws InvalidOperationE if an edge of this polygon or OtherPoly is shorter than EdgeThickness.
106  /// @returns true if there is an overlap, false otherwise.
107  bool Overlaps(const Polygon3T<T>& OtherPoly, bool ReportTouchesAsOverlaps, const T EdgeThickness) const;
108 
109  /// Determines whether this polygon entirely encloses OtherPoly (in the same or mirrored plane).
110  ///
111  /// @param OtherPoly The polygon for which is determined whether it is enclosed by this polygon.
112  /// @param MayTouchEdges If true, OtherPoly may touch the edges of this polygon within EdgeThickness tolerance and is still being
113  /// considered enclosed. If false, OtherPoly must truly be inside this polygon, and it must not touch its edges.
114  /// @param EdgeThickness describes both the "thickness" of the edges of this polygon *and* the minimum length of the edges of this polygon and OtherPoly.
115  /// @returns true if this polygon encloses OtherPoly, false otherwise.
116  /// All edge lengths of this and OtherPoly should be longer than 2*EdgeThinkness, or else the result will be undefined.
117  /// @throws InvalidOperationE if an edge of this polygon is shorter than EdgeThickness.
118  bool Encloses(const Polygon3T<T>& OtherPoly, bool MayTouchEdges, const T EdgeThickness) const;
119 
120  /// Splits the polygon along the passed plane.
121  /// WARNING: This function can return invalid polygons from a valid polygon!
122  /// This happens for example if the polygon is a sharp wedge whose top is cut of. If the wedge was sharp enough,
123  /// vertices may be created at the cut surface that concur with each other!
124  /// Therefore the resulting polygons should ALWAYS be checked for validity by IsValid()!
125  /// @param SplitPlane The plane to split the polygon with.
126  /// @param HalfPlaneThickness DOCTODO
127  /// @return The resulting polygons.
128  ArrayT< Polygon3T<T> > GetSplits(const Plane3T<T>& SplitPlane, const T HalfPlaneThickness) const;
129 
130  /// Cuts this polygon along the edges of Poly. Prerequisite: this->Overlaps(Poly)!
131  /// The last polygon in NewPolys is the overlapping one (*), the front entries lie outside the polygon.
132  /// (If this polygon is contained in Poly (even then this->Overlaps(Poly) is true), NewPolys contains only a copy of this polygon.)
133  /// This also works without this prerequisite, but (*) is no longer true!
134  /// WARNING: This function uses GetSplits() and therfore has the same troubles as this method!
135  /// @param Poly Polygon to cut this polygon with.
136  /// @param EdgeThickness DOCTODO
137  /// @param NewPolys The resulting polygons.
138  void GetChoppedUpAlong(const Polygon3T<T>& Poly, const T EdgeThickness, ArrayT< Polygon3T<T> >& NewPolys) const;
139 
140 
141  /// If poly builds t-junctions at this polygon, the according vertives are added to this polygon.
142  /// WARNING: The resulting polygon will, in general, be *INVALID* (several vertices per edge).
143  /// @param Poly Polygon that is checked for t-junctions with this polygon.
144  /// @param EdgeThickness DOCTODO
145  void FillTJunctions(const Polygon3T<T>& Poly, const T EdgeThickness);
146 
147 
148  /// Merge Poly1 and Poly2 under the following prerequisites:
149  /// - Poly1 and Poly2 have at least 3 vertices (non-degenerate).
150  /// - Both polygons lie in the same plane with the same orientation.
151  /// - Poly1 and Poly2 have one common, but opposed edge.
152  /// - The new polygon is (at the welded joint) also konvex.
153  /// @param Poly1 First polygon to merge.
154  /// @param Poly2 Second polygon to merge.
155  /// @param EdgeThickness DOCTODO
156  /// @throws InvalidOperationE if Poly1 and Poly2 could not be merged.
157  static Polygon3T<T> Merge(const Polygon3T<T>& Poly1, const Polygon3T<T>& Poly2, const T EdgeThickness);
158 
159  /// Given a brush (here: array of polygons), from which only the planes are known.
160  /// WARNING: All normal vectors of the polygons must point to the outside!
161  /// Find the vertices of all polygons and sort them in clockwise direction.
162  /// WARNING: Degenerated inputs are also possible, e.g. the planes from a cube with one side missing.
163  /// Those cases can't be caught here as errors because this functionality is necessary for portal creation.
164  /// In this case polygons with fewer than 3 vertices are returned and an explicit validity check is necessary!
165  /// It is also possible that the input planes of a polygon for example specify a triangle where one edge is shorter than GeometryEpsilon.
166  /// In this case the vertices would be combined and a polygon with only 2 vertices would be the result!
167  /// Further example for similar degenerated cases are also possible.
168  /// Consequence: Check the returned polygon sets ALWAYS for validity, e.g. Polys[...].Vertices.Size()>=3 !
169  /// @param Polys Polygons to complete
170  /// @param HalfPlaneThickness DOCTODO
171  /// @param BoundingSphereCenter DOCTODO
172  /// @param BoundingSphereRadius DOCTODO
173  static void Complete(ArrayT< Polygon3T<T> >& Polys, const T HalfPlaneThickness, const Vector3T<T>& BoundingSphereCenter=Vector3T<T>(0, 0, 0), const T BoundingSphereRadius=10.0*1000.0*1000.0);
174 };
175 
176 #endif
void FillTJunctions(const Polygon3T< T > &Poly, const T EdgeThickness)
If poly builds t-junctions at this polygon, the according vertives are added to this polygon...
Definition: Polygon.cpp:286
SideT WhatSideSimple(const Plane3T< T > &P, const T HalfPlaneThickness) const
Like WhatSide(), but it integrates the "...AndOn" answers with the non-"AndOn" answers.
Definition: Polygon.cpp:140
This class represents a plane in three-dimensional space.
Definition: Plane3.hpp:26
static Polygon3T< T > Merge(const Polygon3T< T > &Poly1, const Polygon3T< T > &Poly2, const T EdgeThickness)
Merge Poly1 and Poly2 under the following prerequisites:
Definition: Polygon.cpp:352
ArrayT< Vector3T< T > > Vertices
Vertices of this polygon.
Definition: Polygon.hpp:32
Polygon3T< T > GetMirror() const
Returns a mirrored copy of this polygon, with reversed plane and reversed order.
Definition: Polygon.cpp:82
The polygon has vertices on the front-side of the plane.
Definition: Polygon.hpp:41
T GetArea() const
Determines the spatial area (Flächeninhalt) of this polygon.
Definition: Polygon.cpp:95
void GetChoppedUpAlong(const Polygon3T< T > &Poly, const T EdgeThickness, ArrayT< Polygon3T< T > > &NewPolys) const
Cuts this polygon along the edges of Poly.
Definition: Polygon.cpp:264
bool Encloses(const Polygon3T< T > &OtherPoly, bool MayTouchEdges, const T EdgeThickness) const
Determines whether this polygon entirely encloses OtherPoly (in the same or mirrored plane)...
Definition: Polygon.cpp:183
This class represents a polymorphic 3-dimensional vector.
Definition: Misc.hpp:11
The polygon is empty (it has no vertices).
Definition: Polygon.hpp:39
The polygon has vertices in the plane. Note that this value alone is never returned by WhatSide()...
Definition: Polygon.hpp:40
This class implements convex polygons.
Definition: Polygon.hpp:28
SideT
Describes on which side of a plane the polygon is.
Definition: Polygon.hpp:37
The polygon has vertices on the back-side of the plane.
Definition: Polygon.hpp:43
The polygon has vertices on both sides of and in the plane.
Definition: Polygon.hpp:46
SideT WhatSide(const Plane3T< T > &P, const T HalfPlaneThickness) const
Determines on what side of plane P this polygon is.
Definition: Polygon.cpp:119
Plane3T< T > GetEdgePlane(unsigned long VertexNr, const T Epsilon) const
Returns the plane that contains the polygon edge defined by (VertexNr, VertexNr+1), that is orthogonal to the polygons plane and whose normal vector points towards the polygon center.
Definition: Polygon.hpp:66
ArrayT< Polygon3T< T > > GetSplits(const Plane3T< T > &SplitPlane, const T HalfPlaneThickness) const
Splits the polygon along the passed plane.
Definition: Polygon.cpp:202
The polygon is in the mirrored version of the plane (opposite normal vectors).
Definition: Polygon.hpp:48
bool IsValid(const double RoundEpsilon, const double MinVertexDist) const
This methods returns whether a polygon is valid wrt.
Definition: Polygon.cpp:14
bool Overlaps(const Polygon3T< T > &OtherPoly, bool ReportTouchesAsOverlaps, const T EdgeThickness) const
Determines whether this polygon overlaps OtherPoly (in the same plane).
Definition: Polygon.cpp:156
static void Complete(ArrayT< Polygon3T< T > > &Polys, const T HalfPlaneThickness, const Vector3T< T > &BoundingSphereCenter=Vector3T< T >(0, 0, 0), const T BoundingSphereRadius=10.0 *1000.0 *1000.0)
Given a brush (here: array of polygons), from which only the planes are known.
Definition: Polygon.cpp:397
The polygon has vertices on the back-side of and in the plane.
Definition: Polygon.hpp:44
The polygon has vertices on the front-side of and in the plane.
Definition: Polygon.hpp:42
The polygon has vertices on both sides of the plane.
Definition: Polygon.hpp:45
bool HasVertex(const Vector3T< T > &A, const T Epsilon) const
Determines whether this polygon has a vertex A, within Epsilon tolerance of the existing vertices...
Definition: Polygon.cpp:110
Plane3T< T > Plane
Plane of this polygon.
Definition: Polygon.hpp:33
Definition: Renderer.hpp:16
The polygon is in the plane.
Definition: Polygon.hpp:47