General-purpose Octree implementation

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.

 

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.

 

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.

 

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> ?

 

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.

 

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

 

Did a few small performance tweaks to this recently. It's now about 25% faster.

 

any updates?

 

I'm using that octree right now. It works very well already, but I would love to hear more about "linearizing the tree internally". I'm trying to drive 100k AI on screen and need all the extra perf I can find.

 

I found a Wikipedia article that said it's an octree that is entirely stored in a single array instead of a tree structure. That's the linear part I supose.

But how do they handle all the nodes, the childs, without slowing down the system by having to iterate the whole thing to find stuff? Having a hard time picturing it, could use some pointers.

 

To be honest I don't know that much about it myself, and wasn't easily able to find a lot of info, which is one reason why I never implemented it that way.

 

You can take a look how to store data in linear arrays for KdTree, which I was converting to DOTS (i.e. https://github.com/chanfort/kdtree-jobified-unity/blob/master/Assets/KDTreeStruct.cs#L31). I think similar patterns could be applied to octree/quadtree as well.

 

@Nition even today there is not much to be found on the subject. BTW how do you update the position of an object in your octree implementation? You remove it and add it at the new position?

@chanfort Thank you, I'll take a good look at it! BTW would this work in a regular project with the JOB system installed?

 

Yeah, it is using only built in job system, burst compiler and mathematics packages. It does not use any preview packages such as entities.