Unity Octree Sorted

A dynamic octree implementation for Unity written in C# forked from https://github.com/Nition/UnityOctree and updated.

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 or GetNearbySorted). You may also get a list of objects that are within x distance from a specified origin point.

Considerations:

See: https://github.com/Nition/UnityOctree

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);

• Here I've used GameObject, but the tree's content can be any type you like (as long as it's all the same type
• The initial size should ideally cover an area just encompassing all your objects. If you guess too small, the octree will grow automatically, but it will be eight times the size (double dimensions), which could end up covering a large area unnecessarily. At the same time, the octree will be able to shrink down again if the outlying objects are removed. If you guess an initial size that's too big, it won't be able to shrink down, but that may be the safer option. Don't worry too much: In reality the starting value isn't hugely important for performance.
• The initial position should ideally be in the centre of where your objects are.
• The minimum node size is effectively a depth limit; it limits how many times the tree can divide. If all your objects are e.g. 1m+ wide, you wouldn't want to set it smaller than 1m.
• The best way to choose a looseness value is to try different values (between 1 and maybe 1.5) and check the performance with your particular data. Generally around 1.2 is good.

Add And Remove

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

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

• The object's type depends on the tree's type.
• The bounds or point determine where it's inserted.

Built-in Functions

bool isColliding = boundsTree.IsColliding(bounds);

List<GameObject> collidingWith = new List<GameObject>();
boundsTree.GetColliding(collidingWith, bounds);

• Where GameObject is the type of the octree

pointTree.GetNearby(myRay, 4);

• Where myRay is a Ray
• In this case we're looking for any point within 4m of the closest point on the ray

pointTree.GetNearby(myPos, 4);

• Where myPos is a Vector3

pointTree.GetNearbySorted(myRay, 4);

• Where myRay is a Ray
• In this case we're looking for any point within 4m of the closest point on the ray
• Returns a SortedList where the keys are the distance (squared) and the values are the objects.

pointTree.GetNearby(myPos, 4);

• Where myPos is a Vector3
• Returns a SortedList where the keys are the distance (squared) and the values are the objects.

Debugging Visuals

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
}

• Must be in Unity's OnDrawGizmos() method in a class that inherits from MonoBehaviour
• Point octrees need the marker.tif file to be in your Unity /Assets/Gizmos subfolder for DrawAllObjects to work

Potential Improvements

See: https://github.com/Nition/UnityOctree