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 parameter 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 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, and L. Zhang. A hierarchical method for real-time distance computation among moving convex bodies. Computatonal Geometry: Theory and Applications, 15(1-3):51–68, 2000.
PDF - L.J. Guibas, D. Hsu, and L. Zhang. H-Walk: hierarchical distance computation for moving convex bodies. In Proc. ACM Symp. on Computational Geometry, pp. 265–273, 1999.
PDF
People
Acknowledgements
We thank Brian Mirtich for providing us an implementation of the V-Clip alogorithm, which greatly eased our experiments.