CS 248: Midterm Solutions

Question 2

Grader: Matt Pharr


Multiply should be implemented using AND, addition with OR. Writing out truth tables for the various cases makes this clear. A number of people said that addition should be implemented with exclusive OR; this is wrong, however, since it means that 1+1 == 0, which is not semantically correct behavior.

Note also that 1-x == NOT(x).

Two points were lost if one of the two was right and one was wrong; both wrong was minus 5 points.


There were a few things that had to be done correctly to get this completely right; most people lost a few points on this here or there.

The general compositing formula (Porter and Duff) is:

Cr = Ca * Fa + Cb * Fb
Note that this formula assumes premultiplied alpha; given that the pixel (0,1) is undefined (from the question), this is the correct assumption.

In the compositing forumla, Cr is the resulting images and Ca and Cb are the two input images. Fa and Fb vary based on the compositing operator being used. The relevant values of Fa and Fb are:

Operator       Fa             Fb
Over            1         1 - alpha(A)
In           alpha(B)          0
Out        1 - alpha(B)        0
Now on to applying the formula and simplifying:


bitmap(R) = (bitmap(A) AND 1) OR (NOT(alpha(A)) AND bitmap(B))
          = (bitmap(A)) OR (NOT(alpha(A)) AND bitmap(B))

alpha(R)  = (alpha(A) AND 1) OR (NOT(alpha(A)) AND alpha(B))
          = (alpha(A)) OR (alpha(B))


bitmap(R) = (bitmap(A) AND alpha(B)) OR (bitmap(B) AND 0)
          = (bitmap(A) AND alpha(B))

alpha(R)  = (alpha(A) AND alpha(B)) OR (alpha(B) AND 0)
          = (alpha(A) AND alpha(B))


bitmap(R) = (bitmap(A) AND (NOT(alpha(B)))) OR (bitmap(B) AND 0)
          = (bitmap(A) AND (NOT(alpha(B))))

alpha(R)  = (alpha(A) AND (NOT(alpha(B)))) OR (alpha(B) AND 0)
          = (alpha(A) AND (NOT(alpha(B))))


Each one was worth three points; if you wrote nothing, however, you got zero points. For each operation, getting the Fa and Fb values wrong but otherwise being correct was minus 2 points. Smaller errors in each one cost one point per error per operation: this included such things as writing the correct operation but not using the logical operations, not simplifying the logical expressions as much as possible, or not assuming premultiplied alpha.