Warnock algorithm

The Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics. It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are obtained that are trivial to compute. In other words, if the scene is simple enough to compute efficiently then it is rendered; otherwise it is divided into smaller parts which are likewise tested for simplicity.

This is a divide and conquer algorithm with run-time of $O(np)$, 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.

External links

• A summary of the Warnock Algorithm