How to split ABT tree for portals
Author
Hi,
I have read through all the ABT links I could find here on gamedev, but I couldn't find the answer to my question. I would like to use an ABT for an indoor scene with hand-placed portals. Now it seems to me like I would need to split the ABT regions on portals, but this contradicts the algorithm where the ABT tree attempts to split on certain criteria, like keeping the poly count evenly distributed between child nodes.
So my question is, does anyone have any advice for how to split/use an ABT for a portal scene? Thanks!
I'm not quite sure what you mean, if you're trying to decompose concave sectors into convex ones ABT trees are not well suited for this task (as far as i'm aware).
ABT trees are really bounding volume hierarchies (BVH), in particular binary AABB trees using a top-down construction method and a splitting strategy similar to axis-aligned BSP trees.
Finding the best/good spliting plane is based on minimizing cost functions to gain the most optimial tree depending on the requirements. The cost function that Yann's gives is quite similliar to the one typically used for collision detection but tailored for efficent rendering not CD.
As with all BVHs these are not on spatial partitioning structures (partitioning space) they're geometric/object partitioning structures (partitioning objects/geometry) as such they don't not give you a strict spatial ordering or any spatial ordering at all because bounding volumes of nodes can and most likely will overlap.
However depending on BV type and construction method they can give you an approximate spatial ordering. The only real difference between normal AABB trees and ABT trees is that the construction of ABT trees try to minimize the amount of overlapping of child bounding volumes to give you an approximate spatial ordering.
I've never seen any BVH construction method or splitting strategy that has this requirement because virtually all the times when you need a BVH you really don't care much for spatial ordering for instance in the context of collision detection.
I assume the reason why Yann's originally choose a geometric partitioning structure over a spatial one is because BVHs have many advantages over spatial partitioning structures the're only down fall is there lack of a strict spatial ordering necassery in some contexts. He must of worked out or noticed that binary AABB trees using a kd-tree like construction method almost gives an approximate spatial ordering and then he added the requirement of minimizing volume overlap.
Anyways if you want to decompose concave sectors into convex regions you really want polygon aligned BSP trees. However now-a-days you don't really need to be so strict with sectors unless you want zero overdraw but it's not worth the effort as you'll most likely not gain anything from it if at all. Other than that it's only worth doing a decomposition into convex regions for collision detection but not for rendering.
[Edited by - snk_kid on May 21, 2007 11:49:33 AM]
ABT trees are really bounding volume hierarchies (BVH), in particular binary AABB trees using a top-down construction method and a splitting strategy similar to axis-aligned BSP trees.
Finding the best/good spliting plane is based on minimizing cost functions to gain the most optimial tree depending on the requirements. The cost function that Yann's gives is quite similliar to the one typically used for collision detection but tailored for efficent rendering not CD.
As with all BVHs these are not on spatial partitioning structures (partitioning space) they're geometric/object partitioning structures (partitioning objects/geometry) as such they don't not give you a strict spatial ordering or any spatial ordering at all because bounding volumes of nodes can and most likely will overlap.
However depending on BV type and construction method they can give you an approximate spatial ordering. The only real difference between normal AABB trees and ABT trees is that the construction of ABT trees try to minimize the amount of overlapping of child bounding volumes to give you an approximate spatial ordering.
I've never seen any BVH construction method or splitting strategy that has this requirement because virtually all the times when you need a BVH you really don't care much for spatial ordering for instance in the context of collision detection.
I assume the reason why Yann's originally choose a geometric partitioning structure over a spatial one is because BVHs have many advantages over spatial partitioning structures the're only down fall is there lack of a strict spatial ordering necassery in some contexts. He must of worked out or noticed that binary AABB trees using a kd-tree like construction method almost gives an approximate spatial ordering and then he added the requirement of minimizing volume overlap.
Anyways if you want to decompose concave sectors into convex regions you really want polygon aligned BSP trees. However now-a-days you don't really need to be so strict with sectors unless you want zero overdraw but it's not worth the effort as you'll most likely not gain anything from it if at all. Other than that it's only worth doing a decomposition into convex regions for collision detection but not for rendering.
[Edited by - snk_kid on May 21, 2007 11:49:33 AM]
Author
Thanks for that very helpful info, especially the distinction between spatial partitioning and geometric partitioning and convex decomposition, I really appreciate it. To clarify, I don't want to decompose concave sectors into convex ones, I just want to have sectors (rooms) in general. Maybe if I explain what my goal is it will help to illustrate.
In my simulation, the player will start outside of a home in an urban neighborhood. They can explore outside, or go inside the house. My thought was that the ABT would be useful to split up all the neighborhood geometry and home geometry for quick frustum culling. I just don't know how to combine that with a portal/sector setup once the player is inside the house.
My current thought is to model each room separately within the house, and have each room a separate object, along with furniture and other items. Each room would have a portal associated with it. I've been trying to follow what Yann talks about in the post entitled "combining octrees with bsp trees". One part in particular confused me about that:
Since the ABT splits arbitrarily and is not a spacial partitioning scheme like you mentioned, how can you enforce that "(a leaf will always belong to a single one, a node might belong to multiple sectors)"? It seems to me a leaf could potentially belong to multiple sectors, i.e. see image below:
I hope that clarifies my setup, any further guidance would be greatly appreciated. I might be totally off on my conceptual map of this whole idea (seems to happen to me a lot ;)
In my simulation, the player will start outside of a home in an urban neighborhood. They can explore outside, or go inside the house. My thought was that the ABT would be useful to split up all the neighborhood geometry and home geometry for quick frustum culling. I just don't know how to combine that with a portal/sector setup once the player is inside the house.
My current thought is to model each room separately within the house, and have each room a separate object, along with furniture and other items. Each room would have a portal associated with it. I've been trying to follow what Yann talks about in the post entitled "combining octrees with bsp trees". One part in particular confused me about that:
Quote:How to render a scene using such a structure ? Very simple, actually. First, traverse the hierarchical structure (octtree, OBB, ABT, whatever you used). For each node, check if it is in the frustum. If yes, then check to which sector it belongs to (a leaf will always belong to a single one, a node might belong to multiple sectors).
Since the ABT splits arbitrarily and is not a spacial partitioning scheme like you mentioned, how can you enforce that "(a leaf will always belong to a single one, a node might belong to multiple sectors)"? It seems to me a leaf could potentially belong to multiple sectors, i.e. see image below:
I hope that clarifies my setup, any further guidance would be greatly appreciated. I might be totally off on my conceptual map of this whole idea (seems to happen to me a lot ;)
It sounds like you're trying to force an AB-Tree to behave like a Quake-style polygon-aligned BSP tree.
I think you have two good options:
1) You could partition your urban neighborhood geometry using an ABT and partition the house using a polygon-aligned BSP tree and switch between the two when the player enters/leaves the house.
2) Consider that you're house is static geometry, as is the urban world around it, you could simply partition the scenery and the house under the same ABT. Modern GFX cards are powerful beasts and depending on the complexity of the house you may even find your entire house is contained within one leaf node of the ABT and can be sent to the GFX card all in one batch.
Under this approach you could still use a portal/sector system, each sector is the size of an entire 'level' with its own ABT and portals join sectors to form a massive seamless world with sectors being streamed from the hard-drive/disk before the player steps through the portal. Sectors need not be regular volumes either they could be arbitrary shapes.
Hope thats some help
I think you have two good options:
1) You could partition your urban neighborhood geometry using an ABT and partition the house using a polygon-aligned BSP tree and switch between the two when the player enters/leaves the house.
2) Consider that you're house is static geometry, as is the urban world around it, you could simply partition the scenery and the house under the same ABT. Modern GFX cards are powerful beasts and depending on the complexity of the house you may even find your entire house is contained within one leaf node of the ABT and can be sent to the GFX card all in one batch.
Under this approach you could still use a portal/sector system, each sector is the size of an entire 'level' with its own ABT and portals join sectors to form a massive seamless world with sectors being streamed from the hard-drive/disk before the player steps through the portal. Sectors need not be regular volumes either they could be arbitrary shapes.
Hope thats some help
Hmmm interesting, I read many of those Yann's posts but I don't remember seeing "a leaf will always belong to a single one, a node might belong to multiple sectors".
I guess maybe you'd need to take portals into account on the splitting functions... or if you don't do that, you could store in the node a list of the sectors it spans... or... you could use an ABT for each sector and when you determine a portal is visible, check which sector is next and check its ABT... sorry maybe all this is nonsense hehe, but it's an interesting question... I'll keep checking this thread.
I guess maybe you'd need to take portals into account on the splitting functions... or if you don't do that, you could store in the node a list of the sectors it spans... or... you could use an ABT for each sector and when you determine a portal is visible, check which sector is next and check its ABT... sorry maybe all this is nonsense hehe, but it's an interesting question... I'll keep checking this thread.
I made some minor mistakes earlier, the main difference between BVH and ABT trees is children volume overlap is minimized/minimal but at the cost of splitting some primitives (making (a few) more polys than there originally where), with BVHs normally you never split primitives that intersect the splitting plane you typically put them into the side there centroid belongs in or just a pick side and then compute the bounding volumes of each subsets.
In both BVHs and ABT trees (typically) leaves are always unique, there are never any of the same polygon(s) in more than one leaf/node.
I also probably over exaggrated the part that BVHs have many advantages over spatial partitioning structures, there main advantages are you don't have the issues of splitting primitives and there easier to deal with movable objects or dynamic/deformable meshes.
In both BVHs and ABT trees (typically) leaves are always unique, there are never any of the same polygon(s) in more than one leaf/node.
I also probably over exaggrated the part that BVHs have many advantages over spatial partitioning structures, there main advantages are you don't have the issues of splitting primitives and there easier to deal with movable objects or dynamic/deformable meshes.
Author
Thanks everyone for your input, I'll try to respond to all the feedback.
@dmatter:
Those are some good options, although I'm trying to avoid using bsp if at all possible. Unfortunately the house is over 70,000 triangles and it has already given me some performance issues so I don't think I can stream the whole thing to the graphics card (although you're right, graphics cards are very powerful beasts :) Having a huge streaming world would be awesome, but for now I only have a small amount of time and so for simplicity am just working on a single scene that (hopefully) can be all loaded into memory at the level load.
@Elefagente_Secreto:
Taking portals into account for the splitting functions is a good idea, but I'm afraid it might lead to an unbalanced tree (i.e. leaf nodes would not have very equal amounts of geometry), maybe forcing the ABT to try to be too much like the polygon-aligned bsp tree as dmatter mentioned. Keeping a list of the sectors an ABT spans sounds like a good idea.
@snk_kid
Thanks for the further clarifications.
So far I've been working in Maya trying to split up every room so each room is a totally separate object, and that seems to be a good way to start off, but I still wonder if there is a better way.
@dmatter:
Those are some good options, although I'm trying to avoid using bsp if at all possible. Unfortunately the house is over 70,000 triangles and it has already given me some performance issues so I don't think I can stream the whole thing to the graphics card (although you're right, graphics cards are very powerful beasts :) Having a huge streaming world would be awesome, but for now I only have a small amount of time and so for simplicity am just working on a single scene that (hopefully) can be all loaded into memory at the level load.
@Elefagente_Secreto:
Taking portals into account for the splitting functions is a good idea, but I'm afraid it might lead to an unbalanced tree (i.e. leaf nodes would not have very equal amounts of geometry), maybe forcing the ABT to try to be too much like the polygon-aligned bsp tree as dmatter mentioned. Keeping a list of the sectors an ABT spans sounds like a good idea.
@snk_kid
Thanks for the further clarifications.
So far I've been working in Maya trying to split up every room so each room is a totally separate object, and that seems to be a good way to start off, but I still wonder if there is a better way.
I really didn't design ABTs to work with portals in mind at all. In fact, they were designed to work in combination with an occlusion culling system (software at the time, hardware nowadays), which entirely replaces portal based approaches.
You can probably make them work in a portal based system, but I wouldn't expect them to perform very well.
70k faces is virtually nothing for a modern graphics card. In fact, if your level is only that small, doing any kind of portal system will probably make you lose speed compared to just brute forcing the entire thing at once. Of course, the data needs to be uploaded as a static resource to the card, not dynamically streamed. ABTs also have a certain CPU overhead, that can be much larger than other structures, if applied to very small scenes. The "happy spot" of an ABT is generally around a couple of million faces. 70k is too low for it to perform adequately.
If you're having performance problem with such a small data set, then this means that there is a serious bottleneck somewhere else in your engine. You should definitely check this before venturing any further into spatial acceleration structures.
You can probably make them work in a portal based system, but I wouldn't expect them to perform very well.
Quote:Original post by trs79
Those are some good options, although I'm trying to avoid using bsp if at all possible. Unfortunately the house is over 70,000 triangles and it has already given me some performance issues
70k faces is virtually nothing for a modern graphics card. In fact, if your level is only that small, doing any kind of portal system will probably make you lose speed compared to just brute forcing the entire thing at once. Of course, the data needs to be uploaded as a static resource to the card, not dynamically streamed. ABTs also have a certain CPU overhead, that can be much larger than other structures, if applied to very small scenes. The "happy spot" of an ABT is generally around a couple of million faces. 70k is too low for it to perform adequately.
If you're having performance problem with such a small data set, then this means that there is a serious bottleneck somewhere else in your engine. You should definitely check this before venturing any further into spatial acceleration structures.
God, I still remember those shots of the four million poly cathedral or whatever it was, running with shadowing and lighting on a GeForce 4. I still would be blown away by seeing that sort of thing on an Xbox 360 today.
[EDIT] I found the shot.
That was posted four and a half years ago, Jan 2003.
[EDIT] I found the shot.
Quote:Approx. 290000 polys visible, 67 fps on a GF4. Not a single lightmap used. 100% dynamic perpixel lighting with shadowmaps:
...
There are 290k faces visible in that frame. The cathedral model itself is approx. 4 million faces. The complete level (there is a terrain and town outside) takes 48 million faces.
...
Large parts are parametric surfaces (NURBS, NURMS, spline surfaces). Those are tesselated at runtime, and make up approx. 30m faces of the 48m. The remaining 18m are hand modeled triangular meshes. You are right, scenes of that size are not manageable in a modeller. We use SGI workstations, but still it's too much. So we split up the scene into several smaller parts (4 to 5 million faces each). The complete scene gets merged and compressed into a single one at level compile time.
That was posted four and a half years ago, Jan 2003.
Author
Thanks for the info, I should clarify about the performance. If I'm just rendering the geometry I get well over 400 fps, but the problem arises when I try to throw shadows in (I'm attempting to have all real-time shadows, no lightmaps) so maybe the issue is with the shadowing algorithm. I can even use normal-mapped shaders and I'm fine with performance. I will definitely check this issue out before worrying much more about spacial stuff.
Sorry if I took your ABT out of context Yann, I'm so new to this I'm just trying to get a grasp of all the concepts available. Curious, are ABT's still best for narrowing down large amounts of outdoor geometry for frustum culling? Would the best system be to use that for a large outdoor level then switch to something else for inside? Eventually I do plan on having much larger levels so spacial efficiency will most likely be an issue, thanks.
Sorry if I took your ABT out of context Yann, I'm so new to this I'm just trying to get a grasp of all the concepts available. Curious, are ABT's still best for narrowing down large amounts of outdoor geometry for frustum culling? Would the best system be to use that for a large outdoor level then switch to something else for inside? Eventually I do plan on having much larger levels so spacial efficiency will most likely be an issue, thanks.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
