Subdivision Algorithm

Subdivision Algorithm

1. Initialize the area to be the whole screen.
2. Create a PVPL with respect to an area, sorted on z min (the smallest z coordinate of the polygon
within the area). Place the polygons in their appropriate categories. Remove polygons hidden by a
surrounding polygon and remove disjoint polygons.
3. Perform the visibility decision tests:
a) If the list is empty, set all pixels to the background color.
b) If there is exactly one polygon in the list and it is a classified as intersecting (category 2) or
contained (category 3), color (scan convert) the polygon, and color the remaining area to the
background color.
c) If there is exactly one polygon on the list and it is a surrounding one, color the area the color of
the surrounding polygon.
d) If the area is the pixel (x, y), and neither a, b, nor c applies, compute the z coordinate z(x, y) at
pixel (x,y) of all polygons on the PVPL. The pixel is then set to the color of the polygon with the
smallest z coordinate.
4. If none of the above cases has occurred, subdivide the screen area into fourths. For each area, go to
step 2.