DiFi: Fast 3D Distance Field Computation Using Graphics Hardware

Avneesh Sud, Miguel A. Otaduy, Dinesh ManochaComputer Graphics Forum 2004 · DOI

TL;DR

This paper introduces DiFi, a novel algorithm that leverages graphics hardware to dramatically accelerate the computation of 3D distance fields. By intelligently culling and clamping the rendering of distance functions, DiFi achieves an order of magnitude speedup over previous methods, making complex distance field computations feasible in near real-time.

What Problem Does This Paper Address?

Computing accurate 3D distance fields is crucial for a wide range of applications in computer graphics, geometric modeling, and robotics, including shape representation, model simplification, collision detection, and path planning. A distance field at any point in space stores the shortest distance to the nearest object's surface. However, calculating these fields for complex 3D models on high-resolution grids is computationally intensive. Existing methods, even those utilizing graphics hardware for rasterization, can be slow due to the sheer number of primitives and the cost of rendering their distance functions for every slice of the 3D grid. This bottleneck limits their applicability to dynamic environments or interactive applications.

Methods

DiFi tackles this challenge by significantly reducing the amount of work required for each 3D grid slice. The core innovations lie in:

  • Site Culling: The algorithm intelligently identifies and discards "sites" (primitives like points, edges, or triangles) whose Voronoi regions are unlikely to intersect the current 2D slice of the 3D grid. This is achieved through a two-pass approach along the Z-axis, classifying sites as "intersecting," "approaching," or "receding" based on their spatial bounds. Occlusion queries on the graphics hardware are used to efficiently determine visibility and refine these classifications.
  • Conservative Sampling: To mitigate potential sampling errors from occlusion queries, DiFi employs a conservative sampling strategy. This involves slightly expanding the effective region of receding sites to ensure they are considered, even if their sampled intersection with the slice is missed.
  • Distance Function Clamping: For the remaining "intersecting" sites, DiFi reduces the rasterization cost by only computing their distance functions within the estimated bounds of their Voronoi regions on the current slice. This is further optimized for manifold surfaces using the CSC algorithm.
  • Spatial Coherence: The algorithm exploits the spatial coherence between adjacent slices in the 3D grid, allowing for incremental updates and further speedups.

Datasets

Not discussed in the paper. The paper focuses on the algorithm's performance on various complex polygonal models, including scanned and CAD models, some of which are non-manifold. Examples include the "Rotor," "Triceratops," "Hugo," "Head," "Shell," "Cassini," and "Dragon" models, with polygon counts ranging from thousands to tens of thousands.

Key Insights and Ideas

  • Voronoi Region Bounds for Culling: The key insight is that by understanding the spatial extent (Voronoi region bounds) of each primitive along the sweep direction (e.g., Z-axis), we can predict which primitives will contribute to a given slice and discard the rest.
  • Graphics Hardware for Visibility: Leveraging occlusion queries on modern GPUs is an efficient way to determine if a primitive's distance function is visible on a given slice, forming the backbone of the culling process.
  • Conservative Approach for Robustness: The conservative sampling strategy is crucial for ensuring accuracy despite the inherent limitations of discrete sampling and hardware queries. It guarantees that no relevant contributions are missed.
  • Clamping to Voronoi Regions: Restricting distance function computation to the estimated Voronoi region on a slice dramatically reduces rasterization load.
  • Complementary Techniques: DiFi's culling and clamping techniques can be combined with specialized algorithms like CSC for manifold surfaces, leading to even greater performance gains.

Key Results

DiFi demonstrates significant performance improvements:

  • Speedup: The algorithm achieves an order of magnitude (or more) speedup compared to previous methods like HAVOC and CSC, and their combinations. For manifold models, speedups of over two orders of magnitude were observed. For non-manifold models, DiFi is 4-20 times faster than HAVOC.
  • Applicability: DiFi works with generic models (non-orientable, non-manifold) without requiring connectivity information.
  • Applications: The paper showcases successful applications in computing simplified medial axes of complex polyhedral models and enabling interactive path planning in dynamic environments.
  • Real-time Performance: For models with a few thousand polygons, DiFi can compute distance fields at almost interactive rates.

Limitations and Future Work

  • Grid Resolution: The accuracy of the distance field is limited by the uniform grid resolution, which is constrained by current graphics hardware capabilities (e.g., 4K x 4K pixel resolution).
  • Fill-Rate Bound: Performance is still bounded by the rasterization cost and fill-rate of the graphics processor.
  • PCI Bus Bottleneck: Reading back large distance fields from the GPU to the CPU can be slow, especially over the PCI bus.
  • Uniform Grids: The algorithm is best suited for uniform grids and may not offer speedups for adaptive distance fields.

Future work suggested by the authors includes:

  • Temporal Coherence: Exploiting temporal coherence for dynamic or deformable models to further improve performance.
  • New Applications: Exploring the algorithm's use in other areas like dynamic simulation, morphing, and proximity computations.

Summary updated

BibTeX
@article{sud2004difi,
  author = {Avneesh Sud and Miguel A. Otaduy and Dinesh Manocha},
  title = {{DiFi: Fast 3D Distance Field Computation Using Graphics Hardware}},
  journal = {Computer Graphics Forum},
  year = {2004},
  doi = {10.1111/j.1467-8659.2004.00787.x},
}
Figure