The static objects in my game are organized in an AABB tree for optimized culling and various other operations. Each node contains two smaller AABB's within it. The tree is built recursively from the bottom up, each node looks for the optimal node to pair with and pairs are made recursively until there is only one node remaining being the root node of the tree. The problem I am facing is trying to find out what is the most optimal node to pair with. One would intuitively think that an AABB of the smallest volume would be the most optimal pairing criteria but this tended to create a lot of large flat objects which contained very little actual geometry and did nothing but cost me more culling checks to render. I found that a better way was to create a pair that had the smallest distance between its maximum and minimum xyz, this tended to create AABBs that took up less screen space and as a result saved computation. So here is my question: does anyone know how I would find AABBs containing two object picked from a set which tend to take up the least space on screen?
Pair finding for bottom up AABB tree
You will be able to find a lot of information on this area if you use the proper Google terms: “Bottom-Up BVH Construction”. Any tree of bounding volumes is a “hierarchy” of bounding volumes, or a Bounding-Volume Hierarchy.
As Wikipedia notes, what is best for your application depends on several factors. For example, my applications did not have large flat objects, so I did not encounter your pitfall.
There is no single best solution, but you want to minimize test-case overlap as much as possible, so in general you want objects that are as close as possible to each other and indeed typically result in the smallest total area for the box.
When it comes to traversing the BVH, the worst possible thing you can do is to not eliminate something that could have been eliminated earlier, so when constructing a good tree, it may work as a general rule of thumb to pick objects that are closest and smallest in area, because this eliminates said problem in general cases, but it still leaves the possibility that an object exists inside the bounding box above it in the tree but does not get culled at that higher level.
An algorithm tailored specifically to find and eliminate these cases will result in the fastest run-time performance.
L. Spiro
