Newell's algorithm

The depth - sort algorithm (English literally means " deep sort algorithm " ) is in computer graphics, an algorithm for occlusion 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 by their distance from the viewer, and then, starting with the farthest polygon to draw all one by one. Here, drawn parts are overwritten by nearer objects when they completely or partially overlap. When the Order was executed properly, this procedure provides a correct view of hidden surfaces.

Steps

The sorting of two polygons P and Q on the depth ( z- direction) occurs in several steps.

The polygons must be planar, that is, all vertices must lie on a plane. The test, whether all vertices on a plane, is performed by inserting the coordinates of all points in the plane equation.

The sequence of steps is selected so that the simple test and the complex first checks are used in the end in order to require less computational time.

The depth - sort algorithm uses much less memory resources than, say, the more commonly used z-buffer algorithm for hidden surface computing, but this is clearly inferior in speed.