Minimizing edge length to connect sparsely sampled unstructured point sets

• A perception-inspired minimization objective for connecting sparse samples with an orientable closed triangulation.
• Introduction of the boundary complex, an extension of the Minimum Spanning Tree into 3D.
• Topological operations to transform the boundary complex into a Closed Manifold Triangulation for extremely sparse point sets.

Most methods for interpolating unstructured point clouds handle densely sampled point sets quite well but get into trouble when the point set contains regions with much sparser sampling, a situation often encountered in practice. In this paper, we present a new method that provides a better interpolation of sparsely sampled features.We pose the surface construction problem as finding the triangle mesh which minimizes the sum of all triangles’ longest edge. Since searching for matching umbrellas among sparsely sampled points to yield a closed manifold shape is a difficult problem, we introduce suitable heuristics. Our algorithm first connects the points by triangles chosen in order of their longest edge and with the requirement that all edges must have at least two incident triangles. This yields a closed non-manifold shape which we call the Boundary Complex. Then we transform it into a manifold triangulation using topological operations. We show that in practice, runtime is linear to that of the Delaunay triangulation of the points. Source code is available online.

Figure optionsDownload high-quality image (172 K)Download as PowerPoint slide