Hello!

I was looking for a data-structure that is meant to handle sorting of 3d-objects, where every object, within trees or child trees, will potentially move/change their position, hence no static objects.

I am mainly curious if there is anything similar to an octree with a cheap update-complexity, because updating one element takes quite some iterations, e.g. recursively entering parent octrees, checking whether they fit in them or not...

I considered to roll out a 3d spatial hashing instead, as octrees' precision seems quite unimportant for my project as well. It would seem to be easier to update compared than an octree.

Why do I worry about performance? I really just would like to use the semantically most fitting structure. I often hear, quad- and octrees shine with static objects, because they allow a high precision via their branching of smaller trees within each tree. On the other hand, I totally do not need this, there is no complex collider either, just cubes.

I might be totally wrong on my performance-observations, though!

Summing it up, what would you recommend/use for a 3d-world with simple cube-colliders where every object is dynamic?

Thanks for your time!

Edit: Fixed terribly screwed sentences that were not even complete, sorry!

I'm far from an expert on this, but my understanding is you're looking for a Scene Graph

Maybe you could sort by Morton Code?

From that nearby objects can be found without the need for a hierarchy by iterating the list in both directions until stuff is too far away.

I'm also not an expert on this, but I've seen tutorials that teach you not to update the tree (octree, bsp tree, whatever), but to clear it out and build a new tree, every frame. While that is expensive, it's less expensive than re-sorting  to update an existing tree, and it's guaranteed to give you the correct results to render in any given frame.

25 minutes ago, masskonfuzion said:

I'm also not an expert on this, but I've seen tutorials that teach you not to update the tree (octree, bsp tree, whatever), but to clear it out and build a new tree, every frame. While that is expensive, it's less expensive than re-sorting  to update an existing tree, and it's guaranteed to give you the correct results to render in any given frame.

This depends on how you store a tree in memory (all children in order vs. a pointer to the next child), what kind of tree you use, how your dynamic / static object count ratio is ,etc. Updating trees can be fast and good, e.g. octree for collision detecten if the tree does not change much from frame to frame. (But in general i agree)

You can also use two seperate trees for static world / dynamic objects (in case of BVH just put both under the root node and done), so you only rebuild for dynamic objects.

Using BVH you can also only rebuild the top levels of the tree and just refit the bottom levels bounding volumes (makes sense if you have large static but moving structures like spaceships).

7 hours ago, Angelic Ice said:

I was looking for a data-structure that is meant to handle partial spatial sorting of 3d-objects, where every object, within trees or child trees, will potentially

The sentence is not finished, being confused...

7 hours ago, Angelic Ice said:

Summing it up, what would you recommend/use for a 3d-world with simple cubes-colliders where every object is capable of moving but also to be expect to move?

You mean expected NOT to move? more confusing...

Are all cubes the same size? Game like Minecraft? You want collision detection or something else?

36 minutes ago, JoeJ said:

The sentence is not finished, being confused...

Thanks for pointing out, I fixed it!

36 minutes ago, JoeJ said:

You mean expected NOT to move? more confusing...

Fixed this as well!

37 minutes ago, JoeJ said:

Are all cubes the same size? Game like Minecraft? You want collision detection or something else?

The gameplay is surely nowhere like Minecraft but the collision-world could be. Not all cubes have the same size, because terrain has a different cube-size compared to the player.

I want collision-detection and gravity-detection, which is pretty much just collision-detection on the height-axis.

There was a thread about spatial hashing recently: https://www.gamedev.net/forums/topic/689399-spatial-hashing/

Personally i'd start with a BVH (AFAIK most if not all physics engines use BVH now), and rebuild it every frame.

The fastest way to build is to run over all current objects to get the bounding box, then use the box center to sort the objects to the 8 resulting subspaces (child nodes) from that.

This gives not the best tree but quality does matter less than building time - usually.

Should be almost as easy to implement than a regular grid.

Deleting a tree data-structure just to rebuild it, with e.g. 200 objects every cycle, shall be more efficient than updating one or two moving objects? Wow! Really have to try that. Sounds like a massive amount of overhead per cycle. Wouldn't deleting an object that just moved and inserting them be a solution too? Though, I could see this become less efficient if every objects out of 200 would be moving at once, but that would never be the case on my end.

12 hours ago, JoeJ said:

Personally i'd start with a BVH (AFAIK most if not all physics engines use BVH now), and rebuild it every frame.

Thanks, I will totally read about BVHs!

5 hours ago, Angelic Ice said:

Deleting a tree data-structure just to rebuild it, with e.g. 200 objects every cycle, shall be more efficient than updating one or two moving objects? Wow! Really have to try that. Sounds like a massive amount of overhead per cycle. Wouldn't deleting an object that just moved and inserting them be a solution too? Though, I could see this become less efficient if every objects out of 200 would be moving at once, but that would never be the case on my end.

You did not tell those numbers, i assumed most of the world would move.

But first: 200 objects is not much - you wont see much difference. BVH build should take something like 0.1ms on one core (wild guess).

You don't need to delete if you rebuild. You did not intend to allocate each node with new, did you? This would be horribly slow. So slow that i did not try this again the last 10 years - maybe memory allocation is less expensive today, but i doupt it. Just preallocate enough memory and write your nodes in cache friendly order. (I also never use recursive function calls to build or traverse a tree - this has not only an additional cost, it also prevents you from understanding what happens. Better to use another preallocated memory  for stack, queue or however you call it. But that's optional. I have to say that most tutorials fail to show this things. They tell you how it works but not how to do it efficiently.)

For a 200 vs 2 objects ratio you're right and updating the tree should be faster than rebuilding. But you loose the property that you can write all child nodes in order (instead you get fragmented memory), and this will slow traversal down. You could traverse the result once to sort for memory order, but that's the same cost as a complete rebuild. Also you have to consider always the worst case, which is a larger number of moving objects.

You would need to implement multiple methods to profile for the fastest, but usually whatever you pick initially is fast enough. For 200 objects you don't need to worry anyways. Rebuild is easier to implement than update, and BVH is easier and more flexible than octree, so it's a good start and probably you'll keep it.