What is Octree? An octree is basically a recursive algorithm for dividing up space into 8, which is why it is called octal tree obviously. So you can see that I’ve already divided up this space here in Unity, and what it’s doing is it’s actually searching through the 3d space, and looking for any particular geometry that might be in there, in this case, we are looking for things with colliders on them, and then what it does is it actually looks for the detail in this world by creating smaller and smaller little voxels around where the detail is, so what you end up with is basically a series of nodes that will define the space, and well in this case tell you what’s empty space and what’s not, so for example, this big cube down here obviously is empty space so if you’re using that for like a path finding algorithm, you’re quite free to go around within here and not hit anything, so what it does is it just keeps dividing up cubes into cubes into cubes until it actually hits an object and then defines it by these small little cubes that sit around it.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OctreeNode
{
Bounds nodeBounds;
float minSize;
public OctreeNode(Bounds b, float minNodeSize)
{
nodeBounds = b;
minSize = minNodeSize;
}
public void Draw()
{
Gizmos.color = new Color(0, 1, 0);
Gizmos.DrawWirecube(nodeBounds.center, nodeBounds.size);
}
}
In unity, we’re using the bounds part of the Unity api as you’ll see in a moment which hasn’t changed for a very long time, and I don’t think it will so we should be pretty safe.
So we got an empty project here, we need to create three c# scripts. CreateOctree.cs, Octree.cs and OctreeNode.cs.
So an octree is a graph structure and it’s a tree like structure, tree-like because if you have a look at it, you were to draw a diagram it looks like an upside down tree, so you have a parent node which then splits into 8 children, so they’re the sort of branches and then each of the children are splitted into 8 and those are splitted into 8, and eventually you stop splitting at either a minimum size or when you’re actually found something of interest in the space that you’re dividing up which is what we’re doing now.
OK, let’s start by going into our octree node code. And it’s not going to be a mono behavior, so we can get rid of that, and we can get rid of our functions that are already sitting in there that Unity gave us. So what we need to do to define a node is that it has a bounds which is its box that’s sitting around it basically. So we create a bounds and we call it nodeBounds, then we want to create a minimum size float minSize, this two is to actually draw what’s going on in our scene view using gizmos. The reason being is that essentially you don’t see the octree, it’s just dividing up space but you need something to be able to debug what you’re doing and see the effects so it’s really important that we put this in.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OctreeNode
{
Bounds nodeBounds;
float minSize;
public OctreeNode(Bounds b, float minNodeSize)
{
nodeBounds = b;
minSize = minNodeSize;
}
public void Draw()
{
Gizmos.color = new Color(0, 1, 0);
Gizmos.DrawWirecube(nodeBounds.center, nodeBounds.size);
}
}Now the Octree class, again, this won’t be a mono behavior. The octree starts with a root. And then for the constructor, we’re going to pass through an array of game objects that we will use to size our octree. In the constructor, we create a bounds, it’s an axis aligned bounding box which means it creates basically a box which covers the extent of the game object but the box is axis aligned, so it’s sitting along the world axis, the x, y and z, so it actually perfectly aligned to that it’s not a skewed or anything even if you rotate your object, you still get a axis aligned bounding box which is why it is called that and you may have seen the abbreviation AABB with respect to collisions and bounds and those sorts of things. So we’ll actually loop through all those world objects now, and make our bounds bigger based on those objects. It’s actually quite easy with the Unity api, so bounds.Encapsulate is called, and we send it our getComponent our collider that’s sitting on our object. Once we’ve done that, we force it into a cube shape.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Octree
{
public OctreeNode rootNode;
public Octree(GameObject[] worldObjects, float minNodeSize)
{
Bounds bounds = new Bounds();
foreach(GameObject go in worldObjects)
{
bounds.Encapsulate(go.GetComponent<Collider>().bounds);
}
float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z });
Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize);
bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector);
rootNode = new OctreeNode(bounds, minNodeSize);
}
}Now we can go to our CreateOctree class, this is a mono behavior, it’s going to be on an object inside of the hierarchy.
using System.Collections;
using System.Collections.Generic;
public class CreateOctree : MonoBehaviour
{
public GameObject[] worldObjects;
public int nodeMinSize = 5;
Octree otree;
// Start is called before the first frame update
void Start()
{
otree = new Octree(worldObjects, nodeMinSize);
}
void onDrawGizmos()
{
if (Application.isPlaying)
{
otree.rootNode.Draw();
}
}
}OK, we’re ready to test something at this point. Let’s go to Unity, and in your hierarchy, we’re going to right click and add in an empty object, and we can call this our octree, we want to add CreateOctree onto it. And here you can also change your node minSize if you want it to be smaller or bigger. And for the worldObjects, we now need to create some world objects, so just go to the 3D object, and add a few cubes.
Now, we can press play, and we will see our node displayed on the screen, so this is the root node. You can see it’s around all of the objects in the scene, but it looks bigger than it needs to be. It should be hugging the edge not that you necessarily want it to be hugging the edge, but when you create this, you actually need to get the size now, because the sizes of the cubes are actually measured from the center. We need to multiply it by 0.5 to halve the size, because we only want half the size in each direction.
So going back to the code, we can make this change:
Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize) * 0.5f;
Now, it’s hugging our cubes.
So in order to divide into 8, we need to update our OctreeNode code. Each child there’s going to be 8, that means we’re sort of cutting the cube in half along the x, the y and the z axis, which ends up giving us 8 separate cubes. The order of the 8 childBounds doesn’t really matter, what the order is as long as you’ve got them and they’re all different combinations of minus a quarter and positive a quarter so you’ve covered all of the octants. That’s all we need for our OctreeNode.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OctreeNode
{
Bounds nodeBounds;
float minSize;
Bounds[] childBounds;
public OctreeNode(Bounds b, float minNodeSize)
{
nodeBounds = b;
minSize = minNodeSize;
float quarter = nodeBounds.size.y / 4.0f;
float childLength = nodeBounds.size.y / 2;
Vector3 childSize = new Vector3(childLength, childLength, childLength);
childBounds = new Bounds[8];
childBounds[0] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, -quarter), childSize);
childBounds[1] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, -quarter), childSize);
childBounds[2] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, quarter), childSize);
childBounds[3] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, quarter), childSize);
childBounds[4] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, -quarter), childSize);
childBounds[5] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, -quarter), childSize);
childBounds[6] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, quarter), childSize);
childBounds[7] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, quarter), childSize);
}
public void Draw()
{
Gizmos.color = new Color(0, 1, 0);
Gizmos.DrawWirecube(nodeBounds.center, nodeBounds.size);
}
}So far, we’ve actually not created any child nodes or children nodes of the root node, we’re just defining the boundaries of where they might possibly be, because we don’t want to actually create them unless we need to based on whether there is anything in the actual environment in that position, so what we’ll do now is actually go back into our octree and work out a way to pass through our objects to our octree node.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Octree
{
public OctreeNode rootNode;
public Octree(GameObject[] worldObjects, float minNodeSize)
{
Bounds bounds = new Bounds();
foreach(GameObject go in worldObjects)
{
bounds.Encapsulate(go.GetComponent<Collider>().bounds);
}
float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z });
Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize);
bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector);
rootNode = new OctreeNode(bounds, minNodeSize);
}
public void AddObjects(GameObject[] worldObjects)
{
foreach(GameObject go in worldObjects)
{
rootNode.AddObject(go);
}
}
}And back into our OctreeNode class, we need to create our method for adding objects. As well as adding the tough part, the recursion to create nodes and then get them to create nodes and get them to create nodes until we reach some kind of ending position where we’ll stop recursing.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OctreeNode
{
Bounds nodeBounds;
float minSize;
Bounds[] childBounds;
OctreeNode[] children = null;
public OctreeNode(Bounds b, float minNodeSize)
{
nodeBounds = b;
minSize = minNodeSize;
float quarter = nodeBounds.size.y / 4.0f;
float childLength = nodeBounds.size.y / 2;
Vector3 childSize = new Vector3(childLength, childLength, childLength);
childBounds = new Bounds[8];
childBounds[0] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, -quarter), childSize);
childBounds[1] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, -quarter), childSize);
childBounds[2] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, quarter), childSize);
childBounds[3] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, quarter), childSize);
childBounds[4] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, -quarter), childSize);
childBounds[5] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, -quarter), childSize);
childBounds[6] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, quarter), childSize);
childBounds[7] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, quarter), childSize);
}
public void AddObject(GameObject go)
{
DivideAndAdd(go);
}
public void DivideAndAdd(GameObject go)
{
if (nodeBounds.size.y <= minSize)
{
return;
}
if (children == null)
children = new OctreeNode[8];
bool dividing = false;
for (int i = 0; i < 8; ++i)
{
if (children[i] == null)
{
children[i] = new OctreeNode(childBounds[i], minSize);
}
if (childBounds[i].Intersects(go.GetComponent<Collider>().bounds))
{
dividing = true;
children[i].DivideAndAdd(go);
}
}
if (dividing == false)
{
children = null;
}
}
public void Draw()
{
Gizmos.color = new Color(0, 1, 0);
Gizmos.DrawWirecube(nodeBounds.center, nodeBounds.size);
if (children != null)
{
for (int i = 0; i < 8; ++i)
{
if (children[i] != null)
{
children[i].Draw();
}
}
}
}
}And also, for the Octree class, we also need to add the below line to the constructor.
AddObjects(worldObjects);using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Octree
{
public OctreeNode rootNode;
public Octree(GameObject[] worldObjects, float minNodeSize)
{
Bounds bounds = new Bounds();
foreach(GameObject go in worldObjects)
{
bounds.Encapsulate(go.GetComponent<Collider>().bounds);
}
float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z });
Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize);
bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector);
rootNode = new OctreeNode(bounds, minNodeSize);
AddObjects(worldObjects);
}
public void AddObjects(GameObject[] worldObjects)
{
foreach(GameObject go in worldObjects)
{
rootNode.AddObject(go);
}
}
}Now, press Play, we’ll see this. We’re not necessarily getting very small node sizes, but it is dividing more and more around where the objects of interest are.
If we set minSize to 1, and press Play, we’ll get a lot smaller detailed cubes around these areas of interest.
And of course, you can also add other things in here as well. For example, add a new sphere to our world objects. We get this.
A good application for this is to achieve pathfinding, to create AI characters who can automatically move through this octree avoiding collisions that they might come across.
Check out the author’s video tutorial here: https://www.youtube.com/watch?v=wrZsTt6Pg2E