Algorithms for Programming assignment #2

From the Help Session, May 5

Final Algorithms to use in Supersampling

These are algorithms that you can use directly to implement supersampling as given in the assignment, given that you have already correctly coded the scan conversion routine.

They differ in the way they perform the accumulation of the supersamples into the final result, using different numbers of temporary canvases and providing different levels of accuracy.

In the following algorithms:

p
represents a pixel position (x,y)
Canvas(p)
is the color stored at location p in the canvas Canvas .
s
is the number of supersampling positions along each dimension, so s*s is the total number of supersamples per pixel. s is the quantity you should control with your slider.
Red(c)
gets the red component of a color c . Green(c) and Blue(c) are defined similarly.
MakeColor(r,g,b)
makes a color from red, green, and blue components.
A reminder: make sure that when you perform arithmetic operations on colors, you do it component-wise. Some operators will happen to work on the color as one unit, but some, such as multiplication and division, will not.

Normal progressive refinement

This is the algorithm given in the handout, which is pretty standard except for the fact that rather than scaling each sample value by 1/(s*s) before adding it in, it uses a different accumulation formula which ensures that the value in the canvas after each subpixel position is a full-intensity average of the samples that have been taken so far, so that the intermediate images can be viewed reasonably.

This algorithm requires one extra canvas and can result in a fair amount of quantization error, but it is all that is required in this assignment. 

    for each pixel position p
        Canvas(p) = 0
    end for
    for i = 1 to s*s
        for each pixel position p
            TempCanvas(p) = 0
        end for
        shift all original vertices of all triangles by the opposite
         of the offset of subpixel position i
        scan convert all new triangles into TempCanvas
        for each pixel position p
            Canvas(p) = ((i-1)/i) * Canvas(p) + (1/i) * TempCanvas(p)
        end for
        display Canvas
    end for

Multiple big canvas method

This algorithm is suggested in the last paragraph of the assignment. To avoid quantization error, we do not divide each sample by the number of samples when adding it in. However, this means that in order to avoid overflow of the canvas values, we use three 32-bit canvases, one for each of red, green, and blue. To form a final image from these three canvases, we then scale the component values down by the number of samples and merge them into one normal color canvas.

This algorithm avoids the quantization error of the previous one, which will result in nicer images and possibly easier debugging, but requires four extra canvases, which will result in a speed disadvantage as well. 

    for each pixel position p
        RedCanvas(p) = 0
        GreenCanvas(p) = 0
        BlueCanvas(p) = 0
    end for
    for i = 1 to s*s
        for each pixel position p
            TempCanvas(p) = 0
        end for
        shift all original vertices of all triangles by the opposite
         of the offset of subpixel position i
        scan convert all new triangles into TempCanvas
        for each pixel position p
            RedCanvas(p)   += Red(TempCanvas(p))
            GreenCanvas(p) += Green(TempCanvas(p))
            BlueCanvas(p)  += Blue(TempCanvas(p))
            if (progressive refinement or i = s*s) then
                Canvas(p) = MakeColor(RedCanvas(p)/i, GreenCanvas(p)/i,
                                      BlueCanvas(p)/i)
            end if
        end for
        if (progressive refinement) then
            display Canvas
        end if
    end for
    if (not progressive refinement) then
        display Canvas
    end if

Mathematical trick method:

This method employs an obscure mathematical trick, as was demonstrated in the help session, to completely avoid quantization error in areas of constant color (although some error will still exist along boundaries between areas of different color), and only uses two extra canvases. In addition, if no progressive refinement is required, the algorithm can be simplified to only require one extra canvas. 
    for each pixel position p
        HackCanvas(p) = 0
    end for
    for i = 1 to s*s
        for each pixel position p
            TempCanvas(p) = 0
        end for
        shift all original vertices of all triangles by the opposite
         of the offset of subpixel position i
        scan convert all new triangles into TempCanvas
        for each pixel position p
            HackCanvas(p) += MakeColor(Red(TempCanvas(p)) + i - 1,
                                       Green(TempCanvas(p)) + i - 1,
                                       Blue(TempCanvas(p)) + i - 1)  / (s*s)
            if (progressive refinement or i = s*s) then
                Canvas(p) = HackCanvas(p) * (s*s / i)
            end if
        end for
        if (progressive refinement) then
            display Canvas
        end if
    end for
    if (not progressive refinement) then
        display Canvas
    end if

tsmith@cs.stanford.edu