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.
distance computation for moving convex bodies
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.
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 |
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)
Acknowledgement We thank Brian Mirtich for providing us an implementation of the V-Clip alogorithm, which greatly eased our experiments.
Maintained by David Hsu Last Modified: Sun Jan 3 20:16:20 PST 1999