Fast Continuous Collision Detection for Articulated Models

Stephane Redon, Ming C. Lin and Dinesh Manocha

Department of Computer Science
University of North Carolina at Chapel Hill

Young J. Kim

Computer Science and Engineering
Ewha Womans University, Korea

Benefits of our continuous collision detection algorithm over discrete methods. These images of our benchmarking system highlight the collision detection between a robot in a CAD environment composed of pipes. The left image shows two discrete positions of the robot. The middle image illustrates the motion trajectory used by our algorithm. The right image indicates the position of the robot arm at the time of first contact with the CAD environment along that trajectory. These computations are performed at almost interactive rates.

Abstract

We present a novel algorithm to perform continuous collision detection for articulated models. Given two discrete configurations of the links of an articulated model, we use an “arbitrary in-between motion” to interpolate its motion between two successive time steps and check the resulting trajectory for collisions. Our approach uses a three-stage pipeline: (1) dynamic bounding-volume hierarchy (D-BVH) culling based on interval arithmetic; (2) culling refinement using the swept volume of line swept sphere (LSS) and graphics hardware accelerated queries; (3) exact contact computation using OBB-trees and continuous collision detection between triangular primitives. The overall algorithm computes the time of collision, contact locations and prevents any interpenetration between the articulated model with the environment. We have implemented the algorithm and tested its performance on a 2.4 GHz Pentium PC with 1 Gbyte of RAM and a NVIDIA GeForce FX 5800 graphics card. In practice, our algorithm is able to perform accurate and continuous collision detection between articulated models and complex environments at nearly interactive rates. 


          Download paper [2.7 MBytes] 


          Authors' pages:

              Stephane Redon
              Young J. Kim
              Ming C. Lin
              Dinesh Manocha 

Benchmarks (corresponding average execution times available in the technical report)

Pipes and Puma robot

Auxiliary Machine Room and Puma robot

Auxiliary Machine Room and star-shaped robot

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.