Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
ConvexHullBuilder.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7//#define JPH_CONVEX_BUILDER_DEBUG
8//#define JPH_CONVEX_BUILDER_DUMP_SHAPE
9
10#ifdef JPH_CONVEX_BUILDER_DEBUG
11 #include <Jolt/Core/Color.h>
12#endif
13
16
18
21{
22public:
23 // Forward declare
24 class Face;
25
27 class Edge : public NonCopyable
28 {
29 public:
31
33 Edge(Face *inFace, int inStartIdx) : mFace(inFace), mStartIdx(inStartIdx) { }
34
37 {
38 Edge *prev_edge = this;
39 while (prev_edge->mNextEdge != this)
40 prev_edge = prev_edge->mNextEdge;
41 return prev_edge;
42 }
43
45 Edge * mNextEdge = nullptr;
46 Edge * mNeighbourEdge = nullptr;
48 };
49
51
53 class Face : public NonCopyable
54 {
55 public:
57
59 ~Face();
60
62 void Initialize(int inIdx0, int inIdx1, int inIdx2, const Vec3 *inPositions);
63
65 void CalculateNormalAndCentroid(const Vec3 *inPositions);
66
68 inline bool IsFacing(Vec3Arg inPosition) const
69 {
70 JPH_ASSERT(!mRemoved);
71 return mNormal.Dot(inPosition - mCentroid) > 0.0f;
72 }
73
77 Edge * mFirstEdge = nullptr;
78 float mFurthestPointDistanceSq = 0.0f;
79 bool mRemoved = false;
80#ifdef JPH_CONVEX_BUILDER_DEBUG
81 int mIteration;
82#endif
83 };
84
85 // Typedefs
88
90 explicit ConvexHullBuilder(const Positions &inPositions);
91
93 ~ConvexHullBuilder() { FreeFaces(); }
94
96 enum class EResult
97 {
98 Success,
99 MaxVerticesReached,
100 TooFewPoints,
101 TooFewFaces,
102 Degenerate,
103 };
104
111 EResult Initialize(int inMaxVertices, float inTolerance, const char *&outError);
112
114 int GetNumVerticesUsed() const;
115
117 bool ContainsFace(const Array<int> &inIndices) const;
118
120 void GetCenterOfMassAndVolume(Vec3 &outCenterOfMass, float &outVolume) const;
121
127 void DetermineMaxError(Face *&outFaceWithMaxError, float &outMaxError, int &outMaxErrorPositionIdx, float &outCoplanarDistance) const;
128
130 const Faces & GetFaces() const { return mFaces; }
131
132private:
134 static constexpr float cMinTriangleAreaSq = 1.0e-12f;
135
136#ifdef JPH_CONVEX_BUILDER_DEBUG
138 static constexpr Real cDrawScale = 10;
139#endif
140
142 class FullEdge
143 {
144 public:
145 Edge * mNeighbourEdge;
146 int mStartIdx;
147 int mEndIdx;
148 };
149
150 // Private typedefs
151 using FullEdges = Array<FullEdge>;
152
153 // Determine a suitable tolerance for detecting that points are coplanar
154 float DetermineCoplanarDistance() const;
155
161 void GetFaceForPoint(Vec3Arg inPoint, const Faces &inFaces, Face *&outFace, float &outDistSq) const;
162
167 float GetDistanceToEdgeSq(Vec3Arg inPoint, const Face *inFace) const;
168
174 bool AssignPointToFace(int inPositionIdx, const Faces &inFaces, float inToleranceSq);
175
177 void AddPoint(Face *inFacingFace, int inIdx, float inToleranceSq, Faces &outNewFaces);
178
180 void GarbageCollectFaces();
181
183 Face * CreateFace();
184
186 Face * CreateTriangle(int inIdx1, int inIdx2, int inIdx3);
187
189 void FreeFace(Face *inFace);
190
192 void FreeFaces();
193
195 static void sLinkFace(Edge *inEdge1, Edge *inEdge2);
196
198 static void sUnlinkFace(Face *inFace);
199
202 void FindEdge(Face *inFacingFace, Vec3Arg inVertex, FullEdges &outEdges) const;
203
205 void MergeFaces(Edge *inEdge);
206
208 void MergeDegenerateFace(Face *inFace, Faces &ioAffectedFaces);
209
212 void MergeCoplanarOrConcaveFaces(Face *inFace, float inToleranceSq, Faces &ioAffectedFaces);
213
215 static void sMarkAffected(Face *inFace, Faces &ioAffectedFaces);
216
221 void RemoveInvalidEdges(Face *inFace, Faces &ioAffectedFaces);
222
226 bool RemoveTwoEdgeFace(Face *inFace, Faces &ioAffectedFaces) const;
227
228#ifdef JPH_ENABLE_ASSERTS
230 void DumpFace(const Face *inFace) const;
231
233 void DumpFaces() const;
234
236 void ValidateFace(const Face *inFace) const;
237
239 void ValidateFaces() const;
240#endif
241
242#ifdef JPH_CONVEX_BUILDER_DEBUG
244 void DrawState(bool inDrawConflictList = false) const;
245
247 void DrawWireFace(const Face *inFace, ColorArg inColor) const;
248
250 void DrawEdge(const Edge *inEdge, ColorArg inColor) const;
251#endif
252
253#ifdef JPH_CONVEX_BUILDER_DUMP_SHAPE
254 void DumpShape() const;
255#endif
256
257 const Positions & mPositions;
258 Faces mFaces;
259
260 struct Coplanar
261 {
262 int mPositionIdx;
263 float mDistanceSq;
264 };
265 using CoplanarList = Array<Coplanar>;
266
267 CoplanarList mCoplanarList;
268
269#ifdef JPH_CONVEX_BUILDER_DEBUG
270 int mIteration;
271 mutable RVec3 mOffset;
272 Vec3 mDelta;
273#endif
274};
275
#define JPH_EXPORT
Definition: Core.h:227
#define JPH_NAMESPACE_END
Definition: Core.h:367
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
#define JPH_ASSERT(...)
Definition: IssueReporting.h:33
#define JPH_OVERRIDE_NEW_DELETE
Macro to override the new and delete functions.
Definition: Memory.h:29
float Real
Definition: Real.h:27
std::vector< T, STLAllocator< T > > Array
Definition: STLAllocator.h:81
Class that holds an RGBA color with 8-bits per component.
Definition: Color.h:16
Class that holds the information of an edge.
Definition: ConvexHullBuilder.h:28
JPH_OVERRIDE_NEW_DELETE Edge(Face *inFace, int inStartIdx)
Constructor.
Definition: ConvexHullBuilder.h:33
Edge * mNextEdge
Next edge of this face.
Definition: ConvexHullBuilder.h:45
int mStartIdx
Vertex index in mPositions that indicates the start vertex of this edge.
Definition: ConvexHullBuilder.h:47
Face * mFace
Face that this edge belongs to.
Definition: ConvexHullBuilder.h:44
Edge * GetPreviousEdge()
Get the previous edge.
Definition: ConvexHullBuilder.h:36
Class that holds the information of one face.
Definition: ConvexHullBuilder.h:54
Vec3 mCentroid
Center of the face.
Definition: ConvexHullBuilder.h:75
bool IsFacing(Vec3Arg inPosition) const
Check if face inFace is facing inPosition.
Definition: ConvexHullBuilder.h:68
Vec3 mNormal
Normal of this face, length is 2 times area of face.
Definition: ConvexHullBuilder.h:74
ConflictList mConflictList
Positions associated with this edge (that are closest to this edge). The last position in the list is...
Definition: ConvexHullBuilder.h:76
A convex hull builder that tries to create hulls as accurately as possible. Used for offline processi...
Definition: ConvexHullBuilder.h:21
const Faces & GetFaces() const
Access to the created faces. Memory is owned by the convex hull builder.
Definition: ConvexHullBuilder.h:130
~ConvexHullBuilder()
Destructor.
Definition: ConvexHullBuilder.h:93
EResult
Result enum that indicates how the hull got created.
Definition: ConvexHullBuilder.h:97
Array< int > ConflictList
Definition: ConvexHullBuilder.h:50
Array< Vec3 > Positions
Definition: ConvexHullBuilder.h:86
Array< Face * > Faces
Definition: ConvexHullBuilder.h:87
Class that makes another class non-copyable. Usage: Inherit from NonCopyable.
Definition: NonCopyable.h:11
Definition: Vec3.h:16