MeshElementIndexer.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/ContainerAllocationPolicies.h"
#include "Containers/Set.h"
#include "CoreMinimal.h"
#include "HAL/UnrealMemory.h"
#include "Math/UnrealMathSSE.h"
#include "MeshAttributeArray.h"
#include "Misc/AssertionMacros.h"
#include "Templates/EnableIf.h"
#include "Templates/UnrealTypeTraits.h"
#include "UObject/NameTypes.h"
 
class FMeshElementChannels;
struct FElementID;
 
 
class FMeshElementIndexer
{
public:
    FMeshElementIndexer() = default;
    MESHDESCRIPTION_API FMeshElementIndexer(const FMeshElementChannels* Key, const FMeshElementChannels* Referencer, FName AttributeName, int32 ReferencerChannelIndex = 0);
 
    // Copying not allowed as they reference elements of a MeshDescription of which they are normally a part
    FMeshElementIndexer(const FMeshElementIndexer&) = delete;
    FMeshElementIndexer& operator=(const FMeshElementIndexer&) = delete;
 
    // Moving OK
    FMeshElementIndexer(FMeshElementIndexer&&) = default;
    FMeshElementIndexer& operator=(FMeshElementIndexer&&) = default;
 
    MESHDESCRIPTION_API void Set(const FMeshElementChannels* Key, const FMeshElementChannels* Referencer, FName AttributeName, int32 ReferencerChannelIndex = 0);
 
    void SetInitialNumReferences(int InInitialSize) { InitialSize = InInitialSize; }
 
    void SetChunkSize(int InChunkSize)
    {
        ChunkBits = FMath::CeilLogTwo(InChunkSize);
        ChunkMask = (1U << ChunkBits) - 1;
    }
 
    void SetUnchunked()
    {
        SetChunkSize(1);
        check(ChunkBits == 0);
        check(ChunkMask == 0);
    }
 
    MESHDESCRIPTION_API void Reset();
 
    TArrayView<const int32> Find(int32 KeyIndex, int32 KeyChannelIndex = 0)
    {
        check(!bSuspended);
        ConditionalBuild(KeyIndex, KeyChannelIndex);
        int32 Chunk = GetChunkForKey(KeyIndex);
        int32 ChunkElement = GetChunkElementForKey(KeyIndex);
 
        check(KeyChannelIndex < PerChannelIndices.Num());
        if (PerChannelIndices[KeyChannelIndex].Chunks.Num() == 0)
        {
            return TArrayView<const int32>();
        }
        return PerChannelIndices[KeyChannelIndex].Chunks[Chunk].Get(ChunkElement);
    }
 
 
    template <typename ElementIDType>
    TArrayView<const ElementIDType> Find(int32 KeyIndex, int32 KeyChannelIndex = 0)
    {
        check(!bSuspended);
        check(KeyIndex != INDEX_NONE);
        ConditionalBuild(KeyIndex, KeyChannelIndex);
        int32 Chunk = GetChunkForKey(KeyIndex);
        int32 ChunkElement = GetChunkElementForKey(KeyIndex);
 
        // If the key hasn't yet had a chunk created for it, assume that nothing has yet referenced it, and return an empty array.
        if (Chunk >= PerChannelIndices[KeyChannelIndex].Chunks.Num())
        {
            return TArrayView<const ElementIDType>();
        }
        return PerChannelIndices[KeyChannelIndex].Chunks[Chunk].Get<ElementIDType>(ChunkElement);
    }
 
 
    MESHDESCRIPTION_API void RemoveKey(int32 KeyIndex, int32 KeyChannelIndex = 0);
 
    MESHDESCRIPTION_API void RemoveReferenceFromKey(int32 KeyIndex, int32 ReferenceIndex, int32 KeyChannelIndex = 0);
 
    MESHDESCRIPTION_API void AddReferenceToKey(int32 KeyIndex, int32 ReferenceIndex, int32 KeyChannelIndex = 0);
 
    void Suspend() { bSuspended = true; }
 
    void Resume()
    {
        bSuspended = false;
        bEverythingStale = true;
    }
 
    MESHDESCRIPTION_API void ForceRebuild();
 
    MESHDESCRIPTION_API void Build();
 
private:
    // Ensure that the right number of per channel indices are allocated
    MESHDESCRIPTION_API void UpdatePerChannelIndices();
 
    // Incrementally builds the index based on the lists of stale keys and referencers
    MESHDESCRIPTION_API void BuildIndex(int32 Index);
 
    // Does a full rebuild of the index from scratch, directly from referencing attributes
    MESHDESCRIPTION_API void RebuildIndex(int32 Index);
 
    // Performs an incremental build if the specified key is stale
    MESHDESCRIPTION_API void ConditionalBuild(int32 KeyIndex, int32 KeyChannelIndex);
 
    // Add a reference to a key in unchunked mode
    MESHDESCRIPTION_API void AddUnchunked(int32 KeyIndex, int32 ReferenceIndex, int32 KeyChannelIndex = 0);
 
    // Return the chunk index relating to this key index
    int32 GetChunkForKey(int32 ElementIndex) const
    {
        checkSlow(ElementIndex != INDEX_NONE);
        return ElementIndex >> ChunkBits;
    }
 
    // Return the chunk element index relating to this key index
    int32 GetChunkElementForKey(int32 ElementIndex) const
    {
        checkSlow(ElementIndex != INDEX_NONE);
        return ElementIndex & ChunkMask;
    }
 
    // Return the currently configured chunk size
    int32 GetChunkSize() const { return (1 << ChunkBits); }
 
    // Return the number of chunks required to accommodate the specified number of keys
    int32 GetNumChunksForKeys(int32 NumElements) const { return (NumElements + ChunkMask) >> ChunkBits; }
 
 
    struct FChunk
    {
        FChunk(int32 InitialSize, int32 ChunkSize)
        {
            // Allocate the block which will contain the actual referencing elements
            Data.SetNumUninitialized(ChunkSize * InitialSize, EAllowShrinking::No);
 
            // Initialize indexing structures
            StartIndex.SetNumUninitialized(ChunkSize);
            Count.SetNumUninitialized(ChunkSize);
            MaxCount.SetNumUninitialized(ChunkSize);
 
            int32 N = 0;
            for (int I = 0; I < ChunkSize; I++)
            {
                StartIndex[I] = N;
                N += InitialSize;
            }
 
            for (int I = 0; I < ChunkSize; I++)
            {
                MaxCount[I] = InitialSize;
            }
 
            FMemory::Memzero(Count.GetData(), sizeof(int32) * ChunkSize);
        }
 
        bool Add(int32 Index, int32 Value);
 
        bool AddUnsorted(int32 Index, int32 Value);
 
        bool Remove(int32 Index, int32 Value);
 
        bool Contains(int32 Index, int32 Value) const;
 
        void Sort(int32 Index);
 
        TArrayView<const int32> Get(int32 Index) const
        {
            // Build array view for the portion of the data array corresponding to this element
            const int32* Ptr = Data.GetData() + StartIndex[Index];
            return TArrayView<const int32>(Ptr, Count[Index]);
        }
 
        template <typename ElementIDType, typename TEnableIf<TIsDerivedFrom<ElementIDType, FElementID>::Value, int>::Type = 0>
        TArrayView<const ElementIDType> Get(int32 Index) const
        {
            // Build array view for the portion of the data array corresponding to this element
            static_assert(sizeof(ElementIDType) == sizeof(int32), "ElementIDType must be 32 bits long");
            const ElementIDType* Ptr = reinterpret_cast<const ElementIDType*>(Data.GetData()) + StartIndex[Index];
            return TArrayView<const ElementIDType>(Ptr, Count[Index]);
        }
 
        TArray<int32> Data;
 
        TArray<int32, TInlineAllocator<1>> StartIndex;
        TArray<int32, TInlineAllocator<1>> Count;
        TArray<int32, TInlineAllocator<1>> MaxCount;
    };
 
    struct FIndexPerChannel
    {
        TArray<FChunk> Chunks;
 
        TSet<int32> StaleKeyIndices;
 
        TSet<int32> StaleReferencerIndices;
    };
 
    TArray<FIndexPerChannel> PerChannelIndices;
 
    const FMeshElementChannels* ReferencedElementType;
 
    TMeshAttributesRef<int, TArrayView<const int32>> ReferencingAttributeRef;
 
    int32 InitialSize = 1;
 
    uint32 ChunkBits = 8;
    uint32 ChunkMask = (1U << ChunkBits) - 1;
 
    bool bSuspended = false;
 
    bool bEverythingStale = true;
};