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

Abstract

We present an implementation of the tangent-plane algorithm for computing the kth-order Voronoi diagram of a set of 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 its 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.