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!

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,

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

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

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!

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.