Graphics Reference
In-Depth Information
Chapter
5
Basic Primitive Tests
After a high-level system has ruled out as many objects as possible from further col-
lision tests, all collision systems must perform low-level tests between primitives or
bounding volumes to determine intersection status. In some cases, a simple indica-
tion whether there is an intersection is sufficient. In other cases, the actual point of
intersection is required. This chapter describes how these low-level tests can be effi-
ciently performed. In addition, the goal is to provide enough specific mathematical
detail to allow derivation of tests that go beyond the scope of this presentation, using
the mathematical ideas examined here.
Note that some of the mathematical expressions presented herein may be subject to
numerical accuracy problems when implemented in floating-point arithmetic. These
problems are only briefly touched on here. A deeper discussion of the robustness
issues due to numerical accuracy problems is found in Chapter 11.
5.1
Closest-point Computations
Closest-point queries are some of the most powerful of collision queries. Given the
closest points between two objects, the distance between the objects is obtained. If
the combined maximum movement of two objects is less than the distance between
them, a collision can be ruled out. In a hierarchical representation, closest-point
computations allow parts of the hierarchy that will never come close enough to collide
to be pruned from further consideration.
Obtaining the closest points between two objects can be seen as a minimization
problem. One approach is to formulate the minimization problem and solve it using
methods of calculus (such as the method of Lagrange multipliers). In this text a more
geometric approach is preferred, and the following subsections illustrate how the
closest points can be obtained for various geometric objects.
125
