# The Painters Algorithm

The painter's algorithm is a VSD algorithm, relying on polygon sorting, which addresses the correctness issue but neglects the efficiency issue. We know that drawing polygons in random order to the screen sometimes results in an incorrect display because farther polygons obscure nearer ones. The solution adopted in the original l3d_world class was the so-called painter's algorithm, where we draw polygons from back-to-front order into the frame buffer. By drawing the nearest polygons last, the pixels for the nearest polygons overwrite any pixels from farther polygons which might already be in the frame buffer at the same positions. This means that nearer polygons always obscure farther polygons.

Since the sample programs using the l3d_world class already use the painter's algorithm, there is no additional sample program here. The painter's algorithm is very simple, and produces mostly correct results most of the time. However, there are a few important shortcomings and observations about the painter's algorithm which we should take note of. ■ Sorting. The painter's algorithm requires us to sort polygons based on their distance to the viewer. Sorting takes time. For large numbers of polygons, the painter's algorithm can spend much of its time sorting the polygons. One technique to avoid such sorting is to create a large list of polygons, say large enough for 4096 polygons. Each entry in this list represents one z depth. Then, before drawing a polygon, we scale its z depth to lie within the range of the list. We round this scaled z depth to an integer and use it as the polygon's insertion position into the list. If two polygons' z depths are close enough, they get assigned to the same slot, which can result in small-scale sorting errors. Then, to draw the polygons, we traverse the list from back to front. In essence, this scheme is a radix sort, using the z depth itself as an index into the list to avoid sorting.

■ Overdraw. The painter's algorithm suffers from overdraw. Overdraw means that a particular pixel is often drawn more than once into the frame buffer. Consider a set of 500 texture mapped polygons, all facing the viewer and positioned one behind the other. With the painter's algorithm, we first draw the farthest polygon, taking the time to transform it into camera space, do perspective division and clipping, and carry out the entire texture mapping computations for every single pixel of the polygon. Then, we draw the second farthest polygon, again performing many computations for every pixel, entirely overwriting the results of the farthest polygon. Then, we draw the third farthest polygon, again entirely overwriting the results of the first two polygons. Although this example is extreme, it shows how a back-to-front drawing of polygons wastes time by carefully computing the correct pixels and colors to be drawn, then possibly overwriting much or all of this work when a nearer polygon is drawn. The painter's algorithm works because of overdraw, but when the overdrawn pixels take a significant amount of time to compute—as is the case with texture mapping—more overdraw means more "wasted" time computing pixels which will be overwritten anyway. It is important to note, however, that the overdraw concern is mainly an issue for software rendering. With hardware-accelerated rendering, it is often possible to completely ignore this issue of overdraw, since the hardware can draw polygons so quickly.

■ Non-orderable polygon groups. The painter's algorithm does not produce correct results all of the time. One classic case is cyclic overlap. If a series of polygons overlap such that they form a cycle (see Figure 4-15), then there is no single ordering which can be applied to draw the polygons so that a correct display results. Similarly, if one polygon pierces another polygon, then there is also no single ordering which is correct: part of the piercing polygon lies in front of, part behind the pierced polygon. In both of these cases, the painter's algorithm can still be used if we perform a number of tests and polygon splitting operations. Splitting polygons into more pieces resolves any ambiguities in the z ordering, producing more independent polygons to be drawn, but which can then be drawn in a correct order. The tests to be done for the splitting are a bit tedious, and in my opinion, not really worth the trouble; we won't cover them further here. Part of the appeal of the painter's algorithm is its simplicity, and if we start to bog down the code with several special case tests, then it might be better just to use a different VSD algorithm entirely. Figure 4-15: Cyclic overlap cannot be resolved by the simple painter's algorithm.

You can see a good example of the kinds of problems which arise with the painter's algorithm in the program textest from Chapter 2. Here, we had two pyramid objects, one static and one rotating. The rotating pyramid object pierced the static pyramid object. If you look closely at the appearance of the piercing pyramid, you will notice that the polygons instantaneously "flip" from in front of the pierced pyramid to behind it. This is because the simple painter's algorithm tries to find a single sort order to draw all polygons, based on the polygon's average z value. As soon as the average z value is smaller, the polygon appears in front; as soon as the average z value is greater, the polygon appears behind the others. In the case of a piercing polygon, as we said before, this is not correct: part of the piercing polygon lies in front of, part behind the pierced polygon. See Figures 4-16 and 4-17: the piercing polygon, highlighted with a white border, is always drawn either completely in front of or completely behind the pierced polygons. When observing the animation in the running program, the polygon appears to flip from one side to the other.

13d application

13d application Figure 4-16: The highlighted polygon is drawn completely behind the static pyramid. Figure 4-17: The highlighted polygon is drawn completely in front of the static pyramid.

Now, let's look at a simple VSD routine which can solve these sorting problems of the painter's algorithm: the z buffer algorithm.

The z buffer algorithm is a per-pixel VSD algorithm which mainly addresses the VSD correctness issue, essentially ignoring the VSD efficiency issue. The idea is very simple. We maintain a 2D array of z values, which has the same dimensions as the rasterizer buffer. This array is called a z buffer. Each position in the z buffer corresponds to a pixel in the rasterizer buffer. Furthermore, each value in the z buffer represents the z value (or a 1/z value, as we see shortly) of the point in 3D space whose projection yields the pixel at that location in the z buffer.

We use the z buffer as follows. At the beginning of each frame, before any objects are rasterized, we clear the z buffer by setting all of its values to represent the maximum possible distance. Then, we rasterize polygons as normal, pixel for pixel. When rasterizing polygons, for each pixel we compute the z value of the current pixel being rasterized. Then, we compare the z value for the current pixel against the z value already in the z buffer at the pixel's location.

If the current z value has a smaller depth than the old z buffer value, then the 3D point corresponding to the pixel being drawn lies closer to the viewer than the 3D point corresponding to the pixel that was previously drawn. Thus, the new pixel must obscure the old pixel. We draw the new pixel and update the z buffer at that pixel position with the new depth.

If, on the other hand, the current z value has a greater depth than the old z buffer value, then this means that the 3D point corresponding to the pixel being drawn lies farther from the viewer than the 3D point corresponding to the pixel that was previously drawn. Thus, the old pixel obscures the new pixel. We do not draw the pixel, we do not update the z buffer, and we continue rasterization of the next pixel in the polygon.