MeshSpatialSort.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "MathUtil.h"
#include "MeshQueries.h"
#include "Spatial/FastWinding.h"
 
namespace UE
{
namespace Geometry
{
 
 
template <class TriangleMeshType>
class TMeshSpatialSort
{
public:
 
    TArrayView<const TriangleMeshType> InputMeshes;
 
    TArray<FAxisAlignedBox3d> MeshBounds;
 
    enum class ENestingMethod
    {
        InLargestParent, // meshes nest flatly in the largest mesh that contains them (simplest structure, fastest to compute, will never have nests inside nests)
        InSmallestParent, // meshes nest in the smallest mesh that contains them, capturing nests inside nests
    };
 
    ENestingMethod NestingMethod = ENestingMethod::InLargestParent;
 
    bool bOnlyNestNegativeVolumes = false;
 
    bool bOnlyParentPostiveVolumes = true;
 
    bool bOnlyCheckSingleVertexForNesting = true;
 
 
 
    struct FMeshNesting
    {
        int OuterIndex; // index of the outer (positive volume) shell
        int ParentIndex = -1; // only used if NestingMethod is InSmallestParent. Index of the mesh that contains the outer index mesh, or -1 if there is no such mesh.
        TArray<int> InnerIndices; // indices of all meshes contained inside outer shell (unless they are recursively nested inside a child mesh)
    };
 
    TArray<FMeshNesting> Nests;
 
    TArray<int> SkippedMeshIndices;
 
    TMeshSpatialSort() {}
 
    TMeshSpatialSort(TArrayView<const TriangleMeshType> InputMeshes, TArrayView<const FAxisAlignedBox3d> MeshBoundsIn = TArrayView<const FAxisAlignedBox3d>())
        : InputMeshes(InputMeshes)
    {
        if (MeshBoundsIn.Num() == InputMeshes.Num())
        {
            MeshBounds = MeshBoundsIn;
        }
        else
        {
            InitBounds();
        }
    }
 
    void Compute()
    {
        if (!ensure(MeshBounds.Num() == InputMeshes.Num()))
        {
            InitBounds();
        }
 
        FAxisAlignedBox3d CombinedBounds;
        for (const FAxisAlignedBox3d& Bounds : MeshBounds)
        {
            CombinedBounds.Contain(Bounds);
        }
 
        Nests.Empty();
 
        int32 N = InputMeshes.Num();
        TArray<int> MeshIndices;
        MeshIndices.SetNum(N);
        for (int i = 0; i < N; i++)
        {
            MeshIndices[i] = i;
        }
 
        // precomputed useful stats on input meshes
        struct FMeshInfo
        {
            double Volume;
            bool bPositiveVolume;
        };
        TArray<FMeshInfo> Info;
        Info.SetNum(N);
        double DimScaleFactor = 1.0 / (CombinedBounds.MaxDim() + KINDA_SMALL_NUMBER);
        for (int i = 0; i < N; i++)
        {
            double SignedVolume = TMeshQueries<TriangleMeshType>::GetVolumeNonWatertight(InputMeshes[i], DimScaleFactor);
            Info[i].bPositiveVolume = SignedVolume >= 0;
            Info[i].Volume = FMathd::Abs(SignedVolume);
        }
 
        MeshIndices.Sort([&Info](int Ind1, int Ind2)
            {
                return Info[Ind1].Volume > Info[Ind2].Volume;
            }
        );
 
        TArray<int> Parent;
        Parent.Init(-1, N);
 
        // From largest mesh to smallest, greedily assign parents where possible
        // (If not nesting in largest: 
        //   If a mesh already has a parent, but a smaller containing parent is found, switch to the new parent)
        for (int ParentCand = 0; ParentCand + 1 < N; ParentCand++)
        {
            int PIdx = MeshIndices[ParentCand];
            const FMeshInfo& PInfo = Info[PIdx];
            const TriangleMeshType& PMesh = InputMeshes[PIdx];
            if (NestingMethod == ENestingMethod::InLargestParent && Parent[ParentCand] != -1)
            {
                continue; // mesh was already contained in a larger mesh
            }
 
            if (!PInfo.bPositiveVolume && NestingMethod != ENestingMethod::InSmallestParent && bOnlyParentPostiveVolumes)
            {
                // negative volume meshes can't be an 'outer shell,' so we can skip unless we're looking for nests-in-nests
                continue;
            }
 
            double WindingTestSign = PInfo.bPositiveVolume ? 1 : -1;
            TMeshAABBTree3<TriangleMeshType> Spatial(&InputMeshes[PIdx]);
            TFastWindingTree<TriangleMeshType> Winding(&Spatial);
            for (int ChildCand = ParentCand + 1; ChildCand < N; ChildCand++)
            {
                int CIdx = MeshIndices[ChildCand];
                const FMeshInfo& CInfo = Info[CIdx];
                const TriangleMeshType& CMesh = InputMeshes[CIdx];
                if (CMesh.VertexCount() == 0)
                {
                    continue;
                }
                if (NestingMethod == ENestingMethod::InLargestParent)
                {
                    // InLargestParent nesting can't have recursive nests or reassign to smaller parents, so we can skip some tests
                    if ((bOnlyNestNegativeVolumes && CInfo.bPositiveVolume) || Parent[ChildCand] != -1)
                    {
                        continue;
                    }
                }
                if (bOnlyCheckSingleVertexForNesting)
                {
                    FVector3d Vert;
                    
                    for (int VID = 0; VID < CMesh.MaxVertexID(); VID++)
                    {
                        if (CMesh.IsVertex(VID))
                        {
                            Vert = CMesh.GetVertex(VID);
                            break;
                        }
                    }
 
                    double WindingNumber = Winding.FastWindingNumber(Vert);
                    if (WindingNumber*WindingTestSign > .5)
                    {
                        Parent[ChildCand] = ParentCand;
                    }
                }
                else
                {
                    bool bHasOutsideSample = false;
                    for (int VID = 0; VID < CMesh.MaxVertexID(); VID++)
                    {
                        if (CMesh.IsVertex(VID))
                        {
                            double WindingNumber = Winding.FastWindingNumber(CMesh.GetVertex(VID));
                            if (WindingNumber * WindingTestSign < .5)
                            {
                                bHasOutsideSample = true;
                                break;
                            }
                        }
                    }
                    if (!bHasOutsideSample)
                    {
                        Parent[ChildCand] = ParentCand;
                    }
                }
            }
        }
 
        // Build nests from parent relationship
        TArray<bool> Taken;
        Taken.SetNumZeroed(N);
        for (int NestCand = 0; NestCand < N; NestCand++)
        {
            int NIdx = MeshIndices[NestCand];
            if (Taken[NestCand])
            {
                continue;
            }
            if (bOnlyParentPostiveVolumes && !Info[NIdx].bPositiveVolume)
            {
                SkippedMeshIndices.Add(NIdx);
                continue;
            }
            FMeshNesting& Nest = Nests.Emplace_GetRef();
            Nest.OuterIndex = NIdx;
 
            if (NestingMethod == ENestingMethod::InSmallestParent)
            {
                int ParentCand = Parent[NestCand];
                if (ParentCand > -1)
                {
                    Nest.ParentIndex = MeshIndices[ParentCand];
                }
            }
            for (int HoleCand = NestCand + 1; HoleCand < N; HoleCand++)
            {
                int MIdx = MeshIndices[HoleCand];
                if (Parent[HoleCand] == NestCand && (!Info[MIdx].bPositiveVolume || !bOnlyNestNegativeVolumes))
                {
                    Nest.InnerIndices.Add(MIdx);
                    Taken[HoleCand] = true;
                }
            }
        }
    }
 
private:
 
    void InitBounds()
    {
        MeshBounds.Reset();
        MeshBounds.Reserve(InputMeshes.Num());
        for (const TriangleMeshType& Mesh : InputMeshes)
        {
            MeshBounds.Add(TMeshQueries<TriangleMeshType>::GetBounds(Mesh));
        }
    }
};
 
 
} // end namespace UE::Geometry
} // end namespace UE