Octree for Unity 2015-01-17

I'm honestly surprised that Unity does not have an Octree class built in (or at least it doesn't have one exposed to scripts). It's such a fundamental and useful structure for game development that almost everyone needs to use an Octree at some point or another.

Since there wasn't one already available in Unity, and even if there was it would probably allocate memory like crazy like many of Unity's built-in classes, I decided to write my own.

I've been using the one presented here in my Combat A.I. sandbox, and it's been pretty solid and fairly performant for me, so I thought I'd share it with anyone who was interested.


You can find basic API documentation here - http://stagpoint.com/docs/octree/annotated.html

ADDING AN ITEM TO THE OCTREE

When you add an item to an Octree, you will get an ISpatialToken reference in return. This token must be retained if the item to be added is not static and permanent, since the token is used to update the item's position as well as to remove it when done.

Code (C#):

void OnEnable()
{
   // Add this GameObject to the Octree and retain the ISpatialToken
   // instance so that the position can be updated later
   this.trackingInfo = SpatialDatabase.AddItem( this, this.collider.bounds );
}

UPDATING AN ITEM'S POSITION IN THE OCTREE

As mentioned above, you will use the ISpatialToken reference to update the item's position in the Octree:

Code (C#):

void Update()
{
   if( this.trackingInfo != null )
   {
     // Update the item's position in the Octree
     this.trackingInfo.Update( collider.bounds );
   }
}

REMOVING AN ITEM FROM THE OCTREE

Similarly, you use the ISpatialToken reference to remove the item from the Octree:

Code (C#):

void OnDisable()
{
   if( this.trackingInfo != null )
   {
     this.trackingInfo.Remove();
     this.trackingInfo = null;
   }
}

EXECUTING A QUERY

Code (C#):

// Execute an octree query looking for objects of type [Agent] that
// are within [radius] meters of [position].
using( var query = octree.ExecuteQuery<Agent>( position, radius ) )
{

   // NOTE: See the section below on MEMORY USAGE
   processResults( query.Results );

}

The Octree class also provides overloads for ExecuteQuery that allow for testing against an axis-aligned bounding box, a line segment, or an array of planes (like a camera frustum).


MEMORY USAGE

This Octree class uses object pooling internally so that it does not result in ongoing memory allocations, which will prevent the performance-killing garbage collection cycles that would result otherwise.

Because of this, you will want to either allocate your own SpatialDatabaseQuery instances and pass those to Octree.ExecuteQuery(), or use the pattern shown in the Executing a Query section, which automatically returns the query to the object pool ready for re-use.

This also means that you must not keep a reference to the query's Results list, since that list will also be recycled. If a persistent list is needed, you should copy the Results list to your own local list.

PERFORMANCE

This is certainly not the most optimized Octree class you could create, but in my current tests it is performant enough. Performing a query against an Octree with nearly 24,000 items in it, for each AI agent in the scene, only takes roughly 1ms per frame. This is of course highly dependent on what's being stored, how densely packed items are, and many other factors, but it's probably safe to say that even the most basic Octree structure can improve performance of proximity/visibility testing by several orders of magnitude over not using any broad-phase testing at all.

LICENSE

This code is released as open source under the MIT license.

The MIT License (MIT)

Copyright (c) 2015 StagPoint Consulting

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.​

 

This code is released under the MIT License. Sorry for the oversight.

I've made a few changes and additions to my local codebase since this was published, but haven't had the time to polish them enough to post an update. Hopefully I will be able to do so soon.

Hope this helps!

 

There's a Version History tab at the top of this page, which I will update when a new version is uploaded.

I may move it off to GitHub to try to encourage participation, though. If I do that, I'll update this thread and the Overview with the new link.

 

One problem with ProximityQuery appears to be that it's tests for determining full containment were broken.

Changing the appropriate overload for IntersectionTests.GetIntersectionType() to the following seems to resolve that particular issue (which seems to manifest when using small query radius):

Code (C#):

/// <summary>
/// Returns the type of intersection (if any) between an axis-aligned bounding box and a sphere
/// </summary>
public static IntersectionType GetIntersectionType( ref Bounds box, ref Vector3 center, float radius )
{

   var closestPointInBox = Vector3.Min( Vector3.Max( center, box.min ), box.max );
   var distanceSquared = ( closestPointInBox - center ).sqrMagnitude;

   if( distanceSquared <= ( radius * radius ) )
   {

     var c = closestPointInBox - center;
     var r = box.extents;
     var x = Math.Abs( c.x ) <= ( r.x - radius );
     var y = Math.Abs( c.y ) <= ( r.y - radius );
     var z = Math.Abs( c.z ) <= ( r.z - radius );

     if( x & y & z )
     {
       return IntersectionType.Contains;
     }

     return IntersectionType.Intersects;

   }

   return IntersectionType.None;

}