Newell's Algorithm is a

3D computer graphics 3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...

procedure for elimination of

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

cycles in the depth sorting required in

hidden surface removal In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts o ...

. It was proposed in 1972 by brothers Martin Newell and

Dick Newell Richard G. Newell is a British businessman and technologist in the software industry in Computer aided design (CAD) and Geographic Information Systems (GIS). Career Newell holds degrees in Civil Engineering and Numerical Analysis and a PhD in Chem ...

, 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 Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...

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 In computer graphics, rasterisation (British English) or rasterization (American English) is the task of taking an image described in a vector graphics format (shapes) and converting it into a raster image (a series of pixels, dots or lines, whic ...

of and do not overlap The tests are given in order of increasing computational difficulty. The polygons must be

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

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

*. *.

References

See also