Warnock algorithm

The Warnock algorithm is a method of computer graphics to masking calculation, ie to determine what parts of objects are visible from the observer. It was developed in 1969 by John Warnock and mostly applied to polygonal scenes.

Principle

The Warnock algorithm divides the image area into four equal squares. This division is continued recursively. At each step of the division process, a polygon on four different types may be associated with a surface element values ​​(see the picture). The division is completed in the following cases because of the representation of a surface element, a simple decision can be made:

  • All of the polygons separated from the surface: in this case, the area is colored with the background color.
  • There is exactly one polygon, and this polygon overlaps the surface or is contained in it. In this case, the surface is first filled with the background color, then the part of the polygon contained in the surface is scanned.
  • There is a single polygon surrounding, but not overlapping or contained polygon. Here, the area is filled with the color of the surrounding polygon.
  • There are more than one overlapping, contained or surrounding polygon, one of which, however, is a bounding polygon that is above all others. To test whether a bounding polygon is in front of the other, the z- coordinates of the planes containing the polygons, as compared to each of the four corners of the sheet. If the coordinates of the bounding polygon as the are on every corner of the remaining smaller, so it is closest, and the surface can be colored with the color of that polygon.

If it has been so far divided so that the surface elements comprise a single pixel only, and none of the above four cases, has occurred, then the z- coordinate of all the polygons is calculated at the center of the surface. The polygon with the z- coordinate that is the closest to the viewer, then determines the color of the pixel. In order to achieve anti-aliasing, the surfaces may be further subdivided such that there is the color of a pixel from the average value of the associated surface elements.

Recursion Plane (geometry)
813627
de