Newells algoritm
Newell's Algorithm är en 3D-datorgrafikprocedur för eliminering av polygoncykler i den djupsortering som krävs vid borttagning av dold yta . Det föreslogs 1972 av bröderna Martin Newell och Dick Newell och Tom Sancha, medan alla tre arbetade på CADCentre .
Om två polygoner i djupsorteringsfasen för borttagning av dold yta inte har någon överlappande utsträckning eller extrema minimum- och maximivärden i x-, y- och z-riktningarna kan de enkelt sorteras. Om två polygoner, Q och P , har överlappande utsträckning i Z-riktningen, är det möjligt att skärning är nödvändig.
I så fall testar Newells algoritm följande:
- Testa för Z-överlappning; underförstått i valet av ansiktet Q från sorteringslistan
- De extrema koordinatvärdena i X av de två ytorna överlappar inte ( minimaxtest i X)
- De extrema koordinatvärdena i Y av de två ytorna överlappar inte (minimaxtest i Y)
- Alla hörn av P ligger djupare än planet för Q
- Alla hörn av Q ligger närmare synpunkten än planet för P
- Rasteriseringen av P och Q överlappar inte varandra
Testerna ges i ordning efter ökande beräkningssvårigheter. Polygonerna måste vara plana . Om alla tester är falska, byt sedan ordningen på P och Q i sorteringen, registrera efter att ha gjort det och försök igen. Om det görs ett försök att ändra ordningen på en polygon en andra gång, finns det en synlighetscykel och polygonerna måste delas. Uppdelningen görs genom att välja en polygon och skära den längs skärningslinjen med den andra polygonen. Ovanstående tester utförs igen och algoritmen fortsätter tills alla polygoner klarar ovanstående tester.
- 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.356625.356 .
- Newell, ME ; Newell, RG ; Sancha, TL (1972), "A new approach to the shaded picture problem", Proc. ACM National Conference , s. 443–450 .