Newell's algorithm

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 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.

Cyclic polygons must be eliminated to correctly sort them by depth

In that case Newell's algorithm tests the following :

1. Test for Z overlap; implied in the selection of the face Q from the sort list

2. The extreme coordinate values in X of the two faces do not overlap(minimax test in X)

3. The extreme coordinate values in Y of the two faces do not overlap (minimax test in Y)

4. All vertices of P lie deeper than the plane of Q

5. All vertices of Q lie closer to the viewpoint than the plane of P

6. The rasterisation of P and Q do not overlap

Note that the tests are given in order of increasing computational difficulty.

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 Characterization of Ten Hidden-Surface Algorithms”, Computing Surveys, Vol 6, No 1, March 1974
Newell, M E, Newell R. G, and sancha, T.L, “ A New Approach to the Shaded Picture Problem”, Proc ACM National Conf. 1972

External links

This computer graphics–related article is a stub. You can help Wikipedia by expanding it.