IBPA: Real-time Free-form Manifold Mesh Reconstruction via Incremental Ball Pivoting with Integrated Hole Detection

Both Remotely Operated underwater Vehicles (ROVs) and Autonomous Underwater Vehicles (AUVs) are frequently deployed to acquire geometric bathymetric data, but traditional methods like Digital Terrain Models (DTMs) are limited in expressiveness because they represent surfaces as height fields, allowing only one elevation value per (x, y) coordinate and thus cannot capture overhangs or vertical structures. This paper proposes the Incremental Ball Pivoting Algorithm (IBPA), a novel method that incrementally constructs an orientable, manifold mesh from streaming point cloud data without imposing assumptions regarding point cloud overlap or spatial distribution.

The gist

The IBPA method is a real-time, incremental surface reconstruction technique that produces orientable and manifold meshes while simultaneously identifying missing data in regions where it should have been acquired.

How it works

The IBPA adapts the original Ball Pivoting Algorithm (BPA) into an incremental formulation to handle streaming point cloud data. To manage the dynamic nature of the input, two primary challenges are addressed: first, making the spatial data structure dynamic; second, checking each newly added point against existing triangles to ensure it does not violate the empty ball configuration. When a new vertex lies inside any existing triangle's circumsphere, that triangle is removed to preserve surface validity without deleting vertices.

Manifold and Orientability Enforcement

The method rigorously enforces topological properties throughout the incremental expansion process. The goal is to produce a mesh that satisfies both edge-manifold and vertex-manifold properties. To ensure vertex-manifoldness, the algorithm distinguishes between two types of non-manifold vertices: 1-disk non-manifold vertices and 0-disk non-manifold vertices. The paper details algorithms (Alg. 2 and Alg. 3) to detect these configurations; for instance, a 1-disk non-manifold vertex is detected by checking if a subset of adjacent facets forms a single connected disk around the vertex with exactly one boundary edge, which are then removed to maintain surface plausibility.

Real-time Hole Detection and Boundary Classification

A key feature is the integrated hole detection mechanism that identifies incomplete mesh regions without resorting to 3D-to-2D projection. The method follows a detect-first-define-later strategy, meaning it first detects missing information and then determines the appropriate sensor poses to acquire it. Boundaries are reconstructed from boundary-edges, and the longest boundary is designated as the main boundary, while all remaining boundaries are treated as holes (e.g., lakes). This allows for actionable feedback to ROV/AUV operators about areas lacking sufficient coverage before mission completion.

Robustness and Performance Enhancements

The IBPA pipeline includes several enhancements for practical application. It incorporates a normal estimation module where the normal vector is estimated by pointing from the vertex toward the associated robot’s pose center, allowing it to function even when input point clouds lack orientation information. To manage computational load, it limits reconstruction complexity by defining a maximum number of orphan vertices per leaf node in the octree, and if exceeded, a subset of these vertices is randomly removed. Furthermore, the method maintains geometric fidelity by not fabricating points or surfaces for visual enhancement and demonstrates robustness to outliers in the point cloud.

Experimental Validation

The performance is validated through offline experiments using datasets like Heinkel, Nyhavna, and Figaro point clouds collected by an AUV equipped with a Multibeam Echosounder (MBES). Results show that the method achieves fast reconstruction times—for example, reconstructing an 886-second mission in just 22 seconds for the Heinkel dataset. The experiments confirm the method's capability to detect holes whose boundaries exceed a user-defined tolerance length and successfully identifies regions exhibiting translational shifts caused by incorrect georeferencing as outliers. Online experiments in controlled and outdoor settings further demonstrate its suitability for real-time stream reconstruction, confirming that it can successfully detect and fill missing information when the hole boundary exceeds the specified threshold.

Conclusion

The IBPA method successfully extends the original BPA to operate incrementally, ensuring an orientable manifold mesh through dynamic octree expansion, empty ball configuration enforcement, and non-manifold vertex removal. By enforcing orientation consistency among neighboring facets and limiting computational complexity via orphan vertex management, it provides a robust framework for real-time 3D surface reconstruction in underwater robotics. The method is open-sourced with full ROS integration for easy deployment. Future work focuses on improving efficiency in boundary-edge indexing and developing methods to check for single edge-connected components without a full scan.

How it works

1. The algorithm adapts the original Ball Pivoting Algorithm (BPA) into an incremental formulation to handle streaming point cloud data.

Here are the specific improvements to AI systems derived from the Incremental Ball Pivoting Algorithm (IBPA) described in this paper, along with what those improved systems can achieve:

1. The ability to perform high-fidelity, real-time 3D surface reconstruction of complex underwater environments.

2. Accurate identification and visualization of incomplete or missing data regions in real-time during data acquisition (e.g., by ROVs or AUVs).

3. Reconstruction of surfaces with complex topologies, including overhangs, vertical walls, and non-planar structures, which traditional Digital Terrain Models (DTMs) cannot capture.

4. Maintenance of geometric integrity through the enforcement of mesh properties: being an orientable manifold mesh (ensuring no self-intersections or topological defects like Möbius strips).

5. Robustness to noise and outliers in sensor data, as the algorithm can effectively ignore incorrect readings while maintaining surface continuity.

This improved AI system (IBPA) can achieve the following specific capabilities:

1. A semi-autonomous underwater mapping system that continuously builds a precise 3D model of the seabed or submerged objects from streaming point cloud data (e.g., Multibeam Echosounder or visual SLAM).

2. Real-time operational awareness for autonomous underwater vehicles (AUVs) and Remotely Operated Vehicles (ROVs), allowing them to see where their current survey coverage is incomplete, enabling operators to make informed decisions about data collection paths instantly.

3. Creation of detailed geometric models suitable for advanced downstream applications, such as:

4. High-quality input for photogrammetry, Neural Radiance Fields (NeRF), or Gaussian Splatting methods, leading to clearer visual reconstructions of underwater scenes with reduced light scattering artifacts.

5. Automated quality control during reconstruction, where the system actively detects and flags areas lacking sufficient data coverage based on a user-defined tolerance length threshold (e.g., detecting holes larger than 3 meters).

6. Generation of topologically sound meshes that accurately represent the physical geometry of objects, ensuring that the resulting models are mathematically valid for topological analysis and surface-based computations.

Both Remotely Operated underwater Vehicles (ROVs) and Autonomous Underwater Vehicles (AUVs) are frequently deployed to acquire geometric bathymetric data. However, it is often discovered post-survey that the acquired data coverage is incomplete. Given the high operational cost associated with underwater deployments, it is essential to incrementally visualize surface coverage in real-time to support informed decision-making by both the operators of ROVs and the AUVs during data collection. In addition, traditional incremental surface reconstruction methods, such as Digital Terrain Models (DTMs), are inherently limited in expressiveness: they represent surfaces as height fields, allows only one elevation value per (x, y) coordinate and thus cannot capture overhangs or vertical structures. To overcome these limitations, we adapt the original Ball Pivoting Algorithm (BPA) into an incremental, real-time, and free-form surface reconstruction method, referred to as Incremental BPA (IBPA). Our method incrementally constructs an orientable, manifold mesh from streaming point cloud data without imposing assumptions regarding point cloud overlap or spatial distribution. Furthermore, we introduce a hole detection mechanism that identifies and highlights incomplete mesh regions. Compared to existing approaches, our method supports more complex surface topologies without prior structural assumptions. The source code of our reference implementation is available: https://github.com/Mauhing/Incremental-BPA