How do you remove an element from a TOctree?

Development Programming & Scripting C++
, , ,
1

I have figured out how to use the TOctree, and successfully implemented it. However I cannot seem to remove elements once they have been added. The function RemoveElement(FOctreeElementId ElementId); requires an ElementId. However I cannot find any way to get or make an ElementId.

Add element doesn’t return the ID even though the comment says otherwise:

/**
 * Adds an element to the octree.
 * @param Element - The element to add.
 * @return An identifier for the element in the octree.
 */
void AddElement(typename TTypeTraits<ElementType>::ConstInitType Element);

The only useful constructor for ElementID is private:

FCustomOctreeElementId(const void* InNode, int32 InElementIndex)

And there is no function:

GetIdByElement(typename TTypeTraits<ElementType>::ConstInitType Element)

I currently have a workaround but its not pretty. Basically I cloned all the code for the TOctree as TMyOctree and related classes/functions and then made changes necessary to remove an element. I would prefer not to have done this, and a real solution would be nice for anyone else trying to use TOctree.

2

I have had some success in figuring out the solution on my own.

In the OctreeSematic there is a function that is given an id when an object is created: FORCEINLINE static void SetElementId(const FOctreeElement& Element, FOctreeElementId Id) however this gives you a ‘const’ element that cannot be directly changed, so you can’t do anything with the Id here.

My solution is to use pointers to get this working. In my FOctreeElement I add the following:

struct MyIdStruct
{
    FOctreeElementId MyId;
} *MyId;

and in my SetElementId I add the following:

Element.MyId->MyId = Id;

and finally to delete the element I add a function:

void MyOctreeManager::RemoveOctreeElement(const FOctreeElement& inOctreeElement)
{
    OctreeData->RemoveElement(inOctreeElement.MyId->MyId);
}

This gets around the const limitation. I am sure this is violating some programming principles, but it works.

Unfortunately deleting elements now crashes UE4.

3

I think I understand why it is crashing UE4. The struct MyIdStruct is always returning the same MyId no matter what element I am accessing. It looks like it always uses the same pointer for all elements. And I have yet to figure out how to fix that.

4

I found an answer myself. I don’t know if it is the best solution, but it works and doesn’t crash (so far).

In the .h:

USTRUCT(BlueprintType)
struct FOctreeElement
{
    GENERATED_USTRUCT_BODY()

    // A GUID to be used for the map.
    FGuid UniqueID;

    FOctreeElement() : UniqueID(FGuid::NewGuid())
    {
    }
};

inline bool operator==(const FOctreeElement& first, const FOctreeElement& second)
{
    return (first.UniqueID == second.UniqueID);
}

inline uint32 GetTypeHash(const FOctreeElement& other) 
{
    return GetTypeHash(other.UniqueID);
}

struct FOctreeSematics
{
    // The magic is in this map.
    static TMap<FOctreeElement, FOctreeElementId> OctreeIds;

    FORCEINLINE static void SetElementId(const FOctreeElement &Element, FOctreeElementId Id)
    {
        // Add this element to the Map.
        OctreeIds.Add(Element, Id);
    }
};

In the .cpp:

TMap<FOctreeElement, FOctreeElementId> FOctreeSematics::OctreeIds;

void ASpacePartitioner::RemoveOctreeElement(const FOctreeElement& inOctreeElement)
{
    check(bInitialized);
    if (FOctreeSematics::OctreeIds.Contains(inOctreeElement))
    {
        OctreeData->RemoveElement(*FOctreeSematics::OctreeIds.Find(inOctreeElement));
        UE_LOG(LogTemp, Log, TEXT("Removed element from Octree."));
        FOctreeSematics::OctreeIds.Remove(inOctreeElement);
    }
    else
    {
        UE_LOG(LogTemp, Log, TEXT("Element Not Found!"));
    }
}
5

I’m trying to use what you put above however I’m getting errors with the map, not sure what’s going on.

‘TWeakPtr::GetTypeHash’: none of the 946 overloads could convert all the argument types

USTRUCT()
struct FOctreeSemantics
{
	GENERATED_BODY()

	static TMap<FOctreeElement, FOctreeElementId2> OctreeIds;
	
	enum { MaxElementsPerLeaf = 1 };
	enum { MinInclusiveElementsPerNode = 1 };
	enum { MaxNodeDepth = 11 };
	
	typedef TInlineAllocator<MaxElementsPerLeaf> ElementAllocator;

	FORCEINLINE static FBoxSphereBounds GetBoundingBox(const FOctreeElement& Element)
	{
	 	return Element.BoxSphereBounds;
	}
	
	FORCEINLINE static void SetElementId(const FOctreeElement &Element, FOctreeElementId2 Id)
	{
		OctreeIds.Add(Element, Id); //This makes it throw the error.
	}
	
};
6

Here is a link to my recent source code.

I just checked any my solution still works on 4.25. I am not sure if there has been any changes to the unreal engine side of the octree code since 4.25. Sometimes they change things. I could look into it if you are still having problems after looking at the source code. I would link my project but it’s just too big :-(.

I was able to put millions of cubes on the screen with no noticeable performance issues.