Collision detection is essential for realistic physical interactions in video games and physically based modeling. To ensure real-time interactivity with the player, video game developers usually approximate the 3D models, such as game characters and static objects, with a set of simple convex shapes, such as ellipsoids, capsules, or convex hulls. While adequate for some simple interactions, these basic shapes provide poor approximations for concave surfaces and generate false collision detections (see Figure 2.8.1).
Figure 2.8.1. Convex ...