Painter's algorithm

The painter's algorithm (also depth-sort algorithm and priority fill) is an algorithm for

topological ordering of a directed acyclic graph representing occlusions between objects.^[10]

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.

sort polygons by depth
for each polygon p:
    for each pixel that p covers:
        paint p.color on pixel

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

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

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

Basic graphical structure

The painter's algorithm is not as complex in structure as its other depth sorting algorithm counterparts.^[9][11] 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.^[8] This simplicity makes it useful in basic computer graphics output scenarios where an unsophisticated render will need to be made with little struggle.^[9]

Memory efficiency

In the early 70s, when the painter's algorithm was developed, physical memory was relatively small.^[12] 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.^[9]

Limitations

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.^[4]

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.^[4]

Efficiency

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

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.^[4]

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-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.^[13] 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]} 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

• ISBN 0-201-12110-7
  .

Wikimedia Commons has media related to Painter's problem.

External links

• 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