Painter's algorithm: Difference between revisions

Revision as of 17:59, 10 June 2007

Latest revision as of 04:41, 27 August 2025

(141 intermediate revisions by 83 users not shown)

Line 1:

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

The '''painter's algorithm''', also known as a '''priority fill''', is one of the simplest solutions to the [[visibility problem]] in [[3D computer graphics]]. When projecting a 3D scene onto a 2D plane, it is at some point necessary to decide which [[polygon]]s are visible and which are [[Hidden surface determination|hidden]].

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

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

The '''painter'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 determination]] 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'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 name "painter's algorithm" refers to a simple-minded painter who paints the distant parts of a scene at first and then covers them by those parts which are nearer. The painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order. It will over-paint the parts that are normally not visible -- thus solving the visibility problem -- though at the cost of having painted redundant areas of distant objects.

<center>

[[Image:Painter's_algorithm.png|600px|center|thumb|The distant mountains are painted first, followed by the closer meadows; finally, the closest objects in this scene, the trees, are painted.]]

</center>

[[Image:Painters_problem.png|right|frame|Overlapping polygons can cause the algorithm to fail]]

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.}}

The algorithm can fail in certain cases. In this example, Polygons A, B and C overlap each other. It's not possible to decide which polygon is above the others or when two polygons intersect one another in three dimensions. In this case the offending polygons must be cut in some way to allow sorting to occur. [[Newell's_algorithm|Newell's algorithm]] proposed in 1972 gives a method for cutting such polygons. Numerous methods have also been proposed in the field of [[Computational_geometry|computational geometry]].

== Algorithm ==

In basic implementations, the painter's algorithm can be inefficient. It forces the system to [[rendering (computer graphics)|render]] each point on every polygon in the visible set, even if that polygon is occluded in the finished scene. This means that, for detailed scenes, the painter's algorithm can overly tax the computer hardware.

Conceptually Painter's Algorithm works as follows:

# Sort each polygon by depth

A '''Reverse painter's algorithm''' is sometimes used in which objects nearest to the viewer are painted first - with the rule that paint must never be applied to parts of the image that are already painted. In a computer graphic system, this can be made to be very efficient since it is not necessary to calculate the colors (using lighting, texturing and such) for parts of the more distant scene that are hidden by nearby objects. However, the reverse algorithm suffers from many of the same problems as the normal version.

# Place each polygon from the farthest polygon to the closest polygon

=== Pseudocode ===

These and other flaws with the 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. Even in such systems, a variant of 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 joins between polygons. To avoid this, some graphics engine implementations "overrender", drawing the affected edges of both polygons in the order given by painter's algorithm. This means that some pixels are actually drawn twice (as in the full painters algorithm) but this happens on only small parts of the image and has a negligible performance effect.

'''sort''' ''polygons'' by ''depth''

'''for each''' ''polygon'' ''p'':

'''for each''' ''pixel'' that ''p'' covers:

'''paint''' ''p.color'' on ''pixel''

=== ExternalTime linksscomplexity ===

The painter's algorithm's time-complexity depends on the [[sorting algorithm]] used to order the polygons. Assuming an optimal sorting algorithm, painter's algorithm has a worst-case complexity of ''[[Big O notation|O]]''(''n'' log ''n + m*n''), where ''n'' is the number of polygons and ''m'' is the number of pixels to be filled.

*[http://www.siggraph.org/education/materials/HyperGraph/scanline/visibility/painter.htm Siggraph Education]

=== Space complexity ===

[[Category:3D computer graphics]]

The painter's algorithm's worst-case space-complexity is ''O''(''n+m''), where ''n'' is the number of polygons and ''m'' is the number of pixels to be filled.

== Advantages ==

[[de:Maleralgorithmus]]

There are two primary technical requisites that favor the use of the painter's algorithm.

[[es:Algoritmo del pintor]]

[[fr:Algorithme du peintre]]

=== Basic graphical structure ===

[[nl:Schildersalgoritme]]

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=live|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" />

[[pl:Algorytm malarza]]

[[pt:Algoritmo do Pintor]]

=== Memory efficiency ===

[[zh:画家算法]]

In the early 70s, when the painter's algorithm was developed, physical memory was relatively small.<ref>{{Cite journal|last1=Freiser|first1=M.|last2=Marcus|first2=P.|date=June 1969|title=A survey of some physical limitations on computer elements|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" />

== Limitations ==

[[File:Painters problem.svg|thumb|Overlapping polygons can cause the algorithm to fail.]]

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

=== Cyclical overlapping ===

In the case of cyclic overlap, as shown in the figure to the right, Polygons A, B, and C overlap each other in such a way that it is impossible to determine which polygon is above the others. In this case, the offending polygons must be cut to allow sorting.<ref name=":0" />

=== Piercing polygons ===

The case of piercing polygons arises when one polygon intersects another. Similar to cyclic overlap, this problem may be resolved by cutting the offending polygons.<ref name=":0" />

=== Efficiency ===

In basic implementations, the painter's algorithm can be inefficient. It forces the system to [[rendering (computer graphics)|render]] each point on every polygon in the visible set, even if that polygon is occluded in the finished scene. This means that, for detailed scenes, the painter's algorithm can overly tax the computer hardware.

== Reducing visual errors ==

There are a few ways to reduce the visual errors that can happen with sorting:

=== Binary Space Partitioning ===

BSP is a method that involves making a BSP tree, and splitting triangles where they intersect. It can be extremely hard to implement, but it fixes most visual errors.

=== Backface culling ===

Backface culling involves calculations to see if a triangles points will appear clockwise or counter-clockwise once projected to the screen, and doesn't draw triangles that shouldn't be visible anyway. It reduces some visual errors, as well as reducing the total triangles drawn.

== Variants ==

=== Extended painter's algorithm ===

[[Newell's algorithm]], proposed as the extended algorithm to painter's algorithm, provides a method for cutting cyclical and piercing polygons.<ref name=":0" />

=== Reverse painter's algorithm ===

Another variant of painter's algorithm includes '''reverse painter's algorithm'''. Reverse painter's algorithm paints objects nearest to the viewer first — with the rule that paint must never be applied to parts of the image that are already painted (unless they are partially transparent). In a computer graphic system, this can be very efficient since it is not necessary to calculate the colors (using lighting, texturing, and such) for parts of a distant scene that are hidden by nearby objects. However, the reverse algorithm suffers from many of the same problems as the standard version.

== 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's Algorithm & 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 engines implement "over-rendering",{{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

|last1 = Foley

|first1 = James

|author-link = James D. Foley

|title = Computer Graphics: Principles and Practice

|publisher = [[Addison-Wesley]]

|year = 1990

|___location = Reading, MA, USA

|page = [https://archive.org/details/computergraphics00fole/page/1174 1174]

|isbn = 0-201-12110-7

|last2 = Feiner

|first2 = Steven K.

|last3 = Hughes

|first3 = John F.

|title-link = Computer Graphics: Principles and Practice

|author-link3 = John F. Hughes (computer scientist)

}}

<references />

{{commons category|Painter's problem}}

== External links ==

* [https://www.cs.cmu.edu/afs/cs/project/anim/ph/463.96/pub/www/notes/zbuf.2.pdf Painter's & Z-Buffer Algorithms and Polygon Rendering]

* https://www.clear.rice.edu/comp360/lectures/old/HiddenSurfText.pdf

* https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene93.pdf

{{Computer graphics}}

[[Category:3D computer graphics]]

[[Category:Computer graphics algorithms]]