A Fast and Simple Surface Reconstruction Algorithm

摘要

We present an algorithm to reconstruct a surface from a dense sample. Given n sample points, it runs in O(n log n) time, which is optimal in the pointer machine model. The only existing O(n log n)- time algorithm due to Punke and Ramos uses some sophisticated data structures for the key task of extracting a locally uniform subsample. Our algorithm is based on a variant of the standard octree, and it is much simpler. We built a prototype, which runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the samples points absent from the subsample via edge flips. The subsample extraction step is very fast and effective. In our experiments with some non-uniform samples, our prototype gives a 51% to 68% speedup from using Cocone alone. Even for locally uniform samples, our prototype is usually much faster.