ABTs, relaxing them and other questions

1.a) One side, the other sides are shrunk from the parent AABB. It's like using box-shaped soap bubbles to cover geometry and do some "tricks" where you split.

1.b) The idea is to minimize the amount of splits _and_ minimize the volume needed for all AABBs, so I'd say the "growth" could even shrink the AABB if there are no intersecting faces.

2) Let's say you're splitting up a cone from top to base into two AABBs. The upper AABB will of course be smaller than the lower one. Their parent, covering the entire cone, will fill up "dead space" (that the smaller, upper cone does not) in order to encompass both AABBs. Thus, the sum of the volumes of both AABBs is smaller than the AABB union. The sum is described as a volume, the union is described as an AABB.

That's the answers I got right now :)

I can't answer all of your questions, but I can clear up a few:

1 a&b) The growth is only applied to a single AABB at a time, and only enough to encompass the polygon in question.

Here's how I understood it: You create the split plane and then seperate the polygons to either side depending on which side their center falls on. More than likely some of these polygons will be overlapping that split plane. If you were to push that split plane out say 10-15% and it completely contained that border poly, then keep it in one piece and add it to the node. Otherwise, split the poly at the original split plane and put the newly split polys in their respective nodes. Once a node has been populated THEN you build a Bounding Box that contains all polys in the node. The bounding boxes will overlap slightly, but that's ok. No matter what happens, however, the bounding boxes will both fit entirely within the parent BB, so no other adjustments will be needed.

2) I think that he's just stating some of the mathmatics behind the structure, not nessicarily pointing out something that needs programming. What he's saying (as far as I understood) was that in Octrees you will end up with a lot of empty nodes because of their rigid structure. Those can reduce the speed of traversing the tree. In an ABT tree, however, you have no empty nodes, which keeps things clean and fast.

3) Can't really help you with this one. Sorry!

Quote:

Original post by dmatter Quote: by Yann L At this point, due to all the overgrowing and optimization, your original node hierarchy will be largely out of sync with the nodes themselves. So you need to rebuild it from the bottom to the top. For each leaf, walk up the tree, and recreate the bounding boxes for each node by unifying the child AABBs to the parent AABB. If everything went well, you'll end up with the same root AABB that you've started with. Your tree is now complete. Again, I don't completely understand what this actually achieves and what process actually occurs (apart from traversing up the tree [smile]).

What i think he is bascially saying you've optimized volumes of child/leaf nodes but the bounding volumes of internal nodes that make up the tree & its structure don't reflect the changes. This step should be very simple once you hit a terminal node walk up the tree all the way to root merging child node's BVs to give you new parent BVs (simple operation for AABBs).

Personally I never understood the last process. Last time I used ABTs, I started out by putting all geometry into one tight AABB. That AABB was split in its "longest dimension" with two planes that were sampled over some interval to minimize the weight function. I then constructed the child AABBs by fitting them tightly against the new separated chunks of geometry which included some split faces and kept recursing down to some limit. Since all AABBs are always fit tight against the geometry, there should be no need for any rebuild as no faces spontaneously pop out of any AABB and no dead space goes to waste (for example, Yann mentioned that the sum of the volumes of the children AABBs is less than the union of them, but it's evident all dead space at the resolution of the AABBs is eliminated). Did Yann let tight-fitting be a post process?

hey, thanks for the great response, between you all I think that I understand it all now [smile].

As far as integrating into a scene-graph system, I was thinking (very dangerous [wink]) should the spatial partitioning system be a node of the scenegraph? If so then because it contains geometry only then should it be a leaf node, or is there any reason why it should be a group node of the scene-graph?
Alternatively should spatial partitioning even be part of the scene-graph system, if this is so then where does it belong?

I think snk_kid had something about this a while back but I can't find it right now, perhaps I should just search for snk_kid + scene-graphs (actually thats not a bad idea).

One more thing, are ABTrees actually invented by Yann? Are/could there be any issues with using the algo (I mean legally of course) for any reason? (though I cant think why)

Again thanks for the help already.

It is quite easy. Say you have your polygon soup.
Now:
1. Create AABB around entire geometry

2. Find best separating axis (you must pick one). This plane that is parallel to either xy, xz or yz plane is going to cut your AABB in two pieces. Also, it will cut right through several faces. In order to minimize splitting, you overgrow child AABB on that side (maybe both of them) to encompass those faces. Now, all faces are in either first or second AABB.

3. Continue process until some condition (recursive end or min faces in AABB)

4. What has happened? When you have split your AABB, you overgrew them in order to minimize face splitting and now they overlap. Also, it may happen that theese AABBs are to big, that is, not optimal. cnosider following example

|-----------|----------------||           |            <>  ||        <> |      __        ||      <>   |     |  |       ||  <>       |     ----       ||----------------------------|

As you can see, these volumes are to big, You need to rebuild AABB starting from bottom up. That upper right polygon has made parent AABB to stretch vertically, but as you can see, he now belongs to right child and left child doesn't need to be vertically stretched to incorporate it.

*

To answer your questions:

Quote:

1) Yann talks about relaxing the bounds to fully encompass entire faces (to reduce splitting)... a) Is this growth only applied to one side of the AABB or all of them?

Applied on that plane which you used for spliiting.

Quote:

b) Is this growth applied to every AABB or do you detect if there are faces interescting the bounds of the AABB and only grow those particarlar ones?

The latter.

Was that helpful?

@ffx: Thanks for clearing up that the post-process just tightens all AABBs, I usually do that when I'm building the tree from the start though.

@dmatter: Just some words on scene-graphs: there are no specific ways to lay out scene graphs in, just put your ABT as a general node wherever it fits. You should try to avoid letting the scene graph see the internals of the ABT, independece makes additional weird representations of geometry easier to integrate. Whether or not the ABT-node shall be able to hold its own children is up to how you want your objects to "talk" (doors could work as children, but they probably do anyway :) ).

I'm pretty sure Yann figured out ABTs, but you can never know where ideas go.

Quote:

Original post by dmatter As far as integrating into a scene-graph system, I was thinking (very dangerous [wink]) should the spatial partitioning system be a node of the scenegraph? If so then because it contains geometry only then should it be a leaf node, or is there any reason why it should be a group node of the scene-graph?

I believe that Yann himself said at one point that it would be a good idea to have your ABT tree (containing only static geometry) as a single node of the scenegraph, rather than making the scenegraph a type of ABT tree. In essence he suggested that any dynamic objects (charecters, lights, etc.) were removed from the ABT tree and handled as seperate nodes of the scenegraph, this working under the assumption that the dynamic objects in a scene would be comparitively few and thus wouldn't be in as great a need for the heiarical (sp?) culling.

One should never use a static ABT for dynamic objects, its design fits best for rendering static geometry. In order to handle dynamic objects, one needs a pretty flexible data structure that can change shape and relocate objects nicely. Changing an ABT leads to a drop in culling efficiency and that is a very bad plan considering the entire world might be in the ABT. Another method is to insert big objects high up the tree in nodes big enough, but that might lead to having many big objects "seen" from everywhere leading to another drop.

Now, if the ABT would be a single scenegraph node, I see no problem with letting it have children. For example, you could have a dynamic object manager as a child node with objects that move within or near the boundaries of the ABT.

Onestly I don't see the problem to insert the dynamic elements into ABT.
It is just a tree, so the dynamic elements will be inserted in the node that fit the entire bounding box of it.


Bye,

Davide

The problem comes in the constant rebalancing of the tree that dynamic objects would require. Especially when you have objects that are overlapping borders. You don't want to split them, since that's way too expensive an operation to be doing in realtime, so you'll have to grow the AABB to include it. That can lead to a "lopsided" tree, and one that performs less than optimally.

Still, I guess it could be done. Just not the way Yann describes.

Quote:

Original post by Toji The problem comes in the constant rebalancing of the tree that dynamic objects would require. Especially when you have objects that are overlapping borders.

It's not written in milestone that the dynamic objects should inserted in the leaf node only.... so you leave the ABT plane as is and insert the dynamic objects in the best fit node (even a branch node).

I touched the problem with putting dynamic objects into the best fit node a few posts up, here's a concrete example:

Say you have an entire city in an ABT and some huge slime monsters sliming (running) about the streets. Even though the AABBs high up in the tree may overlap quite a bit, it may happen that if a monster crosses the border of two leaf AABBs in the ABT, the monster could rocket up the tree very close to the root node. To see this practically, draw a somewhat simple balanced ABT on paper (binary nodes pointing left and right downwards). Whenever a monster crosses the boundaries of the two middle leaves, it will be inserted into the root node if the overlaps are smaller than the size of the monster. Objects will be enclosed by huge AABBs (hundreds or thousands of times bigger than the object would be pretty common) and therefore "considered" (deemed visible, audible or similar) much earlier than if the objects were put in the leaves of custom trees.
Nodes close in some space can be far away in the data structure, this is a golden rule when it comes to trees.

The main idea with ABTs is that they are optimized for rendering specified static geometry that has been preprocessed. Dynamic objects do not have the same space relationships as the world at face-level, therefore using the same tree just isn't a good solution.

Quote:

Original post by coelurus Objects will be enclosed by huge AABBs (hundreds or thousands of times bigger than the object would be pretty common) and therefore "considered" (deemed visible, audible or similar) much earlier than if the objects were put in the leaves of custom trees. Nodes close in some space can be far away in the data structure, this is a golden rule when it comes to trees.

You have the same problem also in the OCTREE structure or Axis aligned BSP Tree: when the object cross a plane (an octant), it will be inserted in the parent node.
Where is the difference?

Davide

I'm not sure what difference you're referring to, but the common boxed trees all suffer from the problem mentioned. Boxed trees are very "strict" and don't "embrace" volumes that are often riddled with box boundaries and dynamic objects may cross those volumes wildly. I haven't investigated a lot of solutions for this problem yet (I soon will have to :) ) so I shouldn't speculate too much here...

Quote:

Original post by coelurus I'm not sure what difference you're referring to, but the common boxed trees all suffer from the problem mentioned.

This is exatly what I mean: all type of box-tree suffer from this problem. However , for example, renderware let you to insert the dynamic elements in the world partitioned tree with a bsp.
So The problem you claim ABT suffer is no a true problem or ,if you want to see that in another point of view, is the problem of all box tree structure but it is utilized many times! ;)

Davide

Quote:

Original post by davidino79 So The problem you claim ABT suffer is no a true problem or ,if you want to see that in another point of view, is the problem of all box tree structure but it is utilized many times! ;)

The fact that it is widely used doesn't mean that it is a good solution - it merely means that it is simple and easy to implement.

Inserting dynamic objects into the same tree as static geometry is a bad idea, regardless of the underlying structure. If you change the shape of the tree to match the dynamic objects, you'll lose culling efficiency on static geometry. If you don't modify it, then many dynamic objects will end up in the top levels of the tree (as coelurus pointed out in his example), and that is a performance nightmare. In a worst case scenario, the whole hierarchical structure loses its meaning in terms of spatial object relationship, and you'll end up with a brute force visibility checking of all your dynamic objects.

I have already addressed this problem a couple of times some years ago, but can't find the relevant threads anymore. Basically, one should always keep in mind that static geometry is fundamentally different to dynamic one, and both exhibit very different behaviour on spatial relationships. A static tree is almost never a good dynamic tree, and vice-versa. So in practice, it's always a good idea to use an independent tree for each geometry type: a static one that is tightly fit and ultra-optimized in a more expensive preprocess. And a dynamic one that, eventhough it might be less efficient from the point of view of culling ratio, is completely adaptive to the inserted objects and can be rebuild at runtime.

ABTs can actually be used for both types, but never in the same tree. Static ABTs were already explained. I touched the subject of dynamic ones a couple of times in the past, but I was being a little vague intentionally, because of a few technical problems we used to have, and because of IP related issues. Both problems are resolved today, and I can be a little more precise.

The basic concept turns around what we finally called a "liquid adaptive binary tree" (LABT). That's a modified form of an ABT, that allows to change shape and hierarchical relationships on the fly, with very little overhead. Temporal and spatial coherency is used to keep the tree structure almost 100% optimal, even if your objects move in completely unpredictable ways. We currently use an LABT implementation in our current visual system, which is able to handle thousands of simultaneously moving objects without a noticeable performance impact.

Let me find the relevant parts of the source (it's been a while I last touched that code), and I'll explain the process in greater details.

Quote:

I believe that Yann himself said at one point that it would be a good idea to have your ABT tree (containing only static geometry) as a single node of the scenegraph, rather than making the scenegraph a type of ABT tree. In essence he suggested that any dynamic objects (charecters, lights, etc.) were removed from the ABT tree and handled as seperate nodes of the scenegraph, this working under the assumption that the dynamic objects in a scene would be comparitively few and thus wouldn't be in as great a need for the heiarical (sp?) culling.

First part is true, the second not :) A SG should in fact hold instances of your dynamic objects, and the static ABT can definitely be a single node somewhere in the SG root. But you should never use the SG to determine visibility. In fact, a dynamic object should be inserted into two different types of trees simultaneously:

* As an SG node, which will handle its logical relationships with other objects or the environment (primarily for animation and AI)
* And as a node in a visibility structure optimized for hierarchical dynamic culling.

Ah, My apologies for the partial-misquote. Digging up the old threads to get the exact wording is a royal pain, though. (When are we going to get a real search function back?)

I'd be very interested in hearing more about your LABT method, though.

whoa! I didn't expect this sort of response to my initial thread :)

I would be highly interested in your LABTs if you could spare time to describe it.

I have another question concerning ABTs, Yann you once said (I can't find where anymore) that the purpose of rebuilding the node tree once you reach the terminal nodes (As snk_kid explained further up) is only necessary when you perform operations that might invalidate nodes such as (and i think this is right, forgive if its not) face swapping and node fusion.
Could someone possibly explain how and when node fusion would be done?

On a side note, I've never thought it a good idea to use the same structure for static and dynamic objects (it doesn't fit the conventions of my engine anyway).

Great responses so far though!