Automatic construction of watertight manifold triangle meshes from scanned point clouds using matched umbrella facets

ABSTRACT

Generation of watertight manifold triangle meshes from scanned point clouds has emerged as a key task in computer-aided design and inspection. An effective algorithm is presented in this paper, targeting the automatic creation of such triangle meshes from unorganized, scanned data points. The algorithm builds on the initial version of the Umbrella Facet Matching (UFM) algorithm developed by the authors. The mesh generation process starts with Delaunay triangulation of the given point cloud to determine the Delaunay triangle set at each data point. The algorithm then seeks to iteratively generate, in parallel, the local 2-dimensional manifold triangle mesh, resembling the shape of an open umbrella, at each data point from its Delaunay triangle set that fully overlaps with its neighboring umbrellas. Particularly, a four-level inheritance priority queuing mechanism is introduced to enhance the prioritization and ordering of the Delaunay triangles at each data point in order to facilitate the iterative establishment of the fully matched umbrella according to the most updated umbrella facet matching results. The presented method has been implemented and validated through a series of minimally post-processed scanned point cloud data sets from physical objects with complex geometry. Improved computational convergence has been observed, which promotes the construction of watertight manifold triangle meshes. The comparison results have demonstrated that the enhanced UFM algorithm outperforms the initial UFM algorithm and an industrial software tool in creating quality triangle meshes from actual scanned point clouds.

GRAPHICAL ABSTRACT

KEYWORDS:

• Watertight manifold mesh
• point cloud
• Delaunay triangles

Acknowledgement

This work was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).

ORCID

Ji Ma http://orcid.org/0000-0001-6536-2617

Jack Szu-Shen Chen http://orcid.org/0000-0002-1225-6340

Hsi-Yung Feng http://orcid.org/0000-0001-6189-6910

Lihui Wang http://orcid.org/0000-0001-8679-8049

Additional information

Funding

This work was supported by Natural Sciences and Engineering Research Council of Canada (NSERC).