Abstract
Numerical instability, rather than algorithmic logic, is often the primary cause of failure in surface reconstruction. This paper identifies that shifting from floating-point calculations to combinatorial logic during the mesh-extraction phase allows for the creation of reconstruction tools that are both faster and significantly more robust against precision errors and "slivers."
Introduction
In computer graphics and computational geometry, surface reconstruction transforms a point cloud into a smooth, continuous triangular mesh. Most state-of-the-art algorithms utilize the 3D Delaunay Triangulation as a starting point. However, a significant gap exists between theoretical beauty and practical implementation. Standard floating-point arithmetic often leads to "robustness issues," causing software to crash, enter infinite loops, or produce meshes with gaping holes. These problems are particularly acute when dealing with "slivers"—extremely flat tetrahedra that occur naturally in Delaunay triangulations and destabilize numerical calculations like surface normals.
Methodology
The authors analyze a three-step framework common to algorithms like Crust and Cocone: filtering triangles, pruning bare edges, and walking the surface. To ensure robustness, the paper introduces two key improvements:
- Exact Predicates via Filters: Using the CGAL library, the initial Delaunay triangulation employs "floating-point filters." This technique calculates an error bound; if the floating-point result is uncertain, the algorithm switches to exact arithmetic.
- Combinatorial Traversal: The core contribution is a redesigned
SurfaceNeighborfunction. Instead of using unstable numerical calculations (e.g., dot products of surface normals) to find the next triangle, the algorithm exploits the combinatorial structure of the triangulation. It "walks" through the tetrahedra incident to an edge until it identifies the next candidate triangle.
Key Insights
The authors advocate for the "Numerical Minimalism" Principle: the only step requiring numerical decisions is the construction of the Delaunay triangulation itself. Subsequent steps—filtering, pruning, and walking—should be purely combinatorial.
Slivers are the primary enemy of numerical approaches. Because these tetrahedra are nearly flat, their normals are mathematically unstable. A combinatorial approach bypasses this by focusing on connectivity rather than geometry. Furthermore, the authors debunk the myth that robustness implies slowness, showing that their combinatorial walk is highly efficient and the overhead for exact arithmetic is minimal.
Results and Discussion
The paper demonstrates that numerical "Walk" implementations frequently produce meshes with holes due to precision errors in sliver tetrahedra. In contrast, the combinatorial approach produces clean, manifold surfaces.
By utilizing CGAL’s filtered predicates, the authors eliminated infinite loops and crashes. The combinatorial SurfaceNeighbor function is also faster than its numerical counterpart, as it replaces expensive trigonometric calculations with simple pointer-following within the triangulation data structure.
Limitations and Future Work
While the approach addresses numerical robustness, it does not focus on "topological robustness" for extremely noisy point clouds. Future work could extend these combinatorial guarantees to non-manifold structures or surfaces with high genus. The authors suggest their design principle of avoiding numerical decisions should be applied more broadly to other geometric algorithms.
Summary updated