Experiments in Ray-Tracing, Part 9: Interpolation
In this article I’m going to present a technique that trades lower image quality for faster rendering time: interpolation.
Instead of ray-tracing every single pixel, we instead start by tracing pixels in an evenly-spaced grid, say every two or four pixels. (So if we have an interpolation step of two, we trace one out of every four pixels, and if we have an interpolation step of four, we trace one out of every sixteen pixels).
The image on the left above represents the pixels that would be traced with an interpolation step of two; the image on the right, an interpolation step of four.
Once we’ve performed this initial trace, we then examine each square region formed by the grid of traced pixels. For each square region, there are two cases to consider:
- The four corner colors are roughly the same;
- The four corner colors differ.
Based on these two cases, we take one of two actions:
- If the four corner colors are roughly the same, we can save time by interpolating (estimating) the colors for the remaining pixels from the four corners.
- If the corner colors differ, then we need to trace the rest of the pixels in the square region normally.
(Alternatively for option two and a large interpolation step, we could subdivide the square and apply the same algorithm with a halved interpolation step).
(As an added bonus, if we want to anti-alias the scene, we only need to anti-alias the pixels in a square that we aren’t interpolating).
As an example, I’ve added debug code to display the interpolated pixels as green in my usual shiny-spheres-on-a-chessboard scene; interpolate step of two above, interpolate step of four below:
So what sort of speed-ups have I seen? Well, I haven’t put much effort into optimizing my interpolation algorithm, since I’m moving onto radiosity, but here’s some numbers:
- No interpolation: 360ms
- Interpolation of two: 200ms
- Interpolation of four: 230ms
- Interpolation of eight: 310ms
As you can see, there’s an optimal interpolation step, in this case, of two. As the interpolation step increases, it becomes more likely that the colors at the corner of each square will differ, and so less interpolation will happen. Higher interpolation steps are also more likely to introduce artifacts into the image.
As I mentioned at the start, this technique does trade off image quality for speed. In the images below, the upper image is properly traced; the lower one has been interpolated with a step of two. You will be able to see some blurring of the reflection of the chessboard in the spheres.
You can regain that detail in the reflections if you simply keep track which object you can see reflected. Note, that it might be better to keep track of which object there is under a pixel, not what color values it has.
I gained a lot of speed by doing a 16×16 initial check on a real-time raytracer I did, then recursing using smaller grids. The biggest problem was that if an object was smaller than the 16×16 and was aligned right between the initial pixels, it would not of course be rendered at all since none of the surrounding four pixels would know there is an object between them. A slightly better approach is to use non-square interpolation. Triangles work nicely.
Also, since anti-aliasing was mentioned: the same technique can be used with a 2×2 grid to find the edges of objects that should then be anti-aliased (and the insides can be interpolated as described in the article), and the original method of comparing color values works even better in that.
Oh and I forgot to mention you can achieve the checker pattern also by interpolating the UV coords you have of the plane, that way you need to raytrace less pixels, the hardware/fast software mapping handles the rest (and again you can interpolate the normals etc.).