Newell's Algorithm is a3D computer graphics procedure for elimination ofpolygon cycles in the depth sorting required inhidden surface removal. It was proposed in 1972 by brothersMartin Newell andDick Newell, and Tom Sancha, while all three were working atCADCentre.
In the depth sorting phase of hidden surface removal, if two polygons have no overlappingextents or extreme minimum and maximum values in the x, y, and z directions, then they can be easily sorted. If two polygons,Q andP, 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:
The tests are given in order of increasing computational difficulty. The polygons must beplanar. If the tests are all false, then switch the order ofP andQ 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. 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.
 | Thiscomputer graphics–related article is astub. You can help Wikipedia byexpanding it. |