CS-460/560, Week 14-A
Spring, 1998
R. Eckert

Z-BUFFER HIDDEN SURFACE REMOVAL ALGORITHM (FOR CONVEX POLYGONS)

Data Structures:

  Assume we have computed the 2-D projected screen coordinates (xs,ys) and
  the viewing z coordinate (zv) of each polygon vertex. These and the
  polygon's color are stored in the polygon's edge table (see notes on the 
  scanline polygon fill algorithm). Also assume we have set up an active 
  edge list which contains the active edges intersected by the current 
  scanline sorted on xs (again see scanline polygon fill notes).

  (From now on in this discussion, any x or y used will refer to screen 
  coordinates and any z to viewing coordinates.)

  We also have the frame buffer fbuf[x][y] which will store the color of
  each pixel (x,y) on the screen and the z-buffer zbuf[x][y] which will
  contain the z distance from the observer of the point on the closest
  polygon that projects to the pixel (x,y) on the screen. Each element of
  fbuf[][] is initialized to the background color, and each element of
  zbuf[][] to infinity (largest possible value).


The Algorithm:

For each polygon
  For each scanline y spanning the polygon
    Get left & right active edges from the active edge list
    Get x,z coordinates of endpoints of these edges from edge table
    Compute scanline intersection pts xL,zL,xR,zR by x/y & z/y interpolation
      For (x=xL to xR)
        Compute z by z/x interpolation
        If (z < zbuf[x,y])
          zbuf[x,y] = z
          fbuf[x,y] = polygon color


Interpolations:

  Assume the lower and upper vertices of the left active edge have
  coordinates: (x0,y0,z0) and (x1,y1,z1) and those of the right active
  edge have coordinates: (x2,y2,z2) and (x3,y3,z3).  (See diagram below.)
  Recall that the x,y coordinates are screen coordinates while the z
  coordinates are viewing coordinates.



  x/y Interpolation: Find intersection points (xL,zL,xR,zR) of current
  scanline (y = y value of current scanline) with left and right active
  edges. Interpolate between lower and upper vertices (obtained from
  edge table)--

    Left Edge:

       xL-x0     y-y0
      ------- = -------
       x1-x0     y1-y0

      Solving for xL gives:

        xL = (x1-x0)*(y-y0)/(y1-y0) + x0

    Right Edge:

       xR-x2      y-y2
      ------- =  -------
       x3-x2      y3-y2

      Solving for xR gives:

        xR = (x3-x2)*(y-y2)/(y3-y2) + x2

  x/y interpolation is done the same way, with x coordinates replaced by
  z coordinates. The results are:

        zL = (z1-z0)*(y-y0)/(y1-y0) + z0

        zR = (z3-z2)*(y-y2)/(y3-y2) + z2


  z/x Interpolation: Find z value on polygon at pixel x on current
  scanline. Interpolate between the left and right edge intersection
  points--

     z-zL       x-xL
    ------- =  -------
     zR-zL      xR-xL

  Solving for z gives:

    z = (zR-zL)*(x-xL)/(xR-xL) + zL

In practice, to avoid multiplications and divisions inside the algorithm
loops, these interpolations are done incrementally. In other words, new
values of xL,xR,zL,zR (in the outer loop), and of z (in the inner loop) are
obtained from old values by computing (once) and adding the appropriate
increments.