Graphics Reference
In-Depth Information
A
(-
B
)
A
B
Figure 3.27
Because rectangle
A
and triangle
B
intersect, the origin must be contained in
their Minkowski difference.
Note that the Minkowski difference of two convex sets is also a convex set, and thus
its point of minimum norm is unique.
There are algorithms for computing the Minkowski sum explicitly (for example,
[Bekker01]). In this topic, however, the Minkowski sum is primarily used conceptually
to help recast a collision problem into an equivalent problem. Occasionally, such as
in the GJK algorithm, the Minkowski sum of two objects is computed implicitly.
The Minkowski difference of two objects is also sometimes referred to as the
trans-
lational configuration space obstacle
(or TCSO). Queries on the TCSO are said to be
performed in
configuration space
.
3.12
Summary
Working in the area of collision detection requires a solid grasp of geometry and linear
algebra, not to mention mathematics in general. This chapter has reviewed some
concepts from these fields, which permeate this topic. In particular, it is important
to understand fully the properties of dot, cross, and scalar triple products because
these are used, for example, in the derivation of virtually all primitive intersection
tests (compare Chapter 5). Readers who do not feel comfortable with these math
concepts may want to consult linear algebra textbooks, such as those mentioned in
the chapter introduction.
This chapter also reviewed a number of geometrical concepts, including points,
lines, rays, segments, planes, halfspaces, polygons, and polyhedra. A delightful
introduction to these and other geometrical concepts is given in [Mortenson99].
Relevant concepts from computational geometry and from the theory of convex
sets were also reviewed. Voronoi regions are important in the computation of closest
points. The existence of separating planes and axes for nonintersecting convex objects
