Newell's algorithm: Difference between revisions

Revision as of 20:05, 22 February 2006

Revision as of 11:13, 8 April 2006

Line 1:

'''Newell's Algorithm''' is a [[3D computer graphics]] procedure for elimination of [[polygon]] cycles in the depth sorting required in [[Hidden_surface_determination | hidden surface removal]]. It was proposed in 1972 by [[M. E. Newell]], R . Newell and T. Sancha.

In the depth sorting phase of hidden surface removal, if two polygons have no overlaping '''extents''' or extreme minimum and maximum values in the x,y, and z directions, then they can be easily sorted. If two polygons, Q and P do have overlaping extents in the Z direction then it is possible that cutting is necessary.

Line 23:

Note also that the polygons must be [[planar]].

If the tests are all false, then the polygons must be split. Splitting is accomplished by selecting one polygon and cutting it along the line of intersection with the other polygon. The above tests are again performed and the algorithm continues until all polygons pass the above tests.

==References==

*Ivan E. Sutherland, Robert F, Sproull, and Robert A, Schumacker, “A"A Characterization of Ten Hidden-Surface Algorithms”Algorithms", Computing Surveys, Vol 6, No 1, March 1974

* Newell, M. E., Newell R. G., and sanchaSancha, T. L, “ "A New Approach to the Shaded Picture Problem”Problem", Proc ACM National Conf. 1972

==See also==

*[[Painter's algorithm]]

{{compu-graphics-stub}}