Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware Kenneth E. Hoff III hoff [at] cs [dot] unc [dot] edu

Abstract: We present a new approach for computing generalized 2D and 3D Voronoi diagrams using interpolation-based polygon rasterization hardware. We compute a discrete Voronoi diagram by rendering a three dimensional distance mesh for each Voronoi site. The polygonal mesh is a bounded-error approximation of a (possibly) non-linear function of the distance between a site and a 2D planar grid of sample points. For each sample point, we compute the closest site and the distance to that site using polygon scan-conversion and the Z-buffer depth comparison. We construct distance meshes for points, line segments, polygons, polyhedra, curves, and curved surfaces in 2D and 3D. We generalize to weighted and farthest-site Voronoi diagrams, and present efficient techniques for computing the Voronoi boundaries, Voronoi neighbors, and the Delaunay triangulation of points. We also show how to adaptively refine the solution through a simple windowing operation. The algorithm has been implemented on SGI workstations and PCs using OpenGL, and applied to complex datasets. We demonstrate the application of our algorithm to fast motion planning in static and dynamic environments, selection in complex user-interfaces, and creation of dynamic mosaic effects.

FAST COMPUTATION OF GENERALIZED VORONOI DIAGRAMS
	Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware (Acrobat) Kenneth E. Hoff III, Tim Culver, John Keyser, Ming Lin, and Dinesh Manocha
	SIGGRAPH '99 Presentation PowerPoint 97 Kenneth E. Hoff III
MOTION PLANNING
	Interactive Motion Planning Using Hardware-Accelerated Computation of Generalized Voronoi Diagrams (PDF), (colorplate.tif) Kenneth Hoff III, Tim Culver, John Keyser, Ming Lin, and Dinesh Manocha
DEMOS
	2D Voronoi Demo PC executable opengl32.dll, glu32.dll, glut32.dll press 'h' for help Kenneth E. Hoff III
	3D Voronoi Demo PC executable opengl32.dll, glu32.dll, glut32.dll press 'h' for help Kenneth E. Hoff III
	Mosaic Tiling Demo (also known as 10,000 point demo) PC executable, source image opengl32.dll, glu32.dll, glut32.dll on-screen instructions Kenneth E. Hoff III

Copyright 1999. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.