Hidden Line / Surface Removal

Area Subdivision

These are more powerful than previous methods (back-face removal and depth sorting - painter's algorithm)

Area - Subdivision - Image space algorithm
Start with total viewing area
Check to see if just a single surface or no surface in area
If just a single surface (or no surface) then scan convert
Else subdivide (by 2) area and repeat until meets conditions (single or no surface) or area covers a single pixel.
4 Possible Cases:
1. A surrounding surface completely encloses testing area
2. An overlapping surface: partly in testing area
3. A surface inside testing area
4. No surfaces inside testing area, only surfaces outside area

We are through and can scan convert the testing area if one of the following is true:

1.All surfaces are outside the area.
2.Only one inside, overlapping, or surrounding surface is in the area.
3.A surrounding surfaces obscures all other surfaces in area. - require a depth sort in object space

Test for 1 Test boundary rectangles (extents) of surfaces against boundary area.

Test for 2 Same as Test 1 for inside surfaces of surrounding surface. For overlapping surface, we need to check if actual surface inside testing area so use line intersection.

Test for 3 Do Z depth ordering , use extents to test for surrounding surface, if Zmax of surrounding surface is less than Z min for enclosed surfaces then test 3 is satisfied.

Note that test 3 is satisfied for surfaces 2 and 3 but not for 1, even though S surrounds 1. So we could do more elaborate testing for 1 but easier to just subdivide and continue with simple tests.