“Fast computation of generalized Voronoi diagrams using graphics hardware” by Hoff, Keyser, Lin, Manocha and Culver

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.

1. F. Aurenhammer. Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23:345-405, 1991.
2. J. Bloomenthal, C. Bajaj, J. Blinn, M-P. Cani-Gascuel, A. Rockwood, B. Wyvill, and G. Wyvill. Introduction to Implicit Surfaces. Morgan Kaufmann Publishers, Inc. San Francisco, CA. 1997.
3. C-S. Chiang. The Euclidean Distance Transform. Ph.D. thesis, Dept. Comp. Sci., Purdue Univ., West Lafayette, IN, August 1992. Report CSD-TR 92-050.
4. T. Culver, J. Keyser, and D. Manocha. Accurate Computation of the Medial Axis of a Polyhedron. Proc. of the Fifth Syrup. on Solid Modeling and Applications. 1999.
5. D. Dutta and C.M. Hoffmann. On the Skeleton of Simple CSG Objects. Journal of Mechanical Design, ASME Transactions, 115(1):87-94, 1993.
6. G.L. Dirichlet. Uber die Reduktion der Positiven Quadratischen Formen mit Drei Unbestimmten Ganzen Zahlen. J. Reine Angew. Math., 40:209-27, 1850.
7. D. Filip and R. Goldman. Conversion from BOzier-rectangles to BOzier-triangles. CAD, 19:25-27, 1987.
8. S. Fortune. A Sweepline Algorithm for Voronoi Diagrams. In Proc. 2nd Annual ACM Symp. on Comp. Geom., pages 313-322, 1986.
9. J. Goldfeather, S. Molnar, G. Turk, and H. Fuchs. Near Realtime CSG Rendering Using Tree Normalization and Geometric Pruning. IEEE Computer Graphics and Applications, 9(3):20-28, May 1989.
10. P. Haeberli. Paint by Numbers: Abstract Image Representation. Computer Graphics (SIGGRAPH ’90 Proc). vol. 25. pgs 207- 214.
11. M. Held. Voronoi Diagrams and Offset Curves of Curvilinear Polygons. Computer-Aided Design, 1997.
12. K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. Technical Report TR99-011, Dept. of Comp. Sci., University of North Carolina at Chapel Hill, 1999.
13. C.M. Hoffmann. How to Construct the Skeleton of CSG Objects. In A. Bowyer and J. Davenport, editors. Proc. of the Fourth IMA Conference, The Mathematics of Surfaces, University of Bath, UK, Sept. 1990. Oxford University Press, New York, 1994.
14. H. Inagaki, K. Sugihara, and N. Sugie. Numerically Robust Incremental Algorithm for Constructing Three-dimensional Voronoi Diagrams. In Proc. 4th Canad. Conf. Comp. Geom., pgs 334-339, 1992.
15. S. Kumar, D. Manocha, and A. Lastra. Interactive Display of Large NURBS Models. IEEE Trans. on Vis. and Computer Graphics. vol 2, no 4, pgs 323-336, Dec 1996.
16. J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991.
17. D. Lavender, A. Bowyer, J. Davenport, A. Wallis, and J. Woodwark. Voronoi Diagrams of Set-theoretic Solid Models. IEEE Computer Graphics and Applications, 12(5):69-77, Sept 1992.
18. D.T. Lee. Medial Axis Transformation of a Planar Shape. IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4:363-369, 1982.
19. J. Lengyel, M. Reichert, B.R. Donald, and D.P. Greenberg. Real-time Robot Motion Planning Using Rasterizing Computer Graphics Hardware. Computer Graphics (SIGGRAPH ’90 Proc.), vol. 24, pgs 327-335, Aug 1990.
20. V. Milenkovic. Robust Construction of the Voronoi Diagram of a Polyhedron. In Proc. 5th Canadian. Conference on Comp. Geom., pgs 473-478, 1993.
21. V. Milenkovic. Robust Polygon Modeling. Computer Aided Design, 25(9), 1993. (special issue on Uncertainties in Geometric Design).
22. A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 1992.
23. J. Rossignac, A. Megahed, and B. Schneider. Interactive Inspection of Solids: Cross-sections and Interferences. Computer Graphics (SIGGRAPH ’92 Proc.), vol. 26, pgs 353-360, July 1992.
24. J.R. Rossignac and A.A.G. Requicha. Depth-buffering Display Techniques for Constructive Solid Geometry. IEEE Computer Graphics and Applications, 6(9):29-39, 1986.
25. D.J. Sheehy, C.G. Armstrong, and D.J. Robinson. Computing the Medial Surface of a Solid from a Domain Delaunay Triangulation. In Proc. ACM/IEEE Symp. on Solid Modeling and Applications, May 1995.
26. M.I. Shamos and D.Hoey. Closest-point Problems. In Proc. 16th Annual IEEE Symposium on Foundations of Comp. Sci., pages 151-162, 1975.
27. K. Sugihara and M. Iri. A Robust Topology-oriented Incremental Algorithm for Voronoi Diagrams. International Journal of Comp. Geom. Appl., 4:179-228, 1994.
28. E.C. Sherbrooke, N.M. Patrikalakis, and E. Brisson. Computation of the Medial Axis Transform of 3D Polyhedra. In Solid Modeling, pages 187-199. ACM, 1995.
29. M. Teichmann and S. Teller. Polygonal Approximation of Voronoi Diagrams of a Set of Triangles in Three Dimensions. Tech Rep 766, Lab ofComp. Sci., MIT, 1997.
30. J. Vleugels and M. Overmars. Approximating Generalized Voronoi Diagrams in Any Dimension. Technical Report UU- CS-1995-14, Dept. ofComp. Sci., Utrecht University, 1995.
31. J. Vleugels, V. Ferrucci, M. Overmars, and A. Rao. Hunting Voronoi Vertices. Comp. Geom. Theory Appl., 6:329-354, 1996.
32. G.M. Voronoi. Nouvelles Applications des ParamOtres Continus gt la ThOorie des Formes Quadratiques. DeuxiOme MOmoire: Recherches sur les ParallOlloOdres Primitifs. J. Reine Angew. Math., 134:198-287, 1908.
33. M. Woo, J. Neider, and T. Davis. OpenGL Programming Guide, Second Edition. Addison Wesley, 1997.