Real-Time Collision Detection

Chapter 9

Convexity-based Methods

It is not a coincidence that the bounding volume representations explored in this book 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 ...