Graphics Reference
In-Depth Information
passed the occlusion query. This is made hierarchical by recursively considering
bounds on smaller parts of the scene when a visible bound is observed.
The second strategy for efficient hardware occlusion culling is the
hierarchi-
cal depth buffer,
a.k.a.
hierarchical
z
-buffer
[GKM93]. This is an image pyra-
mid similar to a MIP map in depth. Level zero of the tree is the full-resolution
depth buffer. Every subsequent level has half the resolution of its parent level.
A sample in level
k
+
1 of the hierarchical depth buffer stores two values: the
minimum and maximum depths of four corresponding samples from level
k
.A
hierarchical rasterizer [GKM93, Gre96] working with such a structure solves for
minimum (or maximum, depending on the desired depth test) depth of a primitive
within the area surrounding each of the depth samples at the lowest resolution.
If the primitive's minimum depth is smaller (i.e., closer to the camera) than the
maximum depth at a sample, then some part of that primitive may be visible at the
highest resolution, so the rasterizer progresses to the next level for that sample. If
the primitive's minimum depth is greater than or equal to the maximum depth at a
depth buffer sample, then even the farthest point in the subtree represented by that
sample is still closer to the camera than the closest point on the primitive and the
primitive must be occluded at all resolutions represented.
A hierarchical depth buffer is naturally most efficient for large primitives.
This is because because when parts of a large primitive are conservatively clas-
sified as invisible near the top of the tree, many high-resolution visibility tests
are eliminated. Small primitives force the rasterizer to begin tests deeper in the
tree where the potential cost savings are smaller. Because hierarchical occlusion
queries on BVHs tend to bound meshes of small primitives with a few large ones,
they benefit from both the occlusion query and the improved hierarchical depth
buffer efficiency. Thus, the “hierarchical” in hierarchical occlusion query often
refers to both the image-space depth buffer tree and the geometric bounding vol-
ume tree.
In this section we explore alternative uses of the spatial partitioning created by
the partition operations that occur when building a BSP tree. These techniques,
especially stabbing trees, were critical for real-time rendering of indoor environ-
ments from the early 1990s through the 2000s. They contain some beautiful com-
puter science and geometric ideas. However, at the time of this writing they are
passing out of favor because hierarchical occlusion culling allows more flexibil-
ity for managing dynamic and arbitrarily shaped environments. Although these
algorithms can be applied for explicit point-to-point visibility tests, they are typ-
ically used to generate a
potentially visible set (PVS)
of primitives for a given
viewpoint.
Recall that the leaves of a BSP tree are polygons that have been repeatedly
clipped against planes, at least for the version that we have discussed in this chap-
ter. If we assume that the original polygons, before all of the subdivision, were
convex and planar, then the leaves must also be convex and planar.
Any point in space can be classified by some path through the tree, correspond-
ing to whether it is in the positive or negative half-space of each node's splitting
plane. That series of planes carves space into a convex polyhedron that contains
the point. The space inside this polyhedron is called a
sector.
The polyhedron may
have infinite volume if the point is near the edge of the scene.
