Consensus meshing

Consider an algorithm for generating a triangle mesh interpolating a fixed set of 3D point samples, where the generated triangle set varies depending on some underlying parameters. In this paper we treat such an algorithm as a means of sampling the space of possible interpolant meshes, and then define a more robust algorithm based on drawing multiple such samples from this process and averaging them. As mesh connectivity graphs cannot be trivially averaged, we compute triangle statistics and then attempt to find a set of compatible triangles which maximize agreement between the sample meshes while also forming a manifold mesh. Essentially, each sample mesh “votes” for triangles, and hence we call our result a consensus mesh. Finding the optimal consensus mesh is combinatorially intractable, so we present an efficient greedy algorithm. We apply this strategy to two mesh generation processes—ball pivoting and localized tangent-space Delaunay triangulations. We then demonstrate that consensus meshing enables a generic decomposition of the meshing problem which supports trivial parallelization.

We used a 3D-model-from-photographs web service to scan a telephone (a, top), then discarded the mesh and generated a consensus meshing using the Ball Pivoting Algorithm (BPA). Due to variable point sampling density, the BPA meshes (a–c, increasing ball radius) exhibit both holes and (insets) undesirable topological changes. The consensus mesh (d) extracted from 100 sample BPA meshes still contains some small holes, but is of higher quality than that achievable with BPA alone.Figure optionsDownload high-quality image (269 K)Download as PowerPoint slideHighlights
► A meta-algorithm that can improve on the results of an existing meshing algorithm.
► Applications to Ball-Pivoting and local Delaunay meshing.
► Generic decomposition of meshing to support parallelization.