Painter's algorithm: Difference between revisions

Revision as of 04:21, 31 October 2020

Revision as of 04:35, 31 October 2020

Line 34:

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. [[Newell's algorithm]], proposed in 1972, provides a method for cutting such polygons.<ref name=":0" /> Numerous methods have also been proposed in the field of [[computational geometry]].

=== Piercing Polygons ===

Line 42:

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.

== Variants ==

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.

=== Extended painter's algorithm ===

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

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

AAnother variant of painter's algorithm includes '''reverse painter's algorithm'''. isReverse sometimespainter's used, inalgorithm whichpaints 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.

== Other computer graphics algorithms ==

Numerous computer graphics algorithms have also been proposed in the field of [[computational geometry]].

These and otherThe flaws withof thepainter'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. 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==