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.

PUBLICATIONS
	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 (Acrobat)
	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 Proc ACM SIGGRAPH, 1999
RELATED WORK
	Proximity Computation Fast Proximity Computation among Deformable Models Using Discrete Voronoi Diagrams Fast and Simple Geometric Proximity Queries Using Graphics Hardware Medial Axis Computation SMA: An Approximate, Simplified Medial Axis Motion Planning C-Plan: Real-Time Constraint-Based Motion Planning V-Plan: A Voronoi-Based Hybrid Motion Planner Interactive Motion Planning Using Hardware-Accelerated Computation of Generalized Voronoi Diagrams Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling UNC GAMMA Group
DOWNLOAD SOFTWARE
GET HAVOC3D!	HAVOC3D is now available for downloading, please visit our download page.
CONTRIBUTORS
	Project Members: Avneesh Sud Naga Govindaraju Russell Gayle Miguel Otaduy Kenneth E Hoff III Andrew Zaferakis Ming Lin Dinesh Manocha Sponsors: DARPA RDECOM Army Research Office Department of Energy ASCI Program Intel National Science Foundation Office of Naval Research

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.