Warnock algorithm

from Wikipedia, the free encyclopedia

The Warnock algorithm is a method from computer graphics for calculating occlusion , i.e. to determine which parts of objects are visible to the viewer. It was developed in 1969 by John Warnock and mostly applied to polygonal scenes.

principle

A polygon can be related to a surface element in four ways: a) surrounding, b) overlapping, c) containing, d) separated.

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 can be related to an area element in four different ways (see picture). The division is completed in the following cases, since a simple decision can be made about the representation of a surface element:

  • All polygons are separated from the area: In this case, the area is colored with the background color.
  • There is exactly one polygon, and this polygon overlaps or is contained in the area. In this case, the area is first filled with the background color, then the part of the polygon contained in the area is rasterized .
  • There is a single surrounding polygon, but no overlapping or contained polygon. Here the area is filled with the color of the surrounding polygon.
  • There is more than one overlapping, contained, or bounding polygon, but one of them is a bounding polygon that precedes all the others. To test whether one surrounding polygon is in front of the others, the z coordinates of the planes containing the polygons are compared at each of the four corners of the surface element. If the coordinates of the surrounding polygon at each corner are smaller than those of the rest, then it is closest and the area can be colored with the color of this polygon.

If it has been subdivided to such an extent that the surface elements only comprise a single pixel, and none of the above four cases has occurred, the z coordinate of all polygons at the center of the surface is calculated. The polygon with the z coordinate that is closest to the viewer then determines the color of the pixel. In order to achieve anti-aliasing , the areas can be subdivided even further so that the color of a pixel results from the mean value of the associated area elements.

literature

  • James D. Foley et al: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6 .
  • William Newman, Robert Sproull: Principles of Interactive Computer Graphics. McGraw-Hill, New York 1973, ISBN 0-07-046337-9 , pp. 297-302.
  • David Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5 .
  • John Warnock: A Hidden-Surface Algorithm for Computer Generated Halftone Pictures. Technical Report TR 4-15, NTIS AD-753 671, Computer Graphics Department, University of Utah, Salt Lake City 1969. (PDF, 1.3 MB)