Newell's algorithm

Newell's algorithm is a procedure from three-dimensional computer graphics for removing cycles among polygons during the depth sorting step of hidden-surface removal. It was proposed in 1972 by the brothers Martin Newell and Dick Newell together with Tom Sancha, all then working at CADCentre. When two polygons overlap in depth, the algorithm applies a sequence of tests, ordered from cheapest to most expensive: whether their extents overlap in x or in y, whether all vertices of one polygon lie deeper than the plane of the other or the reverse, and finally whether their rasterisations overlap. If every test fails, the two polygons are swapped in the sort order and the tests are repeated. A second attempt to swap the same polygon signals a visibility cycle, and one polygon is then cut along its line of intersection with the other, after which the tests run again until every polygon passes. The method assumes that the polygons are planar, and it is closely related to the painter's algorithm, which sorts polygons from far to near.