Real-Time Rendering, Third Edition, 3rd Edition

i

i

i

i

i

i

i

i

Chapter 16

Intersection Test Methods

“I’ll sit and see if that small sailing cloud

Will hit or miss the moon.”

—Robert Frost

Intersection testing is often used in computer graphics. We may wish to

click the mouse on an object, or to determine whether two objects collide,

or to make sure we maintain a constant height off the floor for our viewer

as we navigate a building. All of these operations can be performed with

intersection tests. In this chapter, we cover the most common ray/object

and object/object intersection tests.

In interactive computer graphics applications, it is often desirable to

let the user select a certain object by picking (clicking) on it with the

mouse or any other input device. Naturally, the performance of such an

operation needs to be high. One picking method, supported by OpenGL, is

to render all objects into a tiny pick window. All the objects that overlap

the window are returned in a list, along with the minimum and maximum

z-depth found for each object. This sort of system usually has the added

advantage of being able to pick on lines and vertices in addition to surfaces.

This pick method is always implemented entirely on the host processor and

does not use the graphics accelerator. Some other picking methods do use

the graphics hardware, and are covered in Section 16.1.

Intersection testing offers some benefits that OpenGL’s picking method

does not. Comparing a ray against a triangle is normally faster than send-

ing the triangle through OpenGL, having it clipped against a pick window,

then inquiring whether the triangle was picked. Intersection testing meth-

ods can compute the location, normal vector, texture coordinates, and

other surface data. Such methods are also independent of API support (or

lack thereof).

The picking problem can be solved efficiently by using a bounding vol-

ume hierarchy (see Section 14.1.1). First, we compute the ray from the

camera’s position through the pixel that the user picked. Then, we recur-

sively test whether this ray hits a bounding volume of the hierarchy. If at

725

i

i

i

i

i

i

i

i

726 16. Intersection Test Methods

any time the ray misses a bounding volume (BV), then that subtree can be

discarded from further tests, since the ray will not hit any of its contents.

However, if the ray hits a BV, its children’s BVs must be tested as well.

Finally, the recursion may end in a leaf that contains geometry, in which

case the ray must be tested against each primitive in the geometry node.

As we have seen in Section 14.3, view frustum culling is a means for

efficiently discarding geometry that is outside the view frustum. Tests

that decide whether a bounding volume is totally outside, totally inside, or

partially inside a frustum are needed to use this method.

In collision detection algorithms (see Chapter 17), which are also built

upon hierarchies, the system must decide whether or not two primitive

objects collide. These primitive objects include triangles, spheres, axis-

aligned bounding boxes (AABBs), oriented bounding boxes (OBBs), and

discrete oriented polytopes (k-DOPs).

In all of these cases, we have encountered a certain class of problems

that require intersection tests. An intersection test determines whether two

objects, A and B, intersect, which may mean that A is totally inside B

(or vice versa), that the boundaries of A and B intersect, or that they are

totally disjoint. However, sometimes more information may be needed, such

as the closest intersection point, the distance to this intersection point, etc.

In this chapter, a set of fast intersection test methods is identified and

studied thoroughly. We not only present the basic algorithms, but also

give advice on how to construct new and efficient intersection test meth-

ods. Naturally, the methods presented in this chapter are also of use in

offline computer graphics applications. For example, the algorithms pre-

sented in Sections 16.6 through 16.9 can be used in ray tracing and global

illumination programs.

After briefly covering hardware-accelerated picking methods, this chap-

ter continues with some useful definitions, followed by algorithms for form-

ing bounding volumes around primitives. Rules of thumb for constructing

efficient intersection test methods are presented next. Finally, the bulk of

the chapter is made up of a cookbook of intersection test methods.

16.1 Hardware-Accelerated Picking

There are a few hardware-accelerated picking methods worth mentioning.

One method was first presented by Hanrahan and Haeberli [497]. To sup-

port picking, the scene is rendered with each polygon having a unique color

value that is used as an identifier. The image formed is stored offscreen and

is then used for extremely rapid picking. When the user clicks on a pixel,

the color identifier is looked up in this image and the polygon is immedi-

ately identified. The major disadvantage of this method is that the entire