Painter's algorithm: Difference between revisions

Revision as of 11:51, 31 October 2020

Revision as of 02:58, 30 November 2020

Line 2:

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|volume=|pages=945–950|via=}}</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|language=en}}</ref><ref>Gary Scott Watkins. 1970. [https://ia800301.us.archive.org/29/items/utech-csc-70-101_watkins_dissertation_jun70/UTECH-CSc-70-101_Watkins_Dissertation_Jun70.pdf "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|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|last=Newell|first=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=|pages=443–450|doi=10.1145/800193.569954|isbn=978-1-4503-7491-0|via=}}</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|isbn=|___location=https://www.getty.edu/conservation/publications_resources/pdf_publications/pdf/historical_paintings.pdf|pages=}}</ref><ref>{{Cite journal|last=Wylie|first=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-1614–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}}</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=|___location=https://books.google.com/books?id=WQiIj8ZS0IoC&pg=PA256&lpg=PA256&dq=%22hewells%22+painter%27s+algorithm&source=bl&ots=HbWXoialNt&sig=ACfU3U0do0uKya5QGDaBUKKrXoYJ3uULdA&hl=en&sa=X&ved=2ahUKEwjh1tC14MHsAhUogK0KHWS5BsQQ6AEwAnoECAoQAg#v=onepage&q&f=false|pages=}}</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|isbn=|___location=https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf|pages=}}</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/?id=b1INPTC3w_QC&pg=PA130|page=130|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->&#123;&#123;inconsistent citations&#125;&#125;}}.</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.}}

== Algorithm ==