TAPESTRY: The Art of Representation and Abstraction
Hidden Lines and Surfaces
What's it all about?
Sorting algorithms take advantage of the ubiquitous raster displays and plotters. On these devices new graphics completely obliterate and replace existing graphics on a pixel by pixel basis, without leaving any trace of the old graphic (in contrast to drawing on paper, where all old markings are visible until explicitly (and incompletely) erased).
How SORTING Works
The trick is to draw the model's polygons starting with the most distant one end ending with the closest one. Obviously, this is probably NOT the order in which the data was created, so the polygons must be reordered, or sorted, before the drawing actually begins. (During that process they may be culled, so that we don't bother processing invisible polygons.)
How SORTING Fails
The best illustration of how this approach can fail is provided by the situation shown in plan at right. A simple cruciform (X-shape) is extruded, producing two interlocking polygons.
This should look like the graphic at left. However, the sorting algorithm must draw either one or the other of the two intersecting polygons first (it operates on ENTIRE polygons after all), so it produces one of two incorrect images, such as the one shown at the right.
Sorting is so efficient in general that it is sometimes worth it to take the time to uncover interpenetrating polygons as a first step to the rendering, if both polygons are split along the line of intersection, a correct rendering will result.
Last updated: April, 2014
