Title :
Accelerated proximity queries between convex polyhedra by multi-level Voronoi marching
Author :
Ehmann, Stephen A. ; Lin, Ming C.
Author_Institution :
Dept. of Comput. Sci., North Carolina Univ., Chapel Hill, NC, USA
Abstract :
We present an accelerated proximity query algorithm between moving convex polyhedra. The algorithm combines Voronoi-based feature tracking with a multi-level-of-detail representation, in order to adapt to the variation in levels of coherence and speed up the computation. It provides a progressive refinement framework for collision detection and distance queries. We have implemented our algorithm and have observed significant performance improvements in our experiments, especially on scenarios where the coherence is low
Keywords :
computational complexity; computational geometry; mobile robots; navigation; Voronoi-based feature tracking; accelerated proximity query algorithm; coherence level variation adaptation; collision detection; computation acceleration; convex polyhedra; distance queries; low coherence; multilevel Voronoi marching; progressive refinement framework; Acceleration; Analytical models; Computational modeling; Computer aided manufacturing; Computer science; Design automation; Manufacturing automation; Robot sensing systems; Robotics and automation; Spatial resolution;
Conference_Titel :
Intelligent Robots and Systems, 2000. (IROS 2000). Proceedings. 2000 IEEE/RSJ International Conference on
Conference_Location :
Takamatsu
Print_ISBN :
0-7803-6348-5
DOI :
10.1109/IROS.2000.895281