Home

Awesome

UnityOctree

A dynamic octree implementation for Unity written in C#.
Originally written for my game Scraps but intended to be general-purpose.

There are two octree implementations here:
BoundsOctree stores any type of object, with the object boundaries defined as an axis-aligned bounding box. It's a dynamic octree and can also be a loose octree.
PointOctree is the same basic implementation, but stores objects as a point in space instead of bounds. This allows some simplification of the code. It's a dynamic octree as well.

Octree: An octree a tree data structure which divides 3D space into smaller partitions (nodes) and places objects into the appropriate nodes. This allows fast access to objects in an area of interest without having to check every object.

Dynamic: The octree grows or shrinks as required when objects are added or removed. It also splits and merges nodes as appropriate. There is no maximum depth. Nodes have a constant (numObjectsAllowed) which sets the amount of items allowed in a node before it splits.

Loose: The octree's nodes can be larger than 1/2 their parent's length and width, so they overlap to some extent. This can alleviate the problem of even tiny objects ending up in large nodes if they're near boundaries. A looseness value of 1.0 will make it a "normal" octree.

A few functions are implemented:

With BoundsOctree, you can pass in bounds and get a true/false answer for if it's colliding with anything (IsColliding), or get a list of everything it's collising with (GetColliding). With PointOctree, you can cast a ray and get a list of objects that are within x distance of that ray (GetNearby).

It shouldn't be too hard to implement additional functions if needed. For instance, PointOctree could check for points that fall inside a given bounds.

Considerations:

Tree searches are recursive, so there is technically the potential for a stack overflow on very large trees. The minNodeSize parameter limits node side and hence the depth of the tree, putting a cap on recursion.

I tried switching to an iterative solution using my own stack, but creating and manipulating the stack made the results generally slower than the simple recursive solution. However, I wouldn't be surprised it someone smarter than me can come up with a faster solution.

Another note: You may notice when viewing the bounds visualisation that the child nodes' outer edges are all inside the parent nodes. But loose octrees are meant to make the inner nodes bigger... aren't they? The answer is yes, but the parent nodes are also bigger, and e.g. ((1.2 * 10) - 10) is bigger than ((1.2 * 5) - 5), so the parent node ends up being bigger overall.

This seems to be the standard way that loose octrees are done. I did an experiment: I tried making the child node dimensions looseness * the parent's actual size, instead of looseness * the parent's base size before looseness is applied. This seems more intuitively correct to me, but performance seems to be about the same.

Example Usage

Create An Octree

// Initial size (metres), initial centre position, minimum node size (metres), looseness
BoundsOctree<GameObject> boundsTree = new BoundsOctree<GameObject>(15, MyContainer.position, 1, 1.25f);
// Initial size (metres), initial centre position, minimum node size (metres)
PointOctree<GameObject> pointTree = new PointOctree<GameObject>(15, MyContainer.position, 1);

Add And Remove

boundsTree.Add(myObject, myBounds);
boundsTree.Remove(myObject);

pointTree.Add(myObject, myVector3);
boundsTree.Remove(myObject);

Built-in Functions

bool isColliding = boundsTree.IsColliding(bounds);
List<GameObject> collidingWith = new List<GameObject>();
boundsTree.GetColliding(collidingWith, bounds);
pointTree.GetNearby(myRay, 4);

Debugging Visuals

Visualisation example.

void OnDrawGizmos() {
	boundsTree.DrawAllBounds(); // Draw node boundaries
	boundsTree.DrawAllObjects(); // Draw object boundaries
	boundsTree.DrawCollisionChecks(); // Draw the last *numCollisionsToSave* collision check boundaries

	pointTree.DrawAllBounds(); // Draw node boundaries
	pointTree.DrawAllObjects(); // Mark object positions
}

Potential Improvements

A significant portion of the octree's time is taken just to traverse through the nodes themselves. There's potential for a performance increase there, maybe by linearising the tree - that is, representing all the nodes as a one-dimensional array lookup.