To accellerate the rendering i decided to implement a bounding interval hierarchy according to this paper, because it appears simple to implement, fast to build and numerical stable. In future versions i want to add a KD-Tree implementation to compare performance.
The building algorithm of a BIH-Tree works in the same way as QUICKSORT. Like QUICKSORT the primitives of a subtree are partitioned left (smaller) and right (greater) as to a pivot element. In a first shot i chose to randomize the selection of this element. The list of primitives can be sorted in place, so no extra memory is needed. The nodes themselves hold pointers to their children. There are more efficient ways to store nodes, which i will leave for future versions. The leaves store one index to the first triangle and the number of triangles contained. In doing so, the leaves are able to store more than one triangle. This comes in handy when the triangle intersection test is much faster than the tree traversal. A global constant specifies maximum number of triangles the leaves can contain.
To traverse the BIH tree for ray intersection tests, you need a ray – axis aligned bounding box intersection test. I implemented the unoptimized version described in this paper.
I finally got the BIH tree to work and rendered this well known teapot in under a second: