Libs/Math3D/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