Newell's algorithm: Difference between revisions

Revision as of 20:04, 22 February 2006

Latest revision as of 01:20, 8 May 2023

(22 intermediate revisions by 18 users not shown)

Line 1:

'''Newell's Algorithm''' is a [[3D computer graphics]] procedure for elimination of [[polygon]] cycles in the depth sorting required in [[Hidden_surface_determinationHidden |surface determination |hidden surface removal]]. It was proposed in 1972 by M.Ebrothers [[Martin Newell, R(computer .scientist)|Martin Newell]] and T.[[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 overlapingoverlapping '''extents''' or extreme minimum and maximum values in the x, y, and z directions, then they can be easily sorted. If two polygons, {{var|Q}} and {{var|P}}, do have overlapingoverlapping extents in the Z direction, then it is possible that cutting is necessary.

[[Image:Painters_problem.png|right|frame|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 {{var|Q}} from the sort list

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

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

# 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 {{var|Q}}

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

5.# All vertices of Q lie closer to the viewpoint than the plane of {{var|P}}

3.# The extreme coordinate values in Y[[rasterisation]] of the{{var|P}} twoand faces{{var|Q}} 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.

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

Note also that theThe polygons must be [[plane (geometry)|planar]].

If the tests are all false, then switch the order of {{var|P}} and {{var|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==

*{{citation

*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

| last1 = Sutherland | first1 = Ivan E. | author1-link = Ivan Sutherland

* Newell, M E, Newell R. G, and sancha, T.L, “ A New Approach to the Shaded Picture Problem”, Proc ACM National Conf. 1972

| last2 = Sproull | first2 = Robert F. | author2-link = Bob Sproull

| last3 = Schumacker | first3 = Robert A.

| doi = 10.1145/356625.356626

| issue = 1

| journal = Computing Surveys

| pages = 1–55

| title = A characterization of ten hidden-surface algorithms

| volume = 6

| year = 1974| citeseerx = 10.1.1.132.8222 | s2cid = 14222390 }}.

*{{citation

| last1 = Newell | first1 = M. E. | author1-link = Martin Newell (computer scientist)

| last2 = Newell | first2 = R. G. | author2-link = Dick Newell

| last3 = Sancha | first3 = T. L.

| contribution = A new approach to the shaded picture problem

| pages = 443–450

| title = Proc. ACM National Conference

| year = 1972}}.

==See also==

* [[Painter's algorithm]]

* [[Boolean operations on polygons]]

{{compu-graphics-stub}}

==External links==

*[http://www.evl.uic.edu/aej/488/lecture11.html|Electronic Visualization Labratory, University Illinois at Chicago]

{{compu-graphics-stub}}

[[Category:3D computer graphics]]

[[Category:Computer graphics algorithms]]

[[Category:History of computing in the United Kingdom]]

[[Category:Science and technology in Cambridgeshire]]