Newell's algorithm

Article summary

Newell's Algorithm is a 3D computer graphics procedure for elimination of polygon cycles in the depth sorting required in hidden-surface removal. It was proposed in 1972 by brothers Martin Newell and Dick Newell, and Tom Sancha, while all three were working at CADCentre. In the depth sorting phase of hidden-surface removal, if two polygons have no overlapping extents or extreme minimum and maximum values in the x, y, and z directions, then they can be easily sorted. If two polygons, and , do have overlapping extents in the Z direction, then it is possible that cutting is necessary. In that case, Newell's algorithm tests the following: # Test for Z overlap; implied in the selection of the face from the sort list # The extreme coordinate values in X of the two faces do not overlap (minimax test in X) # The extreme coordinate values in Y of the two faces do not overlap (minimax test in Y) # All vertices of P lie deeper than the plane of # All vertices of Q lie closer to the viewpoint than the plane of # The rasterisation of and do not overlap The tests are given in order of increasing computational difficulty. The polygons must be planar. If the tests are all false, then switch the order of and in the sort, record having done so, and try again. If there is an attempt to switch the order of a polygon a second time, there is a visibility cycle, and the polygons must be split.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.