Fast Collision Detection for Skeletally Deformable Models

Ladislav Kavan
Czech Technical University, Prague
Jiří Žára
Czech Technical University, Prague

(a) reference posture of the creature with spheres on levels 4 and 6 of the tree (precomputed according to section 3.1), (b) an animated posture with spheres refitted by our algorithm (during run-time).


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.

accompanying video


Ladislav Kavan, Jiří Žára. Fast Collision Detection for Skeletally Deformable Models. Computer Graphics Forum 24(3) [Proceedings of Eurographics], 2005.  

Links and Downloads




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.