Dev:Source/Render/BIHTree

The Bounding Interval Hierarchy

The incremental BIH tree after firing one ray diagonally through the standard Budhha model

The current method Blender employs for ray-scene intersection (i.e. efficiently intersecting every triangle in a scene with a ray) is the octree. While the octree is quite fast, it does not automatically adapt to scene geometry; it merely recursively divides the scene bounding box into eight children. The split locations at each recursion are always at the center of the bounding box.

However, there are many ray-scene acceleration structure options. In the graphics community, many papers and thesises have been written on the topic. Wald's PhD thesis showed that for the general case, the kdtree appears to have the most desirable characteristics.

So why a BIH tree for blender instead of a KDTree? The KDTree tends to have two problems: complicated implementation, and very slow building for a full surface-area-heuristic implementation. The SAH basically says that you pick the split location and dimension by checking all possible location/dimensions to see which one minimizes some cost function. This is what the BRL-CAD kdtree does, which is (badly) integrated into blender in this patch. This ran dramatically slower than the octree for the scenes I tested with, because the build times were longer than the render times!

So, I decided to implement the new kid on the block: the BIH tree. The paper describing it was just released recently. I decided, upon reading about the ease of implementation yet results comparable to kdtrees with extremely fast build times, to implement BIH for blender.

Plans in implementaion order

• [done] Write BIH intersection code
  • Though the code is clearly in need of bulletproofing
• Integrate BIH with blender
  • Add new tab to render panel

Links

• ompf raytracing forum
• ompf essential raytracing links - has several important papers and thesises

BIH Implementaion Details

• The tree is built incrementally; that is to say, only parts of the scene that have rays shot at them are indexed in detail.
• 64-bit clean
• Flat structure with (almost) no pointers; suitable for mmaping!
• Picture showing data structure coming soon.