Liquid Adaptive Binary Tree

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Liquid Adaptive Binary Tree

      Hi Guys,

      I've been reading about scene graphs and scene managements in Dave Eberly's book and in GameDev.net for the past couple of days. I've stumbled upon a thread in GameDev.net about ABT and or LABT which stands for Liquid Adaptive Binary Trees invented/popularized by Yann L. I haven't read through his explanation and design about ABTs yet and i think it wasn't finished due to somone stealing his idea and suing him.

      Just wanted to ask Rez, Mr. Mike or anyone who has some experience or knowledge about your thoughts on this? I've read from scanning through the topics that it can be very fast, efficient, and almost capable for almost all kinds of scene types.

    • RE: Liquid Adaptive Binary Tree

      I've never played with ABT or LABT, but I didn't find much real documentation, articles, or whitepapers on it either. It seemed to me to be a variant of a BSP tree. But, what I don't understand well is how it finds an efficient way of recalculating the partition placement at run time. It sounds like something that might not work well with games that have large, mostly static environments.

      But, since I don't know much about it at all, I'm just guessing.
      Mr.Mike
      Author, Programmer, Brewer, Patriot

    • Thanks, Mike!

      I've been digging through some of Yann L's replies in gamedev.net about ABT/LABT.

      Basically, ABT has a set of rules to follow that can be configured to build the most optimal tree. It can be configured parametrically with these set of rules:

      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 )


      But as you've said, although still possible to be used for dynamic objects, this is best to be used for static geometry. A separate/different tree will be used for managing dynamic objects. Yann L, and his partner, shortly developed LABT for handling dynamic objects very efficiently.

      Quote from Yann L.
      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.


      Quote: Original post by yahastu In all honesty, I doubt that even a very smart "liquid" algorithm could beat something simple like using a front/back-buffer mentality to rebuild an optimal kd-tree in the background and swap back when its completed.

      Yann L:
      It beats a full rebuild by orders of magnitude. And on top of that, it can also generate more efficient trees, since due to its predictive heuristics, it knows how the optimal tree will (most probably) look like many frames into the future.


      Sadly, there aren't any more details about his LABT after this. :(