Rendering Competition 07/08

The Bounding Interval Hierarchy

Documentation: BIH class BIHNode class

We implemented this data structure to provide us with an acceleration structure that can be recomputed extremely fast even for huge numbers of rectangles and has quite qood performance, even when compared to SAH based KDTrees (which take orders of magnitude longer to build). We thus use it for objects with motion that cannot be defined with matrizes and for the overall scene. This results in a multi level hierarchy of per object acceleration structures, of which only the BIH structures will be recomputed.

We implemented a templated version of the BIH as described in C. W├Ąchter and A. Keller: Instant Ray Tracing: The Bounding Interval Hierarchy (pdf) to allow us to insert any kind of Traceable that provides the necessary getCentroid() and getBoundingBox() methods to compare against split planes.

We also extend the BIH by nodes that clip in another way: Instead of intervals from (-infinity,clip[0]] and [clip[1],infinity) we clip away empty space with the interval of [clip[0],clip[1]]. We use this when the splitting plane results in an empty list for one of the child nodes anyway.

As this was not one of the features mentioned on the RC sheet, we propose to weight this in the same way as a BVH Structure, for it also is an object partitioning scheme and has quite similar implementation complexity.