Painter's algorithm: Difference between revisions

Revision as of 12:30, 19 January 2021

Revision as of 09:02, 6 May 2021

Line 5:

== Algorithm ==

Conceptually Painter’sPainter's Algorithm works as follows:

# Sort each polygon by depth

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

=== Pseudo-codePseudocode ===

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

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

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

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

=== Time-Complexity complexity ===

The painter's algorithm's time-complexity is heavily dependent on the sorting algorithm used to order the polygons. Assuming the use of the most 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.

=== Space-Complexity complexity ===

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.

Line 26:

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

=== Basic Graphicalgraphical Structurestructure ===

The painter’spainter'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 Efficiencyefficiency ===

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|url=https://ieeexplore.ieee.org/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 ==

Line 36:

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 Polygonspolygons ===

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

Line 73:

== External links ==

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

* [http://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