I'd love to see the tutorial going about Adaptive binary trees.
Below is a shameless copy&paste from gamedev.net where Yann L. esplains the basic concept.
This method seems like the way to go for highly dynamic environments as tree traversal is minimized.
Plus it seems like a really good challenge to implement, because of all the areas it touches upon.
Original thread on gamedev.netWhat it is, and how to build them
The basic concept is similar to both octtrees and BSPs. The geometry is exclusively stored in the leaves, the inner tree nodes are just helper nodes used in hierarchical culling. The difference between Octtrees/BPSs and adaptive binary trees (ABT) is that each node of the former ones does always describe a totally distinct region in space, whereas an ABT node can describe overlapping clusters. An ABT leaf contains the geometry, where each face is unique to a leaf (ie. a face can never be attributed to more than a single leaf).
To build one, start with the root node: create an axis aligned bounding box around your whole scene. Start a recursive subdivision function on it: At each recursive step, the bounding box gets subdivided into two parts, where both children will again be AABBs (unlike BSP trees). The division continues until either the number of faces in a node goes under a threshold, or the depth gets too large. The last created node will then be declared as leaf and contains the renderable geometry.
All this is pretty straightforward, with one exception: how does the node gets divided into two children. This is where it becomes tricky. The division plane is always perpendicular to one of the three major axes. So a node is either split along his X, Y or Z axis, creating two new nodes (both axis aligned). The position of the division plane, as well as the axis, is mathematically a minimization of the following criterions (and their respective functions):
a) good localization of space. The largest axis of the resulting child AABB must be minimized (this will favor division along the largest axis of the parent AABB) ( f1(pos) = max(split_x_axis, split_y_axis, split_z_axis) )
b) the volume of both child nodes should be more or less equal ( f2(pos) = abs(volume_child_1 - volume_child_2) )
c) the number of faces on both sides should be more or less equal ( f3(pos) = abs(face_count_1 - face_count_2) )
d) The number of split faces should be kept at a minimum ( f4(pos) = total_number_of_split_faces )
To find an optimal subdivision axis and position, you need to minimize all the functions above. Note that function c) and d) exhibit both discreet behaviour, so they can have lots of local minima (depending on the topology of the geometry). Each function above is weighted by an importance factor, so the final equation to minimize is:
f(pos) = f1(pos)*w1 + f2(pos)*w2 + f3(pos)*w3 + f4(pos)*w4
The weight distribution depend on your engine: where are the bottlenecks, how should the tree be balanced to make use of the optimized paths, how is your scene structured, how is your scenegraph organized (if any), etc.
One can use several ways to minimize the equation. We use a neural net. A different approach could use successive approximation, or simply sampling a set of positions and taking the one with the lowest f(pos).
At this point, you have the position and orientation of your division plane. Now, if you divided all geometry contained in the parent node at that plane, you'll notice that even though you minimized equation (d), you'll still have a lot of split faces. That's not good, so let's introduce a new feature of ABTs: you can overgrow them. The idea is that an ABT node does not need to represent a distinct region of space, but an approximative one.
Consider one of the two child nodes. Atttribute to this node all faces, that have the largest part of their area in the node's bounding box. You have lots of small faces sticking out of one of the six sides of the box: the one created by the division plane. Those faces would normally need to be subdivided. Now make the box a little bit larger on that axis. Quickly, the number of subdivided faces will drop, as more and more faces will be contained in the AABB. Do the same thing with the other node. Note, that both AABBs will now slightly overlap in the middle. The more you overlap them, the less efficient will the hierarchy of your tree be, so the growth factor should be made a maximal percentage of the boxes volume. I use between 5% to 10%, which eliminates almost 90% of the critical faces. Some really big ones will still need to be subdivided, but in a reasonably tesselated environemnt, those faces will be the minority.
Now it's time to optimize the volume. Because of the property of an AABB to encompass the whole volume of an object along it's primary axes, the AABB of the parent node often has a much larger volume than the combined AABBs of both children nodes. Mathematically expressed:
AABB1 + AABB2 <= AABB1 UNION AABB2
In octtrees, that's a necessary evil, and can result in lots of empty (or almost empty) nodes. But we can do better: for both child nodes, recompute the optimal AABB for the geometry they contain.
Continue the recursive process on both children, by supplying the newly formed AABBs as parameter to the recursive function. Do that until the process has terminated, and all leaves have been created.
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.
Rendering it
Very simple and extremely fast. Start at the root node. For each of the two child nodes, test their bounding boxes (those you recomputed in the last step of the tree creation) against the frustum. If they intersect, continue recursion along the branch. If you hit a leaf, render it.
Note that since a face has a unique leaf, you can directly store a vertex array/buffer in each leaf. So no array repopulation, no checking for doubles and already rendered faces, etc. Just a simple render vertex array/buffer call per leaf. You can't get faster than that (ignoring shader state changes of course, but they are very easy to integrate).
Making it dynamic
An ABT can be used on fully dynamic scenes. When an object moves, just move it's AABB along, and quickly reunify the AABBs of the nodes between the leaf and the root node. That's it. The problem is, that with time, when an object moves far away, the tree will slowly degenerate. It will still work, but it's culling efficiency will decrease. The sloution is to rebuild the degenarted parts of the tree on the fly, depending on degeneracy factors. But I won't go into details here, as it would double the lenght of this already very long post If there is enough interest, I could go into more detail here in another post.
/ Yann
2008/12/19 10:32:01
Tutorial 9 - any requests?
Hazy Mind XNA Engine
« 1 2 »
