Depth sort algorithm

from Wikipedia, the free encyclopedia

The depth sort algorithm (English literally "depth sorting algorithm") is in computer graphics an algorithm for concealment calculation . It was introduced in 1972 by the brothers Martin E. Newell and Richard G. Newell and Tom Sancha.

The basic idea is to sort the polygons to be drawn according to their distance from the viewer and then to draw them all one after the other, starting with the most distant polygon. Parts that have already been drawn are overwritten by objects that are closer to one another if they partially or completely overlap. If the sort is done correctly, this procedure will provide a correct view of hidden surfaces.

steps

The sorting of two polygons P and Q according to depth (Z-direction) takes place in several steps.

Cyclic polygons must be avoided in order to sort correctly by depth
  1. If the extreme values ​​of the Z coordinates of all corner points of P are further back than those of Q , the sorting is trivial. P is sorted further back.
  2. If the polygons to be compared do not have any overlap of their extreme values ​​in x, y, they do not need to be sorted because they do not overlap.
  3. If all corner points of P are further away from the viewer than the plane of Q , P is sorted further back.
  4. If all corner points of Q are closer to the viewer than the plane of P , P is sorted further back.
  5. If the x, y values ​​of P and Q do not overlap anywhere, there is no need to sort.
  6. If sorting was still not possible here, it is a question of cyclic overlapping polygons. In this case, these must be divided up and the sorting continued with the parts that are no longer cyclically overlapping. The subdivision takes place on one of the polygons at the intersection with the other polygon.

The polygons must be planar , that is, all corner points must lie on one plane. The check of whether all corner points are on one plane is carried out by inserting the coordinates of all points into the plane equation .

The order of the steps is chosen so that the simple tests are used first and the more complex tests are used at the end in order to require less computing time.

The depth sort algorithm uses much less memory resources than, for example, the more frequently used Z-buffer algorithm for calculating hidden surfaces, but it is significantly inferior in terms of speed.

See also

literature

  • ME Newell et al: A Solution to the Hidden Surface Problem. In: Proceedings of the ACM Annual Conference 1972. Volume 1, ACM, New York 1972.