Hidden Line / Surface Removal

Scan-line Z-Buffer Algorithm

If the memory requirements of the regular z buffer are too large, then we can use the scan line z buffer method. This method only needs a z buffer large enough for one scan line but requires more pre-processing.

Outline of preprocessing

For all the polygons in the image

1. Do perspective depth transformation

2. Compute plane equation of all polygons

3. Do an orthographic projection onto the viewplane (discard the z values)

4. Clip the polygon to the window

5. Transform all vertices of all projected and clipped polygons to PDC.

Note: Up to this point the same steps must be performed for the regualr z buffer algorithm

6. Put all Polygons (in PDC) into a data structure (array or linked list).

7. Find the largest and smallest Y values for the vertices of each polygon

8. Sort on Ymax to create a table with the following entries:

pointer to actual polygon vertices Ymax Ymin ABCD(plane equation)

Note that this table is similar to the edge list we created in scan converting a polygon. Where as before we had pointers to indicate the active edges for the polygon scan, now we have pointers (first, last) to indicate the active polygons . A polygon is included in the active list if(assuming decreasing Y values as we scan , i.e. scan from Ytop ® 0)

Ymax is >= current scan line and Ymin <= current scan line

first checks Ymax to see if the polygon is in the current scan line (should be added to active list) last checks Ymin to see if the polygon has dropped off the active list

Then the z-buffer scan line algorithm:

for scan = Ytop to 0 do

update first, last (pointers to active polygons)

initialize scan line z buffer to 1.0 ( or max integer value if scaled)

for P <- first to last do

for J <- 1 to Ki do (number of vertices in polygon)

check for edge intersections with scan line

for edge J, J+1

if edge intersection then compute x value and insert x into a sorted

x-table

/* We now have an even number of sorted x-intersections (2*n intersections: note n = 1 for a triangle) */

/* Now we process the pixels from polygon P */

for J = 1 to n do

for x = x1 to x2 where x1 = x_table(J*2-1) and X2 = x_table(J*2)

compute z_depth(x, scan) from plane coefficients in poly_table

if z-depth(x, scan) < z_buffer(x) then

set_pixel(x, scan, color)

z_buffer(x) = z-depth(x, scan)

end x

end J

end I

end scan

Look at analysis of storage requirements for the scan line z buffer algorithm

Assume 640 x 480 resolution) then z_buffer = 640 x 2 (16 bit) = 1280

For the polygon list: (assume triangles)

For each polygon store

3 vertices * 2 coordinates/vertex * 2 bytes/coordinate = 12 bytes

In polygon table store:

Ymax (2 bytes) + Ymin (2 bytes) + ABCD (16 bytes) + index to poly vertices (2 bytes) =

22 bytes/ polygon

So total of 34 bytes/polygon (36 if use linked list)

So for scan line version memory = 1280 + N * 36 Now regular Z-buffer for 640 x 480 x 2 = 614,000 bytes so scan line requires less memory up to about 17,000 polygons.