ConvexHullBuilder.h

Go to the documentation of this file.

// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
// SPDX-License-Identifier: MIT
 
#pragma once
 
//#define JPH_CONVEX_BUILDER_DEBUG
//#define JPH_CONVEX_BUILDER_DUMP_SHAPE
 
#ifdef JPH_CONVEX_BUILDER_DEBUG
    #include <Jolt/Core/Color.h>
#endif
 
#include <Jolt/Core/StaticArray.h>
#include <Jolt/Core/NonCopyable.h>
 
JPH_NAMESPACE_BEGIN
 
class ConvexHullBuilder : public NonCopyable
{
public:
    // Forward declare
    class Face;
 
    class Edge : public NonCopyable
    {
    public:
        JPH_OVERRIDE_NEW_DELETE
 
                        Edge(Face *inFace, int inStartIdx)  : mFace(inFace), mStartIdx(inStartIdx) { }
 
        inline Edge *   GetPreviousEdge()
        {
            Edge *prev_edge = this;
            while (prev_edge->mNextEdge != this)
                prev_edge = prev_edge->mNextEdge;
            return prev_edge;
        }
 
        Face *          mFace;                              
        Edge *          mNextEdge = nullptr;                
        Edge *          mNeighbourEdge = nullptr;           
        int             mStartIdx;                          
    };
 
    using ConflictList = Array<int>;
 
    class Face : public NonCopyable
    {
    public:
        JPH_OVERRIDE_NEW_DELETE
 
                        ~Face();
 
        void            Initialize(int inIdx0, int inIdx1, int inIdx2, const Vec3 *inPositions);
 
        void            CalculateNormalAndCentroid(const Vec3 *inPositions);
 
        inline bool     IsFacing(Vec3Arg inPosition) const
        {
            JPH_ASSERT(!mRemoved);
            return mNormal.Dot(inPosition - mCentroid) > 0.0f;
        }
 
        Vec3            mNormal;                            
        Vec3            mCentroid;                          
        ConflictList    mConflictList;                      
        Edge *          mFirstEdge = nullptr;               
        float           mFurthestPointDistanceSq = 0.0f;    
        bool            mRemoved = false;                   
#ifdef JPH_CONVEX_BUILDER_DEBUG
        int             mIteration;                         
#endif
    };
 
    // Typedefs
    using Positions = Array<Vec3>;
    using Faces = Array<Face *>;
 
    explicit            ConvexHullBuilder(const Positions &inPositions);
 
                        ~ConvexHullBuilder()                { FreeFaces(); }
 
    enum class EResult
    {
        Success,                                            
        MaxVerticesReached,                                 
        TooFewPoints,                                       
        TooFewFaces,                                        
        Degenerate,                                         
    };
 
    EResult             Initialize(int inMaxVertices, float inTolerance, const char *&outError);
 
    int                 GetNumVerticesUsed() const;
 
    bool                ContainsFace(const Array<int> &inIndices) const;
 
    void                GetCenterOfMassAndVolume(Vec3 &outCenterOfMass, float &outVolume) const;
 
    void                DetermineMaxError(Face *&outFaceWithMaxError, float &outMaxError, int &outMaxErrorPositionIdx, float &outCoplanarDistance) const;
 
    const Faces &       GetFaces() const                    { return mFaces; }
 
private:
    static constexpr float cMinTriangleAreaSq = 1.0e-12f;
 
#ifdef JPH_CONVEX_BUILDER_DEBUG
    static constexpr Real cDrawScale = 10;
#endif
 
    class FullEdge
    {
    public:
        Edge *          mNeighbourEdge;                     
        int             mStartIdx;                          
        int             mEndIdx;                            
    };
 
    // Private typedefs
    using FullEdges = Array<FullEdge>;
 
    // Determine a suitable tolerance for detecting that points are coplanar
    float               DetermineCoplanarDistance() const;
 
    void                GetFaceForPoint(Vec3Arg inPoint, const Faces &inFaces, Face *&outFace, float &outDistSq) const;
 
    float               GetDistanceToEdgeSq(Vec3Arg inPoint, const Face *inFace) const;
 
    bool                AssignPointToFace(int inPositionIdx, const Faces &inFaces, float inToleranceSq);
 
    void                AddPoint(Face *inFacingFace, int inIdx, float inToleranceSq, Faces &outNewFaces);
 
    void                GarbageCollectFaces();
 
    Face *              CreateFace();
 
    Face *              CreateTriangle(int inIdx1, int inIdx2, int inIdx3);
 
    void                FreeFace(Face *inFace);
 
    void                FreeFaces();
 
    static void         sLinkFace(Edge *inEdge1, Edge *inEdge2);
 
    static void         sUnlinkFace(Face *inFace);
 
    void                FindEdge(Face *inFacingFace, Vec3Arg inVertex, FullEdges &outEdges) const;
 
    void                MergeFaces(Edge *inEdge);
 
    void                MergeDegenerateFace(Face *inFace, Faces &ioAffectedFaces);
 
    void                MergeCoplanarOrConcaveFaces(Face *inFace, float inToleranceSq, Faces &ioAffectedFaces);
 
    static void         sMarkAffected(Face *inFace, Faces &ioAffectedFaces);
 
    void                RemoveInvalidEdges(Face *inFace, Faces &ioAffectedFaces);
 
    bool                RemoveTwoEdgeFace(Face *inFace, Faces &ioAffectedFaces) const;
 
#ifdef JPH_ENABLE_ASSERTS
    void                DumpFace(const Face *inFace) const;
 
    void                DumpFaces() const;
 
    void                ValidateFace(const Face *inFace) const;
 
    void                ValidateFaces() const;
#endif
 
#ifdef JPH_CONVEX_BUILDER_DEBUG
    void                DrawState(bool inDrawConflictList = false) const;
 
    void                DrawWireFace(const Face *inFace, ColorArg inColor) const;
 
    void                DrawEdge(const Edge *inEdge, ColorArg inColor) const;
#endif
 
#ifdef JPH_CONVEX_BUILDER_DUMP_SHAPE
    void                DumpShape() const;
#endif
 
    const Positions &   mPositions;                         
    Faces               mFaces;                             
 
    struct Coplanar
    {
        int             mPositionIdx;                       
        float           mDistanceSq;                        
    };
    using CoplanarList = Array<Coplanar>;
 
    CoplanarList        mCoplanarList;                      
 
#ifdef JPH_CONVEX_BUILDER_DEBUG
    int                 mIteration;                         
    mutable RVec3       mOffset;                            
    Vec3                mDelta;                             
#endif
};
 
JPH_NAMESPACE_END