Image-Space Algorithms

Scan Conversion w/o Z buffering

sort edges by Y & sweep a scan line up
at each scan line, sweep across active edges in X.

The single-polygon case:

for overlapping polygons, an extra step:

1. find the edge with lowest Z - how? - and draw that color.

use: w/painter's algorithm
time: worse than O(xy log d + n log n), where d is the depth complexity for a given scan line
coherence: object and image-space
scene footprint: total
memory footprint: enough to sort by Y, then enough for the current scan line
overdraw: total
clipping: done
transparency: supported

Z-buffering
Associate a color and a depth with each pixel

Avoid drawing occluded pixels

algorithm
Initialize depth values to infinity (and color vals to some background color)
Draw (usually scan-convert) all the scene objects in any order

for each potential pixel write
if the depth of the pixel is greater than the Z buffer value, throw it away
otherwise store its color and depth value

- very very hardware-accelerable!

use: OpenGL
time: O (xyd), where d is the depth complexity
coherence: none
scene footprint: total (depends on who's feeding the objects in)
memory footprint: size of the Z buffer, and the memory to scan-convert an object
overdraw: total
color values gratuitously stored to the framebuffer: none (front-to-back) to total (back-to-front)
clipping: not done
transparent objects: not supported (Alpha-buffers do this)

Hierarchical Z-buffering (Greene & Kass, 1993)
Keep both a traditional Z-buffer and a hierarchy of smaller Z-buffers

The highest level has the original z buffer
Level 0 has the deepest z value for the entire image so far

requires an extra step over traditional Z buffering - propagate up new depth values.

HZB requires...
Hierarchical Scan Conversion
Try to reject entire objects at a time using the HZB

for each object

get some nearest z for the object - an overly close estimate is fine
compare that z against the level 0 value
if nearest z > level 0,
object's nearest z is farther away than the farthest z in the image
it's guaranteed to be totally occluded
throw away the whole object!
otherwise go to the next Z-buffer level
optionally compute some nearest z for each portion of the object
compare those z's against the Z-buffer and try to reject parts of the object.

worst case: we have to go down to the traditional Z-buffer and resolve depth pixel-by-pixel
-this is not yet in hardware, where it needs to be.

time, worst case, back-to-front drawing: O (d xy l) where
l is the # of hierarchy levels (log s)
d is the depth complexity
*time, usual case: O(unknown)
*coherence: object and image-space
scene footprint: depends on who's feeding the objects in.
memory footprint: size of all the Z buffers
overdraw: total, assuming the Z compare is the last step after rasterizing, clipping & shading
clipping: can be done
transparent objects: not supported