Graphics Reference
In-Depth Information
Chapter 9
Convexity-based
Methods
It is not a coincidence that the bounding volume representations explored in this topic
have one feature in common: they are convex objects. Convex objects have certain
properties that make them highly suitable for use in collision detection tests. One
important property is the existence of a separating plane for nonintersecting convex
objects (see Section 3.8). Another property of convex objects is that the distance
between two points — one from each object — is at a local minimum. The distance is
also a global minimum (Figure 9.1a). This property ensures that the global minimum
distance between two convex objects can be found by simple hill climbing. That is,
starting with any pair of points and moving each point gradually closer to the other
(without moving outside the objects) a globally closest pair of points is eventually
attained.
Concave objects do not share these characteristics. For example, for two concave
objects a local minimum is not necessarily a global minimum (Figure 9.1b).
By exploiting the special properties of convex objects, it is possible to design effi-
cient collision detection algorithms for them. This chapter discusses algorithms of
this type. The algorithms deal largely with (convex) polyhedra, but some algorithms
— notably the GJK algorithm of Section 9.5 — also deal with general convex objects.
In the following, polyhedra are assumed convex unless otherwise stated.
9.1 Boundary-based Collision Detection
To establish a reference frame before looking at more advanced convexity-based meth-
ods, a simple solution to the collision detection problem for two polyhedra is to base
the test on the boundary description of the objects. Let two polyhedra P and Q be
given in a form allowing easy access to their vertices and faces (and therefore edges).
383
Search WWH ::




Custom Search