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

## Recommended Posts

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

##### 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 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 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 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 on other sites
Quote:
 Original post by lordciriuzI 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 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 on other sites
Quote:
 Original post by ColunaWhat 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 on other sites
Quote:
 Original post by dmatterA 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.

Thank you!

##### Share on other sites
Quote:

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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628348
• Total Posts
2982207

• 10
• 9
• 24
• 11
• 9