Fast computation of generallized voronoi diagrams using graphics hardware

摘要

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.