Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU

Ian Fischer, Craig Gotsman
Computer Science Department, Harvard University
Journal of Graphics, GPU, & Game Tools, Volume 11, Number 4 / 2006, p.39-60


   title={Fast approximation of high-order Voronoi diagrams and distance transforms on the GPU},

   author={Fischer, I. and Gotsman, C.},

   journal={Journal of Graphics, GPU, & Game Tools},






   publisher={AK Peters}


Download Download (PDF)   View View   Source Source   



We present a graphics hardware implementation of the tangent-plane algorithm for computing the kth-order Voronoi diagram of a set of point sites in image space. Correct and efficient implementation of this algorithm using graphics hardware is possible only with the use of an appropriate shader program on the GPU. This is achieved by rendering in k passes the parallel projection of the top k levels of an arrangement of planes tangent to the paraboloid z=x^2+y^2. Each level of the arrangement corresponds to the so-called kth-nearest point diagram, which is interesting in its own right. Composition of the images of the k top levels results in the kth-order Voronoi diagram. The diagram facilitates efficient computation of the k nearest neighbors of an arbitrary query point. We describe our implementation of the algorithm in OpenGL and Cg, and several optimizations. We also show how to efficiently compute the distance transform of the given sites using the GPU, based on the first-order Voronoi diagram.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: