Fast Continuous Collision Detection for Articulated Models
- 6 February 2005
- journal article
- Published by Wiley in Journal of Computing and Information Science in Engineering
- Vol. 5 (2) , 126-137
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 spheres (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 and contact locations, and prevents any interpenetration between the articulated model and the environment. We have implemented the algorithm and tested its performance on a 2.4GHz Pentium PC with 1Gbyte 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 modestly complex environments at nearly interactive rates.Keywords
This publication has 12 references indexed in Scilit:
- Computing and visualizing pose-interpolating 3D motionsComputer-Aided Design, 2001
- Computational Line Geometry2001
- Multiple sweeping using the Denavit–Hartenberg representation methodComputer-Aided Design, 1999
- Exact collision detection using virtual objects in virtual reality modeling of a manufacturing processJournal of Manufacturing Systems, 1999
- Efficient collision detection using bounding volume hierarchies of k-DOPsIEEE Transactions on Visualization and Computer Graphics, 1998
- Harmonic projection methods for large non-symmetric eigenvalue problemsNumerical Linear Algebra with Applications, 1998
- Comparing offset curve approximation methodsIEEE Computer Graphics and Applications, 1997
- Collision detection for interactive graphics applicationsIEEE Transactions on Visualization and Computer Graphics, 1995
- The approximation of non-degenerate offset surfacesComputer Aided Geometric Design, 1986
- Methods and Applications of Interval Analysis1979