Sign in to follow this  

How to split ABT tree for portals

This topic is 3859 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

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!

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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:

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 ;)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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.

Share this post


Link to post
Share on other sites
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.
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Promit:
Oh yeah, this one. Sadly, the game was sacked. Oh well.

We're using billion face data sets today, streamed over Myrinet fibre channels from a SAN, and rendered to Barco CAD walls with stereo and head tracking :)

Quote:

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.

The best choice of a spatial structure depends a lot on the way you design your engine, and on the type of 3D geometry you use. ABTs, and Kd trees in general, are designed for a certain type of geometry. The idea behind them was to eliminate the need to diferentiate between outdoor and indoor gemoetry, and to avoid having to conform the modelling to some arbitrary limitations such as portals.

But if you have a very closed, room-like geometry, with sporadic outdoor parts (read: Doom3-like), then portals and quadtree terrain rendering might still be the best approach.

Tell us a little bit more about your levels or scenes, and we can see what might be the best fit for you.

Share this post


Link to post
Share on other sites
!!!!!!! That image is amazing, not to mention a dataset in the billions of triangles! I have a lot to learn that's for sure! Thanks for the interest, you all are life savers for beginning game designers like me :)

A typical level will be a combination of indoor and outdoor, mostly resembling urban neighborhoods/cities. My test level right now consists of a cul-de-sac neighborhood, with one main house at the end of the circle, the street, and several side houses with fence and backyards.

Players can start out at any point in the neighborhood, so they very well could start outside, run into a house, explore, go back outside, go into another house, etc. I guess that's why I'm a bit confused as to how to proceed since I don't have the luxury of keeping the player in a nicely confined house.

That's why I thought if the player was inside of a house, maybe a good way to go would be to use an ABT to quickly cull away the rest of the neighborhood and even somehow the rest of the rooms in the house to quickly isolate which room the player was in. Then I thought about using portals from that point on, but only if the player was inside the house. If they were outside, ABT would be all that was used.

However triangle count even with shadows and the entire neighborhood in the frustum was 400K, so maybe I don't even need partitioning as mentioned, however when I do get larger datasets (i.e. an entire city is a level) I would like to have some kind of an action plan. I hope that gives some better info, thanks.

Share this post


Link to post
Share on other sites
As Yann mentioned ABTrees remove the need to differentiate between indoor and outdoor scenes, I think if you want a (nearly) good-for-all solution then go for my second point I gave earlier [smile],

Quote:
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.

Share this post


Link to post
Share on other sites

This topic is 3859 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this