Using BIHs for dynamic geometry

Since the Utah 3D Animation Repository has some nice keyframed animations I had to try to do some animations with my ray tracer. My first approach was to simply create a new BIH each frame representing the interpolation between two keyframes. Already I could ray trace some nice animated models in real-time, although at rather low resolutions. Still, this shows how efficient the in-place BIH construction is. I wasn't quite satisfied yet though, so I implemented lazy construction of the BIH (what Wächter and Keller refer to as construction on demand). If I'd been coding the ray tracer in Haskell instead of C++ I guess I'd gotten lazy construction for free :) Anyways, lazy construction gave a nice little speed-up of up to 20% in some cases.

I then got an idea that I decided to try out. I noticed that for some models the difference between successive keyframes would be rather low. Thus, I implemented an approach where I precompute one BIH for each pair of successive keyframes in the animation. For the part of the BIH construction that needs the bounding boxes of the triangles in a model I simply use the unions of the bounding boxes of the triangles in the successive keyframes. I then do the interpolation between two triangles in the keyframe pair every time a ray intersects against a leaf node containing the id of the given triangle pair. A single BIH can thus be used to intersect against all possible interpolations (in the range [0,1]) between two keyframes. This gives a big boost to the frame rate in the cases where the BIH construction is the bottleneck.

The table below shows frame rates achieved with the different approaches. "Eager" is the approach where the full BIH is recomputed for each frame, "Lazy" is the approach where only the parts of the BIH that are needed are recomputed for each frame, and "Precomputed" is the precomputed BIH approach.

	200x200			800x800
	Eager	Lazy	Precomputed	Eager	Lazy	Precomputed
Wood doll	35.2	35.7	44.2	3.32	3.49	3.00
Hand	15.5	16.5	23.4	1.88	1.90	1.57
Ben	5.37	6.32	21.9	1.97	2.05	1.45
Fairy	1.55	1.61	0.59	0.28	0.28	0.03

The table demonstrates the small but consistent performance increase that lazy construction gives compared to eager construction. The interesting part however is how the precomputed BIH approach compares to recomputing the BIH each frame. First, note that it is consistently slower at 800x800, because at that resolution the ray traversal and intersection becomes the bottleneck, and thus the tighter fit that the recomputed BIHs give cause them to outperform the precomputed ones. For animations where there is a lot of change between successive keyframes precomputed BIHs perform very poorly as the results from the "Fairy" animation show (the animation contains a lot of movement in just 21 keyframes). The "Ben" animation however shows that when there is little change between successive keyframes _and_ the BIH construction is a bottleneck (when there is a low amount of rays hitting the model for example), then the precomputed BIH approach really shines. A possibility might be to use precomputed BIHs when viewing a model from a distance, and then swap to recomputed BIHs once we're up close. One thing I didn't take into account is that more time can be spent to improve the quality of the precomputed BIHs, as they are only computed once. In my current implementation I use the same construction heuristics for both precomputed and recomputed BIHs.



The picture above shows what a single frame of the "Ben" animation looks like in 200x200. That's all for this post, and I hope someone will find the precomputed BIH approach interesting :)