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 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 determination algorithms. 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.
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. 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. 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. 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. 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.
Algorithm
Conceptually Painter's Algorithm works as follows:
- Sort each polygon by depth
- Place each polygon from the farthest polygon to the closest polygon
Pseudocode
sort polygons by depth
for each polygon p:
for each pixel that p covers:
paint p.color on pixel
Time complexity
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 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. 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. 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. 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", 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.