Fast computation of generalized Voronoi diagrams using graphics hardware

Kenneth Hoff, John Keyser, Ming Lin, Dinesh Manocha, Tim Culver
University of North Carolina at Chapel Hill, Department of Computer Science
In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques (1999), pp. 277-286.


   title={Fast computation of generalized Voronoi diagrams using graphics hardware},

   author={Hoff III, K.E. and Keyser, J. and Lin, M. and Manocha, D. and Culver, T.},

   booktitle={Proceedings of the 26th annual conference on Computer graphics and interactive techniques},




   organization={ACM Press/Addison-Wesley Publishing Co.}


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.
Rating: 2.5/5. From 1 vote.
Please wait...

Recent source codes

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: