DynamicMeshOverlay.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 "DynamicMesh/DynamicMesh3.h"
#include "GeometryTypes.h"
#include "IndexTypes.h"
#include "InfoTypes.h"
#include "IntVectorTypes.h"
#include "Math/UnrealMathSSE.h"
#include "Math/Vector.h"
#include "Math/Vector2D.h"
#include "Math/Vector4.h"
#include "Misc/AssertionMacros.h"
#include "Templates/Function.h"
#include "Templates/UnrealTemplate.h"
#include "Util/CompactMaps.h"
#include "Util/DynamicVector.h"
#include "Util/RefCountVector.h"
#include "Util/SmallListSet.h"
#include "VectorTypes.h"
 
class FArchive;
namespace DynamicMeshInfo { struct FEdgeCollapseInfo; }
namespace DynamicMeshInfo { struct FEdgeFlipInfo; }
namespace DynamicMeshInfo { struct FEdgeSplitInfo; }
namespace DynamicMeshInfo { struct FMergeEdgesInfo; }
namespace DynamicMeshInfo { struct FPokeTriangleInfo; }
namespace DynamicMeshInfo { struct FVertexSplitInfo; }
 
namespace UE
{
namespace Geometry
{
 
class FDynamicMesh3;
 
template<typename RealType, int ElementSize>
class TDynamicMeshOverlay
{
 
protected:
    FDynamicMesh3* ParentMesh;
 
    FRefCountVector ElementsRefCounts;
    TDynamicVector<RealType> Elements;
    TDynamicVector<int> ParentVertices;
 
    TDynamicVector<int> ElementTriangles;
 
    friend class FDynamicMesh3;
    friend class FDynamicMeshAttributeSet;
 
public:
    TDynamicMeshOverlay()
    {
        ParentMesh = nullptr;
    }
 
    TDynamicMeshOverlay(FDynamicMesh3* ParentMeshIn)
    {
        ParentMesh = ParentMeshIn;
    }
private:
    void Reparent(FDynamicMesh3* ParentMeshIn)
    {
        ParentMesh = ParentMeshIn;
    }
public:
    const FDynamicMesh3* GetParentMesh() const { return ParentMesh; }
    FDynamicMesh3* GetParentMesh() { return ParentMesh; }
 
    void Copy(const TDynamicMeshOverlay<RealType,ElementSize>& Copy)
    {
        ElementsRefCounts = FRefCountVector(Copy.ElementsRefCounts);
        Elements = Copy.Elements;
        ParentVertices = Copy.ParentVertices;
        ElementTriangles = Copy.ElementTriangles;
    }
 
    void CompactCopy(const FCompactMaps& CompactMaps, const TDynamicMeshOverlay<RealType, ElementSize>& Copy)
    {
        ClearElements();
 
        // map of element IDs
        TArray<int> MapE; MapE.SetNumUninitialized(Copy.MaxElementID());
 
        // copy elements across
        RealType Data[ElementSize];
        for (int EID = 0; EID < Copy.MaxElementID(); EID++)
        {
            if (Copy.IsElement(EID))
            {
                Copy.GetElement(EID, Data);
                MapE[EID] = AppendElement(Data);
            }
            else
            {
                MapE[EID] = -1;
            }
        }
 
        // copy triangles across
        check(CompactMaps.NumTriangleMappings() == Copy.GetParentMesh()->MaxTriangleID()); // must have valid triangle map
        for (int FromTID : Copy.GetParentMesh()->TriangleIndicesItr())
        {
            if (!Copy.IsSetTriangle(FromTID))
            {
                continue;
            }
            const int ToTID = CompactMaps.GetTriangleMapping(FromTID);
            FIndex3i FromTriElements = Copy.GetTriangle(FromTID);
            SetTriangle(ToTID, FIndex3i(MapE[FromTriElements.A], MapE[FromTriElements.B], MapE[FromTriElements.C]));
        }
    }
 
    void CompactInPlace(const FCompactMaps& CompactMaps)
    {
        int iLastE = MaxElementID() - 1, iCurE = 0;
        while (iLastE >= 0 && ElementsRefCounts.IsValidUnsafe(iLastE) == false)
        {
            iLastE--;
        }
        while (iCurE < iLastE && ElementsRefCounts.IsValidUnsafe(iCurE))
        {
            iCurE++;
        }
 
        // make a map to track element index changes, to use to update element triangles later
        // TODO: it may be faster to not construct this and to do the remapping per element as we go (by iterating the one ring of each parent vertex for each element)
        TArray<int> MapE; MapE.SetNumUninitialized(MaxElementID());
        for (int ID = 0; ID < MapE.Num(); ID++)
        {
            // mapping is 1:1 by default; sparsely re-mapped below
            MapE[ID] = ID;
            // remap all parents
            if (ParentVertices[ID] >= 0)
            {
                ParentVertices[ID] = CompactMaps.GetVertexMapping(ParentVertices[ID]);
            }
        }
 
        TDynamicVector<unsigned short>& ERef = ElementsRefCounts.GetRawRefCountsUnsafe();
        RealType Data[ElementSize];
        while (iCurE < iLastE)
        {
            // remap the element data
            GetElement(iLastE, Data);
            SetElement(iCurE, Data);
            ParentVertices[iCurE] = ParentVertices[iLastE];
            ERef[iCurE] = ERef[iLastE];
            ERef[iLastE] = FRefCountVector::INVALID_REF_COUNT;
            MapE[iLastE] = iCurE;
 
            // move cur forward one, last back one, and  then search for next valid
            iLastE--; iCurE++;
            while (iLastE >= 0 && ElementsRefCounts.IsValidUnsafe(iLastE) == false)
            {
                iLastE--;
            }
            while (iCurE < iLastE && ElementsRefCounts.IsValidUnsafe(iCurE))
            {
                iCurE++;
            }
        }
        ElementsRefCounts.Trim(ElementCount());
        Elements.Resize(ElementCount() * ElementSize);
        ParentVertices.Resize(ElementCount());
 
        // Remap and compact triangle element indices.
        int32 MaxNewTID = -1;
        for (int TID = 0, OldMaxTID = ElementTriangles.Num() / 3; TID < OldMaxTID; TID++)
        {
            const int32 OldStart = TID * 3;
            const int32 NewTID = CompactMaps.GetTriangleMapping(TID);
            if (NewTID == IndexConstants::InvalidID)
            {
                // skip if there's no mapping
                continue;
            }
 
            MaxNewTID = FMath::Max(NewTID, MaxNewTID);
 
            const int32 NewStart = NewTID * 3;
            if (ElementTriangles[OldStart] == IndexConstants::InvalidID)
            {
                // triangle was not set; copy back InvalidID
                for (int SubIdx = 0; SubIdx < 3; SubIdx++)
                {
                    ElementTriangles[NewStart + SubIdx] = IndexConstants::InvalidID;
                }
            }
            else
            {
                for (int SubIdx = 0; SubIdx < 3; SubIdx++)
                {
                    ElementTriangles[NewStart + SubIdx] = MapE[ElementTriangles[OldStart + SubIdx]];
                }
            }
        }
        // ElementTriangles should never grow during a compaction, so just resizing is ok
        // (i.e., we shouldn't need to set InvalidID on any added triangles)
        checkSlow(ElementTriangles.Num() >= (MaxNewTID + 1) * 3);
        ElementTriangles.Resize((MaxNewTID + 1) * 3);
 
        checkSlow(IsCompact());
    }
 
    void Append(const TDynamicMeshOverlay& ToAppend, const FDynamicMesh3::FAppendInfo& AppendInfo)
    {
        // We expect to be appending s.t. the intial ElementTriangles map to the pre-append triangles
        if (!ensure(ElementTriangles.Num() == AppendInfo.TriangleOffset * 3))
        {
            ElementTriangles.SetNum(AppendInfo.TriangleOffset * 3);
        }
        check(ToAppend.ElementTriangles.Num() == AppendInfo.NumTriangle * 3);
 
        int32 ElementIDOffset = ElementsRefCounts.GetMaxIndex();
        int32 ElementTrianglesOffset = ElementTriangles.Num();
        ElementTriangles.Add(ToAppend.ElementTriangles);
        for (int32 Idx = ElementTrianglesOffset, N = ElementTriangles.Num(); Idx < N; ++Idx)
        {
            int32& ElID = ElementTriangles[Idx];
            if (ElID != IndexConstants::InvalidID)
            {
                ElID += ElementIDOffset;
            }
        }
 
        checkSlow(ElementIDOffset == ParentVertices.Num()); // ParentVertices must be 1:1 with Element IDs
        ParentVertices.Add(ToAppend.ParentVertices);
        for (int32 Idx = 0; Idx < ToAppend.ParentVertices.Num(); ++Idx)
        {
            int32& Parent = ParentVertices[Idx + ElementIDOffset];
            if (Parent != IndexConstants::InvalidID)
            {
                Parent += AppendInfo.VertexOffset;
            }
        }
        ElementsRefCounts.Append(ToAppend.ElementsRefCounts);
        Elements.Add(ToAppend.Elements);
    }
    void AppendDefaulted(const FDynamicMesh3::FAppendInfo& AppendInfo)
    {
        // Note: ElementRefCounts, Elements and ParentVertices remain unchanged, since the new triangles are unset
        checkSlow(ElementTriangles.Num() == AppendInfo.TriangleOffset * 3);
        ElementTriangles.Resize(3 * (AppendInfo.TriangleOffset + AppendInfo.NumTriangle), IndexConstants::InvalidID);
    }
 
    void ClearElements();
 
    template <typename EnumerableIntType>
    void ClearElements(const EnumerableIntType& Triangles)
    {
        for (int32 TriID : Triangles)
        {
            UnsetTriangle(TriID);
        }
    }
 
    int ElementCount() const { return (int)ElementsRefCounts.GetCount(); }
    int MaxElementID() const { return (int)ElementsRefCounts.GetMaxIndex(); }
    inline bool IsElement(int vID) const { return ElementsRefCounts.IsValid(vID); }
 
    bool IsCompact() const { return ElementsRefCounts.IsDense(); }
 
 
    typedef typename FRefCountVector::IndexEnumerable element_iterator;
 
    element_iterator ElementIndicesItr() const { return ElementsRefCounts.Indices(); }
 
 
    int AppendElement(RealType ConstantValue);
    int AppendElement(const RealType* Value);
 
    void SetParentVertex(int ElementIndex, int ParentVertexIndex)
    {
        ParentVertices[ElementIndex] = ParentVertexIndex;
    }
 
    void InitializeTriangles(int MaxTriangleID);
 
    EMeshResult SetTriangle(int TriangleID, const FIndex3i& TriElements, bool bAllowElementFreeing = true);
 
    void FreeUnusedElements(const TSet<int>* ElementsToCheck = nullptr);
 
    void UnsetTriangle(int TriangleID, bool bAllowElementFreeing = true);
 
    bool IsSetTriangle(int TID) const
    {
        bool bIsSet = ElementTriangles[3 * TID] >= 0;
        // we require that triangle elements either be all set or all unset
        checkSlow(ElementTriangles[3 * TID + 1] >= 0 == bIsSet);
        checkSlow(ElementTriangles[3 * TID + 2] >= 0 == bIsSet);
        return bIsSet;
    }
 
 
    void CreateFromPredicate(TFunctionRef<bool(int ParentVertexIdx, int TriIDA, int TriIDB)> TrisCanShareVertexPredicate, RealType InitElementValue);
 
    void CreatePerVertex(RealType InitElementValue);
 
    void SplitVerticesWithPredicate(TFunctionRef<bool(int ElementIdx, int TriID)> ShouldSplitOutVertex, TFunctionRef<void(int ElementIdx, int TriID, RealType* FillVect)> GetNewElementValue);
 
    bool MergeElement(int SourceElementID, int TargetElementID);
 
    int SplitElement(int ElementID, const TArrayView<const int>& TrianglesToUpdate);
 
    int SplitElementWithNewParent(int ElementID, int SplitParentVertexID, const TArrayView<const int>& TrianglesToUpdate);
 
    void SplitBowtiesAtVertex(int32 Vid, TArray<int32>* NewElementIDs = nullptr);
 
    void SplitBowties(bool bParallel = true);
 
 
    //
    // Support for inserting element at specific ID. This is a bit tricky
    // because we likely will need to update the free list in the RefCountVector, which
    // can be expensive. If you are going to do many inserts (eg inside a loop), wrap in
    // BeginUnsafe / EndUnsafe calls, and pass bUnsafe = true to the InsertElement() calls,
    // to the defer free list rebuild until you are done.
    //
 
    void BeginUnsafeElementsInsert()
    {
        // do nothing...
    }
 
    void EndUnsafeElementsInsert()
    {
        ElementsRefCounts.RebuildFreeList();
    }
 
    EMeshResult InsertElement(int ElementID, const RealType* Value, bool bUnsafe = false);
 
 
    //
    // Accessors/Queries
    //  
 
 
    inline void GetElement(int ElementID, RealType* Data) const
    {
        int k = ElementID * ElementSize;
        for (int i = 0; i < ElementSize; ++i) 
        {
            Data[i] = Elements[k + i];
        }
    }
 
    template<typename AsType>
    void GetElement(int ElementID, AsType& Data) const
    {
        int k = ElementID * ElementSize;
        for (int i = 0; i < ElementSize; ++i) 
        {
            Data[i] = Elements[k + i];
        }
    }
    
    template<typename AsType>
    inline void GetElementAtVertex(int TriangleID, int VertexID, AsType& Data) const
    {
        int ElementID = GetElementIDAtVertex(TriangleID, VertexID);
        
        checkSlow(ElementID != IndexConstants::InvalidID);
        if (ElementID != IndexConstants::InvalidID) 
        {
            GetElement(ElementID, Data);
        }
    }   
 
    inline int GetParentVertex(int ElementID) const
    {
        return ParentVertices[ElementID];
    }
 
 
    inline FIndex3i GetTriangle(int TriangleID) const 
    {
        int i = 3 * TriangleID;
        return FIndex3i(ElementTriangles[i], ElementTriangles[i + 1], ElementTriangles[i + 2]);
    }
 
    inline bool GetTriangleIfValid(int TriangleID, FIndex3i& TriangleOut) const 
    {
        int i = 3 * TriangleID;
        int a = ElementTriangles[i];
        if ( a >= 0 )
        {
            TriangleOut = FIndex3i(a, ElementTriangles[i+1], ElementTriangles[i+2]);
            checkSlow(TriangleOut.B >= 0 && TriangleOut.C >= 0);
            return true;
        }
        return false;
    }
 
    inline void SetElement(int ElementID, const RealType* Data)
    {
        int k = ElementID * ElementSize;
        for (int i = 0; i < ElementSize; ++i)
        {
            Elements[k + i] = Data[i];
        }
    }
 
    template<typename AsType>
    void SetElement(int ElementID, const AsType& Data)
    {
        int k = ElementID * ElementSize;
        for (int i = 0; i < ElementSize; ++i)
        {
            Elements[k + i] = Data[i];
        }
    }
 
    inline bool TriangleHasElement(int TriangleID, int ElementID) const
    {
        int i = 3 * TriangleID;
        return (ElementTriangles[i] == ElementID || ElementTriangles[i+1] == ElementID || ElementTriangles[i+2] == ElementID);
    }
 
 
    bool IsSeamEdge(int EdgeID, bool* bIsNonIntersectingOut = nullptr) const;
    bool IsSeamEndEdge(int EdgeID) const;
    bool IsSeamVertex(int VertexID, bool bBoundaryIsSeam = true) const;
    bool IsSeamIntersectionVertex(int32 VertexID) const;
 
    bool IsBowtieInOverlay(int32 VertexID) const;
 
    bool AreTrianglesConnected(int TriangleID0, int TriangleID1) const;
 
    void GetVertexElements(int VertexID, TArray<int>& OutElements) const;
    int CountVertexElements(int VertexID, bool bBruteForce = false) const;
 
    void GetElementTriangles(int ElementID, TArray<int>& OutTriangles) const;
 
    int GetElementIDAtVertex(int TriangleID, int VertexID) const;
 
    bool HasInteriorSeamEdges() const;
 
    template<typename AsType>
    void GetTriBaryInterpolate(int32 TriangleID, const AsType* BaryCoords, AsType* DataOut) const
    {
        int32 TriIndex = 3 * TriangleID;
        int32 ElemIndex0 = ElementTriangles[TriIndex] * ElementSize;
        int32 ElemIndex1 = ElementTriangles[TriIndex+1] * ElementSize;
        int32 ElemIndex2 = ElementTriangles[TriIndex+2] * ElementSize;
        const AsType Bary0 = (AsType)BaryCoords[0], Bary1 = (AsType)BaryCoords[1], Bary2 = (AsType)BaryCoords[2];
        for (int32 i = 0; i < ElementSize; ++i)
        {
            DataOut[i] = Bary0*(AsType)Elements[ElemIndex0+i] + Bary1*(AsType)Elements[ElemIndex1+i] + Bary2*(AsType)Elements[ElemIndex2+i];
        }
    }
 
    bool CheckValidity(bool bAllowNonManifoldVertices = true, EValidityCheckFailMode FailMode = EValidityCheckFailMode::Check) const;
 
    bool IsSameAs(const TDynamicMeshOverlay<RealType, ElementSize>& Other, bool bIgnoreDataLayout) const;
 
    friend FArchive& operator<<(FArchive& Ar, TDynamicMeshOverlay<RealType,ElementSize>& Overlay)
    {
        Overlay.Serialize(Ar, nullptr, false);
        return Ar;
    }
 
    void Serialize(FArchive& Ar, const FCompactMaps* CompactMaps, bool bUseCompression);
 
    SIZE_T GetByteCount() const
    {
        return ElementsRefCounts.GetByteCount() + Elements.GetByteCount() + ParentVertices.GetByteCount() + ElementTriangles.GetByteCount();
    }
 
public:
    void InitializeNewTriangle(int TriangleID);
    void OnRemoveTriangle(int TriangleID);
    void OnReverseTriOrientation(int TriangleID);
    void OnSplitEdge(const DynamicMeshInfo::FEdgeSplitInfo& SplitInfo);
    void OnFlipEdge(const DynamicMeshInfo::FEdgeFlipInfo& FlipInfo);
    void OnCollapseEdge(const DynamicMeshInfo::FEdgeCollapseInfo& CollapseInfo);
    void OnPokeTriangle(const DynamicMeshInfo::FPokeTriangleInfo& PokeInfo);
    void OnMergeEdges(const DynamicMeshInfo::FMergeEdgesInfo& MergeInfo);
    void OnMergeVertices(const DynamicMeshInfo::FMergeVerticesInfo& MergeInfo);
    void OnSplitVertex(const DynamicMeshInfo::FVertexSplitInfo& SplitInfo, const TArrayView<const int>& TrianglesToUpdate);
 
protected:
    void SetElementFromLerp(int SetElement, int ElementA, int ElementB, double Alpha);
    void SetElementFromBary(int SetElement, int ElementA, int ElementB, int ElementC, const FVector3d& BaryCoords);
 
    void InternalSetTriangle(int TriangleID, const FIndex3i& TriElements, bool bUpdateRefCounts, bool bAllowElementFreeing = true);
 
};
 
 
 
 
 
 
template<typename RealType, int ElementSize, typename VectorType>
class TDynamicMeshVectorOverlay : public TDynamicMeshOverlay<RealType, ElementSize>
{
public:
    using BaseType = TDynamicMeshOverlay<RealType, ElementSize>;
 
    TDynamicMeshVectorOverlay()
        : TDynamicMeshOverlay<RealType, ElementSize>()
    {
    }
 
    TDynamicMeshVectorOverlay(FDynamicMesh3* parentMesh) 
        : TDynamicMeshOverlay<RealType, ElementSize>(parentMesh)
    {
    }
 
    inline int AppendElement(const VectorType& Value)
    {
        // Cannot use cast operator here because Core Vector types do not define it.
        // However assuming that vector has .X member is also not good...
        //return BaseType::AppendElement((const RealType*)Value);
        return BaseType::AppendElement(&Value.X);
    }
 
    inline int AppendElement(const RealType* Value)
    {
        return BaseType::AppendElement(Value);
    }
 
    inline VectorType GetElement(int ElementID) const
    {
        VectorType V;
        BaseType::GetElement(ElementID, V);
        return V;
    }
 
    inline void GetElement(int ElementID, VectorType& V) const
    {
        BaseType::GetElement(ElementID, V);
    }
 
    inline VectorType GetElementAtVertex(int TriangleID, int VertexID) const
    {
        VectorType V;
        BaseType::GetElementAtVertex(TriangleID, VertexID, V);
        return V;
    }
 
    inline void GetElementAtVertex(int TriangleID, int VertexID, VectorType& V) const
    {
        BaseType::GetElementAtVertex(TriangleID, VertexID, V);
    }
 
    inline void GetTriElement(int TriangleID, int32 TriVertexIndex, VectorType& Value) const
    {
        checkSlow(TriVertexIndex >= 0 && TriVertexIndex <= 2);
        GetElement(BaseType::ElementTriangles[(3 * TriangleID) + TriVertexIndex], Value);
    }
 
    inline void GetTriElements(int TriangleID, VectorType& A, VectorType& B, VectorType& C) const
    {
        int i = 3 * TriangleID;
        GetElement(BaseType::ElementTriangles[i], A);
        GetElement(BaseType::ElementTriangles[i+1], B);
        GetElement(BaseType::ElementTriangles[i+2], C);
    }
 
 
    inline void SetElement(int ElementID, const VectorType& Value)
    {
        BaseType::SetElement(ElementID, Value);
    }
 
    bool EnumerateVertexElements(
        int VertexID,
        TFunctionRef<bool(int TriangleID, int ElementID, const VectorType& Value)> ProcessFunc,
        bool bFindUniqueElements = true) const;
};
 
 
#if PLATFORM_COMPILER_CLANG
#define UE_EXTERN_TEMPLATE_API GEOMETRYCORE_API
#else
#define UE_EXTERN_TEMPLATE_API
#endif
 
#if !UE_MERGED_MODULES
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<float, 1>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<double, 1>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<int, 1>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<float, 2>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<double, 2>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<int, 2>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<float, 3>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<double, 3>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<int, 3>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<float, 4>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshOverlay<double, 4>;
 
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<float, 2, FVector2f>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<double, 2, FVector2d>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<int, 2, FVector2i>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<float, 3, FVector3f>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<double, 3, FVector3d>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<int, 3, FVector3i>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<float, 4, FVector4f>;
extern template class UE_EXTERN_TEMPLATE_API TDynamicMeshVectorOverlay<double, 4, FVector4d>;
#endif
 
#undef UE_EXTERN_TEMPLATE_API
 
} // end namespace UE::Geometry
} // end namespace UE