i
i
i
i
i
i
i
i
14.3. Hierarchical View Frustum Culling 665
Figure 14.12. A set of geometry and its bounding volumes (spheres) are shown on the
left. This scene is rendered with view frustum culling from the point of the eye. The
BVH is shown on the right. The BV of the root intersects the frustum, and the traversal
continues with testing its children’s BVs. The BV of the left subtree intersects, and one
of that subtree’s children intersects (and thus is rendered), and the BV of the other child
is outside and therefore is not sent through the pipeline. The BV of the middle subtree
of the root is totally inside and is rendered immediately. The BV of the right subtree
of the root is also fully inside, and the entire subtree can therefore be rendered without
further tests.
If instead the BV is inside or intersecting the frustum, then the contents of
that BV may be visible and must be sent through the rendering pipeline.
See Section 16.14 for methods of testing for intersection between various
bounding volumes and the view frustum.
By using a spatial data structure, this kind of culling can be applied
hierarchically [179]. For a bounding volume hierarchy (BVH), a preorder
traversal [201] from the root does the job. Each node with a BV is tested
against the frustum. If the BV of the node is outside the frustum, then that
node is not processed further. The tree is pruned, since the BV’s contents
and children are outside the view.
If the BV is fully inside the frustum, its contents must all be inside
the frustum. Traversal continues, but no further frustum testing is needed
for the rest of such a subtree. If the BV intersects the frustum, then the
traversal continues and its children are tested. When a leaf node is found to
intersect, its contents (i.e., its geometry) is sent through the pipeline. The
primitives of the leaf are not guaranteed to be inside the view frustum. An
example of view frustum culling is shown in Figure 14.12. It is also possible
to use multiple BV tests for an object or cell. For example, if a sphere BV
around a cell is found to overlap the frustum, it may be worthwhile to also
i
i
i
i
i
i
i
i
666 14. Acceleration Algorithms
perform the more accurate (though more expensive) box/frustum test if
this box is known to be much smaller than the sphere [1145].
A useful optimization for the “intersects frustum” case is to keep track of
which frustum planes the BV is fully inside [89]. This information, usually
stored as a bitmask, can then be passed with the intersector for testing
children of this BV. Only those planes that intersected the BV need to be
tested against the children. In this way, the root BV will be tested against
6 frustum planes, but as BVs come into view the number of plane/BV tests
done at each child will go down.
View frustum culling operates in the application stage (CPU), which
means that the load on the GPU can often be dramatically reduced. For
large scenes or certain camera views, only a fraction of the scene might
be visible, and it is only this fraction that needs to be sent through the
rendering pipeline. In such cases a large gain in speed can be expected.
View frustum culling techniques exploit the spatial coherence in a scene,
since objects that are located near each other can be enclosed in a BV, and
nearby BVs may be clustered hierarchically.
Other spatial data structures than the BVH can also be used for view
frustum culling. This includes octrees and Binary Space Partitioning (BSP)
trees [1099]. These methods are usually not flexible enough when it comes
to rendering dynamic scenes. That is, it takes too long to update the
corresponding data structures when an object stored in the structure moves
(an exception is loose octrees). But for static scenes, these methods can
perform better than BVHs. Hybrid methods can also be used, e.g., using
BVs to tightly bound the contents of octree nodes. Another approach is to
keep separate structures for static versus dynamic objects.
Polygon-aligned BSP trees are simple to use for view frustum culling. If
the box containing the scene is visible, then the root node’s splitting plane
is tested. If the plane intersects the frustum (i.e., if two corners on the
frustum are found to be on opposite sides of the plane [see Section 16.10]),
then both branches of the BSP tree are traversed. If instead, the view
frustum is fully on one side of the plane, then whatever is on the other
side of the plane is culled. Axis-aligned BSP trees and octrees are also
simple to use. Traverse the tree from the root, and test each box in the
tree during traversal. If a box is outside the frustum, traversal for that
branch is terminated.
For view frustum culling, there is a simple technique for exploiting
frame-to-frame coherency.
4
If a BV is found to be outside a certain plane
of the frustum in one frame, then (assuming that the viewer does not move
too quickly) it will probably be outside that plane in the next frame too.
So if a BV was outside a certain plane, then an index to this plane is stored
4
This is also called temporal coherency.
i
i
i
i
i
i
i
i
14.4. Portal Culling 667
(cached) with the BV. In the next frame in which this BV is encountered
during traversal, the cached plane is tested first, and on average a speedup
can be expected [48].
If the viewer is constrained to only translation or rotation around one
axis at a time from frame to frame, then this can also be exploited for
faster frustum culling. When a BV is found to be outside a plane of the
frustum, then the distance from that plane to the BV is stored with the
BV. Now, if the viewer only, say, translates, then the distance to the BV
can be updated quickly by knowing how much the viewer has translated.
This can provide a generous speedup in comparison to a naive view frustum
culler [48].
14.4 Portal Culling
For architectural models, there is a set of algorithms that goes under the
name of portal culling. The first of these were introduced by Airey [5, 6] in
1990. Later, Teller and S´equin [1258, 1259] and Teller and Hanrahan [1260]
constructed more efficient and more complex algorithms for portal culling.
The rationale for all portal-culling algorithms is that walls often act as
large occluders in indoor scenes. Portal culling is thus a type of occlusion
culling, discussed in the next section. We treat portal culling here because
of its importance. This occlusion algorithm uses a view frustum culling
mechanism through each portal (e.g., door or window). When traversing a
portal, the frustum is diminished to fit closely around the portal. Therefore,
this algorithm can be seen as an extension of view frustum culling. Portals
that are outside the view frustum are discarded.
Portal-culling methods preprocess the scene in some way. The scene
is divided into cells that usually correspond to rooms and hallways in a
building. The doors and windows that connect adjacent rooms are called
portals. Every object in a cell and the walls of the cell are stored in a data
structure that is associated with the cell. We also store information on ad-
jacent cells and the portals that connect them in an adjacency graph. Teller
presents algorithms for computing this graph [1259]. While this technique
worked back in 1992 when it was introduced, for modern complex scenes
automating the process is extremely difficult. For that reason defining cells
and creating the graph is currently done by hand.
Luebke and Georges [799] use a simple method that requires only a
small amount of preprocessing. The only information that is needed is the
data structure associated with each cell, as described above. Rendering
such a scene is accomplished through the following steps:
1. Locate the cell V where the viewer (eye) is positioned.
i
i
i
i
i
i
i
i
668 14. Acceleration Algorithms
2. Initialize a two-dimensional bounding box P to the rectangle of the
screen.
3. Render the geometry of the cell V using view frustum culling for
the frustum that emanates from the viewer and goes through the
rectangle P (initially the whole screen).
4. Recurse on portals of the cells neighboring V . For each visible portal
of the current cell, project the portal onto the screen and find the
two-dimensional axis-aligned bounding box (BB) of that projection.
Compute the logical intersection of P and the BB of the portal (which
is done with a few comparisons).
5. For each intersection: If it is empty, then the cell that is connected
via that portal is invisible from the current point of view, and that
cell can be omitted from further processing. If the intersection is not
empty, then the contents of that neighbor cell can be culled against
the frustum that emanates from the viewer and goes though the (rect-
angular) intersection.
6. If the intersection was not empty, then the neighboring cells of that
neighbor may be visible, and so we recurse to Step 3 with P being
the intersection BB. Each object may be tagged when it has been
rendered in order to avoid rendering objects more than once.
An optimization that can well be worth implementing is to use the stencil
buffer for more accurate culling. Since the portals are overestimated with
an AABB, the real portal will most likely be smaller. The stencil buffer can
be used to mask away rasterization (e.g., texturing and depth test) outside
that real portal. Similarly, a scissor rectangle around the portal can be
set for the accelerator to increase performance [4]. Stencil and scissor are
particularly useful when dealing with a transparent object seen through
multiple portals. The object should be rendered only once per portal in
order to perform transparency correctly; multiple renderings of the same
object in a portal will give an incorrect result.
The portal culling algorithm is illustrated in Figure 14.13 with an exam-
ple. The viewer or eye is located in cell E and therefore rendered together
with its contents. The neighboring cells are C, D,andF . The original frus-
tum cannot see the portal to cell D and is therefore omitted from further
processing. Cell F is visible, and the view frustum is therefore diminished
so that it goes through the portal that connects to F . The contents of F
are then rendered with that diminished frustum. Then, the neighboring
cells of F are examined—G is not visible from the diminished frustum and
so is omitted, while H is visible. Again, the frustum is diminished with
the portal of H, and thereafter the contents of H are rendered. H does
i
i
i
i
i
i
i
i
14.4. Portal Culling 669
eye
Figure 14.13. Portal culling: Cells are enumerated from A to H, and portals are openings
that connect the cells. Only geometry seen through the portals is rendered.
not have any neighbors that have not been visited, so traversal ends there.
Now, recursion falls back to the portal into cell C. The frustum is dimin-
ished to fit the portal of C, and then rendering of the objects in C follows,
with frustum culling. No more portals are visible, so rendering is complete.
See Figure 14.14 for another view of the use of portals. This form of
portal culling can also be used to trim content for planar reflections (see
Section 9.3). The left image of the plate shows a building viewed from the
top; the white lines indicate the way in which the frustum is diminished
with each portal. The red lines are created by reflecting the frustum at
a mirror. The actual view is shown in the image on the right side of the
Figure 14.14. Portal culling. The left image is an overhead view of the Brooks House.
The right image is a view from the master bedroom. Cull boxes for portals are in
white and for mirrors are in red. (Images courtesy of David Luebke and Chris Georges,
UNC-Chapel Hill.)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.