Continuous Collision Detection for Articulated Models using
Taylor Models and Temporal Culling

Xinyu Zhang 1    Stephane Redon 2    Minkyoung Lee  1    Young J. Kim 1

1-Ewha Womans University, Korea

 2-INRIA Rhone-Alpes, France


ACM SIGGRAPH 2007 [Note] [Paper (4.1 MB)] [Full video (67 MB)] [BibTex] [TechRep] [Source (9.51 MB)]

[Abstract]  We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as collision witness features. We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated body dynamics and character motion planning. Our algorithm can perform CCDs including self-collisions for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.



(Download 67M)


Benchmarking Scenarios


Walking Mannequin on a Chessboard [Video, 3.1M]

A mannequin model walks on a chessboard where 16 chessmen are placed. The mannequin consists of 15 links and 20K triangles, and the chessmen consists of 101K triangles. The locomotion of the mannequin has been generated by creating key poses of the mannequin and running the FootstepTM software in 3DSMaxTM. We generated the movements of the mannequin without considering collisions, and so the mannequin often collides with chessmen as well as with itself (leg crossing).


Exercising Mannequin [Video, 1.9M]

We created a key-framed animation with self-collisions between links in a mannequin model. For example, as shown in the left image, the right hand of the mannequin collides with its own right foot.


Construction Site in the Toy World 1 [Video, 3.5M]

After moving from the initial site to the second, an excavator picks up a weight and loads it into a truck as shown in the left image. The whole construction site consists of 0.394M triangles and 0.17M convex pieces besides an excavator which consists of 18.94K triangles and 13K convex pieces.


Construction Site in the Toy World 2 [Video, 3.0M]

After moving from the first site to the second, a tower crane picks up a weight and drops it into a pipe. The whole construction site consists of 0.394M triangles besides a moving tower crane which consists of 1,288 triangles and 272 convex pieces.


Collision Course 1 [Video, 1.4M]

We simulate the rigid body dynamics of articulated models, apply our CCD algorithm to each frame in the simulation. In the first scenario, four train models consisting of 10 links and 23K triangles each are collided and tangled with one another. The trains have 17,444 convex pieces in total.


Collision Course 2

A train model consisting of 17 links and 42K triangles drops from the sky and comes to rest onto a mountain model consisting of 29K triangles..

Related Links

FAST: Interactive Continuous Collision Detection for Non-Convex Polyhedra


Articulate: Fast Continuous Collision Detection for Articulated Models


MPK: The Stanford Motion Planning Kit Library


SWIFT++: The UNC Proximity Query Library


Copyright 2007 Computer Graphics Laboratory
Dept of Computer Science & Engineering
Ewha Womans University, Seoul, Korea
Last update: May 2, 2007