TAPESTRY: The Art of Representation and Abstraction
Depth Sorting
DEFINITION
An algorithm for creating a hidden-line drawing of polygon data sets by drawing the polygons from the most distant to the closest, in order.
EXPLANATION
Because raster displays destructively overwrite existing data when new objects are displayed (i.e., the new color data for a pixel in an overlap area completely replaces the previous color data), it is possible (with well-behaved data) to create an image in which hidden lines are removed (not visible) with minimal computational overhead. This is accomplished by displaying the polygons of which the scene is composed after sorting them according to their distance from the observer.
OPERATION
Most data is stored in the order it was created. When a program needs to display the data using a depth-sort, the polygons are preprocessed to determine their depth in the scene (obviously most are not perpendicular to the view vector, so some approximation may be performed). After preprocessing the polygons are drawn, in their entirety, to the screen. Any polygon or portion of polygon which is obscured by a closer polygon will be overwritten by that polygon when it (the closer one) is drawn. The net result is a hidden-line image.
BENEFITS
The sorting computation is very fast, so a quick calculation of the image display is possible.
The finished image data remains object based (sorted polygons), and can be edited in terms of line weight, "exploded" views, etc. It will also print at the highest resolution available on devices such as postscript laser printers.
LIMITATIONS
Certain conditions, such as intersecting polygons or cyclic overlap (A covers part of B, which covers part of C, which covers part of A), are not processed correctly, since parts of each *should* be visible, but the algorithm will always yield a sorted list.
Last updated: April, 2014
