Painter's algorithm: Difference between revisions

Revision as of 03:45, 5 May 2005

Revision as of 12:23, 18 June 2005

Line 1:

The '''painter's algorithm''' 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 [[polygon]]s 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. Similarly, theThe 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 and thus solves the visibility problem.

<center>

[[Image:Painter's_algorithm.png|600px|center|thumb|The distant mountains are painted first, followed by the closer meadows; finally, the closest objects in this scene - the trees - are painted.]]

Line 11:

In basic implementations, 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 is an inefficient solution.

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.

[[Category:Computer graphics]]