Painter's algorithm: Difference between revisions

Revision as of 16:48, 1 June 2022

Revision as of 16:08, 2 June 2022

Line 2:

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

[[File:Genesis fractal landscape software (Commodore Amiga).webm|thumb|upright=1.2|A [[fractal landscape]] being rendered using the painter’s algorithm on a [[Commodore Amiga]]]]

The '''painter’s algorithm''' (also '''depth-sort algorithm''' and '''priority fill''') is an algorithm for [[Hidden surface determination#Visible%20surface%20determination|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|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=deadlive|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’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|url=https://doi.org/10.1145/362736.362739|journal=Communications of the ACM|volume=13|issue=9|pages=527–536|doi=10.1145/362736.362739|s2cid=15941472|issn=0001-0782}}</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 journal|last1=Newell|first1=M. E.|last2=Newell|first2=R. G.|last3=Sancha|first3=T. L.|date=1972-08-01|title=A solution to the hidden surface problem|url=https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/newell-newell-sancha.pdf|journal=Proceedings of the ACM Annual Conference - Volume 1|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 journal|last1=Wylie|first1=Chris|last2=Romney|first2=Gordon|last3=Evans|first3=David|last4=Erdahl|first4=Alan|date=1967-11-14|title=Half-tone perspective drawings by computer|url=https://doi.org/10.1145/1465611.1465619|journal=Proceedings of the November 14–16, 1967, Fall Joint Computer Conference|series=AFIPS '67 (Fall)|___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}}</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.}}

Line 29:

=== Basic graphical structure ===

The painter's algorithm is not as complex in structure as its other depth sorting algorithm counterparts.<ref name=":1" /><ref>{{Cite journal|last=Warnock|first=John E.|date=1969-06-01|title=A Hidden Surface Algorithm for Computer Generated Halftone Pictures|url=https://apps.dtic.mil/sti/citations/AD0753671|archive-url=https://web.archive.org/web/20201108193625/https://apps.dtic.mil/sti/citations/AD0753671|url-status=deadlive|archive-date=November 8, 2020|language=en}}</ref> Components such as the depth-based rendering order, as employed by the painter’s algorithm, are one of the simplest ways to designate the order of graphical production.<ref name=":2" /> This simplicity makes it useful in basic computer graphics output scenarios where an unsophisticated render will need to be made with little struggle.<ref name=":1" />

=== Memory efficiency ===