Newell's algorithm
Encyclopedia
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, Q and P, 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:
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.
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
procedure for elimination of polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
cycles in the depth sorting required in hidden surface removal
Hidden surface determination
In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint...
. It was proposed in 1972 by brothers Martin Newell
Martin Newell
Martin Newell may refer to:*Martin Newell , British computer scientist, creator of the Utah teapot*Martin Newell , British rock musician, poet and author, known as "the Wild Man of Wivenhoe"...
and Dick Newell
Dick Newell
Dr. Richard G. Newell has spent over 30 years in the software industry in Computer aided design and Geographic Information Systems .Dick holds degrees in Civil Engineering and Numerical Analysis and a PhD in Chemical Engineering....
, and Tom Sancha, while all three were working at CADCentre
CADCentre
AVEVA Group plc is a British multinational company headquartered in Cambridge, United Kingdom. It provides engineering design, information management solutions, and CAD/CAM software along with technology consulting services for the Plant , Power and Marine industries.It is listed on the...
.
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, Q and P, do have overlapping extents in the Z direction, then it is possible that cutting is necessary.
- Test for Z overlap; implied in the selection of the face Q from the sort list
- The extreme coordinate values in X of the two faces do not overlap (minimaxMinimaxMinimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
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 Q
- All vertices of Q lie closer to the viewpoint than the plane of P
- The rasterisationRasterisationRasterisation is the task of taking an image described in a vector graphics format and converting it into a raster image for output on a video display or printer, or for storage in a bitmap file format....
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
Planar
In computer graphics, planar is the method of representing pixel colours with several bitplanes of RAM. Each bit in a bitplane is related to one pixel on the screen...
.
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.