CS 248 - Introduction to Computer Graphics

Autumn Quarter, 2000

Marc Levoy

(1) | (2) |

Figure 2 shows an example supersampling pattern. The crosshairs represent the pixel centers. The four circles surrounding the pixel centers are the supersamples associated with the pixel. For this pattern, each supersample is weighted equally. Since the weights for any supersampling pattern must add to 1, this means that for this pattern, each supersample has a weight of 1/4. This is the supersampling pattern that will be used in the remainder of this document.

Note that for this pattern, the supersamples form a regular grid. This need not be the case for other patterns.

- The triangles are sampled at all the supersample locations.
The pixels generated by the scan conversion are stored
in a dense array which is
*s*times the size of the final picture array, where*s*is the number of supersample positions per pixel. - Set each pixel in the final antialiased image
equal to the weighted average of
the values of the
*s*supersamples corresponding to that pixel. For the supersampling pattern given in section 2, set:canvas[pixel] := denseimage[pixel][supersample1] / 4 + denseimage[pixel][supersample2] / 4 + denseimage[pixel][supersample3] / 4 + denseimage[pixel][supersample4] / 4

- An array of
*p × s*pixels for temporary storage of the supersamples. - An array of
*p*pixels for the final image. - At least
*p × s*pixel writes into the temporary array (depends on the number, sizes, and shapes of the triangles). *p*pixel writes into the final image array.*1*scan conversion at supersampled density.

- For each of the
*s*supersample locations, shift all triangles an amount exactly opposite the offset of the supersample from the pixel center. Apply normal scan conversion to those shifted triangles. Each one of these passes produces an entire image at the normal density. - Set each pixel in the final antialiased image
equal to the weighted average of the values of the pixel
from the
*s*passes. In other words, for supersample locations given in section 2:canvas[pixel] := temp[supersample1][pixel] / 4 + temp[supersample2][pixel] / 4 + temp[supersample3][pixel] / 4 + temp[supersample4][pixel] / 4

In the formulation above we store the results of each of the *s* passes in
separate arrays and average them when all the passes are completed.
In practice, we can accumulate the result of each pass into the final array
as they are completed.
This reduces the number of temporary buffers that are needed from *s* to
one.

Also, we can shift each triangle right before we scan convert it. This way, we won't need to shift all the triangles at once.

In general, if the supersampling pattern contains *s* supersamples and the
image contains *p* pixels, we would need:

- An array of
*p*pixels for temporary storage of the supersamples. - An array of
*p*pixels for the final image. - At least
*p × s*pixel writes into the temporary array (depends on the number, sizes, and shapes of the triangles). *p × s*pixel writes into the final image array.*s*scan conversions at normal density. There is more time overhead due to initializations in the scan conversion.

Keep in mind that both single-pass and multi-pass methods result in the same final image array (ignoring possible floating-point errors). The difference is in the time and space (memory) efficiency of the two methods. The single-pass method uses more space but takes less time than the multi-pass method.

1 for each pixel in canvas canvas[pixel] := black; 2 for i = 1 to s 3 for each pixel in canvas temp[pixel] := black; 4 for each triangle 5 shift triangle for supersample position 6 for each pixel in triangle 7 temp[pixel] := triangle color; 8 for each pixel in canvas 9 canvas[pixel] := canvas[pixel] + 1/s * temp[pixel]; 10 update canvas(The assignment handout says 'subpixel' instead of 'supersample.' It's the same thing.)

Roughly, the reason you need two arrays is that sometimes you want to overwrite the pixel in the canvas, and other times, you want to add to it. You cannot have it both ways if you only have one array.

9 canvas[pixel] := canvas[pixel] + 1/s * temp[pixel];in the pseudocode above, the contents of

(a) | ||||

(b) |

What we really want is a sequence like 5(b), where the image still gets smoother but the brightness stays constant. To do this, we have to renormalize the weights at each step so that the sum of the weights for the supersamples obtained so far is 1. I won't give the derivation here, but this process of renormalization yields the following accumulation rule:

9 canvas[pixel] := (i-1)/i * canvas[pixel] + 1/i * temp[pixel];This gives you the image sequence in 5(b). The accumulation rule is the same as the one given in Appendix A of the assignment #2 handout. There is one restriction: This accumulation rule will work only in the case where the supersamples have equal weights.

Here is the accumulation rule for the general case.
Suppose the supersample weights are given by
`w[1], w[2] ... , w[s]`, where
the `w[i]`'s sum to 1. Let `v[i] = w[1] + w[2] + ... + w[i]`.
Then the accumulation rule is:

9 canvas[pixel] := (v[i]-w[i])/v[i] * canvas[pixel] + w[i]/v[i] * temp[pixel];Note that if all the weights are equal (i.e.

hishii@cs.stanford.edu

Last update: October 27, 2000 03:00:00 AM