Efficient octree

[narushevich]

This is my first post, so I say hello to all of the community!)
I'm trying to make a game graphically similiar to Transport Tycoon, Simcity 3000, RollerCoaster Tycoon, but with mixed sprites+ simple 3d objects.

Here's what I had a year ago.
http://narushevich.lv/isometrica
Basically any of the available 3D engines would fit perfectly, BUT, as I found out it's hard to reproduce that feel of oldschool sprite graphics with sharp pixels etc. in 3D engine,

and  using engines such as three.js would be like running VW Beetle on jet engine.
That's why I decided to teach myself and write a simple 2.5D game engine, currently only with sprite rendering.

And it's already a while as I try to make an efficient octree, with realisation that wouldn't be tied to some game engine, and would be as reusable module.

What I have found on the web is:
- ThreeOctree - which is kinda efficent realisation of octree for three.js, but it's strictly tied to three.js.

- Few non-serious demo realisations - which was slow.

 

What I need:

- octree with grow/shrink functionality

- point & AABB support

- fast insert/remove

 

I have tried to do it myself, you can explores sources here:

https://bitbucket.org/narushevich/octree/src

 

But it takes ~30ms, to build tree of 10k AABBs on my i5 quad-core. That's slow.
I'm not going to rebuild whole tree on each frame, I rather update items that have changed their position/orientation.
Insert/remove is slow. Also it takes to much time to retrieve items. Mostly becauses of usage of indexOf's to remove item duplicates in resulting item array.

 

I had some test using typed arrays for Node and Item data structures, pooling then on startup. But that was even slower.

 

 

I created this topic in hope that someone could point me to already done super-fast octree/quadtree realisation!

It would be good if someone would also tell me the most efficient octree or quadtree writen in ActionScript or even C++, I would then try to port them to javascript.

[Ezelia]

I guess you need octree to handle collisions right ?

if so, and if you are using 2.5D and not real 3D, have you considered using simpler methods for collusions détection ?

[narushevich]

I guess you need octree to handle collisions right ?

if so, and if you are using 2.5D and not real 3D, have you considered using simpler methods for collusions détection ?

 

Actually no, I'm going to use it for view frustum culling. It's expensive to iterate over all objects in scene in order to detect if they should be rendered.

What do you mean as simpler methods?)

[Chris]

How many objects do you have there so that iterating over them actually gets expensive? Must be millions...

[Ezelia]

@narushevich in my isometric engine a collision occures when two objects are in the same grid node, so I only compare x and y coords everytime an object moves.
also, to avoid iterating over all object, everytime an object coord change I "attach" it to a global hashed array, so when another object moves to that same position, I detect immediately that there is another object there.

if you only iterate throught your objects without rendering them, number is not really an issue, I iterate/manipulate over about 4000 objects each frame without problems, what degrades performance is rendering, if you need to render each object then you can have performance issues.

[narushevich]

I have 10k objects to iterate, thats not a big problem. Problem is with multiple cameras/viewports. If there is multiple cameras/viewports then number of iterations multiplies to number of cameras.

[narushevich]

I have 10k objects to iterate, thats not a big problem. Problem is with multiple cameras/viewports. If there is multiple cameras/viewports then number of iterations multiplies to number of cameras.

[Gio]

I think you can easily get away with a quadtree rather than an octree. That's what I'm doing with my 2.5D engine anyway.

 

The thing is, if everything is on the same plane, the 3rd dimension doesn't count when you're determining what needs rendering, so things are actually much simpler.

 

One suggestion though: don't retrieve objects from your quadtree (or whatever data structure you choose to use) every frame. That is, doing a quadtree search that returns an array is going to be slow (you have to create the array, then insert lots of items into it, and these items would be objects with more than one reference, so there is some memory management overhead that happens behind the scenes too). If you can, reuse the array from the previous frame: most objects will be the same, add and remove only the ones that have changed and it should be much quicker.

[narushevich]

I've never thought that inserting int may be faster than inserting object. Thanks for hint. Ill rework code in order to manage only indexes to items and nodes rather references. And actually degrading implementation to quadtree doesnt give big performance boost , because it's just one check less in my implementation. Don't you mind to share your implementation?

[Gio]

I don't mind sharing, but I'm afraid that my implementation is also tied to our engine. I think you'll find that this is the case with any reasonably optimised implementation, as you will have to make some assumptions about the structure of the objects that go into your quadtree/octree.

 

Just to be clear, I insert objects into the quadtree, but I insert object indices into the array representing the quadtree query result.

 

In reality I have a few ways of retrieving objects from the quadtree. The simplest of them is flagging objects that are in the quadtree (setting a property of the objects that match the query to 1), so not returning an array at all. Then you still have to iterate through all your objects to see which ones have been flagged, which is not optimal, but this is still MUCH quicker than returning an array of objects. If you do it this way, you don't have to worry about duplicates. Also, keep in mind that in a 2.5D environment you may not need frustum culling tests at all - that is, this quadtree query effectively IS your culling code. In our engine, this looks like this:

QuadTreeNode.prototype.flagObjects = function(box, property){    if (wade.boxIntersectsBox(this, box))    {        for (var j=0; j<this._objects.length; j++)        {            var obj = this._objects[j];            if (wade.boxIntersectsBox(box, obj.boundingBox))            {                obj[property] = 1;            }        }        for (var i=0; i<this._children.length; i++)        {            this._children[i].flagObjects(box, property);        }    }};

Then I have another way of retrieving objects, that may be faster depending on the number of objects that you have (in my case I use this only when the object count is greater than 3000). This involves a couple of extra steps: I have an array of results (that contains object indices, not objects), and a result look up table to determine which objects need to be inserted/removed compared to the previous frame. In fact I have 2 of these look up tables: one for the objects of the current frame (resultLookup), one for the objects of the previous frame (oldResultLookup). It looks like this:

QuadTreeNode.prototype.getObjects_highCount = function(box, result, resultLookup, oldResultLookup){    if (wade.boxIntersectsBox(this, box))    {        for (var j=0; j<this._objects.length; j++)        {            var obj = this._objects[j];            if (wade.boxIntersectsBox(box, obj.boundingBox) && !oldResultLookup[obj.id])            {                result.push(obj.id);                resultLookup[obj.id] = 1;            }        }        for (var i=0; i<this._children.length; i++)        {            this._children[i].getObjects_highCount(box, result, resultLookup, oldResultLookup);        }    }};

But when you're finished visiting all your child nodes, you have to do an extra step, that is removing the objects that were in the result array from the previous frame, but are not supposed to be in the result array in the new frame. This is potentially quite slow, but it's typically only very few objects per frame (like 5 or 6).

for (var i=0; i<result.length; i++){    if (!resultLookup[result[i]] && oldResultLookup[result[i]])    {        wade.removeObjectFromArrayByIndex(result, i);    }};

Regarding your other points: a quadtree is a bit faster than an octree if you don't need the 3rd dimension and uses less memory, so I don't see any reason to go with an octree really.

 

Also, I don't see why you would need to worry about duplicate results as you mention in your first post: any object can only be in one quadtree / octree node at any one time, and you should not visit any node more than once per query, so duplicates should not be possible.

[narushevich]

Thanks for detailed answer and few ideas!) I have duplicates in cases when box'es are intersecting with multiple nodes!

[Gio]

Even then, I don't think you should have duplicates Objects should never be in more than one node, so even if you're visiting multiple nodes there is no way you can add an object twice, in theory.

 

To me the fact that there are sometimes duplicates suggests that there may be a bug somewhere in the quadtree/octree implementation?

[narushevich]

That's because I'm storing items only in leaf nodes.

Initially I was storing them  in leaf and branch nodes, but later I were suggested to rework code to store only in leaf and it seems now it was waste of time.

Also just now I've tried storing only indices to items, but that's somehow was slower rather then storing object itself, despite the fact that pushing int can be more than twice as quicker .

I guess that's because querying data of item by given index drawbacks all performance boost from usage of int.
Now I'm gonna rework back to storing items in branches+leafs and get rid of indexof's. This should give me the quickies version of my implementation.

Thanks for advice, Gio!)

[narushevich]

Thanks for idea about flaging items when retrieving. 
Now its under 2ms to retrieve 10k of items in requested node, instead of 300ms previously!)