Interactive 3D distance field computation using linear factorization

Avneesh Sud, Naga Govindaraju, Russell Gayle, Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill
In I3D ’06: Proceedings of the 2006 symposium on Interactive 3D graphics and games (2006), pp. 117-124.


   title={Interactive 3D distance field computation using linear factorization},

   author={Sud, A. andGovindaraju, N. and Gayle, R. and Manocha, D.},

   booktitle={Proceedings of the 2006 symposium on Interactive 3D graphics and games},






Download Download (PDF)   View View   Source Source   



We present an interactive algorithm to compute discretized 3D Euclidean distance fields. Given a set of piecewise linear geometric primitives, our algorithm computes the distance field for each slice of a uniform spatial grid. We express the non-linear distance function of each primitive as a dot product of linear factors. The linear terms are efficiently computed using texture mapping hardware. We also improve the performance by using culling techniques that reduce the number of distance function evaluations using bounds on Voronoi regions of the primitives. Our algorithm involves no preprocessing and is able to handle complex deforming models at interactive rates. We have implemented our algorithm on a PC with NVIDIA GeForce 7800 GPU and applied it to models composed of thousands of triangles. We demonstrate its application to medial axis approximation and proximity computations between rigid and deformable models. In practice, our algorithm is more accurate and almost one order of magnitude faster as compared to previous distance computation algorithms that use graphics hardware.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: