Painter's algorithm: Difference between revisions

Revision as of 11:26, 31 December 2023

Revision as of 05:58, 21 March 2024

Line 1:

{{Short description|Algorithm for visible surface determination in 3D graphics}}

{{Distinguish|Schlemiel the Painter's algorithm}}

[[File:Genesis fractal landscape software (Commodore Amiga).webm|thumb|A [[fractal landscape]] being rendered using the painter’spainter's algorithm on an Amiga]]

The '''painter’spainter's algorithm''' (also '''depth-sort algorithm''' and '''priority fill''') is an algorithm for [[Hidden-surface determination#Visible surface determination|visible surface determination]] in [[3D computer graphics]] that works on a [[polygon|polygon-by-polygon]] basis rather than a [[pixel|pixel-by-pixel]], row by row, or area by area basis of other [[hidden surface removal|Hidden-Surface Removal]] algorithms.<ref>{{Cite journal|last=Appel|first=Arthur|date=1968|editor-last=Morrel|editor-first=A. J. H.|title=On calculating the illusion of reality|url=http://graphics.stanford.edu/courses/Appel.pdf |archive-url=https://web.archive.org/web/20080720031432/http://graphics.stanford.edu/courses/Appel.pdf |archive-date=2008-07-20 |url-status=live|journal=Information Processing, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968, Volume 2 - Hardware, Applications|pages=945–950}}</ref><ref>{{Cite journal|last=Romney|first=Gordon Wilson|date=1969-09-01|title=Computer Assisted Assembly and Rendering of Solids.|url=https://apps.dtic.mil/sti/citations/AD0753673|archive-url=https://web.archive.org/web/20201102232139/https://apps.dtic.mil/sti/citations/AD0753673|url-status=live|archive-date=November 2, 2020|language=en}}</ref><ref>Gary Scott Watkins. 1970. [https://archive.org/details/utech-csc-70-101_watkins_dissertation_jun70 "A real time visible surface algorithm. Ph.D. Dissertation."] The University of Utah. Order Number: AAI7023061.</ref> The painter’spainter's algorithm creates images by sorting the polygons within the image by their depth and placing each polygon in order from the farthest to the closest object.<ref name=":0" /><ref>{{Cite journal|last=Bouknight|first=W. Jack|date=1970-09-01|title=A procedure for generation of three-dimensional half-toned computer graphics presentations|journal=Communications of the ACM|volume=13|issue=9|pages=527–536|doi=10.1145/362736.362739|s2cid=15941472|issn=0001-0782|doi-access=free}}</ref>

The painter's algorithm was initially proposed as a basic method to address the [[Hidden-surface determination]] problem by [[Martin Newell (computer scientist)|Martin Newell]], [[Dick Newell|Richard Newell]], and Tom Sancha in 1972, while all three were working at [[CADCentre]].<ref name=":0">{{Cite book|last1=Newell|first1=M. E.|last2=Newell|first2=R. G.|last3=Sancha|first3=T. L.|title=Proceedings of the ACM annual conference on - ACM'72 |chapter=A solution to the hidden surface problem |date=1972-08-01|chapter-url=https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/newell-newell-sancha.pdf |archive-url=https://web.archive.org/web/20200922053518/https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/newell-newell-sancha.pdf |archive-date=2020-09-22 |url-status=live|series=ACM '72|___location=Boston, Massachusetts, USA|publisher=Association for Computing Machinery|volume=1|pages=443–450|doi=10.1145/800193.569954|isbn=978-1-4503-7491-0|s2cid=13829930}}</ref> The name "painter's algorithm" refers to the technique employed by many painters where they begin by painting distant parts of a scene before parts that are nearer, thereby covering some areas of distant parts.<ref>{{Cite book|last=Berland|first=Dinah|title=Historical Painting Techniques, Materials, and Studio Practice|publisher=The Getty Conservation Institute|year=1995|url=https://www.getty.edu/conservation/publications_resources/pdf_publications/pdf/historical_paintings.pdf}}</ref><ref>{{Cite book|last1=Wylie|first1=Chris|last2=Romney|first2=Gordon|last3=Evans|first3=David|last4=Erdahl|first4=Alan|title=Proceedings of the November 14-16, 1967, fall joint computer conference on - AFIPS '67 (Fall) |chapter=Half-tone perspective drawings by computer |date=1967-11-14|chapter-url=https://doi.org/10.1145/1465611.1465619|___location=Anaheim, California|publisher=Association for Computing Machinery|pages=49–58|doi=10.1145/1465611.1465619|isbn=978-1-4503-7896-3|s2cid=3282975}}</ref> Similarly, the painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest.<ref name=":2">{{Cite book|last=Desai|first=Apurva|title=Computer Graphics|publisher=PHI Learning Pvt. Ltd.|year=2008|isbn=9788120335240|url=https://books.google.com/books?id=WQiIj8ZS0IoC&dq=%22hewells%22+painter%27s+algorithm&pg=PA256}}</ref> It will paint over the parts that are normally not visible — thus solving the visibility problem — at the cost of having painted invisible areas of distant objects.<ref name=":1">{{Cite book|last=de Berg|first=Mark|title=Computational Geometry|publisher=Springer|year=2008|url=https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf |archive-url=https://web.archive.org/web/20160803163744/http://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf |archive-date=2016-08-03 |url-status=live}}</ref> The ordering used by the algorithm is called a '''<nowiki>depth order'</nowiki>'' and does not have to respect the numerical distances to the parts of the scene: the essential property of this ordering is, rather, that if one object obscures part of another, then the first object is painted after the object that it obscures.<ref name=":1" /> Thus, a valid ordering can be described as a [[topological ordering]] of a [[directed acyclic graph]] representing occlusions between objects.<ref>{{Cite book|title=Ray Shooting, Depth Orders and Hidden Surface Removal|volume=703|series=Lecture Notes in Computer Science|first=Mark|last=de Berg|publisher=Springer|year=1993|isbn=9783540570202|url=https://books.google.com/books?id=b1INPTC3w_QC&pg=PA130|page=130}}.</ref>{{wide image|Painter's algorithm.svg|600px|The distant mountains are painted first, followed by the closer meadows; finally, the trees, are painted. Although some trees are more distant from the viewpoint than some parts of the meadows, the ordering (mountains, meadows, trees) forms a valid depth order, because no object in the ordering obscures any part of a later object.}}