4/30/07

Geometry instancing

Just implemented geometry instancing, so I wanted to share some renders with you. This scene contains one million instances of the hand model, which in itself contains 17135 polygons. Each instance is simply defined by a transformation matrix specifying its position and orientation. Performance doesn't suffer significantly from instancing either, as I use a top-level BIH for the instances.


4/28/07

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.

200x200800x800
EagerLazyPrecomputedEagerLazyPrecomputed
Wood doll35.235.744.23.323.493.00
Hand15.516.523.41.881.901.57
Ben5.376.3221.91.972.051.45
Fairy1.551.610.590.280.280.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 :)

4/26/07

Ray tracing again

I recently started working on a new ray tracer. I've started from scratch redesigning everything to create a core that's both efficient and flexible enough to allow me to experiment with various algorithms and techniques. I created this blog to act as a journal on my progress, as well as a scratch-pad for random thoughts and ideas. This is also my first attempt at blogging, so if it shines through bear with me :)

The status quo is a ray tracer which supports the obj and ply model formats. I've already done some ray tracing and simple path tracing with it, so here are some obligatory pictures:





The acceleration structures I have implemented currently are a uniform grid and the bounding interval hierarchy. I was really amazed by how simple the latter was to implement, while still being both efficient and flexible. The in-place quick sort-like construction algorithm with the global heuristic is especially elegant. I'm looking forward to implementing a kd-tree to see how the BIH compares with it at ray traversal.

As I mentioned I have implemented a simple, bare-bone unbiased path tracer already (very simple once you have the ray-model intersection code). However, it's quite noisy and requires an intimidating amount of samples to get a decent result. Eventually I'm planning to implement bidirectional path tracing and metropolis light transport to try to mitigate that. But first I want to optimize the acceleration structures so that they can act as a core for both stochastic and real-time ray tracing. This will probably involve implementing and SIMD-izing both single-ray and coherent traversal routines.

Other stuff I want to experiment with: terrain, volumetric ray tracing, sub-surface scattering, etc... I'll see where things lead and how long until interest fades :)

References:
Instant Ray Tracing: The Bounding Interval Hierarchy
The Utah 3D Animation Repository
The Stanford 3D Scanning Repository