Continuous Collision Detection for Non-rigid Contact Computations
using Local Advancement

Min Tang1,  Young J. Kim1 and Dinesh Manocha2
1Department of Computer Science & Engineering
Ewha Womans University, Seoul, Korea
2Department of Computer Science
University of North Carolina at Chapel Hill

1. Publication in ICRA 2010 in PDF  (858KBytes), BibTex

To Appear in the IEEE International Conference on Robotics and Automation,  May 3-8, Anchorage, Alaska, 2010.




    We present a novel algorithm to perform continuous collision detection (CCD) between non-rigid, deformable models using local advancement. Given the initial and final configurations of a deformable model, our algorithm computes linear deformation by interpolating the vertices from the initial to the final configurations with a straight line path and checks for collision along that path. Our approach is applicable to polygon-soup models with arbitrary topology, handles self collisions and makes no assumption about the underlying nonrigid motion. We accelerate the algorithm by computing motion bounds on the primitives and their bounding volumes. These bounds are combined with hierarchical culling techniques and used for fast collision checking. In practice, we have observed
up to four times improvement in running time because of local advancement.


Benchmarking Scenarios

1. UNC Dynamic Scene Benchmarks

   Our method can be used to detect self-collision on dynamic scene benchmarks, and finding out the global ToC for entitle body or per-Triangle ToCs. 

Exploding Dragon (252K)                        Cloth simulation (92K)                         N-body Simulation (146K)

2. Deformable Motion Planning Benchmarks

We also used a different set of benchmarks based on motion planning in an environment composed of deformable
objects, in which both robots and obstacles can have non-rigid motions and the robots try to reach the goal configuration under such constraints such as shape preservation, collision response, manipulation and gravity forces.



                                     Bar and Spheres (636)

Human Organs (14K)


UNC Dynamic Scene Benchmarks:˜geom/DynamicB/

Self-CCD: Continuous Collision Detection for Deforming Objects

Open CCD:

Copyright 2011 Computer Graphics Laboratory
Dept of Computer Science & Engineering
Ewha Womans University, Seoul, Korea
Last update: 2011-05-12