Fast Distance Field and Voronoi Diagram Computation
using Graphics Hardware

Given a set of geometric primitives (sites) and a distance function, the Voronoi diagram is a partition of space into cells such that point inside one cell are closer to one site. The distance field is a scalar field which gives the distance to the closest site at any point in space. Distance fields and Voronoi diagrams are closely related and one can be efficiently computed from the other. Graphics hardware (GPUs) can be used to efficiently compute a discrete distance field and approximate Voronoi diagrams. We present the research done on fast distance field and Voronoi diagram computation using GPUs performed at GAMMA group at UNC-Chapel Hill.

Surface Distance Maps

Avneesh Sud, Naga Govindaraju, Russell Gayle, Erik Andersen, Dinesh Manocha

Proc. Graphics Interface, 2007

Fast Proximity Computation Among Deformable Models Using Discrete Voronoi Diagrams

Avneesh Sud, Naga Govindaraju, Russell Gayle, Ilknur Kabul, Dinesh Manocha

ACM Transaction on Graphics (to appear), (Proc SIGGRAPH 2006) 2006

Interactive 3D Distance Field Computation using Linear Factorization

Avneesh Sud, Naga Govindaraju, Russell Gayle, Dinesh Manocha

Proc. ACM Symposium on Interactive 3D Graphics and Games (I3D), 2006

Interactive Computation of Discrete Generalized Voronoi Diagrams using Range Culling

Avneesh Sud, Naga Govindaraju, Dinesh Manocha

Proc. 2nd Internaltional Symposium on Voronoi Diagrams in Science and Engineering, 2005


DiFi: Fast 3D Distance Field Computation Using Graphics Hardware

Avneesh Sud, Miguel Otaduy, Dinesh Manocha

Computer Graphics Forum 23 (3), 2004 (Proc. Eurographics, 2004)

Fast Computation of GVD using Graphics Hardware (HAVOC)

Kenneth E Hoff III, Andrew Zaferakis, Ming Lin, Dinesh Manocha


Copyright 2006. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
last updated: 03/11/2006