Painter's algorithm: Difference between revisions

Revision as of 02:58, 30 November 2020

Revision as of 02:59, 30 November 2020

Line 1:

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

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|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|lastlast1=Newell|firstfirst1=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 annualAnnual conferenceConference - 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|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|lastlast1=Wylie|firstfirst1=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, fallFall jointJoint computerComputer conferenceConference|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=|___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/books?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 ==

Line 30:

=== Memory Efficiency ===

In the early 70s, when the painter’s algorithm was developed, physical memory was relatively small<ref>{{Cite journal|lastlast1=Freiser|firstfirst1=M.|last2=Marcus|first2=P.|date=June 1969|title=A survey of some physical limitations on computer elements|url=https://ieeexplore.ieee.org/abstract/document/1066403|journal=IEEE Transactions on Magnetics|volume=5|issue=2|pages=82–90|doi=10.1109/TMAG.1969.1066403|bibcode=1969ITM.....5...82F|issn=1941-0069}}</ref>. This required programs to manage memory as efficiently as possible to conduct large tasks without crashing. The painter’s algorithm prioritizes the efficient use of memory but at the expense of higher processing power since all parts of all images must be rendered.<ref name=":1" />[[File:Painters problem.svg|thumb|right|Overlapping polygons can cause the algorithm to fail|285x285px]]

== Limitations ==

The algorithm can fail in some cases, including cyclic overlap or piercing polygons.

Line 50:

== Other computer graphics algorithms ==

The flaws of painter's algorithm led to the development of [[Z-buffering|Z-buffer]] techniques, which can be viewed as a development of the painter's algorithm by resolving depth conflicts on a pixel-by-pixel basis, reducing the need for a depth-based rendering order.<ref>{{Cite book|last=Nyberg|first=Daniel|url=http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-130849|title=Analysis of Two Common Hidden Surface Removal Algorithms, Painter&apos;s Algorithm &amp; Z-Buffering.|date=2011}}</ref> Even in such systems, a variant of the painter's algorithm is sometimes employed. As Z-buffer implementations generally rely on fixed-precision depth-buffer registers implemented in hardware, there is scope for visibility problems due to rounding error. These are overlaps or gaps at joints between polygons. To avoid this, some graphics engine implementations "overrender"{{Citation needed|date=January 2008}}, drawing the affected edges of both polygons in the order given by the painter's algorithm. This means that some pixels are actually drawn twice (as in the full painter's algorithm), but this happens on only small parts of the image and has a negligible performance effect.

==References==

* {{cite book |lastlast1 = Foley

|firstfirst1 = James

|authorlink = James D. Foley

|title = Computer Graphics: Principles and Practice