Abstract
Given a finite point set in ℝ3, the surface reconstruction problem asks for a surface that passes through many but not necessarily all points. We describe an unambiguous definition of such a surface in geometric and topological terms,and sketch a fast algorithm for constructing it. Our solution overcomes past limitations to special point distributions and heuristic design decisions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.-D. Boissonnat. Geometric structures for three-dimensional shape representation.ACM Trans. Graphics 3 (1984), 266-286.
C. Bregler and S. M. Omohundro. Nonlinear manifold learning for visual speech recognition. In ¡°Proc. 5th Internat. Conf. Comput. Vision, 1995¡±, 494-499.
K. L. Clarkson, K. Mehlhorn and R. Seidel. Four results on randomized incremental constructions. In “Proc. 9th Ann. Sympos. Theoret. Aspects Comput. Sci., 1992”, 463-474, Lecture Notes in Comput. Sci. 577, Springer-Verlag.
H. Edelsbrunner. An acyclicity theorem for cell complexes in d dimensions.Combinatorica 10 (1990), 251-260.
H. Edelsbrunner and E. P. Mücke. Simulation of Simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graphics 9 (1990), 66-104.
H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graphics 13 (1994), 43-72.
H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. In ¡°Proc. 8th Ann. Sympos. Comput. Geom., 1992¡±,43-52.
M. Facello. Geometric Techniques for Molecular Shape Analysis. Ph. D. Thesis, Dept. Comput. Sci., Univ. Illinois, Urbana, 1996.
H. Fuchs, Z. Kedem, and S.P.Uselton. Optimal surface reconstruction from planar contours. Comm. ACM 20 (1977), 693-702.
P. J. Giblin. Graphs, Surfaces, and Homology. Second edition, Chapman and Hall, London, 1981.
H. Hoppe, T. de Rose, T. Duchamp, J. McDonald, and W. St¡§utzle.Surface reconstruction from unorganized points. Computer Graphics, Proc.siggraph 1992, 71-78.404 H. Edelsbrunner
D. W. Matula and R. R. Sokal. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane.Geographic Analysis 12 (1980), 205-222.
D. Meyers, S. Skinner and K. Sloan. Surfaces from contours. ACM Trans.Graphics 11 (1992), 228-258.
J. Milnor. Morse Theory. Annals Math. Studies, Princeton Univ. Press,1963.
R. C. Veltkamp. Closed Object Boundaries from Scattered Points. Springer-Verlag, Berlin, 1994.
A. Wallace. Differential Topology. First Steps. Benjamin, New York, 1968.
N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22 (1999), 481-504.
N. Amenta, S. Choi and R. Kolluri. The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl. 19 (2001), 127-153.
F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva and G. Taubin.The ball-pivoting algorithm for surface reconstruction. IEEE Trans. Visual.Comput. Graphics 5(1999), 349-359.
F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using α-shapes. In “Proc. 9th Canadian Conf. Comput. Geom., 1997”±, 193-198.
J.-D. Boissonnat and F. Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In “Proc. 16th Ann. Sympos.Comput. Geom. 2000” 223-232.
B. Curless and M. Levoy. A volumetric method for building complex models from range images. Comput. Graphics, Proc. siggraph 1996, 303-312.
H. Edelsbrunner, D. Letscher and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., to appear.
R. Forman. Combinatorial differential topology and geometry. In New Perspective in Geometric Combinatorics, MSRI Publication 8, 1999, 177-206.
S. Funke and E. A. Ramos. Smooth surface reconstruction in near-linear time. In ¡°Proc. 13th Ann. SIAM-ACM Sympos. Discrete Algorithms, 2002¡±,781-790.
G. Meenakshisundaram. Theory and Practice of Sampling and Reconstruction for Manifolds with Boundaries. Ph. D. Thesis, Dept. Comput. Sci., Univ.North Carolina, Chapel Hill, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Edelsbrunner, H. (2003). Surface Reconstruction by Wrapping Finite Sets in Space. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds) Discrete and Computational Geometry. Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55566-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-55566-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-62442-1
Online ISBN: 978-3-642-55566-4
eBook Packages: Springer Book Archive