Warnock Algorithm in Computer graphics

This is one of the class of “area” algorithms. It tries to solve the hidden surface problem recursively. The algorithm proceeds on the following lines.

i. Try to solve the problem by taking the entire screen as one window. If no polygons overlap either in x or y or even if they do, overlap so that they do not obscure, then return the screen

ii. If the problem is not easily solvable in step (i) the algorithm divides the screen into 4 equal parts and tries to apply step (i) each of them. If it is not solvable, again divides into smaller windows and so on.

iii. The recursive process continues till each window is trivially solvable or one endsup with single pixels.

We have still not described how the actual “solution” is done. To do this, in any window, the algorithm classifies the polygons into three groups

i) Disjoint Polygons: Polygons that do not overlap in the window and hence can be trivially passed.

ii) A bigger and a smaller polygon overlapping so that the smaller one will be completely blocked by the bigger one (if the Z of the larger polygon is smaller than Z of the smaller one).

iii) Intersected polygons: Polygons that partly obscure each other.

Polygons that fall into category (i) and (ii) are removed at each level. If the remaining polygons can be easily solved, the recursive process stops at that level, else the process continues (with the polygons of category (i) and (ii) removed).

Since at each recursive level a few polygons are removed, as the windows become smaller and smaller with the advance of recursion, the list of polygons falling into them also reduces and hopefully the problem of hidden surfaces gets solved trivially

One main draw back of algorithm is that the windows get divided into smaller and smaller rectangles. In many cases it would be efficient if one can divide the window roughly in the shape of the polygons themselves. Such an algorithm, developed by Wieler and Atherton, was found more efficient, though more complex in terms of larger complexities of recursive divisions and clippings

Leave a Comment