Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!

Pair finding for bottom up AABB tree

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1 ic0de   Members   -  Reputation: 934


Posted 14 July 2013 - 10:13 PM

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?

Edited by ic0de, 14 July 2013 - 10:14 PM.

you know you program too much when you start ending sentences with semicolons;


#2 L. Spiro   Crossbones+   -  Reputation: 16190


Posted 15 July 2013 - 12:05 AM

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

Edited by L. Spiro, 15 July 2013 - 12:06 AM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.