Welcome to Our Community

Welcome to our support forums. We hope you find the information you are looking for. Please note that some areas of these forums are not visible to guests, and require a forum account. Registration is free and easy, and we won't spam you or share your email address with anyone.

Sign Up
  1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Octree for Unity 2015-01-17

A basic Octree implementation for Unity

  1. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    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.

    octree-snapshot-2.png
    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.​
     
    #1
  2. Danothom

    Danothom New Member

    Joined:
    Feb 26, 2015
    Messages:
    3
    Likes Received:
    0
    I notice you don't have any kind of license attached to your packages apart from a blanket 'copyright'. As such I believe that drives away most interest as that's just murky water.

    If you're interested in sharing these great Unity tools, then I suggest you either choose a CC license and add visibility of it so as to reduce ambiguity/confusion!
    http://creativecommons.org/choose/

    For example. I'd love to use this Octree and I think the implementation is great - but, like most devs, I stay away from anything without a clear licence, even if it is in 'the public domain' so to speak.

    Thanks.
     
    #2
  3. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    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!
     
    #3
  4. Danothom

    Danothom New Member

    Joined:
    Feb 26, 2015
    Messages:
    3
    Likes Received:
    0
    I really appreciate the prompt response. I've been dying to integrate your Octree into my engine. With the MIT license it looks like it's finally viable.

    Also, if you're improving and evolving the codebase, then perhaps placing a link at the bottom of the article pointing to the latest dev or stable repo (git/gist/bit etc) would keep things current.

    Anyways, great site and resources, and thanks a bunch!
     
    #4
  5. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    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.
     
    #5
  6. Danothom

    Danothom New Member

    Joined:
    Feb 26, 2015
    Messages:
    3
    Likes Received:
    0
    Hi. So I got around to finally using you Octree implementation a bit more recently and, after throwing in some visual Gizmo debugging, I'm having some issues with query radii.

    The ProximityQuery appears to be behaving very strangely. Initially I thought that perhaps you'd mistakenly used the term radius when in fact you meant diameter. However while the BoundsQuery appears to be working correctly, simple tests with a ProximityQuery give me really random (read:broken) results.

    I'm assuming that intended behaviour for a ProximityQuery from a position using a radius of 5f should query all Octree entities within a sphere from the origin with a radius of 5m. However, as mentioned already, while the Unity Gizmo correctly draws a sphere with a radius of of 5m, the entities the query is displaying are far outside of the 5m radius, sometimes in an uneven, non uniform pattern.

    Any insight would be appreciated, thanks.
     
    #6
    • Agree Agree x 1
  7. StagPoint

    StagPoint Administrator
    Staff Member Verified Customer Beta Tester

    Joined:
    Dec 3, 2014
    Messages:
    20
    Likes Received:
    0
    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;

    }
     
    #7

Share This Page