Fast evaluation of smooth distance constraints on co-dimensional geometry

Abhishek Madan, David I. W. Levin

TL;DR

This paper introduces a novel method for computing smooth distance fields from diverse geometric data (points, edges, triangles), enabling robust and efficient collision detection in simulations. By combining a LogSumExp-based distance function with a modified Barnes-Hut acceleration, they achieve conservative, accurate, and fast evaluations, paving the way for direct simulation of complex, real-world scenarios like those involving lidar scans.

What Problem Does This Paper Address?

Accurate and efficient collision detection is crucial for realistic physics simulations. Traditional methods often struggle with "co-dimensional" geometry – data composed of mixed types like points, edges, and triangles, common in real-world scans (e.g., lidar). Existing distance field representations can be memory-intensive, require costly preprocessing, or lack smoothness, hindering their use in optimization-based simulations. Furthermore, exact distance fields are not smooth, which complicates their use in gradient-based optimization. This paper aims to bridge this gap by providing a single, smooth, and efficient distance function that can handle mixed geometry types and accurately represent complex shapes, even those with sparse or noisy data.

Methods

The core of the proposed method is a smooth minimum distance function based on the LogSumExp (LSE) function, often referred to as the Kreisselmeier-Steinhauser distance. This function naturally provides a smooth approximation of the minimum distance between a query point and a set of geometric primitives. To handle different geometry types (points, edges, triangles), the authors extend the LSE formulation.

Key innovations include:

  • Weight Functions: To mitigate "bulging" artifacts that arise when multiple primitives share the same closest point, they introduce carefully designed weight functions. These functions are derived from polynomial approximations based on point constraints and derivative constraints, ensuring smoothness and local influence.
  • Modified Barnes-Hut Acceleration: For efficient evaluation, especially with large datasets, they adapt the Barnes-Hut algorithm. Crucially, they modify the far-field approximation to place the expansion center on the closest point of a cluster's bounding box to the query primitive, rather than the center of mass. This ensures the conservative property (underestimation of true distance) is maintained, which is vital for collision detection.
  • Co-Dimensional Geometry Handling: The method is designed to work seamlessly with mixed geometry types by treating points, edges, and triangles as "simplices" and extending distance calculations and weight functions accordingly.

Datasets

The paper utilizes several datasets for evaluation and demonstration:

  • Thingi10K Dataset: A large dataset of 3D printing models used for performance benchmarking. The authors create point, edge, and triangle meshes from these models.
  • Stanford Bunny Mesh: Used for demonstrating the Barnes-Hut approximation and sphere tracing.
  • City Lidar Point Cloud: Used for demonstrating robustness with noisy, sparse data.
  • Terrain Point Cloud (from OpenTopography): Used in simulations.
  • Motorcycle and Deer Models: Used in example visualizations.

No new benchmarks were introduced, but the paper demonstrates the method's applicability to existing, challenging datasets.

Key Insights and Ideas

  • Smoothness is Key for Optimization: The paper strongly emphasizes that the C¹ differentiability of their smooth distance function is critical for its use in gradient-based optimization for physics simulation, unlike exact distance fields which are only C⁰.
  • Conservatism is Non-Negotiable for Collision Detection: The modified Barnes-Hut approach, specifically placing the expansion center on the closest point of a bounding box, is a crucial insight for maintaining the conservative property. This ensures that if the smooth distance is non-negative, the actual geometry is guaranteed to be separated, preventing interpenetration.
  • Unified Framework for Mixed Geometry: The ability to handle points, edges, and triangles within a single LSE framework, augmented by appropriate weights, is a significant step towards simulating complex, real-world scenes composed of diverse geometric representations.
  • Lidar Data Integration: The method's capacity to smooth and handle sparse, noisy point clouds directly addresses a major bottleneck in using raw lidar data for simulation, opening up new application possibilities.

Key Results

  • Efficiency: The modified Barnes-Hut acceleration provides significant speedups. For example, on the Thingi10K dataset, they observed up to a 30x speedup on points and 5x on edges and triangles when running on a GPU compared to CPU. Even on CPU, the Barnes-Hut approximation reduced computation time by an order of magnitude.
  • Accuracy: The method achieves low isosurface approximation error relative to the bounding box diagonal, even with significant Barnes-Hut approximation (e.g., less than 4% error for β=0.5). The error is logarithmic with respect to mesh size and improves with increasing a.
  • Robustness: The method successfully handles various geometry types and noisy data, enabling simulations of complex scenarios like rigid body collisions with lidar-acquired terrain and co-dimensional objects (e.g., spiky spheres, edge meshes).
  • Qualitative Demonstrations: The paper showcases compelling simulations, including a motorcycle jumping onto a lidar point cloud street, an octopus mesh sliding on point cloud terrain, and a spiky sphere falling into an edge mesh bowl, all without interpenetration.

Limitations and Future Work

  • Parameter Selection: While the method is effective, selecting optimal parameters (a, au, β) can require careful tuning, especially to avoid inf values and ensure accuracy. The authors suggest heuristics but acknowledge that a fully automated solution is needed.
  • Tight Contacts: The method might need augmentation for extremely tight contacts (e.g., a nut screwing into a bolt), as it tends to be overly conservative.
  • Weight Function Generalization: The current weight functions are primarily designed for data meshes. Generalizing them to work for query meshes, perhaps through a more theoretically grounded approach, is a promising future direction.
  • Hessian Computation: For applications requiring second-order derivatives (e.g., Newton iterations in optimization), computing and storing smooth distance Hessians is challenging due to their size and discontinuities. Approximating these Hessians using techniques like hierarchical matrices is suggested.
  • Deforming Meshes and Friction: Extending the method to handle deforming meshes and developing smooth friction computations are identified as future research avenues.
  • GPU Parallelization: While GPU performance is presented, further exploration of parallelization strategies (e.g., parallelizing traversals within per-query primitive evaluations) is suggested.

Summary updated

Abstract

We present a new method for computing a smooth minimum distance function based on the LogSumExp function for point clouds, edge meshes, triangle meshes, and combinations of all three. We derive blending weights and a modified Barnes-Hut acceleration approach that ensure our method approximates the true distance, and is conservative (points outside the zero isosurface are guaranteed to be outside the surface) and efficient to evaluate for all the above data types. This, in combination with its ability to smooth sparsely sampled and noisy data, like point clouds, shortens the gap between data acquisition and simulation, and thereby enables new applications such as direct, co-dimensional rigid body simulation using unprocessed lidar data.
BibTeX
@article{madan2022fast,
  author = {Abhishek Madan and David I. W. Levin},
  title = {{Fast evaluation of smooth distance constraints on co-dimensional geometry}},
  journal = {ACM Trans. Graphics},
  year = {2022},
  doi = {10.1145/3528223.3530093},
}
Figure