Hierarchical and Controlled Advancement for

Continuous Collision Detection of Rigid and Articulated Models

Min Tang¹, Dinesh Manocha² and Young J. Kim¹

¹Department of Computer Science & Engineering

Ewha Womans University, Seoul, Korea

tangmin@ewha.ac.kr kimy@ewha.ac.kr

²Department of Computer Science

University of North Carolina at Chapel Hill

dm@cs.unc.edu

Download

1. Accepted in TVCG 2014 in PDF (1903KBytes)

2. Publication in ICRA 2009 in PDF (698KBytes), BibTex

To Appear in the IEEE International Conference on Robotics and Automation, May 12 - 17, Japan, 2009.

3. Source Code in C++

Abstract

We present fast CCD algorithm for general rigid and articulated models based on conservative advancement. We

have implemented the CCD algorithm with two different acceleration techniques which can handle rigid models, and have extended one of them to articulated models. The resulting algorithms take a few milliseconds for rigid models with tens of thousands of triangles, and a few milliseconds for articulated models with tens of links. We show that the performance of our algorithms is much faster than existing CCD algorithms for polygon-soup models and it is also comparable to competing CCD algorithms that are limited to manifold models. The preliminary version of this paper appeared in ICRA 2009.

Benchmarking Scenarios

1. Grasping (104.8K):
In the figure below, the hand model is composed of 21 links and 8k triangles, and the sphere of 2k triangles. Our CCD algorithm is used to find the first contact between the hand and sphere during the approaching motion of the hand; it is then used again to find the ToC between the fingers and the sphere, as well as between the fingers themselves as they close.

Grasping

2. Club vs Club (104.8K):
In the figure below, the red, blue, and green objects denote the club model at initial, final and TOC configurations respectively. The TOC configuration is computed by our continuous collision detection algorithm after linearly interpolating the initial and final configurations. The yellow object shows the configuration of an obstacle. There are more than 200 simulation steps in the benchmark, and in all trials no collision-free situation exists.

Club vs Club

Download Video in WMV (0.7MBytes)

3. Hammer (1.7K) vs CAD Piece (2.6K):

A similar set up like the benchmark 1.

Hammer vs CAD Piece

Download Video in WMV (0.4MBytes)

4. Rigid Body Dynamics for Bunnies: Using the same benchmarking (Rigid Body Dynamics for Bunnies) setup as FAST: http://graphics.ewha.ac.kr/FAST/. In the figure, the TOC configurations are shown as green objects. In the following graph, "*" shows the simulation steps when the TOC should be computed.

Rigid Body Dynamics for Bunnies

Download Video in WMV (0.5MBytes)

Abstract

Benchmarking Scenarios

RELATED LINKS