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.

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

The tests are given in order of increasing computational difficulty. The polygons must be planar. If the tests are all false, then switch the order of P and Q 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

edit
  • Sutherland, Ivan E.; Sproull, Robert F.; Schumacker, Robert A. (1974), "A characterization of ten hidden-surface algorithms", Computing Surveys, 6 (1): 1–55, CiteSeerX 10.1.1.132.8222, doi:10.1145/356625.356626, S2CID 14222390.
  • Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972), "A new approach to the shaded picture problem", Proc. ACM National Conference, pp. 443–450.

See also

edit
Stub icon

This computer graphics–related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Painter's algorithm

The painter's algorithm (also depth-sort algorithm and priority fill) is an algorithm for visible surface determination in 3D computer graphics that works

Algorithm

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ) is a finite sequence of mathematically rigorous instructions, typically used to solve

List of algorithms

An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem

Martin Newell (computer scientist)

1977 and Smallworld in 1987). At CADCentre, the two Newells and Tom Sancha developed Newell's algorithm, a technique for eliminating cyclic dependencies

Heuristic (computer science)

central to many informed search algorithms and optimization techniques for AI: A* Search Algorithm The A* search algorithm is one of the most popular heuristic

Dick Newell

for 3D process plant design. In 1972 Newell, his brother Martin and Tom Sancha proposed the Newell's algorithm procedure. He co-founded his first company

Alpha–beta pruning

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an

Scanline rendering

Scanline rendering (also scan line rendering and scan-line rendering) is an algorithm for visible surface determination, in 3D computer graphics, that works