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:
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 (minimax 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 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.
Referencesedit
Sutherland, Ivan E.; Sproull, Robert F.; Schumacker, Robert A. (1974), "A characterization of ten hidden-surface algorithms", Computing Surveys, 6 (1): 1–55, CiteSeerX10.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.
newell, algorithm, newell, algorithm, computer, graphics, procedure, elimination, polygon, cycles, depth, sorting, required, hidden, surface, removal, proposed, 1972, brothers, martin, newell, dick, newell, sancha, while, three, were, working, cadcentre, depth. 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 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 minimax 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 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 editSutherland 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 editPainter s algorithm Boolean operations on polygons nbsp This computer graphics related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Newell 27s algorithm amp oldid 1153736058, wikipedia, wiki, book, books, library,
