Rendering a CSG object

 X - (Y u Z) = (X - Y) - Z
 X n (Y u Z) = (X - Y) u (X - Z)
 X - (Y n Z) = (X - Y) u (X - Z)
 X n (Y n Z) = (X n Y) n Z
 X - (Y - Z) = (X - Y) u (X n Z)
 X n (Y - Z) = (X n Y) - Z
 (X u Y) - Z = (X - Z) u (Y - Z)
 (X u Y) n Z = (X n Z) u (Y n Z)

 
       normalize(T) 
         {
           if (T==primitive) return;
           else 
             repeat {
               while (T matches any left side of 1-8,
                      doing 1-6 before 7-8)
                      replace right side by left side;
               Normalize (T.left);
             until (T==union or (T.right == primitive and T.left not a union)
             Normalize (T.right);
         }


 Write union as + , intersection as product.  If Y' denotes the complement
of Y, then X - Y = X n Y' = XY'.  Hence normalization converts a CSG
expression into a "sum of products" of the form:

 CSG = M1 + M2 + M3 + ...

 where each M = A1A2A3.., and each A is a primitive or a complement of a primitive.
 


        Rendering a CSG object using 1-bit Stencil Buffer SB 

        front(primitive P)
         { 
           render front(P) into zTemp and colorTemp;
           SB[x][y] = 1 for pixels in front(P);
           else SB[x][y] = 0;
         }

        back(primitive P)
         {
           render back(P) into zTemp and colorTemp;
           SB[x][y] = 1 for pixels in back(P);
           else SB[x][y] = 0;
         }

        intersect(primitive P)
         {
           for each pixel (x,y) {
              if (stored zTemp[x][y] not between zFront and zBack of P)
               zTemp = zFar;
               colorTemp = background color;
               SB[x][y] = 0; 
            }
         }

        subtract(primitive P)
         {
           for each pixel (x,y) {
              if (stored zTemp[x][y] between zFront and zBack of P)
               zTemp = zFar;
               colorTemp = background color;
               SB[x][y] = 0; 
             }
         }

        renderCSG(product M)
        {
            for each P in M {
                if (P is uncomplemented) front(P);
                else back(P);
                for each Q != P in M {
                    if (Q is uncomplemented) intersect(Q);
                    else subtract(Q);
                for each (x,y) with SB[x][y]=1
                    composite(zTemp,colorTemp) into (zFinal, colorFinal);
              }
         }