Consensus Meshing

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