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.
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 :)