   multi-view scenegraph, kd-tree, ABT, BVH, static vs dynamic objects
  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!   
  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 hierarchyOctree -> 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 objectsCull ABT1 to get visible dynamic objectsCull ABT2 to get visible lightsDraw static and dynamic objects to sceneFor each visible lights do calculations.I hope this helps you a little?   ;  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,;  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   ;  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;  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.   ;  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   ;  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   ;  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 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.   