Graphics Reference
In-Depth Information
fairly small. Teller observed
O
(
n
)
behavior in practice on complex indoor models.
Nonetheless, the latter step must be performed for each pair of sectors, so the
entire algorithm is slow enough to be an offline process that may take minutes or
hours. When the algorithm terminates, each sector is annotated with a list of all
other sectors that are conservatively visible to it.
At runtime in Teller's framework, a point in space is associated with a sec-
tor by walking the original BSP tree in typically O
(log
n
)
time. That sector then
provides its list of all potentially visible sectors, which quickly culls most of the
scene geometry. Individual point-to-point visibility tests by ray casting can then be
performed for explicit visibility tests. Alternatively, all polygons (including detail
objects) in the potentially visible sectors can be rasterized with a depth buffer
for implicit visibility during rendering. The latter approach was introduced in the
Quake
video game in 1996 and quickly spread throughout the game industry.
Teller's stabbing trees require a long precomputation step that precludes their
application to scenes with dynamic (nondetail) geometry. The Portals and Mir-
rors algorithm [LG95] is an alternative. It is simpler to implement and extends to
both dynamic scenes and a notion of indirect visibility through mirrors. It revis-
its the frustum created when looking through a portal, but in the absence of the
BSP tree and in the case where sectors may be nonconvex. That allows the sector
geometry to change at runtime. The idea of the algorithm is to recursively trace
the view frustum through portals, clipping it to each portal traversed. Figure 36.19
shows two visualizations of the algorithm. The first image is the camera's view,
with clipping regions at portals and mirrors highlighted. The second image is a top
view of the scene, showing how the frustum shrinks as it passes through successive
portals and reflects when it hits a mirror.
Let the scene be represented as the sector polyhedra, the adjacency infor-
mation between them, and the detail objects. Assume that at the beginning of
an interactive sequence we know which sector contains the viewer, and that the
viewer must move continuously through space (i.e., no teleportation!). Whenever
the viewer moves through a portal, update the viewer state to retain a pointer to
the sector that now contains the center of projection by following the adjacency
information associated with that portal. This allows identifying the viewer's sector
in
O
(
1
)
time during any frame.
To render a frame, let
clipPoly
initially be the screen-space rectangle
bounding the viewport and
sector
be the viewer's current sector. Invoke the
portalRender(sector, clipPoly)
function from Listing 36.5. It will recursively
render objects seen through portals, recursing when there are no new portals that
can be seen. The
intersect
routine is simply 2D convex polygon-polygon inter-
section, which can be performed using the Sutherland-Hodgman algorithm.
For a scene in which the sectors
are
convex and there is no detail geometry, this
algorithm provides exact visibility—no depth buffer is needed. A strength of the
method is that if we do use a depth buffer, not only can it accommodate noncon-
vex portals and detail geometry, but also the general 2D clipping can be replaced
with conservative rectangle clipping on the bounding box of
projPoly
. This may
trigger a few extra recursive calls, but it dramatically simplifies the clipping/
intersection process because we need only work with screen-space, axis-aligned
rectangles.
