ConvexHull3.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Array.h"
#include "Containers/ArrayView.h"
#include "Containers/Set.h"
#include "CoreMinimal.h"
#include "HalfspaceTypes.h"
#include "IndexTypes.h"
#include "LineTypes.h"
#include "Math/UnrealMathSSE.h"
#include "Math/Vector.h"
#include "MathUtil.h"
#include "PlaneTypes.h"
#include "Templates/Function.h"
#include "Templates/UnrealTemplate.h"
#include "Util/ProgressCancel.h"
#include "VectorTypes.h"
 
class FProgressCancel;
 
namespace UE {
namespace Geometry {
 
using namespace UE::Math;
 
template<typename RealType>
struct TExtremePoints3
{
    int Dimension = 0;
    int Extreme[4]{ 0, 0, 0, 0 };
 
    // Coordinate frame spanned by input points
    TVector<RealType> Origin{ 0,0,0 };
    TVector<RealType> Basis[3]{ {0,0,0}, {0,0,0}, {0,0,0} };
 
    TExtremePoints3(int32 NumPoints, TFunctionRef<TVector<RealType>(int32)> GetPointFunc, TFunctionRef<bool(int32)> FilterFunc = [](int32 Idx) {return true; }, RealType Epsilon = TMathUtil<RealType>::Epsilon)
    {
        Init(NumPoints, GetPointFunc, FilterFunc, Epsilon);
    }
 
private:
    GEOMETRYCORE_API void Init(int32 NumPoints, TFunctionRef<TVector<RealType>(int32)> GetPointFunc, TFunctionRef<bool(int32)> FilterFunc, RealType Epsilon = TMathUtil<RealType>::Epsilon);
};
 
template<typename RealType>
struct TConvexHullSimplificationSettings
{
    RealType DegenerateEdgeTolerance = (RealType)0;
 
    int32 MaxHullVertices = -1;
 
    RealType SkipAtHullDistanceAbsolute = -TMathUtil<RealType>::MaxReal;
    RealType SkipAtHullDistanceAsFraction = -TMathUtil<RealType>::MaxReal;
};
 
template<typename RealType>
class TConvexHull3
{
public:
 
    bool bSaveTriangleNeighbors = false;
 
    // Settings controlling whether and how to generate a simpler hull
    TConvexHullSimplificationSettings<RealType> SimplificationSettings;
 
    // Helper to compute the a convex hull and return only its volume. If the hull cannot be constructed, a volume of 0 will be returned.
    GEOMETRYCORE_API static double ComputeVolume(const TArrayView<const TVector<RealType>> Vertices);
 
    GEOMETRYCORE_API bool Solve(int32 NumPoints, TFunctionRef<TVector<RealType>(int32)> GetPointFunc, TFunctionRef<bool(int32)> FilterFunc);
    bool Solve(int32 NumPoints, TFunctionRef<TVector<RealType>(int32)> GetPointFunc)
    {
        return Solve(NumPoints, GetPointFunc, [](int32 Idx) {return true;});
    }
 
    template<typename VectorType>
    bool Solve(TArrayView<const VectorType> Points, TFunctionRef<bool(int32)> FilterFunc)
    {
        return Solve(Points.Num(), [&Points](int32 Idx)
            {
                return Points[Idx];
            }, FilterFunc);
    }
 
    // default FilterFunc version of the above Solve(); workaround for clang bug https://bugs.llvm.org/show_bug.cgi?id=25333
    template<typename VectorType>
    bool Solve(TArrayView<const VectorType> Points)
    {
        return Solve(Points.Num(), [&Points](int32 Idx)
            {
                return Points[Idx];
            }, [](int32 Idx) {return true;});
    }
 
    bool IsSolutionAvailable() const
    {
        return Dimension == 3;
    }
 
    void GetTriangles(TFunctionRef<void(FIndex3i)> TriangleFunc)
    {
        for (FIndex3i Triangle : Hull)
        {
            TriangleFunc(Triangle);
        }
    }
 
    TArray<FIndex3i> const& GetTriangles() const
    {
        return Hull;
    }
 
    GEOMETRYCORE_API void GetFaces(TFunctionRef<void(TArray<int32>&, TVector<RealType>)> PolygonFunc, TFunctionRef<TVector<RealType>(int32)> GetPointFunc) const;
 
    GEOMETRYCORE_API void GetSimplifiedFaces(TFunctionRef<void(TArray<int32>&, TVector<RealType>)> PolygonFunc, TFunctionRef<TVector<RealType>(int32)> GetPointFunc,
        RealType FaceAngleToleranceInDegrees = (RealType)1.0, RealType PlaneDistanceTolerance = (RealType)1.0) const;
 
    // Polygon face array type: A nested array with inline allocator per face, optimizing for the case where most faces have less than 8 vertices
    using FPolygonFace = TArray<int32, TInlineAllocator<8>>;
    GEOMETRYCORE_API void GetSimplifiedFaces(TArray<FPolygonFace>& OutPolygons, TFunctionRef<TVector<RealType>(int32)> GetPointFunc,
        RealType FaceAngleToleranceInDegrees = (RealType)1.0, RealType PlaneDistanceTolerance = (RealType)1.0, TArray<TVector<RealType>>* OutPolygonNormals = nullptr) const;
 
    TArray<FIndex3i> const& GetTriangleNeighbors() const
    {
        ensure(bSaveTriangleNeighbors && Hull.Num() == HullNeighbors.Num());
        return HullNeighbors;
    }
 
    TArray<FIndex3i>&& MoveTriangles()
    {
        return MoveTemp(Hull);
    }
 
    template<typename VectorType>
    TArray<THalfspace3<RealType>> GetAsHalfspaces(TArrayView<const VectorType> Points) const
    {
        TArray<THalfspace3<RealType>> Halfspaces;
        for (FIndex3i Tri : Hull)
        {
            THalfspace3<RealType> TriHalfspace(Points[Tri.A], Points[Tri.B], Points[Tri.C]);
            Halfspaces.Add(TriHalfspace);
        }
        return Halfspaces;
    }
 
    template<typename VectorType>
    TArray<THalfspace3<RealType>> GetAsHalfspaces(TFunctionRef<VectorType(int32)> GetPointFunc) const
    {
        TArray<THalfspace3<RealType>> Halfspaces;
        for (FIndex3i Tri : Hull)
        {
            THalfspace3<RealType> TriHalfspace(GetPointFunc(Tri.A), GetPointFunc(Tri.B), GetPointFunc(Tri.C));
            Halfspaces.Add(TriHalfspace);
        }
        return Halfspaces;
    }
 
    void Empty()
    {
        Dimension = 0;
        NumHullPoints = 0;
        Hull.Empty();
    }
 
    inline int GetDimension() const
    {
        return Dimension;
    }
    inline TLine3<RealType> const& GetLine() const
    {
        return Line;
    }
    inline TPlane3<RealType> const& GetPlane() const
    {
        return Plane;
    }
 
    int GetNumHullPoints() const
    {
        return NumHullPoints;
    }
 
 
    FProgressCancel* Progress = nullptr;
 
    // Useful helper for walking the border of a convex region, or of a QHull horizon. Will also work for extracting a group boundary for any closed triangle mesh.
    // Note: Assumes TriangleNeighbors are listed such that the first neighbor is the tri across from the (Tri.A, Tri.B) edge
    static void WalkBorder(const TArray<FIndex3i>& Triangles, const TArray<FIndex3i>& TriangleNeighbors, TFunctionRef<bool(int32)> InGroupFunc, int32 StartIdx, TArray<int32>& OutBorderVertexIndices);
 
protected:
 
    int32 Dimension;
    TLine3<RealType> Line;
    TPlane3<RealType> Plane;
 
    int NumHullPoints = 0;
    TArray<FIndex3i> Hull;
    // We can optionally also return the hull triangle adjacencies
    TArray<FIndex3i> HullNeighbors;
    
};
 
typedef TExtremePoints3<float> FExtremePoints3f;
typedef TExtremePoints3<double> FExtremePoints3d;
typedef TConvexHull3<float> FConvexHull3f;
typedef TConvexHull3<double> FConvexHull3d;
 
 
} // end namespace UE::Geometry
} // end namespace UE