Graphics Reference
In-Depth Information
ordering resolve visibility. This is neither exact nor conservative
1
, but it has the
benefit of extreme simplicity. It is used almost exclusively for 2D graphical user
interface rendering to handle overlapping windows. The primary 3D application of
the painter's algorithm today is for rasterization of translucent surfaces, although
recent trends favor more accurate per-sample stochastic and lossy-volumetric
alternatives [ESSL10, LV00, Car84, SML11, JB10, MB07].
Many applications combine multiple visibility determination algorithms. For
example, a hybrid renderer might rasterize primary and shadow rays but perform
ray casting for visibility determination on other global illumination paths. A real-
time hardware rasterization renderer might augment its depth buffer with hier-
archical occlusion culling or precomputed conservative visibility. Many games
rely on those techniques, but they include a ray-casting algorithm for visibility
determination used to determine line of sight for character AI logic and physical
simulation.
Ray casting is a direct process for answering an intersection query. As previously
shown, it also computes the visibility function:
V
(
P
,
Q
)=
1, if
P
is the result of
the intersection query on the ray with origin
Q
and direction
(
P
; and
V
(
P
,
Q
)=
0 otherwise. Chapter 15 introduced an algorithm for casting rays in
scenes described by arrays of triangles, and showed that the same algorithm can
be applied to primary and indirect (in that case, shadow) visibility.
The time cost of casting a ray against
n
triangles in an array is
O
(
n
)
opera-
tions. If
V
(
P
,
Q
)=
1, then the algorithm must actually test every ray-triangle pair.
If
V
(
P
,
Q
)=
0, then the algorithm can terminate early when it encounters any
intersection with the open segment
PQ
. In practice this means that computing the
visibility function by ray casting may be faster than solving the intersection query;
hence, resolving one shadow ray may be faster than finding the surface to shade
for one ray from the camera. For a dense scene with high depth complexity, the
performance ratio between them may be significant.
Terminating on any intersection still only makes ray casting against an array
of surfaces faster by a constant, so it still requires
O(
n
)
operations for
n
surfaces.
Linear performance is impractical for large and complex scenes, especially given
that such scenes are exactly those in which almost all surfaces are not visible
from a given point. Thus, there are few cases in which one would actually cast
rays against an array of surfaces, and for almost all applications some other data
structure is used to achieve sublinear scaling.
Chapter 37 describes many spatial data structures for accelerating ray intersec-
tion queries. These can substantially reduce the time cost of visibility determina-
tion compared to the linear cost under an array representation. However, building
such a structure may only be worthwhile if there will be many visibility tests
over which to amortize the build time. Constants vary with algorithms and archi-
tectures, but for more than one hundred triangles or other primitives and a few
−
Q
)
/|
P
−
Q
|
1.
. . . nor how artists actually paint—for example, sometimes the sky is painted
after
foreground objects—but the name is now both a technical term and appropriately
evocative.
