i
i
i
i
i
i
i
i
8.4. Culling Primitives for Efficiency 181
The easiest way to implement box-filter antialiasing is by supersampling:cre-
ate images at very high resolutions and then downsample. For example, if our
goal is a 256 × 256 pixel image of a line with width 1.2 pixels, we could rasterize
a rectangle version of the line with width 4.8 pixels on a 1024 × 1024 screen,
andthenaverage4× 4 groups of pixels to get the colors for each of the 256 ×
256 pixels in the “shrunken” image. This is an approximation of the actual box-
filtered image, but works well when objects are not extremely small relative to the
distance between pixels.
Supersampling is quite expensive, however. Because the very sharp edges
that cause aliasing are normally caused by the edges of primitives, rather than
sudden variations in shading within a primitive, a widely used optimization is
to sample visibility at a higher rate than shading. If information about coverage
and depth is stored for several points within each pixel, very good antialiasing
can be achieved even if only one color is computed. In systems like RenderMan
that use per-vertex shading, this is achieved by rasterizing at high resolution: it is
inexpensive to do so because shading is simply interpolated to produce colors for
the many fragments, or visibility samples. In systems with per-fragment shading,
such as hardware pipelines, multisample antialiasing is achieved by storing for
each fragment a single color plus a coverage mask and a set of depth values.
8.4 Culling Primitives for Efficiency
The strength of object-order rendering, that it requires a single pass over all the
geometry in the scene, is also a weakness for complex scenes. For instance, in a
model of an entire city, only a few buildings are likely to be visible at any given
time. A correct image can be obtained by drawing all the primitives in the scene,
but a great deal of effort will be wasted processing geometry that is behind the
visible buildings, or behind the viewer, and therefore doesn’t contribute to the
final image.
Identifying and throwing away invisible geometry to save the time that would
be spent processing it is known as culling. Three commonly implemented culling
strategies (often used in tandem) are:
• view volume culling—the removal of geometry that is outside the view
volume;
• occlusion culling—the removal of geometry that may be within the view
volume but is obscured, or occluded, by other geometry closer to the
camera;
• backface culling—the removal of primitives facing away from the camera.
i
i
i
i
i
i
i
i
182 8. The Graphics Pipeline
We will briefly discuss view volume culling and backface culling, but culling
in high performance systems is a complex topic; see (Akenine-M¨oller et al., 2008)
for a complete discussion and for information about occlusion culling.
8.4.1 View Volume Culling
When an entire primitive lies outside the view volume, it can be culled, since it
will produce no fragments when rasterized. If we can cull many primitives with a
quick test, we may be able to speed up drawing significantly. On the other hand,
testing primitives individually to decide exactly which ones need to be drawn may
cost more than just letting the rasterizer eliminate them.
View volume culling, also known as view frustum culling, is especially help-
ful when many triangles are grouped into an object with an associated bounding
volume. If the bounding volume lies outside the view volume, then so do all the
triangles that make up the object. For example, if we have 1000 triangles bounded
by a single sphere with center c and radius r, we can check whether the sphere
lies outside the clipping plane,
(p − a) · n =0,
where a is a point on the plane, and p is a variable. This is equivalent to checking
whether the signed distance from the center of the sphere c to the plane is greater
than +r. This amounts to the check that
(c − a) · n
n
>r.
Note that the sphere may overlap the plane even in a case where all the triangles
do lie outside the plane. Thus, this is a conservative test. How conservative the
test is depends on how well the sphere bounds the object.
The same idea can be applied hierarchically if the scene is organized in one
of the spatial data structures described in Chapter 12.
8.4.2 Backface Culling
When polygonal models are closed, i.e., they bound a closed space with no holes,
then they are often assumed to have outward facing normal vectors as discussed
in Chapter 10. For such models, the polygons that face away from the eye are
certain to be overdrawn by polygons that face the eye. Thus, those polygons can
be culled before the pipeline even starts. The test for this condition is the same
one used for silhouette drawing given in Section 10.3.1.
i
i
i
i
i
i
i
i
8.4. Culling Primitives for Efficiency 183
Frequently Asked Questions
• I’ve often seen clipping discussed at length, and it is a much more in-
volved process than that described in this chapter. What is going on here?
The clipping described in this chapter works, but lacks optimizations that an
industrial-strength clipper would have. These optimizations are discussed in de-
tail in Blinn’s definitive work listed in the chapter notes.
• How are polygons that are not triangles rasterized?
These can either be done directly scan-line by scan-line, or they can be broken
down into triangles. The latter appears to be the more popular technique.
• Is it always better to antialias?
No. Some images look crisper without antialiasing. Many programs use unan-
tialiased “screen fonts” because they are easier to read.
• The documentation for my API talks about “scene graphs” and “matrix
stacks.” Are these part of the graphics pipeline?
The graphics pipeline is certainly designed with these in mind, and whether we
define them as part of the pipeline is a matter of taste. This book delays their
discussion until Chapter 12.
• Is a uniform distance z-buffer better than the standard one that includes
perspective matrix non-linearities?
It depends. One “feature” of the non-linearities is that the z-buffer has more res-
olution near the eye and less in the distance. If a level-of-detail system is used,
then geometry in the distance is coarser and the “unfairness” of the z-buffer can
be a good thing.
• Is a software z-buffer ever useful?
Yes. Most of the movies that use 3D computer graphics have used a variant of the
software z-buffer developed by Pixar (Cook et al., 1987) .
i
i
i
i
i
i
i
i
184 8. The Graphics Pipeline
Notes
A wonderful book about designing a graphics pipeline is Jim Blinn’s Corner:
A Trip Down the Graphics Pipeline (J. Blinn, 1996). Many nice details of the
pipeline and culling are in 3D Game Engine Design (Eberly, 2000) and Real-Time
Rendering (Akenine-M¨oller et al., 2008).
Exercises
1. Suppose that in the perspective transform we have n =1and f =2. Under
what circumstances will we have a “reversal” where a vertex before and
after the perspective transform flips from in front of to behind the eye or
vice-versa?
2. Is there any reason not to clip in x and y after the perspective divide (see
Figure 11.2, stage 3)?
3. Derive the incremental form of the midpoint line-drawing algorithm with
colors at endpoints for 0 <m≤ 1.
4. Modify the triangle-drawing algorithm so that it will draw exactly one pixel
for points on a triangle edge which goes through (x, y)=(−1, −1).
5. Suppose you are designing an integer z-buffer for flight simulation where
all of the objects are at least one meter thick, are never closer to the viewer
than 4 meters, and may be as far away as 100 km. How many bits are
needed in the z-buffer to ensure there are no visibility errors? Suppose that
visibility errors only matter near the viewer, i.e., for distances less than 100
meters. How many bits are needed in that case?
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.