Painter's algorithm
From Wikipedia, the free encyclopedia
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics. When projecting a 3D scene onto a 2D plane, it is at some point necessary to decide which polygons are visible and which are hidden.
The name "painter's algorithm" refers to a simple-minded painter who paints the distant parts of a scene at first and then covers them by those parts which are nearer. The painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order. It will over-paint the parts that are normally not visible -- thus solving the visibility problem -- though at the cost of having painted redundant areas of distant objects.
The algorithm can fail in certain cases. In this example, Polygons A, B and C overlap each other. It's not possible to decide which polygon is above the others or when two polygons intersect one another in three dimensions. In this case the offending polygons must be cut in some way to allow sorting to occur. Newell's algorithm proposed in 1972 gives a method for cutting such polygons. Numerous methods have also been proposed in the field of computational geometry.
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. In a computer graphic system, this can be made to be very efficient since it is not necessary to calculate the colors (using lighting, texturing and such) for parts of the more distant scene that are hidden by nearby objects. However, the reverse algorithm suffers from many of the same problems as the normal 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 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 joins between polygons. To avoid this, some graphics engine implementations "overrender", 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 painters algorithm) but this happens on only small parts of the image and has a negligible performance effect.
