Warnock algorithm
The Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics.[1] It works by recursive subdivision of a scene until areas are obtained that are trivial to compute. It solves the problem of rendering a complicated image by avoiding the problem. If the scene is simple enough to compute then it is rendered; otherwise it is divided into smaller parts and the process is repeated.[2]
This is a divide and conquer algorithm with run-time of , where n is the number of polygons and p is the number of pixels in the viewport.
The inputs are a list of polygons and a viewport. The best case is that if the list of polygons is simple then draw the polygons in the viewport. Simple is defined as one polygon or a viewport that is one pixel in size. The continuous step is to split the viewport into 4 equally sized quadrants and to recursively call the algorithm for each quadrant with a polygon list modified such that it only contains polygons that are visible in that quadrant.
References
- ^ Warnock, John (1969). "A hidden surface algorithm for computer generated halftone pictures" (PDF). University of Utah.
The algorithm was Warnock's doctoral thesis.
, 32 pages - ^ Daintith, John (2009). Oxford Dictionary of Computing. Oxford University Press. ISBN 978-0199234004.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help), 608 pages
 | This computer-programming-related article is a stub. You can help Wikipedia by expanding it. |