Sign in to follow this  
lordciriuz

multi-view scenegraph, kd-tree, ABT, BVH, static vs dynamic objects

Recommended Posts

I readed a lot of threads here on gamedev, papers and articles about spatial partitioning and scene management. I am learning a lot from you guys. I am redesigning my own 3d engine going to a multi-view scenegraph approach, using an object soup, where every object is linked through several specialized datastructures intended for optimizing different aspects such as object sharing, LOD, transformations, visibility culling, collision detection, animation, material (render state, shaders) and rendering. Regarding to visibility culling, I found two major approaches: BVH and spatial partitioning. I spent some time reading about kd-tree (axis aligned bsp), octrees, ABT (adaptive binary tree) and BVH, for static and dynamic objects. I know that it is also necessary to have an early traversal termination heuristic in order to achieve sublinear complexity. I found algorithms that take advantage of hardware occlusion queries for this purporse. I also know the importance of spatial and temporal coherence for issuing the queries and I found a few papers about that (ie: "Coherent Hierarchical Culling: Hardware Occlusion Queries Made Useful", J. Bittner et al). I know how to build each of these structures, but in the case of kd-trees I dont know how to place the spliting planes in some situations, for example, in an indoor enviroment with curve-shaped walls. Maybe I am wrong, and the kd-tree is not suitable for visibility culling in indoor environments. In order to achieve better culling, I know that static objects should be treated separately for doing expensive optimizations in preprocess and dynamic objects should be treated together into another tree optmized for spatial changes. I know that for static objects I should compute the PVS determing cell-to-cell visibility in preprocess. I think that this kind of task could be done using portals, but I am not sure if it is the only way. I also know that indoor and outdoor environment have significant differences about how should be treated. Some people said that kd-trees are not suitable for dynamic environments and others said the opposite. I read several threads in gamedev about ABT, claiming that it is well suitable for both, static and dynamic environments. So, I have a huge mix in my brain about that ;). I would appreciate if someone could point me to the right direction? Thanks in advance!

Share this post


Link to post
Share on other sites
In my opinion I think it is alright to just use one or two tree structure. For example, the ABT with the Octree.

In my humble opinion I think you can catergorize stuffs into:

Scenegraph -> Manage the scene objects, and their hierarchy
Octree -> Manages the spatialization of static objects in the scene.
ABT1 -> Manages the spatialization of dynamic objects and their changes.
ABT2 -> Manages the spatialization of Light volumes.

To render:
Cull Octree to get visible static objects
Cull ABT1 to get visible dynamic objects
Cull ABT2 to get visible lights

Draw static and dynamic objects to scene
For each visible lights do calculations.

I hope this helps you a little?

Share this post


Link to post
Share on other sites
Hi littlekid,

Thank you for your reply. What about calculating cell-to-cell visibility in an indoor environment? Should I use portals? How could I place the splitting boxes (or planes, in a general kd-tree) for matching indoor level geometry?

Thank you,

Share this post


Link to post
Share on other sites
For indoor geometry, it would be alright to calculate the PVS among each nodes. However for me, I reuse the same tree that I would split for a outdoor scene.

In my opinion, for the indoor geometry to be split properly, you may split them only room boundaries then further split the room if necessary.

Hope this help

Share this post


Link to post
Share on other sites
Ok, but what if my room boundaries are not axis-aligned or even regular? How should I place the splitting planes for building the tree? Regarding to PVS calculation, how should I evaluate cell-to-cell visibility? It should be made using portals? Is there another way?

Thanks in advance

Share this post


Link to post
Share on other sites
I think you can either do a rough estimation and split it at a axis-aligned plane/box. Which means neighbouring rooms may slightly overlaps, or just split it with a non-axis-aligned plane. And we will still be able to test whether we are infront or behind the plane by a Plane dot Coordinate.

As for PVS, you can precalculate them and store them in each node since room to room visiblity is static.

You can have something like:

Building
|---Room A (PVS: RoomB)
|---Branch node
|---Room B (PVS: RoomA, RoomC)
|---Room C (PVS: RoomB)


For example we test that we are in Room A, we draw Room A, PVS info tells us we can see Room B too, hence in addition, we have to draw room B too.

Share this post


Link to post
Share on other sites
But if I split at an arbitrary plane (non axis aligned) I loose an important advantage of using a kd-tree, such as the fast traversal. In that case I would be using a BSP, not a kd-tree.

Is it a good option to use kd-tree for walkthrough architectural environments?

tnx

Share this post


Link to post
Share on other sites
If it is only to strictly draw and handle architectural environments, like building-interior walkthrough, both KD and BSP are alright. However if you wish to allow your tree to handle both outdoor and indoor at the same time, you might wish to consider a separate tree(e.g octrees) for the outdoor part.

Another option that might work is to use a bounding volume tree.

Hope this helps

Share this post


Link to post
Share on other sites
I am considering to use a kd-tree for static geometry and ABT for dynamic one. I think that kd-tree is better than octree for an outdoor environment (sparse or dense occluded). because it isolates quickly large amount of geometries.

Thank you!

Share this post


Link to post
Share on other sites
Quote:
Original post by lordciriuz
I am considering to use a kd-tree for static geometry and ABT for dynamic one. I think that kd-tree is better than octree for an outdoor environment (sparse or dense occluded). because it isolates quickly large amount of geometries.

Thank you!


A kd-tree is a special case of BSP and an ABTree can be thought of as a kd-tree that is converted to a BVH so that its volumes can be further optimised.
As such, it may be reasonable to say that an ABT will generally outperform a kd-tree for both static and dynamic scenes.

A note on those dynamic scenes with ABT's; you mentioned the importance of spatial and temporal coherence, so if you take the ABT concept and combine it with this theory then you end up with a liquid adaptive binary tree.

Share this post


Link to post
Share on other sites
What exactly do u put into your ABT/Octree : the render primitive itself (a mesh, billboard) or a higher level object, like a LOD object that decides witch mesh it should draw? Where do u put objects that needs a constant update , like animated meshes and particle systems, and static ones that never needs to be updated, like the level's mesh?

Share this post


Link to post
Share on other sites
Quote:
Original post by Coluna
What exactly do u put into your ABT/Octree : the render primitive itself (a mesh, billboard) or a higher level object

For a dynamic entities spatial structure I populate it with higher level objects.
For a static scene spatial structure I populate it with a polygon soup.

Quote:
Where do u put objects that needs a constant update , like animated meshes and particle systems

High level logic, like updates, indicates they go in the scene-graph.

Quote:
and static ones that never needs to be updated, like the level's mesh?

As I said above, the static level geometry is partitioned into a spatial structure.

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter

A note on those dynamic scenes with ABT's; you mentioned the importance of spatial and temporal coherence, so if you take the ABT concept and combine it with this theory then you end up with a liquid adaptive binary tree.


Is there any additional information about LABTs?

Thank you!

Share this post


Link to post
Share on other sites
Quote:
Original post by lordciriuz
Is there any additional information about LABTs?

No, none really. I believe Yann is restriced on what information he is allowed to disseminate.

I don't think LABTs are particularly ground-breaking, they probably work much as you would expect.
I have a feeling that, prior to developing the term LABTs, Yann had a similar (possibly more infantile) implementation bootstraped onto classic ABTs. I'm referring to a mention in this thread; the quote of relevance is below:

Quote:
Original post by Yann L
Quote:
If you use an adaptive tree (which is what I think Yann and Eberly suggest), the problem is figuring out how you would keep your tree from quickly becoming mangled.
Yes, preventing tree degeneration is the key to truely making the adaptive approach work. There are several methods to that, but this is how we did it: each node has a degradation factor (d-factor), that states how much the node has shifted from it''s optimal shape and position. Parent nodes include all d-factors from their children. Various heuristics are possible here, eg. sum or median value. It will influence to reaction of the tree to spatial delocalization.

If an object is moved, it''s d-factor is updated, and this change is propagated up the hierarchy. As soon as the d-factor of a node reaches a critical threshold, the whole subbranch (starting from that node and including all of it''s children) is deleted from the tree, and rebuild from scratch. At this point, the rebuilt subtree is optimal again, so all d-factors are set to 0. This approach periodically renews parts of the tree that get too degenerated, and works pretty well. It also helps to minimize empty nodes: keep the tree as flat as possible (since flat trees are more efficient in terms of traversal speed and memory usage, if you have to visit every node), while still maintaining a good degree of spatial clustering.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this