MeshSurfacePointSampling.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "MathUtil.h"
#include "VectorTypes.h"
#include "FrameTypes.h"
#include "Util/ProgressCancel.h"
 
class FProgressCancel;
 
namespace UE
{
namespace Geometry
{
 
class FDynamicMesh3;
 
// class for efficiently drawing weighted samples (when you need to draw more than a very small amount of them)
// note this is a more flexible version of the algorithm in Engine/WeightedRandomSampler.h, 
// with support for cases where some IDs cannot be sampled (e.g. when sampling triangles of non-compact meshes)
template<typename RealType>
class TWeightedSamplingAliasTable
{
public:
    GEOMETRYCORE_API bool Init(TConstArrayView<RealType> Weights, RealType SumOfValidWeights, bool bAllowInvalidWeights);
 
    TWeightedSamplingAliasTable() = default;
    TWeightedSamplingAliasTable(TConstArrayView<RealType> Weights, RealType SumOfValidWeights, bool bAllowInvalidWeights)
    {
        Init(Weights, SumOfValidWeights, bAllowInvalidWeights);
    }
    TWeightedSamplingAliasTable(TConstArrayView<RealType> Weights)
    {
        bool bHasInvalidWeight = false;
        RealType WtSum = (RealType)0;
        for (RealType Wt : Weights)
        {
            if (Wt < 0)
            {
                bHasInvalidWeight = true;
                continue;
            }
            WtSum += Wt;
        }
        Init(Weights, WtSum, bHasInvalidWeight);
    }
    
    inline int32 Num() const
    {
        return Probability.Num();
    }
 
    inline bool IsValid() const
    {
        return !Probability.IsEmpty();
    }
    
    // UniformRandom1, UniformRandom2 must be in the [0,1) range
    inline int32 Sample(RealType UniformRandom1, RealType UniformRandom2) const
    {
        checkSlow(IsValid() && UniformRandom1 < (RealType)1);
        int32 Idx = FMath::TruncToInt32(UniformRandom1 * (RealType)Probability.Num());
        return UniformRandom2 < Probability[Idx] ? Idx : Alias[Idx];
    }
 
private:
    // Table of probability that you should keep a given index chosen by unweighted random sampling (can be MaxReal if should always pick the index)
    TArray<RealType> Probability;
    // Table indicating the alternative index you should choose, if you don't keep the initial index
    TArray<int32> Alias;
};
 
// Class to help draw uniform-random surface samples from a (possibly non-compact) triangle mesh. 
// TMeshType must implement: IsTriangle, MaxTriangleID, and GetTriVertices. RealType must be float or double.
template<typename TMeshType, typename RealType>
class TMeshUniformSurfaceSampling
{
public:
    
    TMeshUniformSurfaceSampling() = default;
    TMeshUniformSurfaceSampling(const TMeshType& Mesh)
    {
        Init(Mesh);
    }
    
    // @return true on successful initialization
    bool Init(const TMeshType& Mesh)
    {
        const int32 MaxTID = Mesh.MaxTriangleID();
        TArray<RealType> Wts;
        RealType WtSum = (RealType)0;
        bool bHasInvalidWeights = false;
        for (int32 TID = 0; TID < MaxTID; ++TID)
        {
            if (Mesh.IsTriangle(TID))
            {
                TVector<RealType> A, B, C;
                Mesh.GetTriVertices(TID, A, B, C);
                RealType Area = (RealType)VectorUtil::Area(A, B, C);
                WtSum += Area;
                Wts.Add(Area);
            }
            else
            {
                bHasInvalidWeights = true;
                Wts.Add(-1);
            }
        }
        return AliasTable.Init(Wts, WtSum, bHasInvalidWeights);
    }
 
    // @return true if we can generate samples (e.g., if the class has been initialized with a non-empty mesh)
    bool IsValid() const
    {
        return AliasTable.IsValid();
    }
 
    int32 DrawTriangleIDSample(RealType UniformRandom1, RealType UniformRandom2) const
    {
        return AliasTable.Sample(UniformRandom1, UniformRandom2);
    }
    
private:
    TWeightedSamplingAliasTable<RealType> AliasTable;
};
 
using FMeshUniformSurfaceSampling = TMeshUniformSurfaceSampling<FDynamicMesh3, double>;
using FWeightedSamplingAliasTabled = TWeightedSamplingAliasTable<double>;
using FWeightedSamplingAliasTablef = TWeightedSamplingAliasTable<float>;
 
 
class FMeshSurfacePointSampling
{
public:
    // 
    // Basic sampling parameters
    //
 
    double SampleRadius = 10.0;
 
    uint32 MaxSamples = TNumericLimits<uint32>::Max();
    
    double SubSampleDensity = 10.0;
 
    int32 RandomSeed = 0;
 
    int32 MaxSubSamplePoints = 50000000;
 
    int32 SamplingMethodVersion = INDEX_NONE;
 
    //
    // Parameters for non-uniform / variable-radius sampling. 
    // Disabled if MaxSampleRadius <= SampleRadius
    //
 
    double MaxSampleRadius = 0.0;
 
    enum class ESizeDistribution
    {
        Uniform = 0,
        Smaller = 1,
        Larger = 2
    };
    ESizeDistribution SizeDistribution = ESizeDistribution::Uniform;
 
    double SizeDistributionPower = 2.0;
 
 
    bool bUseVertexWeights = false;
 
    TArray<double> VertexWeights;
 
    enum class EInterpretWeightMode
    {
        RadiusInterp = 0,
        RadiusInterpWithFill = 1,
        WeightedRandom = 2
    };
    EInterpretWeightMode InterpretWeightMode = EInterpretWeightMode::RadiusInterpWithFill;
 
    bool bInvertWeights = false;
 
    bool bComputeBarycentrics = false;
 
    //
    // TODO: when MaxSamples is set, it would be useful to be able to use Weight to modulate
    // positional distribution instead of radius, (or both!)
    //
 
public:
    //
    // Outputs
    //
 
    FGeometryResult Result;
 
    TArray<FFrame3d> Samples;
 
    TArray<double> Radii;
 
    TArray<int32> TriangleIDs;
 
    TArray<FVector3d> BarycentricCoords;
 
public:
 
    GEOMETRYCORE_API void ComputePoissonSampling(const FDynamicMesh3& Mesh, FProgressCancel* Progress = nullptr);
 
 
    // ability to incrementally increase existing sample sizes to more tightly pack them?
    // ability to iteratively redistribute samples to improve uniformity (ie potential field / mass-spring type method, point smoothing, ?)
};
 
 
 
 
 
 
} // end namespace UE::Geometry
} // end namespace UE