Interactive Motion Planning Using Hardware-Accelerated Computation of Generalized Voronoi Diagrams

Kenneth E. Hoff III, Tim Culver, John Keyser, Ming Lin, and Dinesh Manocha

ABSTRACT: We present techniques for fast motion planning by using discrete approximations of generalized Voronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are applicable to both static and dynamic environments of fairly high complexity.  We compute a discrete Voronoi diagram by rendering a three-dimensional distance mesh for each Voronoi site. The sites can be points, line segments, polygons, polyhedra, curves and surfaces.  The computation of the generalized Voronoi diagram provides fast proximity query toolkits for motion planning.  The tools provide the distance to the nearest obstacle stored in the Z-buffer, as well as the Voronoi boundaries, Voronoi vertices and weighted Voronoi graphs extracted from the frame buffer using continuation
methods. Our approaches are not only applicable to classical motion planning problems, but are also suitable for dynamic environments and sensor-based planning. We have implemented these algorithms and demonstrated their performance for path planning in a complex dynamic environment composed of more
than 140,000 polygons.
Technical Report UNC CS TR99-036 (.pdf) / Colorplate (.gif)
2d.avi / 2d_dynamic.avi / 3d.avi
Overhead view of house floorplan. Current position of music stand is shown in the center of the image. The closest node of the Voronoi graph is shown in red and the next subgoal is shown in blue. 3D view of house motion planner. We are planning the motion of the music stand (near the center of the image).
last updated: 11/2/99