Real-Time Rendering, Third Edition, 3rd Edition

i

i

i

i

i

i

i

i

Chapter 14

Acceleration Algorithms

“Now here, you see, it takes all the running you can do to keep

in the same place. If you want to get somewhere else, you

must run at least twice as fast as that!”

—Lewis Carroll

One of the great myths concerning computers is that one day we will have

enough processing power. Even in a relatively simple application like word

processing, we find that additional power can be applied to all sorts of

features, such as on-the-fly spell and grammar checking, antialiased text

display, voice recognition and dictation, etc.

In real-time rendering, we have at least four performance goals: more

frames per second, higher resolution and sampling rates, more realistic ma-

terials and lighting, and increased complexity. A speed of 60–85 frames per

second is generally considered a fast enough frame rate; see the Introduc-

tion for more on this topic. Even with motion blurring (Section 10.14),

which can lower the frame rate needed for image quality, a fast rate is still

needed to minimize latency when interacting with a scene [1329].

IBM’s T221 LCD display offers 3840 × 2400 resolution, with 200 dots

per inch (dpi) [1329]. A resolution of 1200 dpi, 36 times the T221’s den-

sity, is offered by many printer companies today. A problem with the

T221 is that it is difficult to update this many pixels at interactive rates.

Perhaps 1600 × 1200 is enough resolution for a while. Even with a limit

on screen resolution, antialiasing and motion blur increase the number of

samples needed for generating high-quality images. As discussed in Sec-

tion 18.1.1, the number of bits per color channel can also be increased,

which drives the need for higher precision (and therefore more costly)

computations.

As previous chapters have shown, describing and evaluating an object’s

material can be computationally complex. Modeling the interplay of light

645

i

i

i

i

i

i

i

i

646 14. Acceleration Algorithms

Figure 14.1. A “reduced” Boeing model with a mere 350 million triangles rendered with

ray tracing. Sectioning is performed by using a user-defined clipping plane. This model

can be rendered at 15 fps without shadows on 16 Opteron cores, using more flexible but

untuned OpenRT ray tracing code. It can also be rendered at about 4 fps at 640 × 480

with shadows, on heavily tuned code on a dual processor. Once camera movement stops,

the image can be progressively enhanced with antialiasing and soft shadowing. (Image

courtesy of Computer Graphics Group, Saarland University. Source 3D data provided

by and used with permission of the Boeing Company.)

and surface can absorb an arbitrarily high amount of computing power.

This is true because an image should ultimately be formed by the contri-

butions of light traveling down a limitless number of paths from an illumi-

nation source to the eye.

Frame rate, resolution, and shading can always be made more com-

plex, but there is some sense of diminishing returns to increasing any of

these. There is no real upper limit on scene complexity. The render-

ing of a Boeing 777 includes 132,500 unique parts and over 3,000,000 fas-

teners, which would yield a polygonal model with over 500,000,000 poly-

gons [206]. See Figure 14.1. Even if most of those objects are not seen

due to size or position, some work must be done to determine that this

is the case. Neither Z-buffering nor ray tracing can handle such mod-

els without the use of techniques to reduce the sheer number of compu-

tations needed. Our conclusion: Acceleration algorithms will always be

needed.

In this chapter, a sm¨org˚asbord of algorithms for accelerating computer

graphics rendering, in particular the rendering of large amounts of geome-

try, will be presented and explained. The core of many such algorithms is

based on spatial data structures, which are described in the next section.

Based on that knowledge, we then continue with culling techniques.These

are algorithms that try to find out which objects are at all visible and need

to be treated further. Level of detail techniques reduce the complexity of

rendering the remaining objects. Finally, systems for rendering very large

models, and point rendering algorithms, are briefly discussed.