Shortest Path to Boundary for Self-Intersecting Meshes

Anka He Chen, He Chen 0006, Elie Diaz, Cem YukselACM Trans. Graphics 2023 · DOI

TL;DR

This paper introduces a novel method for precisely calculating the shortest path from an internal point to the boundary of a 3D mesh, even when the mesh is self-intersecting. This is crucial for robustly handling collisions in simulations where objects can deform and overlap, a common problem that existing methods struggle with.

What Problem Does This Paper Address?

In computer graphics and simulations, self-intersecting meshes are a frequent occurrence, arising from modeling limitations, animation, or physics simulations themselves. These self-intersections pose a significant challenge for collision detection and response. Traditional methods often assume or require intersection-free meshes, or they employ computationally expensive techniques that can fail under complex deformations. Existing approaches for handling self-intersections are often approximate, can introduce inaccuracies, or fail to provide a general solution. This paper tackles the problem of finding an exact and efficient shortest path to the boundary for points within a self-intersecting mesh, which is a fundamental step towards robust collision resolution in such scenarios.

Methods

The core of the paper is a formal definition of a "valid path" and the "shortest path to boundary" for self-intersecting meshes. The authors leverage the insight that the shortest path, when projected back to an "undeformed pose" (a hypothetical intersection-free state), must be a straight line segment.

Their algorithm works by:

  • Defining a Valid Path: A path is valid if it's the image of a path fully contained within the undeformed mesh.
  • Shortest Path Theorem: The shortest valid path from an internal point p to the boundary is the shortest line segment from p to a boundary point s that forms a valid path.
  • Efficient Testing: Instead of checking all boundary points, they propose testing only one candidate point per boundary face – specifically, the Euclidean closest point on that face to p.
  • Tetrahedral Ray Traversal: For 3D tetrahedral meshes, they employ a robust tetrahedral traversal algorithm to check if a line segment is a valid path. This traversal is designed to handle numerical inaccuracies and potential infinite loops, which are critical for correctness in their application.
  • Feasible Region Culling: An optimization technique that quickly eliminates candidate boundary points that cannot possibly be the closest, further speeding up the search.

Datasets

Not discussed in the paper. The authors use various simulated scenarios and models (e.g., squishy balls, beams, noodles, octopi) to demonstrate their method's effectiveness.

Key Insights and Ideas

  • The "Undeformed Pose" Trick: By considering the hypothetical intersection-free state of the mesh, the problem of finding a complex geodesic path in the deformed mesh is simplified to finding a straight line segment in the undeformed pose.
  • Shortest Path is a Line Segment: This is a crucial simplification that allows for efficient checking of candidate paths.
  • Robust Tetrahedral Traversal is Key: The success hinges on a reliable way to trace paths through the volumetric mesh, especially when dealing with self-intersections and potential numerical issues.
  • Feasible Region Culling for Speed: Geometric pruning significantly accelerates the search for the closest boundary point.

Key Results

The paper demonstrates that their method can effectively handle complex self-collision scenarios that cause existing methods to fail or produce unstable results.

  • Robustness: The method successfully resolves numerous deep self-intersections and rest-in-contact conditions in simulations involving deformable objects.
  • Efficiency: While introducing a computational overhead, it's described as "relatively minor" and can be significantly improved with optimizations like feasible region culling (achieving 10-30x speedup in some cases).
  • Integration: The method can be integrated with fast physics simulation techniques like XPBD, which do not guarantee collision resolution, thereby enhancing their robustness.
  • Qualitative Examples: Figures showcase simulations of squishy balls, twisted beams, nested knots, and large-scale scenes (e.g., 600 octopi) with complex self-collisions being resolved.

Limitations and Future Work

  • Volumetric Meshes Only: The current method is designed for tetrahedral meshes in 3D and triangular meshes in 2D. It doesn't handle codimensional objects like cloth or strands.
  • No Guarantee for All Inversions: While they handle some inverted elements, the method may struggle with all types, especially if inverted elements are on the boundary and cause self-intersections.
  • Non-Euclidean Spaces: The method relies on Euclidean metrics and cannot directly handle geodesic paths on surfaces in 3D.
  • DCD Limitations: When used with Discrete Collision Detection (DCD), deep penetrations can still lead to issues if the time steps are too large, though this can be mitigated by combining DCD with Continuous Collision Detection (CCD).
  • Future Work: The authors suggest GPU acceleration for collision detection and shortest path querying to further improve performance. They also note that the method's robustness makes it suitable for large-scale simulations with many objects.

Summary updated

BibTeX
@article{chen2023shortest,
  author = {Anka He Chen and He Chen and Elie Diaz and Cem Yuksel},
  title = {{Shortest Path to Boundary for Self-Intersecting Meshes}},
  journal = {ACM Trans. Graphics},
  year = {2023},
  doi = {10.1145/3592136},
}
Figure