< Zurück | Inhalt | Weiter >

Depth sorting (Painter’s algorithm)


The so−called Painter’s algorithm also operates in object space; however, it takes a slightly different approach. The University of North Carolina at Chapel Hill Computer Science Department online course Introduction to Computer Graphics (
http://www.cs.unc.edu/~davemc/Class/136/
) explains the Painter’s algorithm (
http://www.cs.unc.edu/~davemc/Class/136/Lecture19/Painter.php
).


The basic approach for the Painter’s algorithm is to sort the triangles in the scene by their distance from the viewer. The triangles are then rendered in order: triangle furthest away rendered first, closest triangle rendered last. This ensures that the closer triangles will overlap and obscure triangles that are further away.

An uncomplicated depth sort is easy to implement; however, once you start using it you will begin to see strange rendering artifacts. The essential problem comes down to how you measure the distance a triangle is from the viewer. Perhaps you would


Take the average distance of each of the three vertices

Take the distance of the centroid of the triangle


With either of these simple techniques, you can generate scenes with configurations of triangles that render incorrectly. Typically, problems occur when:


Triangles intersect

Centroid or average depth of the triangle is not representative of the depth of the corners

Complex shapes intersect

Shapes require splitting to render correctly


For example, figure 2.5 shows some complex configurations of triangles that cannot be depth sorted using a simple algorithm.


image


Figure 2.5 Interesting configurations of triangles that are challenging for depth−sorting algorithms


The depth of an object in the scene can be calculated if the position of the object is known and the position of the viewer or image plane is known. It would be computationally intensive to have to re−sort all the triangles in the scene every time an object or the viewer’s position changed. Fortunately, binary space partition (BSP) trees can be used to store the relative positions of the object in the scene such that they do not need to be re−sorted when the viewpoint changes. BSP trees can also help with some of the complex sorting configurations shown earlier.