Graphics Reference
In-Depth Information
Primarily-2D rendering systems such as windowed GUIs that also incorporate
occlusion or “stacking” are called
2.5D
because they have a depth ordering
(a.k.a.
z
-order
) and overlap even though explicit position in a third dimension
is ambiguous. We've argued that this is a reasonable application of the painter's
algorithm, especially when the primitives obey a strict depth ordering so that
sorting is guaranteed to correctly resolve visibility.
An alternative for occlusion in 2.5D systems is to consider only local solu-
tions and relax the need for a consistent global interpretation of the scene (even
though one may exist). Two examples of this are Live Paint and Local Layer-
ing.
Live Paint
[ASP07] is a system for editing 2D drawings composed of
curves and flood-fill regions, that is, “presentation vector graphics” such as
those found in Microsoft PowerPoint or created in Adobe Illustrator. Most sys-
tems for such graphics treat the elements as 2.5D filled primitives, with stack-
ing creating the occlusion. Operations for computing intersections, unions, and
subtractions between them allow editing based on occlusion but destroy the
underlying curves in the process. Live Paint instead works with the curves
themselves as a planar graph and attempts to maintain the consistency of the
fill commands through a series of clever methods. This allows for more natural
editing of the image and preserves curves during editing operations.
Local Layering [MP09] is an alternative system for managing discrete,
nonconvex primitives in a 2.5D system. Instead of assigning a strict global
depth ordering, it allows the artist to specify which primitive is closer to the
viewer separately at each intersection. This allows complex overlapping behav-
ior such as braiding different primitives together.
When we render with a depth buffer and an early depth test, it is advantageous
to encounter proximate surfaces before distant ones. Distant surfaces will then
fail the early depth test where they are occluded, and not require shading. A
reverse painter's algorithm improves efficiency in that case: Render from front to
back. A depth prepass eliminates the need for ordering. During the prepass itself
the ordering provides a speedup. Surprisingly, for many models a static ordering
of primitives can be precomputed that provides a good front-to-back ordering
from any viewpoint [SNB07]. This allows the runtime performance without the
runtime cost.
The painter's algorithm is often employed for translucency, which can be mod-
eled as fractional visibility values between zero and one, as done in OpenGL
and Direct3D. Compositing translucent surfaces from back to front allows a good
approximation of their fractional occlusion of each other and the background in
many cases. However, stochastic methods yield more robust results for this case
at the expense of noise and a larger memory footprint. See Section 36.9 for a more
complete discussion.
Newell et al.'s
depth-sort algorithm
[NNS72] extends the painter's algorithm for
polygons to produce correct output in all cases. It operates in four steps.
