Technique Description
Progressive refinement rendering is a special rendering technique which makes it possible to render a coarse version of the 3D scene which is refined over time. The render stops when the maximum rendering quality is reached. This is usually when all the pixels (or pixel samples) of the frame have been rendered.
This video show an image being rendered using a very simple implementation of this technique which is described at the end of this chapter (more complex algorithm will be presented in the next chapters):
Ape model provided by Kenichi Nishida (http://www.kenichinishida.com © 2011 Kenichi Nishida).
A trend ?
Progressive refinement makes it possible to compete with GPU accelerated ray tracers, by providing an intermediate solution to displaying results much faster than with traditional rendering modes (bucket rendering). This technique is only used for interactive rendering sessions while in batch, bucket rendering or traditional rendering modes continue to be used (for final production rendering quality). Despite being well studied in the mid 80s by major researchers from the CG community, the technique never really made it through to commercial applications (to the exception of a few such as Bryce). It was maybe perceived that despite using potentially more pixel samples on average, uniform sampling algorithms run faster than adaptive ones due to their simplicity (this is just an hypothesis). However, adaptive progressive rendering is not only a technical tool that can improve the frame quality. It is also a technique that can be used to the advantage of an artist to provide quicker feedbacks on the frame being rendered. This might be the reason why the technique seems to make an interesting come back in the early 2010s which is also motivated we feel by a competition between GPU and CPU renderers. Implementing this technique in an existing renderer requires far less work that developing a GPU accelerated ray tracer compatible with its CPU counterpart. It is therefore no surprise to see that progressive rendering was recently added to Prman for example (a renderer developed and commercialised by Pixar) and promoted to be used as a relighting tool.
Why is it useful ?
The main advantage of the technique from the user point of view, is to be able to quickly get a visual feedback about what the frame looks like before it is completely finished. This might be useful when an artist is tweaking the lighting or the materials of the scene.
Adaptive progressive refinement rendering
From a more technical point of view, the technique also presents advantages compared to a more classic rendering technique (such as bucket rendering). As the scene is being progressively rendered, the program can gather information about the image properties and use this information to focus its computational resources in areas of the frame which would require better sampling. If you render a sphere for example, the center of the sphere does not have a lot of shading variation. If the sphere is diffuse, it is very likely that the pixel intensity and color will vary smoothly from pixel to pixel. However at the edges of the sphere, it is very likely that super sampling the pixels will be needed in order to get rid of aliasing. Ideally we would use a low number of pixel samples for pixels covering the center of the sphere, and a high number of pixel samples for pixels covering the edges of the object. In a naive ray tracer however, we need to use a conservative number of pixel samples to be sure that anti-aliasing will be good everywhere even though too many samples will be used in areas of the frame where using a lower number of samples for these regions, wouldn't make any visual difference. In short, it is not possible to adaptively distribute the number of samples being used in a clever way. With progressive refinement though, it is quite easy to use adaptive sampling. As we refine the image, we can use various techniques to find areas which are likely to need more pixel samples than the other pixels in the frame. Usually adaptive sampling is usually controlled in the renderer through two parameters: a minimum (optional, at least 1 sample per pixel is needed) and maximum (lets say 8) pixel samples. Pixels in the frame will all be rendered with at least the minimum number of pixels samples (1 is the minimum). If more pixel samples are needed then more samples can be cast until the maximum number of samples is reached. This can lead to a significant gain in rendering efficiency (rendering time). For the same rendering time an image rendered with adaptive sampling might also look better than the same frame rendered with a uniform sampling scheme (same number of pixel samples for all the pixels): with adaptive sampling, more pixel samples can be used in areas which are more difficult to reproduce with a good visual quality than others (edges of objects, motion blurred areas, high frequency shading, etc.). These areas are slower to render (more samples are used) than the other regions of the frame but since we use a lower number of samples (say 1 or 2) for these other regions, then all in all, the render time ends being more or the less the same than if we had used 4 pixel samples for all the pixels of the frame (our pixel samples credit is just distributed differently, i.e. adaptively).
Figure 1: these images are copied from the original paper Antialiased Ray Tracing by Adaptive Progressive Refinement (Painter and Sloan © ACM 1989). Rendered images are on the left. On the right, gray-scale images represent the number of samples used per pixel. Brighter regions are clearly the edges of objects, shadow boundary, and high frequency shading details (teapot example).
So far, we have only mentioned that edges of objects were the areas of the frame that needed more samples. However there is potentially many more areas in the frame that could benefit from better sampling such as regions with high frequency lighting (sharp shadows) and shading (high frequency textures, specular reflections). Motion blur usually requires also a lot of samples. Overall it was described in some papers on progressive rendering, that the contrast of an image was a good measurement tool to decide which part of the frame needed more samples. Contrast measures the variation of color and brightness between neighbour pixels. If there is a region of high contrast (we also speak of variance) it is likely that we are in one of situations we have mentioned: we have detected edges between objects, or a region of the image depicting high frequency shading or lighting features.
To implement an adaptive progressive refinement algorithm we need a metric (also called error estimator in the litterature) to measure how far we think the current rendering pass is from an ideal image and a stopping condition which we can use to decide when we stop casting more pixel samples. We just mentioned that contrast (measure the color and intensity between neighbour pixels or regions of the frame) could be used as a metric. The stopping condition often takes the form of a threshold value on the error estimator. For instance, when the variation of brightness between regions of the frame, neighbour pixels or sub pixel samples is lower than a certain threshold then we stop casting new samples.
History
Progressive refinement rendering went in pair with work on sampling which was a very active field of research in the early 80s when a lot of fundamental problems in CG were to be solved and many techniques or algorithm which are are using today (or variants of these techniques) were proposed. At the end of this lesson we have listed a few seminal papers on sampling and adaptive rendering. Adaptive sampling and progressive refinement were active field of research until the end of the 80s by which time techniques and problems were fairly well known, covered and studied. Most papers on the topic published later were just improvements to these techniques. One paper of particular importance entitled The Rendering Equation was published by Kajiya in 1986. Not only this paper lays the theory of rendering which has become a standard in the CG research community, but Kajiya also proposes in the same paper a few algorithms to implement adaptive progressive refinement (which he refers to as hierachical sampling). These algorithms will be studied in the next chapter.
Implementing a simple progressive refinement algorithm
In the chapter we will show how to implement a very simple form of progressive refinement in a ray tracer. The technique is based on paper proposed in 2000 in a paper entitled "An Algorithm for Progressive Refinement" (listed in the reference section). The idea is to subdivide the frame in two and render the line separating these two regions. Once all the pixels of the lines have been computed, they are just duplicated to fill up the upper and lower regions of the frame which haven't been rendered yet. This process is repeated recursively to empty regions until every line of the frame has been rendered. The following figures illustrating the first few iterations of the process might help you understanding the technique better.
The authors of the paper points out that after 50 percent completion there is no significant improvement to the image quality. In fact after 25% to 35% it is already possible to have a very good idea of what the image looks like.
Any new lines that is rendered beyond that point contributes very little to the final look of the frame (it's more about image quality than image properties). This confirms the idea that progressive refinement is ideal for relighting applications. By quickly displaying a complete representation of the image, an artist can start to make judgements about the lighting and shading qualities of the scene very quickly. For a given period of time, many more changes can be made to the scene using this technique than with a traditional rendering mode (bucket rendering).
This technique is very simple to implement and requires only few changes to the render() function. A more elaborate technique suitable for adaptive sampling and based on Kajiya's paper, will be presented in the next chapter.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
What's next ?
In this chapter we have given a brief introduction to the progressive refinement rendering technique and explained in non technical terms, the concept of adaptive progressive refinement rendering. We have also provided the code to add a simple progressive refinement rendering mode to a ray tracer. In the next chapter, we will cover more mathematical grounds on adaptive sampling and provide with an implementation of the Kajiya technique called Hierarchical Sampling.
References
Statistically Optimized Sampling for Distributed Ray Tracing. Lee, Redner, Uselton and Tulsa (1985)
Antialising Through Stochastic Sampling. Dippé (1985)
The Rendering Equation. Kajiya (1986)
Antialised Ray Tracing by Adaptive Refinement. Painter and Sloane (1989)
An Algorithm for Progressive Refinement Raytracing. Arikan and Gudukbay (2000)
Chapter 1 of 1
