Graphics Reference
In-Depth Information
Some of the faces of a sector correspond to leaves in the BSP tree. These poly-
gons block visibility. Others are empty space. Those are called
portals
because
they are windows to adjacent sectors. A convex space has a nice visibility prop-
erty: All points within the space are visible to all other points. (For a pinhole
camera, one may choose to then restrict that visibility by the field of view to the
image frame.) From any point in a sector, one can look through any portal into
any adjacent sector. However, in doing so, our visibility
within the adjacent sec-
tor
is restricted to a frustum that is the extrusion of the portal's boundary away
from the viewer. If we look straight through a sector into another sector through a
second portal, visibility becomes restricted by the intersection of the two portals'
extrusions. After many portals, this frustum can become small; if one portal lies
outside the frustum of another, the intersection of their frusta is empty. Most of
these key observations are due to Jones [Jon71] and form a family of visibility
determination algorithms.
Consider the graph in which sectors are nodes and portals are edges. A point
is visible to another point only if it is reachable in this graph. Furthermore, we
can detect cases where the specific geometry of adjacent sectors prevents looking
straight through more than two portals. For example, in a grid of nonrefractive
and nonreflective windows, we can look through a window to our north into an
adjacent sector and then through its east window into another one; but we cannot
look through that sector's south window because that would require bending a
viewing ray into an arc. This corresponds to the case of the third sector's south
window lying entirely outside the intersection for the frusta of the first two.
For an interesting scene there might be a tremendous number of sectors, so
following the graph line of thinking might be inefficient. But if we exclude small
objects such as furniture from the sector-building algorithm and only consider
large objects such as walls when building sectors and portals, we may find a rel-
atively small number of sectors [Air90]. Any approach to visibility computation
that ignores the so-called small
detail objects
only provides conservative visibil-
ity, and must be succeeded by another algorithm for correctness—the depth buffer
is a common choice here.
Explicitly,
V
(
P
,
Q
)
must be zero if no part of the sector containing point
P
is
visible to the sector containing
Q
. Given some algorithm for determining sector-
to-sector visibility, we can then conservatively approximate point and primitive
visibility. Airey [Air90] pioneered a number of sector-to-sector visibility algo-
rithms including ray casting and shadow volumes. The methods that he described
are all correct with high probability for large numbers of samples, but are not all
conservative; thus, the net visibility computation is not conservative under those
approaches.
Teller [Tel92] devised a closed-form, conservative, analytic algorithm for conser-
vative visibility between sectors. His algorithm computes a BSP tree on
n
poly-
gons in
O
(
n
2
)
operations to form the sectors. It then computes all possible straight-
line
stabbing line
traversals through the sector adjacency graph until occlusion in
worst-case
O
(
n
3
)
time, using a linear programming optimization framework. The
full set of traversals from one sector is called a
stabbing tree.
In practice, the
O
(
n
3
)
asymptotic bound is misleading. There are many trivial rejection cases,
such as when a portal is a backface to the viewer, and the constant factors are
