Fast Collision Detection for Skeletally Deformable Models

We present a new method of collision detection for models deformed by linear blend skinning. The linear blend skinning (also known as skeleton- subspace deformation, vertex-blending, or enveloping) is a popular method to animate believable organic models. We consider an exact collision detection based on a hierarchy of bounding spheres. The main problem with this approach is the update of bounding volumes -- they must follow the current deformation of the model. We introduce a new fast method to refit the bounding spheres, which can be executed on spheres in any order. Thanks to this on-demand refitting operation we obtain a collision detection algorithm with speed comparable to the standard rigid body collision detection. The algorithm was tested on a variety of practical situations, including an animated crowd. According to these experiments, the proposed approach is considerably faster than the previous method.