This is a very old article, included for historical interest only!
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:
Based on these two cases, we take one of two actions:
(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:
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.
Published: Sunday, September 07, 2008
Hackification.io is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to amazon.com. I may earn a small commission for my endorsement, recommendation, testimonial, and/or link to any products or services from this website.