Content deleted Content added
Hangandrew (talk | contribs) →Other computer graphics algorithms: Added citation for relation with zbuffer and painters |
Skkapur1471 (talk | contribs) m Citation changes and minor punctuation changes. |
||
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.
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-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. -->{{inconsistent citations}}}}.</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 29 ⟶ 30:
=== 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|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 ===
Line 42 ⟶ 43:
=== Efficiency ===
In basic implementations, the painter's algorithm can be inefficient.
== Variants ==
| |||