An interactive tour of Voronoi diagrams on the GPU
ShaderX6/Charles River Media/Thomson publishing.
Frank NIELSEN
BibTex
@incollection{n-voronoigpu-2008,
author="Frank Nielsen",
title="An interactive tour of Voronoi diagrams on the GPU",
booktitle="ShaderX$^6$: Advanced Rendering Techniques",
year= 2008,
publisher = "Charles River Media (\url{http://www.charlesriver.com/})"
}
The Voronoi diagram is a well-studied fundamental structure in computational geometry that has found countless
applications in computer graphics such as collision detection, path planning, meshing and surface reconstruction, just to name a few. Voronoi diagrams has also lead to a rich variety of GPU techniques to discretely compute them.
In this chapter, we present a set of shaders that emphasizes graphically key geometric properties of Voronoi diagrams.
Namely, we describe how to compute:
- The Voronoi diagrams by the distance field transform: (2D rendering with isolines and bisectors),
- The Voronoi diagrams by minimization diagrams (2D & 3D rendering with the up-lifting transform),
- The Delaunay triangulations as dual of Voronoi diagrams (bisectors & geodesics, orthogonality).
We mention discretization errors incurred by GPU per-pixel fragment shading, common programming pitfalls and ways to circumvent them to improve stability.
Finally, we show how these techniques can be extended to handle various useful generalizations of Voronoi diagrams:
- k-order diagrams,
- Power & affine diagrams,
- Moebius & Appolonius diagrams,
- Hyperbolic & spherical diagrams,
- Csiszar f-divergences Voronoi diagrams,
- Bregman divergences Voronoi diagrams.
This set of shaders yields in a single application an interactive GPU tool to visualize on the fly dynamically these structures.
GPU Programs with Cg codes
Eight programs are available on the accompanying DVD. See videos below for session captures.
Color figures
(All images are in TIFF format (Apple Quicktime(R) players display them) and are screenshots of the GPU applications)
- Figure 1: Rendering styles for ordinary Voronoi diagrams
IMG a
IMG b
IMG c
IMG d
- Figure 2: Voronoi and orthogonally dual Delaunay triangulation
IMG
- Figure 3: Curved and affine Voronoi diagrams
IMG a
IMG b
IMG c
IMG d
- Figure 4: Spherical and hyperbolic Voronoi diagrams
IMG a
IMG b
IMG c
- Figure 5: Csiszar f-divergence Voronoi diagrams
IMG a
IMG b
IMG c
IMG d
- Figure 6: Bregman primal/dual Voronoi diagrams
IMG a
IMG b
- Figure 7: Voronoi diagrams interpreted as lower envelopes (minimization diagrams)
IMG
Videos
- Ordinary Voronoi diagrams (Euclidean geometry):
- Voronoi diagrams on the sphere (Elliptical geometry):
Voronoi diagram on the sphere
- Voronoi diagrams in hyperbolic geometry;
- Csiszar f-divergence Voronoi diagrams:
- Bregman divergence Voronoi diagrams:
- Voronoi diagrams as minimization diagrams (lower envelopes):
References
- Frank Nielsen: Visual Computing: Geometry, Graphics, and Vision. Charles River Media, ISBN 1-58450-427-7, 2005.
- Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec: Curved Voronoi Diagrams. In Effective Computational Geometry for Curves and Surfaces. Springer-Verlag 2006.
- Guodong Rong, Tiow-Seng Tan: Jump flooding in GPU with applications to Voronoi diagram and distance transform. ACM SI3D, 109-116.
- Avneesh Sud, Naga K. Govindaraju, Russell Gayle, Dinesh Manocha: Interactive 3D distance field computation using linear factorization. ACM SI3D, 117-124.
- Frank Nielsen, Jean-Daniel Boissonnat and Richard Nock: Bregman Voronoi Diagrams: Properties, Algorithms, and Applications. INRIA TR 6154, 2007.
Last updated, August 2007.