Graphics Reference
In-Depth Information
A B
A
B
Figure 3.26 The Minkowski sum of a triangle A and a square B .
The Minkowski difference of two point sets A and B is defined analogously to the
Minkowski sum:
= a
B .
A
B
b
:
a
A , b
Geometrically, the Minkowski difference is obtained by adding A to the reflection of
B about the origin; that is, A
B ) (Figure 3.27). For this reason, both
terms are often simply referred to as the Minkowski sum. For two convex polygons, P
and Q , the Minkowski sum R
B
=
A
(
Q has the properties that R is a convex polygon
and the vertices of R are sums of the vertices of P and Q . The Minkowski sum of two
convex polyhedra is a convex polyhedron, with corresponding properties.
Minkowski sums both directly and indirectly apply to collision detection. Con-
sider the problem of having a complex object move past a number of other equally
complex obstacles. Instead of performing expensive tests on these complex objects,
the obstacles can be “grown” by the object at the same time the object is “shrunk,”
allowing the collision testing of the moving object to be treated as a moving point
against the grown obstacles. This idea is further explored in, for example, Chapter 8,
in regard to BSP trees.
The Minkowski difference is important from a collision detection perspective
because two point sets A and B collide (that is, have one or more points in com-
mon) if and only if their Minkowski difference C
=
P
=
contains the origin
(Figure 3.27). In fact, it is possible to establish an even stronger result: computing
the minimum distance between A and B is equivalent to computing the minimum
distance between C and the origin. This fact is utilized in the GJK algorithm presented
in Chapter 9. The result follows because
(
C
A
B
)
min a
b :
B
distance( A , B )
=
a
A , b
min c :
B .
=
c
A
Search WWH ::




Custom Search