Scalable point cloud meshing for image-based large-scale 3D modeling

Jiali Han, Shuhan ShenVis. Comput. Ind. Biomed. Art 2019 · DOI

TL;DR

This paper introduces a scalable point cloud meshing method for large-scale 3D scene reconstruction from images. It addresses the memory and time limitations of existing global methods by partitioning large point clouds into manageable, overlapping chunks, processing them in parallel, and then merging the results. This approach achieves comparable accuracy and completeness to global methods while significantly improving efficiency.

What Problem Does This Paper Address?

Reconstructing detailed 3D models of large-scale environments, such as entire cities, from images is a crucial task for applications like virtual reality and urban planning. A key step in this process is generating a "watertight" mesh from the noisy point clouds produced by multi-view stereo (MVS) algorithms. While methods like global Delaunay-based optimization can produce high-quality meshes, they struggle with the sheer volume of data in large scenes, leading to prohibitive memory and computation time requirements. Existing attempts to address this often involve partitioning the data, but these can lead to redundant computations or incomplete reconstructions. This paper aims to bridge this gap by proposing a scalable meshing approach that efficiently handles massive point clouds without sacrificing quality.

Methods

The proposed method breaks down the meshing process into three main stages:

  1. Region Partitioning: Instead of processing the entire point cloud at once, the scene is divided into smaller, overlapping chunks. This is achieved by creating a regular grid on the x-y plane and grouping points within these grids. The key innovation here is the overlapping boundary strategy, which ensures that adjacent chunks share data. This partitioning is done iteratively until each chunk's point count is below a defined maximum ($N_{max}$), making it manageable for a single computer node. This differs from some prior methods that might use a strict voxel grid, potentially leading to more redundant calculations.
  2. Local Surface Reconstruction: For each chunk, a Delaunay-based optimization algorithm is applied. This algorithm, inspired by existing work, uses point visibility and surface quality to define an energy function. This function is then minimized using a minimum s-t cut algorithm to extract a local surface. This step is performed in parallel across all chunks.
  3. Surface Merging: After local meshing, the overlapping boundaries are used to stitch the individual chunk meshes together. This involves extracting consistent triangles from both internal and boundary regions. Inconsistencies at the boundaries are resolved by carefully selecting triangles that span internal and boundary grids, and then processing repeated triangles that appear in multiple chunks. Finally, a hole-filling algorithm (using the VCG library) and Laplacian smoothing are applied to produce a complete and smooth final mesh.

Datasets

The authors evaluated their method on three large-scale, real-world datasets:

  • Temple: Ancient Chinese buildings and forests.
  • City1: City buildings, squares, and roads.
  • City2: Houses and streets.

These datasets were generated using off-the-shelf Structure-from-Motion (SfM) and Multi-View Stereo (MVS) algorithms from aerial photography. The paper does not introduce new benchmarks but uses these existing large-scale datasets to demonstrate the scalability and effectiveness of their approach.

Key Insights and Ideas

  • Scalability through Parallelism and Overlap: The core idea of partitioning into overlapping chunks and processing them in parallel is a highly effective strategy for tackling massive datasets. The overlap is crucial for seamless merging and avoiding artifacts at chunk boundaries.
  • Balancing Memory and Completeness: The parameter $N_{max}$ (maximum points per chunk) allows for a direct trade-off between memory usage and reconstruction completeness. Smaller $N_{max}$ values reduce memory but can slightly compromise completeness due to more frequent hole-filling operations.
  • Efficiency of Local Delaunay: Applying the Delaunay-based optimization locally on smaller chunks, rather than globally on the entire dataset, dramatically reduces computation time and memory footprint.
  • Strategic Hole Filling: The method's hole-filling strategy, which prioritizes patches farther from chunk boundaries and uses patches instead of individual triangles, is key to efficiently resolving inconsistencies introduced by local processing.

Key Results

  • Scalability: The method successfully processed city-scale scenes with hundreds of millions of points and thousands of images, demonstrating its ability to handle large datasets.
  • Accuracy and Completeness: Qualitative comparisons show that the proposed method achieves results comparable to the state-of-the-art global Delaunay-based method, outperforming other methods like GDMR and FSSR in retaining details and completeness.
  • Efficiency: The paper reports significant improvements in memory usage and time consumption compared to the global method. For instance, on the Temple dataset, their method achieved a peak memory usage of 5 GB per process compared to 16 GB for the global method, and a total processing time of 40 minutes versus 50 minutes for the global method (though the global method's time is noted as sequential).
  • Parameter Sensitivity: Experiments showed that while decreasing $N_{max}$ (increasing partitions) reduces memory consumption and local processing time, it increases the time for surface merging (specifically hole filling). The authors suggest choosing $N_{max}$ based on available memory.

Limitations and Future Work

  • Hole Filling Parallelization: The authors acknowledge that the hole-filling step is currently performed sequentially. They propose parallelizing this step as a key area for future work to further improve running speed and efficiency.
  • Theoretical Guarantee: While experimental results show good watertightness, the authors note that they cannot theoretically guarantee a hole-free final mesh, similar to global optimization methods.
  • Noise Handling: The paper mentions that isolated outliers can be incorporated into the final surface, though they suggest a visibility-based noise removal technique as a potential solution.

Summary updated

BibTeX
@article{han2019scalable,
  author = {Jiali Han and Shuhan Shen},
  title = {{Scalable point cloud meshing for image-based large-scale 3D modeling}},
  journal = {Vis. Comput. Ind. Biomed. Art},
  year = {2019},
  doi = {10.1186/s42492-019-0020-y},
}
Figure