Graphics Reference
In-Depth Information
find that the painter's algorithm is embedded in most user interface systems, and
is often encountered even in sophisticated 3D renderers for handling issues like
transparency when memory or render time is severely limited.
Some list-priority algorithms are heuristics that often generate a correct order-
ing, but fail in some cases. Others produce an exact ordering, which may require
splitting the input primitives to resolve cases such as Figure 36.15. There's an
important caveat for the algorithms that produce exact results: If we are going to
do the work of subdivision, we can achieve more efficient rendering by simply
culling all occluded portions, rather than just overdrawing them later in render-
ing. This was a popular approach in the 1970s. Area-subdivision algorithms such
as Warnock's Algorithm [War69] and the Weiler-Atherton Algorithm [WA77]
eliminate culled areas in 2D. There are similar per-scanline 1D algorithms such
as those by Wylie et al. [WREE67], Bouknight [Bou70], Watkins [Wat70], and
Sechrest and Greenberg [SG81] that use an active edge table to maintain the
current-closest polygon along a horizontal line. These were historically extended
to single-line depth buffers [Mye75, Cro84]. The obvious trend ensued, and today
all of these are largely ignored in favor of full-screen depth buffers. This is a cau-
tionary tale for algorithm development in the long run, since the simplicity found
in the depth buffer and painter's algorithm leads to better performance and more
practical implementation than decades of sophisticated visibility algorithms.
Figure 36.15: Three convex poly-
gons that cannot be rendered
properly using the painter's algo-
rithm due to their mutual over-
laps. At each point, a strict depth
ordering exists, but there is no
correct ordering of whole rectan-
gles.
36.4.1 The Painter's Algorithm
Consider a possible process for an artist painting a landscape. The artist paints
the sky first, and then the mountains occluding the sky. In the foreground, the
artist paints trees over the mountains. This is called the painter's algorithm in
computer graphics. Occlusion and visibility are achieved by overwriting colors
due to distant points with colors due to nearer points. We can apply this idea
to each sample location because at each sample there is always a correct back-
to-front ordering of the points directly affecting it. In this case, the algorithm is
potentially inefficient because it requires sorting all of the points, but it gives a
correct result.
For efficiency, the painter's algorithm is frequently applied to whole primi-
tives, such as triangles. Here it fails as an algorithm. While primitives larger than
points can often be ordered so as to give correct visibility, there are situations
where this cannot be done. Figure 36.15 shows three triangles for which there is
no correct back-to-front order. Here the “algorithm” is merely a heuristic, although
it can be an effective one. If we allow subdividing primitives where their projec-
tions cross, then we can achieve an ordering. This is discussed in the following
section.
Despite its inability to generate either correct or conservative results in the
general case, the painter's algorithm is employed for some niche applications in
computer graphics and is a useful concept in many cases. It is trivially simple,
requires no space, and can operate out of core (provided the sort is implemented
out of core). It is the predominant visibility algorithm in 2D user interfaces and
presentation graphics. In these systems, all objects are modeled as lying in planes
parallel to the image plane. For that special case, the primitives can always be
ordered, and the ordering is trivial to achieve because those planes are typically
parallel to the image plane.
 
 
Search WWH ::




Custom Search