A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We propose an accurate collision detection algorithm for use in virtual reality applications. The algorithm works for three-dimensional graphical environments where multiple objects, represented as polyhedra (boundary representation), are undergoing arbitrary motion (translation and rotation). The algorithm can be used directly for both convex and concave objects and objects can be deformed (non-rigid) during motion. The algorithm works efficiently by first reducing the number of face pairs that need to be checked accurately for interference by first localizing possible collision regions using bounding box and spatial subdivision techniques; face pairs that remain after this pruning stage are then accurately checked for interference. The algorithm is efficient, simple to implement, and does not require any memory intensive auxiliary data structures to be precomputed and updated. Since polyhedral shape representation is one of the most common shape representation schemes, this algorithm should be useful to a wide audience. Performance results are given to show the efficiency of the proposed method.Keywords
This publication has 18 references indexed in Scilit:
- Fast contact determination in dynamic environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient distance computation between non-convex objectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The use of awareness in collision predictionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Solving the collision detection problemIEEE Computer Graphics and Applications, 1994
- Interference detection through rasterizationThe Journal of Visualization and Computer Animation, 1991
- Curved surfaces and coherence for non-penetrating rigid body simulationACM SIGGRAPH Computer Graphics, 1990
- Collision Detection and Response for Computer AnimationPublished by Association for Computing Machinery (ACM) ,1988
- A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Journal on Robotics and Automation, 1988
- Fast collision detection scheme by recursive decomposition of a manipulator workspacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Interference detection among solids and surfacesCommunications of the ACM, 1979