Painter's algorithm

This is an old revision of this page, as edited by Hhanke (talk | contribs) at 23:46, 30 January 2003 (image included). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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, at some point, you need 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. Similarly, when you want to use this algorithm in your rendering system, you first sort all the polygons by their depth and then paint them in this order. You will over-paint the parts that are normally not visible and thus solve the visibility problem.

Note that this approach has several problems. What happens when polygon A partly covers B, B partly covers C and C partly covers A again? It's not possible to decide which polygon is above the others. Or when two polygons intersect one another in three dimensions? The painter's algorithm will fail in these cases.

Image: how painter's algorithm fail

Another problem is that it is very slow because the computer needs to render the intensities at all points of all polygons even if they will not be seen in the final scene because the polygon is not visible.