Why is my Octree generation not working? (Code review)

I am trying to generate a visualization of Octree using C++ in Unreal Engine. I am basically, creating a class OctTree, which is the biggest bounding box. The box is drawn using a DrawDebugBox function.
This root box, then calls a function that spawns more OctTree but with subdivided origin and extent locations. The spawn functions keep getting called till the extent goes below a certain limit (100).

Here are the data members in the header:

This is a manager blueprint that spawns the first OctTree node:

The DrawNode() function now draws the box and calls the BuildTree() function which starts mapping out the octants for this node and spawns them as more OctTrees:

void AOctTree::DrawNode()
{
	if (boundingBox.extent.X < 100)
		return;
	UWorld *world = GetWorld();

	DrawDebugBox(world, boundingBox.origin, boundingBox.extent, 
		FColor(FMath::RandRange(0, 255), FMath::RandRange(0, 255), FMath::RandRange(0, 255)),true,120,(uint8)'\000',10);

	BuildTree();
}

Here is the BuildTree() function:

void AOctTree::BuildTree()
{
		FVector dimension = boundingBox.extent - boundingBox.origin;

		if (dimension.X < 1)
		{
			return;
		}

		FVector half = dimension / 2;

		FVector center = half;

		Node octNodes[8];

		FColor color = FColor(FMath::RandRange(0, 255), FMath::RandRange(0, 255), FMath::RandRange(0, 255));

		UWorld *world = GetWorld();
		//Top Left back : -x,-y, +z
		octNodes[0].origin = FVector(boundingBox.origin.X - center.X, boundingBox.origin.Y - center.Y,
			boundingBox.origin.Z + center.Z);
		octNodes[0].extent = boundingBox.extent / 2;


		//Top right back: +x,-y,+z
		octNodes[1].origin = FVector(boundingBox.origin.X + center.X, boundingBox.origin.Y - center.Y,
			boundingBox.origin.Z + center.Z);
		octNodes[1].extent = boundingBox.extent / 2;


		//Top Left front: -x,+y,+z
		octNodes[2].origin = FVector(boundingBox.origin.X - center.X, boundingBox.origin.Y + center.Y,
			boundingBox.origin.Z + center.Z);
		octNodes[2].extent = boundingBox.extent / 2;

		//Top right front: +x,+y,+z
		octNodes[3].origin = FVector(boundingBox.origin.X + center.X, boundingBox.origin.Y + center.Y,
			boundingBox.origin.Z + center.Z);
		octNodes[3].extent = boundingBox.extent / 2;

		//Bottom Left back: -x,-y,-z
		octNodes[4].origin = FVector(boundingBox.origin.X - center.X, boundingBox.origin.Y - center.Y,
			boundingBox.origin.Z - center.Z);
		octNodes[4].extent = boundingBox.extent / 2;

		//Bottom right back: +x,-y,-z
		octNodes[5].origin = FVector(boundingBox.origin.X + center.X, boundingBox.origin.Y - center.Y,
			boundingBox.origin.Z - center.Z);
		octNodes[5].extent = boundingBox.extent / 2;

		//Bottom Left front: -x,+y,-z
		octNodes[6].origin = FVector(boundingBox.origin.X - center.X, boundingBox.origin.Y + center.Y,
			boundingBox.origin.Z - center.Z);
		octNodes[6].extent = boundingBox.extent / 2;

		//Bottom right front: +x,+y,-z
		octNodes[7].origin = FVector(boundingBox.origin.X + center.X, boundingBox.origin.Y + center.Y,
			boundingBox.origin.Z - center.Z);
		octNodes[7].extent = boundingBox.extent / 2;

		int newDepth = boundingBox.depth + int(1);

		UE_LOG(LogTemp, Warning, TEXT("Depth is %d"), newDepth);

		for (int i = 0; i < 8; ++i)
		{
			FTimerHandle UnusedHandle;
			FTimerDelegate TimerDelegate;

			TimerDelegate.BindUFunction(this, FName("SpawnOctree"), octNodes[i].origin, octNodes[i].extent, newDepth);

			GetWorldTimerManager().SetTimer(UnusedHandle,TimerDelegate, 5.0f, false);

		}
}

And finally, the class constructor, spawn function and init function to initialize new dimensions:

// Sets default values
AOctTree::AOctTree()
{
	PrimaryActorTick.bCanEverTick = false;
	SetBoundingBox(FVector(0, 0, 0), FVector(128,128, 128), int(1));
	minNodeSize = 1;
	maxNodeSize = boundingBox.extent.X;
}

Spawn function:

void AOctTree::SpawnOctree(FVector spawnLocation, FVector spawnExtent, int depth)
{
	FRotator Rotation(0.0f, 0.0f, 0.0f);
	FActorSpawnParameters SpawnInfo;
	AOctTree *newTree = GetWorld()->SpawnActor<AOctTree>(spawnLocation, Rotation, SpawnInfo);

	newTree->init(spawnLocation, spawnExtent, depth);
}

Init function:

void AOctTree::init(FVector const origin, FVector const extent, int const depth)
{
	PrimaryActorTick.bCanEverTick = false;
	SetBoundingBox(origin, extent,depth);
	minNodeSize = 1;
	maxNodeSize = (extent).X;
	DrawNode();
}
	
void AOctTree::SetBoundingBox(FVector origin, FVector extent, int depth)
{
	boundingBox.origin = origin;
	boundingBox.extent = extent;
	boundingBox.depth = depth;
}

Every time the init() method is called, it in turn calls the DrawNode() with the updated box dimensions and builds the tree again for the particular octree. It goes on till the bounding box extent is below 100.

However, after the first iteration of building the 1st octree, the origin position seems to go haywire, some boxes don’t get generated. Here is the output of the current code:

1:

2:

3:

I think it has to do with how you get the center of the new boxes. I think it has to do with these lines:

octNodes[0].origin = FVector(boundingBox.origin.X - center.X, boundingBox.origin.Y - center.Y, boundingBox.origin.Z + center.Z);

You take the origin of the very first box and substract the center of the new box (which is half of the previous iteration of the box, if I understand that correctly). This works fine for the first iteration. However for any following iteration it doesn’t, because:
lets say the bounding box is 2x2x2

1st iteration:
x: 0 - 1 = -1
y: 0 - 1 = -1
z: 0 + 1 = 1

2nd iteration:
x: 0 - 0.5 = -0.5
y: 0 - 0.5 = -0.5
z: 0 + 0.5 = 0.5

this would make the numbers incorrect in what you’re trying to achieve.
If I have it correctly in my head the numbers for the second iteration would need to be:
x: -1.5
y: -1.5
z: 1.5

I’m not sure though. the longer i think about it the less sense it makes (the stuff I’ve written), but ultimately I think the issue is somewhere around that area.

That was it! The dimension value was set to 0 in many cases since the origin and the extent would sum up to a zero vector. Just changing the dimension vector to be the extent of each box makes more sense!

FVector dimension = boundingBox.extent;

Here is how it looks now. Thanks, man :slight_smile:

I’m glad I could help.