Jump to content
  • Advertisement
Sign in to follow this  
lordciriuz

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

This topic is 3771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!