Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualL. Spiro

Posted 15 July 2013 - 12:06 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


#1L. Spiro

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 case, 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


PARTNERS