Warnock's Algorithm (Area Subdivision Algorithm):-

An interesting approach to the hidden-surface problem was developed by Warnock. He developed area subdivision algorithm which subdivides each area into four equal squares. At each stage in the recursive-subdivision process, the relationship between projection of each polygon and the area of interest is checked for four possible relationships:

1. Surrounding Polygon - One that completely encloses the (shaded)area of interest (see Fig.h (a))

2. Overlapping or Intersecting Polygon - One that is partly inside and partly outside the area (see Fig. h (b))

3. Inside or Contained Polygon - One that is completely inside the area (see Fig. h (c)).

4. Outside or Disjoint Polygon - One that is completely outside the area (see Fig. h (d)).

After checking four relationships we can handle each relationship as follows:

1. If all the polygons are disjoint from the area, then the background colour is displayed in the area.

2. If there is only one intersecting or only one contained polygon, then the area is first filled with the background colour, and then the part of the polygon contained in the area is filled with colour of polygon.

3. If there is a single surrounding Polygon, but no intersecting or contained polygons, then the area is filled with the colour of the surrounding polygon.

4. If there are more than one polygon intersecting, contained in. or surrounding the area then we have to do some more processing.

See figure (i). In Fig. i (a), the four intersections of surrounding polygon are all closer to the viewpoint than any of the other intersections. Therefore, the entire area is filled with the colour of the surrounding polygon. However, figure i (b) shows that surrounding polygon is not completely in front of the intersecting polygon. In such case we cannot make any decision and hence Warnock’s algorithm subdivides the area to simplify the problem. This is illustrated in Fig. (j).

As shown in the Fig. (j) we cannot make any decision about which Polygon is in front of the other. But after dividing area of interest polygon 1 is ahead of the Polygon 2 in left area and polygon 2 is ahead of polygon 1 in the right area. Now we can fill these two areas with corresponding colours of the polygons.

The Warnock’s algorithm stops subdivision of area only when the problem is simplified or when area is only a single pixel.

Algorithm:-

1. Initialize the area to be the whole screen.

2. Create the list of polygons by sorting them with their z-values of vertices. Don’t include disjoint polygons in the list because they are not visible.

3. Find the relationship of each polygon.

4. Perform the visibility decision test

   a) If all the polygons are disjoint from the area, then fill area with background colour.

   b) If there is only one intersecting or only one contained polygon then first fill entire area with background colour and
   then fill the part of the polygon contained in the area with the colour of polygon.

   c) If there is a single surrounding polygon, but no intersecting or contained polygons, then fill the area with the colour of the surrounding polygon.

   d) If surrounding polygon is closer to the viewpoint than all other polygons, so that all other polygons are hidden by it, fill the area with the colour of the surrounding polygon.

   e) If the area is the pixel (x, y), and neither a,b,c, nor d applies, compute the z coordinate at pixel (x, y) of all polygons in the list. The pixel is then set to colour of the Polygon which is closer to the viewpoint.

5. If none of the above tests are true then subdivide the area and go to step 2.

Advantages:-

1. It follows the divide-and-conquer strategy, Therefore, parallel computers can be used to speed up the process.

2. Extra memory buffer is not required