Stephane Redon, Ming C. Lin and Dinesh Manocha
Department of Computer
Young J. Kim
Computer Science and
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.
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.
Benchmarks (corresponding average execution times available in the technical report)
Auxiliary Machine Room and Puma robot
Auxiliary Machine Room and star-shaped robot
Auxiliary Machine Room and chain 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.
Last revision : April 15, 2003