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.