i
i
i
i
i
i
i
i
670 14. Acceleration Algorithms
same plate, where the white rectangles are the portals and the mirror is
red. Note that it is only the objects inside any of the frustums that are
rendered.
There are many other uses for portals. Mirror reflections can be cre-
ated efficiently by transforming the viewer when the contents of a cell seen
through a portal are about to be rendered. That is, if the viewer looks at
a portal, then the viewer’s position and direction can be reflected in the
plane of that portal (see Section 9.3.1). Other transformations can be used
to create other effects, such as simple refractions.
14.5 Detail Culling
Detail culling is a technique that sacrifices quality for speed. The rationale
for detail culling is that small details in the scene contribute little or nothing
to the rendered images when the viewer is in motion. When the viewer
stops, detail culling is usually disabled. Consider an object with a bounding
volume, and project this BV onto the projection plane. The area of the
projection is then estimated in pixels, and if the number of pixels is below a
user-defined threshold, the object is omitted from further processing. For
this reason, detail culling is sometimes called screen-size culling.Detail
culling can also be done hierarchically on a scene graph. The geometry
and rasterizer stages both gain from this algorithm. Note that this could
be implemented as a simplified LOD technique (see Section 14.7), where
one LOD is the entire model, and the other LOD is an empty object.
14.6 Occlusion Culling
As we have seen, visibility may be solved via a hardware construction called
the Z-buffer (see Section 2.4). Even though it may solve visibility correctly,
the Z-buffer is not a very smart mechanism in all respects. For example,
imagine that the viewer is looking along a line where 10 spheres are placed.
This is illustrated in Figure 14.15. An image rendered from this viewpoint
will show but one sphere, even though all 10 spheres will be rasterized and
compared to the Z-buffer, and then potentially written to the color buffer
and Z-buffer. The middle part of Figure 14.15 shows the depth complexity
for this scene from the given viewpoint. Depth complexity refers to how
many times each pixel is overwritten. In the case of the 10 spheres, the
depth complexity is 10 for the pixel in the middle as 10 spheres are rendered
there (assuming backface culling was on), and this means that 9 writes to
the pixel are unnecessary. This uninteresting scene is not likely to be found
in reality, but it describes (from the given viewpoint) a densely populated
i
i
i
i
i
i
i
i
14.6. Occlusion Culling 671
Figure 14.15. An illustration of how occlusion culling can be useful. Ten spheres are
placed in a line, and the viewer is looking along this line (left). The depth complexity
image in the middle shows that some pixels are written to several times, even though
the final image (on the right) only shows one sphere.
Figure 14.16. A simple city example, with a bird’s eye view to show the effect of culling.
The middle image shows view frustum culling, while the right shows occlusion culling
and view frustum culling [277].
model. These sorts of configurations are found in real scenes such as those
of a rain forest, an engine, a city, and the inside of a skyscraper. An
example of a Manhattan-style city is shown in Figure 14.16.
Given the examples in the previous paragraph, it seems plausible that
an algorithmic approach to avoid this kind of inefficiency may pay off in
terms of speed. Such approaches go under the name of occlusion culling
algorithms, since they try to cull away (avoid drawing) objects that are
occluded, that is, hidden by other objects in the scene. The optimal occlu-
sion culling algorithm would select only the objects that are visible. In a
sense, the Z-buffer selects and renders only those objects that are visible,
but not without having to send all objects inside the view frustum through
most of the pipeline. The idea behind efficient occlusion culling algorithms
i
i
i
i
i
i
i
i
672 14. Acceleration Algorithms
Figure 14.17. The left figure shows point-based visibility, while the right shows cell-based
visibility, where the cell is a box. As can be seen, the circles are occluded to the left from
the viewpoint. To the right, however, the circles are visible, since rays can be drawn
from somewhere within the cell to the circles without intersecting any occluder.
is to perform some simple tests early on to cull sets of hidden objects. In
a sense, backface culling is a simple form of occlusion culling. If we know
in advance that an object is solid and is opaque, then the backfaces are
occluded by the frontfaces and so do not need to be rendered.
There are two major forms of occlusion culling algorithms, namely
point-based and cell-based. These are illustrated in Figure 14.17. Point-
based visibility is just what is normally used in rendering, that is, what
is seen from a single viewing location. Cell-based visibility, on the other
hand, is done for a cell, which is a region of the space, normally a box or
a sphere. An invisible object in cell-based visibility must be invisible from
all points within the cell. The advantage of cell-based visibility is that once
it is computed for a cell, it can usually be used for a few frames, as long as
the viewer is inside the cell. However, it is usually more time consuming
to compute than point-based visibility. Therefore, it is often done as a
preprocessing step. Note that point-based and cell-based visibility often
are compared to point and area light sources. For an object to be invisible,
it has to be in the umbra region, i.e., fully occluded.
One can also categorize occlusion culling algorithms into those that
operate in image space, object space,orray space. Image-space algorithms
do visibility testing in two dimensions after some projection, while object-
space algorithms use the original three-dimensional objects. Ray space [90,
91, 685] methods perform their tests in a dual space. Each point (often
two dimensional) of interest is converted to a ray in this dual space. The
idea is that testing is simpler, more exact, or more efficient in this space.
Pseudocode for one type of occlusion culling algorithm is shown in Fig-
ure 14.18, where the function isOccluded, often called the visibility test,
checks whether an object is occluded. G is the set of geometrical objects
to be rendered, O
R
is the occlusion representation, and P is a set of poten-
tial occluders that can be merged with O
R
. Depending on the particular
i
i
i
i
i
i
i
i
14.6. Occlusion Culling 673
1: OcclusionCullingAlgorithm(G)
2: O
R
=empty
3: P =empty
4: for each object g ∈ G
5: if(isOccluded(g,O
R
))
6: Skip(g)
7: else
8: Render(g)
9: Add(g,P)
10: if(LargeEnough(P ))
11: Update(O
R
,P)
12: P =empty
13: end
14: end
15: end
Figure 14.18. Pseudocode for a general occlusion culling algorithm. G contains all the
objects in the scene, and O
R
is the occlusion representation. P is a set of potential
occluders, that are merged into O
R
when it contains sufficiently many objects. (After
Zhang [1403].)
algorithm, O
R
represents some kind of occlusion information. O
R
is set
to be empty at the beginning. After that, all objects (that pass the view
frustum culling test) are processed.
Consider a particular object. First, we test whether the object is oc-
cluded with respect to the occlusion representation O
R
. If it is occluded,
then it is not processed further, since we then know that it will not con-
tribute to the image. If the object cannot be determined to be occluded,
then that object has to be rendered, since it probably contributes to the
image (at that point in the rendering). Then the object is added to P,and
if the number of objects in P is large enough, then we can afford to merge
the occluding power of these objects into O
R
. Each object in P can thus
be used as an occluder.
Note that for the majority of occlusion culling algorithms, the perfor-
mance is dependent on the order in which objects are drawn. As an exam-
ple, consider a car with a motor inside it. If the hood of the car is drawn
first, then the motor will (probably) be culled away. On the other hand,
if the motor is drawn first, then nothing will be culled. Therefore, perfor-
mance can be improved by techniques such as rough front-to-back sorting
of the objects by their approximate distance from the viewer and rendering
in this order. Also, it is worth noting that small objects potentially can
be excellent occluders, since the distance to the occluder determines how
i
i
i
i
i
i
i
i
674 14. Acceleration Algorithms
much it can occlude. As an example, a matchbox can occlude the Golden
Gate Bridge if the viewer is sufficiently close to the matchbox.
14.6.1 Hardware Occlusion Queries
Modern GPUs support occlusion culling by using a special rendering mode.
5
Simply put, the user can query the hardware to find out whether a set of
polygons is visible when compared to the current contents of the Z-buffer.
These polygons most often form the bounding volume (for example, a box
or k-DOP) of a more complex object. If none of these polygons are visible,
then the object can be culled. The implementation in hardware rasterizes
the polygons of the query and compares their depths to the Z-buffer. A
count of the number of pixels n in which these polygons are visible is gen-
erated, though no pixels are actually modified. If n is zero, all polygons
are occluded (or clipped). Therefore, the occlusion queries operate in im-
age space. Similar queries are used by the hierarchical Z-buffer algorithm
(Section 14.6.2).
If the pixel count n = 0, and the camera’s position is not inside the
bounding volume,
6
then the entire bounding volume is completely occluded,
and the contained objects can safely be discarded. If n>0, then a fraction
of the pixels failed the test. If n is smaller than a threshold number of
pixels, the object could be discarded as being unlikely to contribute much
to the final image [1360]. In this way, speed can be traded for possible loss of
quality. Another use is to let n help determine the LOD (see Section 14.7) of
an object. If n is small, then a smaller fraction of the object is (potentially)
visible, and so a less detailed LOD can be used.
When the bounding volume is found to be obscured, we gain per-
formance by avoiding sending the complex object through the rendering
pipeline. However, if the test fails, we actually lose a bit of performance as
we spent additional time testing this bounding volume to no benefit.
With such techniques, performance has been reported to be up to twice
as fast as rendering that does not use any occlusion culling [1143]. For
large city scenes or building interiors, gains could be even higher.
The latency of a query is often a relatively long time; often, hundreds or
thousands of polygons can be rendered within this time (see Section 18.3.5
5
This type of hardware support was first implemented on a Kubota Pacific Titan
3000 computer with Denali GB graphics hardware [450].
6
More precisely, no part of the camera frustum’s visible near plane should be inside
the bounding volume. For orthographic views, used in CAD applications, the camera is
normally fully outside of all objects, so this is not a problem. For perspective viewing,
this near-plane case is important. One solution is to be conservative, never testing such
bounding volumes for occlusion.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.