Taxonomy of Hidden Surface Removal Algorithms.
Copyright (c) Susan Laflin. August 1999.
The text by Giloi includes a classification based on the form of the input data and provides examples of algorithms for some of these. This classification has been simplified slightly (four classes reduced to three) and the algorithms identified. It is not complete, other algorithms do not fall into these categories and other methods of classifying these algorithms are also possible.
Class One
These include `solids' made up of plane polygonal facets. The resulting object may be represented as a set of `contour lines' and `lines of intersection' or it may be output as a shaded object. e.g. Appel's method, or Watkin's method, or Encarnacao's Priority Method (requires input data as triangles).
Class Two
These are `surfaces' made up of curved faces. The resulting object is represented as a net of grid lines. e.g. Encarnacao's Scan-Grid Method.
Class Three
These are general objects defined analytically. No example of an algorithm for this class is given in Giloi.
Alternatively the methods may be grouped according to the type of method. This gives the following:
Scan-line Methods
These include Watkin's method and a number of others. These work in terms of scan lines with the pixel-colour at each point along the line calculated and output. If there is enough storage to hold a copy of the entire screen, instead of just one line across it, we may use a `Z-buffer' algorithm, in which the z value corresponding to each pixel is used to decide on the colour of that pixel. The polygons may be added in any order, but the z-value is used to decide whether a pixel should be changed or not as the next polygon is added. Again coherence may be used to reduce the number of tests needed.
When we come to consider the special case of drawing an isometric projection drawing of a surface (fishnet output), one of the methods of deciding which parts of the drawing should be visible is the `Template method'. Here the order of output is chosen to work from the front of the surface and calculate each section of the drawing in turn. In parallel with this, for each x-value on the screen, a y-value is stored indicating the largest value currently output. This builds up a `template' of the area of screen currently covered by the drawing. New lines are only drawn if they lie outside this area (i.e. if the new y-values are greater than those previously stored). This allows fast, accurate output of the drawing of the surface.
List-Priority Methods.
Depth-sort or Painters' Algorithm.
This relies on the polygons for output being sorted into order, so that the polygon furthest from the viewer is output first. It also assumes that output of a second polygon on top of the first will overwrite it and none of the earlier output will remain. This is true on most screens, but not on most printers or plotters. It is similar to the method used by painters in situations where the latest coat of paint conceals the ones below.
This may also be used for the case where the output is an image of the isometric projection of a surface. In this case, it is easy to output the patches of the surface with those furthest from the viewpoint being output first and the later ones drawn on top.
Another method of this type is Encarnacao's Priority Method .
Ray-tracing Methods.
These use the idea of dropping a line, or ray, from the viewpoint (or eye of the viewer) onto parts of the objects and on to the viewing plane. Appel's method of hidden surface removal introduces the concept of `quantitative invisibility' (counting the number of faces between the surface being tested and the viewer) and uses coherence to reduce the number of tests to give the correct output.
Methods for Curved Surfaces.
One example of such a method is Encarnacao's Scan-Grid Method .