Hi everybody,
Having an octree for static scene is not a big deal, you know the size by computing the AABB, you can then make the 8 children recursively.
But what about a dynamic scene? How to have it efficient?

There is two problems at least:
1) How to have the moving object efficiently set to the new octree child node?
2) How to handle the new octree size when the octree has to grow or reduce his size?

One solution is to have 2 octree, 1 for static and 1 for dynamic, but not sure it's a good solution.
Another solution for scene with low dynamic object is just to have static octree and have dynamic without culling method, but works only for very small dynamic object list surely.

Thanks!

1 hour ago, Alundra said:

Hi everybody,
Having an octree for static scene is not a big deal, you know the size by computing the AABB, you can then make the 8 children recursively.
But what about a dynamic scene? How to have it efficient?

There is two problems at least:
1) How to have the moving object efficiently set to the new octree child node?
2) How to handle the new octree size when the octree has to grow or reduce his size?

One solution is to have 2 octree, 1 for static and 1 for dynamic, but not sure it's a good solution.
Another solution for scene with low dynamic object is just to have static octree and have dynamic without culling method, but works only for very small dynamic object list surely.

Thanks!

Octrees are not the most well known structures for managing dynamic scenes. But if you have moving objects (apart from dynamically changing world size as it seems you're talking about in your second point), loose octrees might be something you might have a look at.

I use octrees for a lot of different things, but generally I have octrees of spheres where the boundaries cross so they are kind of loose. They work pretty well.  This whole voxel world is built on a giant octree, with the root level being and ictree (icosahedron ).  It grows and shrinks as needed, and it also has chunking (3D prism chunks).  A chunk is simply defined as some point in the octree and everything below it. This means I can easily change chunk sizes as you zoom in and out.   I also used octrees before for doing JIT terrain (Just in time) for collision, which I plan to use here also. Finally I copy to a second octree for generating scenes with frustum culling.  Dynamic enough for you?

 

Looks very good but it looks to be octree for tessellation, so it's one time generated I think?
I talk about octree for Scene Management of game object containing mesh or light components.

4 minutes ago, Alundra said:

Looks very good but it looks to be octree for tessellation, so it's one time generated I think?
I talk about octree for Scene Management of game object containing mesh or light components.

It's not one time generated. It grows and shrinks as you zoom in and out and pan.  It's being rebuilt all the time in the video. Since all the terrain is procedural, it has to. Everything is built as you see it. Later I'll be putting game objects in it like trees and so forth. So it does also manage the scene.  From the main octree it copies to a second pair of octrees specifically for display, so as the world is rebuilt it can still display at a good frame rate.

I often use BVH with 8 children instead octrees. Allows more flexible refitting because there is no world space related quantization necessary.

I also use seperate dynamic / static branches of the tree. This also is easier with BVH because node intersections are no problem. 

Another possibility is to precalculate high quality trees, e.g. for the triangles of a mesh, and at runtime they can be moved around without a need to rebuild. For bounding box you need to travrese bottom up to refit them, but with bounding spheres it's only necessary to transform the centers (no dependencies across levels -> great for GPU). Only the top levels of the trees need to be rebuilt per frame. (Same idea as DXR uses)

Building / refitting on GPU works well. For that i usually build the 'little work' top levels at once with a single wide workgroup, and the bottom levels with small workgroups and dispatch per level. (No real difference here between BVH or Octree)

 

BVHs are generally easier. Sparse octrees are really neat and can speed up tracing a lot, they're the same as a signed distance field so you can estimate soft shadows with one sample, cone trace, etc. But they have scaling/updating problems that aren't solved yet.

On the other hand there's been a ton of work for realtime BVH lately, cause raytracing. Here's a very nice BVH updating paper: http://box2d.org/files/GDC2019/ErinCatto_DynamicBVH_Full.pdf

And as a bonus, a more efficient shape than a box, an axis aligned bounding octahedra: https://github.com/bryanmcnett/aabo