Graphics Reference
In-Depth Information
efficient culling. This isn't the historical order of development. In fact, the topic
developed in the opposite order.
Historically, the first notion of visibility was the question “Is any part of this
triangle visible?” That grew more precise with “How much of this triangle is vis-
ible?” which was a critical question when all rendering involved drawing edges
on a monochrome vector scope or rasterizing triangles on early displays and slow
processors. With the rise of ray tracing and general light transport algorithms, a
new visibility question was framed on points. That then gave a formal definition
for the per-primitive questions, which expanded under notions of partial coverage
to the framework encountered today. Of course, classic graphics work on primi-
tives was performed with an understanding of the mathematics of intersection and
precise visibility. The modern notion is just a redirection of the derivation: work-
ing up from points and rays with the rendering equation in mind, rather than down
from surfaces under an ad hoc illumination and shading model.
Visible surface determination algorithms are grounded in a precise definition of
visibility. We present this formally here in terms of geometry as the basis for
the high-level algorithms. While it is essential for defining and understanding the
algorithms, this direct form is rarely employed.
A performance reason that we can't directly apply the definition of visibility
is that with large collections of surfaces in a scene, exhaustive visibility testing
would be inefficient. So we'll quickly look for ways to amortize the cost across
multiple surfaces or multiple point pairs.
A correctness concern with direct visibility is that under digital representa-
tions, the geometric tests involved in single tests are also very brittle. In general,
it is impossible to represent most of the points on a line in any limited-precision
format, so the answer to “Does this point occlude that line of sight?” must neces-
sarily almost always be “no” on a digital computer. We can escape the numerical
precision problem by working with spatial intervals—for example, line segments,
polygons, and other curves—for which occlusion of a line of sight is actually rep-
resentable, but we must always implicitly keep in mind the precision limitation
at the boundaries of those intervals. Thus, the question of whether a ray passes
through a triangle if it only intersects the edge is moot. In general, we can't even
represent that intersection location in practice, so our classification is irrelevant.
So, beware that everything in this chapter is only valid in practice when we are
considering potential intersections that are “far away” from surface boundaries
with respect to available precision, and the best that we can hope for near bound-
aries is a result that is spatially coherent rather than arbitrarily changing within the
imprecise region.
Given points
P
and
Q
in the scene, let
visibility function
V
(
P
,
Q
)=
1 if there
is no intersection between the scene and the open-ended line segment between
P
and
Q
, and
V
(
P
,
Q
)=
0 otherwise. This is depicted in Figure 36.2. Sometimes it
is convenient to work with the
occlusion function
H
(
P
,
Q
)=
1
B
C
window
mirror
A
P
D
V
(
P
,
A
)=
Figure
36.2:
1
because
there
is
no
occluder.
V
0
because a wall is in
the way. V
(
P
,
C
)=
0
because,
even though P can see C through
the window, the window is an
occluder as far as mathematical
“visibility” is concerned. Like-
wise, V
(
P
,
D
)=
0
, even though
P sees a reflection of D in the
mirror.
(
P
,
B
)=
−
V
(
P
,
Q
)
.The
visibility function is necessarily symmetric, so
V
(
P
,
Q
)=
V
(
Q
,
P
)
.
Note that the “visibility” in “visibility function” refers strictly to geometric
line-of-sight visibility. If
P
and
Q
are separated by a pane of glass,
V
(
P
,
Q
)
is zero
because a nonempty part of the scene (the glass pane) is intersected by the line
segment between
P
and
Q
. Likewise, if an observer at
Q
has no direct line of sight
