Continuous Collision Detection for
Articulated Models using
Taylor Models and Temporal Culling
[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.
|
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.. |
|
