User:HexUser32F/sandbox
The painter’s algorithm (also depth-sort algorithm and priority fill) is an algorithm for visible surface determination, in 3D computer graphics, that works on a polygon-by-polygon basis rather than a pixel-by-pixel, row by row, or area by area basis of other Hidden Surface Removal algorithms.[1][2][3][4][5][6][7] 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.[8]
The painter's algorithm was initially proposed as a basic method to address the Hidden-surface determination problem by Martin Newell, Richard Newell, and Tom Sancha in 1972, while all three were working at CADCentre.[1] 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 which are nearer thereby covering some areas of distant parts.[9] 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.[10] 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.[11] The ordering used by the algorithm is called a 'depth order', 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.[11] Thus, a valid ordering can be described as a topological ordering of a directed acyclic graph representing occlusions between objects.[12]
The algorithm can fail in some cases, including cyclic overlap or piercing polygons. 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. Newell's algorithm, proposed in 1972, provides a method for cutting such polygons. Numerous methods have also been proposed in the field of computational geometry.
The case of piercing polygons arises when one polygon intersects another. As with cyclic overlap, this problem may be resolved by cutting the offending polygons.
In basic implementations, the painter's algorithm can be inefficient. It forces the system to 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.
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 (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.
These and other flaws with the algorithm led to the development of 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 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], 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 painter's algorithm) but this happens on only small parts of the image and has a negligible performance effect.
Overview and History
[edit]Algorithm
[edit]Conceptually Painter’s Algorithm works as follows:
- Sort each polygon by depth
- Place each polygon from the furthest polygon to the closest polygon
Pseudo-code
[edit]1 sort polygons by depth 2 for each polygon p: 3 for each pixel: 4 paint p.color on pixel
Time-Complexity
[edit]Space-Complexity
[edit]Uses
[edit]Limitations
[edit]The algorithm can fail in some cases, including cyclic overlap or piercing polygons. 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. Newell's algorithm, proposed in 1972, provides a method for cutting such polygons. Numerous methods have also been proposed in the field of computational geometry.
The case of piercing polygons arises when one polygon intersects another. As with cyclic overlap, this problem may be resolved by cutting the offending polygons.
In basic implementations, the painter's algorithm can be inefficient. It forces the system to 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.
Variants
[edit]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 (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.
These and other flaws with the algorithm led to the development of 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 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], 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 painter's algorithm) but this happens on only small parts of the image and has a negligible performance effect.
[13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26]
References
[edit]- ^ a b Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972-08-01). "A solution to the hidden surface problem" (PDF). Proceedings of the ACM annual conference - Volume 1. ACM '72. Boston, Massachusetts, USA: Association for Computing Machinery: 443–450. doi:10.1145/800193.569954. ISBN 978-1-4503-7491-0.
- ^ Appel, Arthur (1968). Morrel, A. J. H. (ed.). "On calculating the illusion of reality" (PDF). Information Processing, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968, Volume 2 - Hardware, Applications: 945–950.
- ^ Wylie, Chris; Romney, Gordon; Evans, David; Erdahl, Alan (1967-11-14). "Half-tone perspective drawings by computer". Proceedings of the November 14-16, 1967, fall joint computer conference. AFIPS '67 (Fall). Anaheim, California: Association for Computing Machinery: 49–58. doi:10.1145/1465611.1465619. ISBN 978-1-4503-7896-3.
- ^ Romney, Gordon Wilson (1969-09-01). "Computer Assisted Assembly and Rendering of Solids".
{{cite journal}}: Cite journal requires|journal=(help) - ^ Gary Scott Watkins. 1970. "A real time visible surface algorithm. Ph.D. Dissertation." The University of Utah. Order Number: AAI7023061.
- ^ Bouknight, W. Jack (1970-09-01). "A procedure for generation of three-dimensional half-toned computer graphics presentations". Communications of the ACM. 13 (9): 527–536. doi:10.1145/362736.362739. ISSN 0001-0782.
- ^ Warnock, John E. (1969-06-01). "A Hidden Surface Algorithm for Computer Generated Halftone Pictures".
{{cite journal}}: Cite journal requires|journal=(help) - ^ Nyberg, Daniel (2011). "Analysis of Two Common Hidden Surface Removal Algorithms, Painter's Algorithm & Z-Buffering". KTH, School of Computer Science and Communication.
- ^ Berland, Dinah (1995). Historical Painting Techniques, Materials, and Studio Practice. https://www.getty.edu/conservation/publications_resources/pdf_publications/pdf/historical_paintings.pdf: The Getty Conservation Institute.
{{cite book}}: External link in|location= - ^ Desai, Apurva (2008). Computer Graphics. 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: PHI Learning Pvt. Ltd.
{{cite book}}: External link in|location= - ^ a b de Berg, Mark (2008). Computational Geometry. https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf: Springer.
{{cite book}}: External link in|location= - ^ de Berg, Mark (1993). Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science. Vol. 703. Springer. p. 130. ISBN 9783540570202{{inconsistent citations}}
{{cite book}}: CS1 maint: postscript (link). - ^ de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark, eds. (2008), "Binary Space Partitions", Computational Geometry: Algorithms and Applications, Berlin, Heidelberg: Springer, pp. 259–281, doi:10.1007/978-3-540-77974-2_12, ISBN 978-3-540-77974-2, retrieved 2020-10-21
- ^ Nyberg, Daniel (2011). Analysis of Two Common Hidden Surface Removal Algorithms, Painter's Algorithm & Z-Buffering.
- ^ DESAI, APURVA A. (2008-10-22). Computer Graphics. PHI Learning Pvt. Ltd. ISBN 978-81-203-3524-0.
- ^ http://www.cs.cmu.edu/afs/cs/project/anim/ph/463.96/pub/www/notes/zbuf.2.pdf
- ^ https://www.clear.rice.edu/comp360/lectures/old/HiddenSurfText.pdf
- ^ https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene93.pdf
- ^ Computational geometry : algorithms and applications (PDF). Berg, Mark de. (3rd ed ed.). Berlin: Springer. 2008. ISBN 978-3-540-77974-2. OCLC 261325416.
{{cite book}}:|edition=has extra text (help)CS1 maint: others (link) - ^ Historical painting techniques, materials, and studio practice : preprints of a symposium, University of Leiden, the Netherlands, 26-29 June, 1995 (PDF). Wallert, Arie, 1950-, Hermens, Erma, 1958-, Peek, Marja, 1961-. [Marina Del Rey, Calif.]: Getty Conservation Institute. 1995. ISBN 0-89236-322-3. OCLC 32131812.
{{cite book}}: CS1 maint: others (link) - ^ https://www.cs.utexas.edu/~bajaj/graphics2012/cs354/lectures/lect23.pdf
- ^ Jia, Z.; Gallagher, A.; Chang, Y.; Chen, T. (2012-06). "A learning-based framework for depth ordering". 2012 IEEE Conference on Computer Vision and Pattern Recognition: 294–301. doi:10.1109/CVPR.2012.6247688.
{{cite journal}}: Check date values in:|date=(help) - ^ https://bioinformatics.cs.vt.edu/~murali/papers/thesis/
- ^ http://design.inf.unisi.ch/sites/default/files/biblio/webist2018.pdf
- ^ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.299.1541&rep=rep1&type=pdf
- ^ http://www.math.tau.ac.il/~michas/pierce.pdf
 | This is a user sandbox of HexUser32F. You can use it for testing or practicing edits. This is not the sandbox where you should draft your assigned article for a dashboard.wikiedu.org course. To find the right sandbox for your assignment, visit your Dashboard course page and follow the Sandbox Draft link for your assigned article in the My Articles section. |