Collision Detection  

Overview 
Computing distance between objects is an important problem in many applications, for example, virtual environment simulation, computer animation, and robot motion planning. Distance information can be used to detect collision, as collision has undesirable consequences in most systems. It can also be used to guide sampling in randomized motion planning algorithms. This project investigates efficient algorithms for collision detection and distance computation. The particular emphasis is on collision detection among moving objects. 

H-Walk: distance computation for moving convex bodies 
The Hierarchical Walk, or H-Walk algorithm, maintains the distance between two moving convex bodies by exploiting both coherence of motion and hierarchical representation. For convex polygons, we have proven that H-Walk improves on the classic Lin-Canny and the Dobkin-Kirkpatrick algorithms. We have also implemented H-Walk for moving convex polyhedra in three dimensions. Experimental results indicate that unlike previous incremental distance computation algorithms, H-Walk scales well with respect to coherence. 
 
Quicktime movie showing H-Walk in working (0.9 MB). 
Download the Quicktime viewer.
 
        In our experiments, we used a pair of identical objects. One of them is fixed at the origin, and the other orbits around it and rotates about some randomly chosen axis. The plots below show the performance of H-Walk, as well as that of V-Clip, a very efficient implementation of the Lin-Canny algorithm. In the graphs below, the horizontal axis is some estimate of coherence. The vertical axis is the number of steps that it takes each algorithm to find the closest pair of features. H-Walk can also automatically adjust a paramter in the algorithm in order to respond to changes  in the level of coherence and thus maintain the best performance. In the experiments, we kept the parameter fixed in order to see the its effect on the algorithm. In the graphs, "h-walk n" stands for H-Walk with the parameter set to n.  See the paper for details and more experimental results. 
 
 

 

References 
L. J. Guibas, D. Hsu, L. Zhang. A hierarchical method for real-time distance computation among moving convex bodies. Computational Geometry: Theory and Applications, Special Issue on Virtual Reality, 15 (1-3), 51-68, 2000. (Postscript, 3.8MB | PDF, 2.0MB)

L. J. Guibas, D. Hsu, L. Zhang. H-Walk: Hierarchical distance computation for moving convex bodies. In Proc. ACM Symposium on Computational Geometry, pages 265-273, 1999. (Postscript, 0.3MB | PDF, 0.1MB)

People 
  Leonidas J. Guibas
   David Hsu
   Li Zhang 

Acknowledgement We thank Brian Mirtich for providing us an implementation of the V-Clip alogorithm, which greatly eased our experiments.

back 
 
Maintained by David Hsu     Last Modified: Sun Jan  3 20:16:20 PST 1999