“A new Voronoi-based surface reconstruction algorithm” by Amenta, Bern and Kamvysselis

We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR3. The algorithm is the first for this problem with provable guarantees. Given a “good sample” from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases. The definition of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples. The output mesh interpolates, rather than approximates, the input points. Our algorithm is based on the three-dimensional Voronoi diagram. Given a good program for this fundamental subroutine, the algorithm is quite easy to implement.

1. Nina Amenta, Marshall Bern and David Eppstein. The Crust and the/3-Skeleton: Combinatorial Curve Reconstruction. To appear in Graphical Models and Image Processing.
2. Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. To appear in 14th ACM Symposium on Computation Geometry, June 1998.
3. D. Attali. r-Regular Shape Reconstruction from Unorganized Points. In 13th ACM Symposium on Computational Geometry, pages 248-253, June 1997.
4. C. Bajaj, F. Bernardini, and G. Xu. Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans. SIGGRAPH’95 Proceedings, pages 109-118, July 1995.
5. F. Bernardini and C. Bajaj. Sampling and reconstructing manifolds using o~-shapes, In 9th Canadian Conference on Computational Geometry, pages 193-198, August 1997.
6. J-D. Boissonnat. Geometric structures for three-dimensional shape reconstruction, ACM Transactions on Graphics 3: 266- 286, 1984.
7. K. Clarkson, K. Mehlhorn and R. Seidel. Four results on randomized incremental constructions. Computational Geometry: Theory and Applications, pages 185-121, 1993.
8. B. Curless and M. Levoy. A volumetric method for building complex models from range images. In SIGGRAPH ’96 Proceedings, pages 303-312, July 1996.
9. H. Edelsbrunner, D.G. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane, IEEE Transactions on Information Theory 29:551-559, (1983).
10. H. Edelsbrunner and E. P. Mt~cke. Three-dimensional Alpha Shapes. ACM Transactions on Graphics 13:43-72, 1994.
11. L.H. de Figueiredo and J. de Miranda Gomes. Computational morphology of curves. Visual Computer 11:105-112, 1995.
12. A. Witkin and P. Heckbert. Using particles to sample and control implicit surfaces, In SIGGRAPH’94 Proceedings, pages 269-277, July 1994.
13. H. Hoppe. Surface Reconstruction from Unorganized Points. Ph.D. Thesis, Computer Science and Engineering, University of Washington, 1994.
14. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface Reconstruction from Unorganized Points. In SIGGRAPH’ 92 Proceedings, pages 71-78, July 1992.
15. M. Melkemi, ,A-shapes and their derivatives, In 13th ACM Symposium on Computational Geometry, pages 367-369, June 1997
16. G. Taubin and J. Rossignac. Geometric compression through topological surgery. Research Report RC20340, IBM, 1996.