Search Unity

  1. Unity 2020.1 has been released.
    Dismiss Notice
  2. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    Dismiss Notice

General-purpose Octree implementation

Discussion in 'Assets and Asset Store' started by Nition, May 9, 2014.

  1. Nition

    Nition

    Joined:
    Jul 4, 2012
    Posts:
    753
    I wrote a general-purpose octree recently for my game Scraps. I was going to put in on the Unify Wiki but I'm waiting for them to approve my account, so I've put it up on GitHub: https://github.com/Nition/UnityOctree

    Before making this, I was looking for octree implementations and couldn't find anything that wasn't super basic or ancient, so maybe this can help to fill the gap a little. This is a dynamic, loose, general-purpose octree implementation. Someone can probably make it faster and better than I managed, but it may be useful to some. It's easy to use and pretty efficient.
     
    Last edited: May 9, 2014
    MarkTension likes this.
  2. lilymontoute

    lilymontoute

    Joined:
    Feb 8, 2011
    Posts:
    1,181
    Looks solid! I've worked with a few spatial partitions in C# so far (including octrees) - the #1 performance recommendation I could give would be to take a look at linearizing the tree internally (representing all of the nodes in a one-dimensional array, and then pointing to indices). It dramatically increases performance in pretty much all cases. Of course, it makes the code a lot less readable, so there's a trade-off in that sense.
     
  3. Nition

    Nition

    Joined:
    Jul 4, 2012
    Posts:
    753
    Thanks, that makes a lot of sense! Traversing through the nodes is easily the slowest part of doing anything with the tree at the moment. I'll look into it.
     
    Last edited: May 9, 2014
  4. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    623
    More than half year passed, so maybe thread is dead, but probably worth to ask. I am working with simple lists of Vector3 and my interest is to find nearest neighbours as soon as possible. I am currently using
    http://forum.unity3d.com/threads/point-nearest-neighbour-search-class.29923/
    algorithm for NN searches, however I would be very interested to compare its performance with your octree implementation. How I can access simple NN search in List<Vector3> ?
     
  5. Nition

    Nition

    Joined:
    Jul 4, 2012
    Posts:
    753
    Hi, the octree would need a couple of changes to do what you're looking for.

    - You would use the PointOctree but at the moment it expects a GameObject and a Vector3 position for each entry rather than just a Vector3. You'd need to change the Add method to take just a vector instead of an object and a vector, and then just strip out the rest of the object related stuff. Instead of returning an object you'd return the position vector instead.

    - I only implemented a method to find nearest neighbours to a ray (PointOctree.GetNearby), because that was what I needed. Assuming you want to find nearest neighbours to a point, that needs to be added as a feature. It should actually be simpler than the ray-based method.

    If I had a bit more free time I'd make those changes for you but I don't really have time at the moment sorry.
     
  6. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    623
    Transitions between GameObject <=> Transform <=> Vector3 looks quite easy ones, but nearest neighbour to the point still looks a bit tricky. P.S. isn't that true, that ray is just special case and can be unified with point-point NN search algorithm?

    Well, I will keep looking for news in the future then :)
     
  7. Nition

    Nition

    Joined:
    Jul 4, 2012
    Posts:
    753
    Did a few small performance tweaks to this recently. It's now about 25% faster.
     
    hippocoder likes this.
unityunity