Octrees in Unreal Engine 4

A short while ago, I was asked about space partitioning algorithms at an interview, and it was something that I had learned about in the past, however it wasn’t something I could recall on the spot. I went away and started working on a 2D Platformer for Android in Unreal Engine 4 with C++, so I could get a game released and learn a little about Unreal Engine 4. On the way, I decided an Octree might be a nice way to determine how many platforms which have been generated are clustered in a particular area, as well as force me to learn something new so if I’m asked again, I can recall on the spot.

Before we start, here’s the two sources I used to piece together Octrees, if anyone wants to learn more, then here’s a good place to start:
BitBoy92’s GitHub project and Josh Petrie’s answer on the UE4 forums.

Octrees are a space partitioning algorithm which maps the world into a tree, where each node holds nodes. In games dev we apply this by dividing the world into sections based on the number of elements within the tree, and then dividing each child node into sections based on it’s number of children. This can repeat any number of times, you define the variables.

Enough explanations, let’s explore how it works in code.

Defining Data Structures for the Octree

First off, lets include the header for octrees, and any actors or scene components you want to create inside the octree.

#include  "GenericOctree.h"

Next you need to define a data structure to hold elements to be added to the octree, think of this as each node in the tree. Mine looks like this, where APlatformActor is an actor I’ve already defined.

struct FOctreeElement
{
	TSharedPtr<APlatformActor> PlatformActor;

	FBoxCenterAndExtent BoxCenterAndExtent;

	FOctreeElement (TSharedPtr<APlatformActor> platformActor)
	{
		PlatformActor = platformActor;
		BoxCenterAndExtent = FBoxCenterAndExtent(PlatformActor->Box->Bounds.GetBox().GetCenter(), PlatformActor->Box->Bounds.GetBox().GetExtent());
	}

	~FOctreeElement()
	{
	}

private:	
	FOctreeElement()
	{
		PlatformActor = nullptr;
		BoxCenterAndExtent = FBoxCenterAndExtent(FVector(0.0f, 0.0f, 0.0f), FVector(1.0f, 1.0f, 1.0f));
	}

};

In our FOctreeElement struct, we have:

  • A shared pointer pointing at our PlatformActor, this is the object we’re going to create in the world, and pass into our octree. We’re not using unique pointer as it’s possible we’ll need multiple references to an actor later down the line.
  • The centre of the bounding box and it’s extent (width, height and depth).
  • Constructors
  • Destructors

That’s all there is to this struct, a pretty basic data structure to represent each node in the tree.

Next we need to define the data structure for the tree. This is where we’ll define any rules for the tree itself. You can customise this as you please.

struct FPlatformOctreeSemantics
{
	enum { MaxElementsPerLeaf = 4 };
	enum { MinInclusiveElementsPerNode = 1 };
	enum { MaxNodeDepth = 16 };

	typedef TInlineAllocator<MaxElementsPerLeaf> ElementAllocator;

	FORCEINLINE static FBoxCenterAndExtent GetBoundingBox(const FOctreeElement& Element)
	{
		return Element.BoxCenterAndExtent;
	}

	FORCEINLINE static bool AreElementsEqual(const FOctreeElement& a, const FOctreeElement& b)
	{
		return a.PlatformActor == b.PlatformActor;
	}

	/** Ignored for this implementation */
	FORCEINLINE static void SetElementId(const FOctreeElement& Element, FOctreeElementId Id)
	{
	}
};

The max elements per leaf is best explained by the picture below, where there can be 4 child nodes for each node, and each child nodecan have 4 more child nodes as such:

Min inclusive elements per node is the minimum number of elements which can exist in each node, in our case, the minimum number of FOctreeElement instances that can exist in each partition. The max node depth is the number of edges of a graph between the root node and a given node.

Finally, we have our typedef definition to make defining our octree much simpler. This is done like this:

typedef TOctree<FOctreeElement, FPlatformOctreeSemantics> FPlatformOctree;

Now whenever we need to define a variable of type octree, we can simply use ‘FPlatformOctree octree;’.

Using the Octree

Now the hard bit is done, we just need to use the octree. Define a member variable unique pointer for the Octree, and initialise it as such.

PlatformOctree = MakeUnique<FPlatformOctree>(bounds.GetCenter(),bounds.GetExtent().GetMax());

Next, we need to add some items to our octree, I’ll just add one for now, you can add as many as you like.

TSharedPtr<APlatformActor> platformActor = MakeShareable(GetWorld()->SpawnActor<APlatformActor>(APlatformActor::StaticClass()));
platformActor->SetActorLocation(FVector(1600.0f, -100.0f, 100.0f));
FOctreeElement* ele = new FOctreeElement(platformActor);
PlatformOctree->AddElement(*ele);

Great, now we have a few elements in our octree, we should be able able to use it. However, an octree isn’t actually a visible model, so we’ll need to draw some boxes around the edge of the octree. I’m going to use a slightly adapted method from the one found in BitBoys GitHub project which I mentioned at the start of the article. In a tick component, I’ll draw it with this code:

void UPlatformGenerator::DrawBounds()
{
	int level = 0;
	FBoxCenterAndExtent OldBounds = FBoxCenterAndExtent();

	// Go through the nodes of the octree
	for (FPlatformOctree::TConstIterator<> NodeIt(*PlatformOctree); NodeIt.HasPendingNodes(); NodeIt.Advance())
	{
		const FPlatformOctree::FNode& CurrentNode = NodeIt.GetCurrentNode();
		const FOctreeNodeContext& CurrentContext = NodeIt.GetCurrentContext();
		const FBoxCenterAndExtent& CurrentBounds = CurrentContext.Bounds;


		FOREACH_OCTREE_CHILD_NODE(ChildRef)
		{
			if (CurrentNode.HasChild(ChildRef))
			{
				NodeIt.PushChild(ChildRef);
			}
		}

		// If the extents have changed then we have moved a level.
		if (!OldBounds.Extent.Equals(CurrentBounds.Extent))
		{
			level++;
		}
		OldBounds = CurrentBounds;

		// Draw the 
		DrawDebugBox(GetWorld(), CurrentContext.Bounds.Center, CurrentContext.Bounds.Extent, FColor().Blue, false, 0.0f);

		for (FPlatformOctree::ElementConstIt ElementIt(CurrentNode.GetElementIt()); ElementIt; ++ElementIt)
		{
			const FOctreeElement& Sample = *ElementIt;
			float max = Sample.PlatformActor->Box->Bounds.GetBox().GetExtent().GetMax();
			FVector maxExtent = FVector(max * Sample.PlatformActor->GetActorScale().X,
				max * Sample.PlatformActor->GetActorScale().Y,
				max * Sample.PlatformActor->GetActorScale().Z);

			// Draw debug boxes around elements
			DrawDebugBox(GetWorld(), Sample.BoxCenterAndExtent.Center, maxExtent, FColor().Blue, false, 0.0f);
		}
	}
}

And that’s all there is to it! You should now be able to see the various nodes within your octree, how you use it from here is entirely up to you.