high performance computing on graphics processing units: hgpu.org

We present an optimized algorithm to compute 3D distance fields using the bilinear interpolation capabilities of GPUs while preserving the features of the model. For a geometric model, our algorithm computes the Euclidean distance fields on each 2D slice of a 3D grid by applying linear decomposition to the non-linear distance function of each primitive and evaluating it using texture mapping hardware. We compute the bounds of the Voronoi region of each primitive on a 2D slice to reduce rasterization cost of the distance functions. Further more, culling techniques are incorporated to remove primitives that do not contribute to the distance field of a given slice. Our method is able to preserve the features of the model such as sharp edges and corners by detecting them and storing the associated information explicitly during the distance field computation. The experiment demonstrates that the algorithm is accurate and can compute 3D distance fields of complex models consisting of thousands of triangles while preserving the features efficiently.