Detecting undersampling in surface reconstruction

ABSTRACT

Current surface reconstruction algorithms perform satisfactorily on we ll-sampled, smooth surfaces without boundaries. However, these algorithms face difficulty with undersampling. Cases of undersampling are prevalent in real data since often they sample a part of the boundary of an object, or are derived from a surface with high curvature or nonsmoothness. In this paper we present an algorithm to detect the boundaries where dense sampling stops and undersampling begins. This information can be used to reconstruct surfaces with boundaries, and also to localize small and sharp features where usually undersampling happens. We report the effectiveness of the algorithm with a number of experimental results. Theoretically, we justify the algorithm with some mild assumptions that are valid for most practical data.

REFERENCES

• 1: Udo Adamy , Joachim Giesen , Matthias John, New techniques for topologically correct surface reconstruction, Proceedings of the conference on Visualization '00, p.373-380, October 2000, Salt Lake City, Utah, United States
• 2: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom., 22, (1999), 481-504.
• 3: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 4: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 5: N. Amenta, S. Choi and R. K. Kolluri. The power crust, unions of balls, and the medial axis transform. Manuscript, 2000.
• 6: Dominique Attali, r-regular shape reconstruction from unorganized points, Proceedings of the thirteenth annual symposium on Computational geometry, p.248-253, June 04-06, 1997, Nice, France [doi>10.1145/262839.262980]
• 7: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 8: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 9: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 10: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 11: Tamal K. Dey , Edgar A. Ramos , Kurt Mehlhorn, Curve reconstruction: connecting dots with good reason, Computational Geometry: Theory and Applications, v.15 n.4, p.229-244, April 2000 [doi>10.1016/S0925-7721(99)00051-6]
• 12: T. K. Dey, J. Giesen, N. Leekha and R. Wenger. Detecting boundaries for surface reconstruction using co-cones. Intl. J. Comput. Graphics & CAD/CAM, (2001), to appear.
• 13: Herbert Edelsbrunner, Shape Reconstruction with Delaunay Complex, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.119-132, April 20-24, 1998
• 14: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 15: H. Edelsbrunner and N. Shah. Triangulating topological spaces. Intl. J. Comput. Geom. Appl., 7, (1997), 365-378.
• 16: T. Gutzmer and A. Iske. Detection of discontinuities in scattered data approximation. Numerical Algorithms, 16, (1997), 155-170.
• 17: Hisamoto Hiyoshi , Kokichi Sugihara, Voronoi-based interpolation with higher continuity, Proceedings of the sixteenth annual symposium on Computational geometry, p.242-250, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336210]
• 18: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 19: D. Zorin and P. Schroder. Subdivision for modeling and animation. SIGGRAPH 99 Course Notes.
• 20: http://www.cis.ohiostate.edu/ctamaldey/cocone.html
• 21: http://www.cgal.org

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Theory