TL;DR
This paper introduces a novel GPU-accelerated algorithm for computing surface distance maps on triangulated 3D models. By leveraging texture mapping hardware and a clever parameterization of mesh surfaces, the authors achieve significant speedups (5-10x) over previous volumetric methods, enabling interactive proximity queries for complex, deforming objects.
What Problem Does This Paper Address?
Accurately and efficiently determining the distance between objects is crucial for many applications in computer graphics, robotics, and computational geometry, including collision detection, animation, and shape analysis. Traditional methods often rely on volumetric representations (like voxel grids) to compute distance fields. However, these approaches suffer from high storage overhead and computational costs, making them too slow for real-time applications, especially with complex or deforming models. Furthermore, volumetric methods can have limited accuracy as grid vertices may not precisely lie on the object's surface. This paper addresses the need for a faster, more accurate, and surface-centric approach to computing distance information for 3D models.
Methods
The core of the paper's contribution lies in its innovative use of GPU hardware for surface distance map computation. Here's a breakdown of their key techniques:
- Surface Parameterization: The algorithm first computes a piecewise planar parameterization of the 3D mesh. This essentially "unwraps" each triangle of the mesh onto a 2D plane, creating a texture atlas. An affine transformation is defined for each triangle to map its 3D vertices to corresponding 2D coordinates within this atlas.
- GPU-Accelerated Distance Computation: Instead of discretizing space into a volumetric grid, the algorithm leverages the GPU's texture mapping capabilities. For each "site" (a primitive of the other object), its distance function is rasterized onto the 2D texture atlas. The GPU's bilinear interpolation hardware is used to efficiently compute the distance from any point on the 2D texture (which corresponds to a point on the 3D mesh surface) to the closest site.
- Stencil Test for Clipping: To ensure that distance computations are only performed within the relevant regions of the mesh, the GPU's stencil test is employed. This effectively clips the distance functions to the projected areas of the triangles in the 2D texture atlas.
- Hierarchical Culling and Caching: To further optimize performance, the authors introduce hierarchical culling using Axis-Aligned Bounding Boxes (AABBs) to quickly discard triangle-site pairs that are too far apart. They also employ a stencil caching mechanism to reduce redundant stencil operations.
- Affine Transformations for Deformations: The paper explicitly handles non-rigid deformations by recomputing the affine transformations for deforming triangles and updating the distance maps accordingly.
Datasets
The paper evaluates its algorithm on several benchmarks, including:
- Hugo Model: A 17.2K polygon model used to demonstrate surface distance maps on a box and vice-versa.
- Deforming Alphabets ("EG"): A scene with two deforming alphabets (3.7K polygons total) used to showcase collision and separation distance computation.
- Deforming Bunnies: A scenario with two deforming bunnies (2K polygons each) to demonstrate dynamic simulation and proximity queries.
The authors do not introduce new datasets but rather use these existing models and scenarios to highlight the performance and capabilities of their algorithm.
Key Insights and Ideas
- Shifting from Volumetric to Surface-Centric: The most significant insight is the move away from volumetric grids towards a surface-based approach. By directly computing distances on the mesh surface using texture mapping, they bypass the inherent limitations of voxelization.
- Leveraging GPU Texture Mapping for Distance: The clever application of texture mapping hardware for distance interpolation is a key innovation. This allows for efficient, hardware-accelerated computation of distance values across the surface.
- Affine Transformations as a Bridge: The use of affine transformations to map 3D mesh triangles to 2D texture space is crucial. This provides a consistent framework for applying GPU rasterization and interpolation to surface geometry.
- Interactive Performance for Deformable Models: The ability to achieve interactive frame rates for complex, deforming objects is a major breakthrough, opening doors for real-time applications that were previously infeasible.
Key Results
- Speedup: The algorithm achieves a 5-10x speedup in proximity computation compared to prior volumetric distance field algorithms.
- Accuracy: The method can compute high-resolution distance maps (e.g., 1K x 1K at 32-bit floating-point precision) with tight error bounds, offering higher accuracy than volumetric methods.
- Interactive Rates: The algorithm can compute high-resolution distance fields in a few hundred milliseconds, enabling interactive rates for complex models.
- Deformable Model Handling: The algorithm effectively handles deforming models, with proximity queries taking around 100ms for scenes with thousands of polygons.
- Storage Efficiency: Surface distance maps require O(n²) storage, significantly less than the O(n³) required for volumetric approaches.
Limitations and Future Work
- Limitations:
- Fixed Connectivity: The current algorithm is limited to deforming triangles with fixed connectivity. Handling objects with changing topologies would require updating the planar parameterization and spatial hierarchies.
- Packing Efficiency: The current packing of 2D domain triangles into the texture atlas may not be optimal.
- Pairwise Queries: The algorithm currently only performs proximity computations between a pair of objects, not N-body computations.
- Future Work:
- Spatial and Temporal Coherence: Further improve performance by exploiting spatial and temporal coherence between successive frames.
- Changing Topologies: Extend the algorithm to handle objects with changing topologies.
- Self-Proximity Queries: Apply the proximity computation algorithm to perform self-proximity queries, including self-collisions or self-penetrations in cloth simulation.
- Ray Tracing Acceleration: Utilize surface distance maps to accelerate ray tracing of dynamic scenes.
- Conservative Distance Bounds: Combine the algorithm with conservative distance bounds for object-space precision in proximity queries.
Summary updated