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.
This work has been partly supported by the Ministry of Education, Youth and Sports of the Czech Republic under research program MSM 6840770014 (Research in the Area of the Prospective Information and Navigation Technologies). We would like to thank to the anonymous reviewers as well as to Daniel Sýkora and Ivana Kolingerova for numerous valuable comments. We thank also to Stĕpán Prokop and Psionic for providing the example models and to Eliska Žárová and Ondřej Žára for help with the accompanying video.