Provable surface reconstruction from noisy samples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Provable surface reconstruction from noisy samples

Full text

Pdf (1.83 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twentieth annual symposium on Computational geometry table of contents

Brooklyn, New York, USA

SESSION: Session 9 table of contents

Pages: 330 - 339

Year of Publication: 2004

ISBN:1-58113-885-7

Authors

Tamal K. Dey	The Ohio State University
Samrat Goswami	The Ohio State University

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 71, Citation Count: 26

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/997817.997867 What is a DOI?

ABSTRACT

We present an algorithm for surface reconstruction in presence of noise. We show that, under a reasonable noise model, the algorithm has theoretical guarantees. Actual performance of the algorithm is illustrated by our experimental results.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom. 22 (1999), 481--504.
	2	N. Amenta, S. Choi, T. K. Dey and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. & Applications 12 (2002), 125--141.
	3	N. Amenta, S. Choi and R. K. Kolluri. The power crust, union of balls, and the medial axis transform. Comput. Geom.: Theory Applications 19 (2001), 127--153.
	4	Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999 [doi>10.1109/2945.817351]
	5	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]
	6	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]
	7	Th. Bröcker and K. J.anich. Introduction to differential topology. Cambridge University Press, New York, 1982.
	8	H.-L. Cheng, T. K. Dey, H. Edelsbrunner and J. Sullivan. Dynamic skin triangulation. Discrete Comput. Geom. 25 (2001), 525--568.
	9	Siu-Wing Cheng , Stefan Funke , Mordecai Golin , Piyush Kumar , Sheung-Hung Poon , Edgar Ramos, Curve reconstruction from noisy samples, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777838]
	10	Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378682]
	11	T. K. Dey and S. Goswami. Tight cocone: A watertight surface reconstructor. J. Computing Informat. Sci. Engin. 13 (2003), 302--307.
	12	T. K. Dey and S. Goswami. Smoothing noisy point cloud data with Delaunay preprocessing and MLS. Tech. Rep. OSU-CISRC-3/04-TR17, Dept. of CSE, The Ohio State University, 2004.
	13	Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378682]
	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	Herbert Edelsbrunner , Nimish R. Shah, Triangulating topological spaces, Proceedings of the tenth annual symposium on Computational geometry, p.285-292, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178010]
	16	Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.71-78, July 1992
	17	R. K. Kolluri, J. R. Shewchuk and J. F. O'Brien. Watertight spectral surface reconstruction. Manuscript, 2003.
	18	David Levin, The approximation power of moving least-squares, Mathematics of Computation, v.67 n.224, p.1517-1531, Oct. 1998 [doi>10.1090/S0025-5718-98-00974-0]
	19	J. Milnor. Morse theory. Annals of Mathematics Studies, Princeton University Press, Princeton, New Jersey, 1963.
	20	N. J. Mitra, A. Nguyen and L. Guibas. Estimating surface normals in noisy point cloud data. Internat. J. Comput. Geom. Appl., to appear.
	21	http://www.cis.ohio-state.edu/~tamaldey/cocone.html
	22	http://www.cgal.org

CITED BY 26

	Ravikrishna Kolluri , Jonathan Richard Shewchuk , James F. O'Brien, Spectral surface reconstruction from noisy point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
	Ravikrishna Kolluri, Provably good moving least squares, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	David Cohen-Steiner , Herbert Edelsbrunner , John Harer, Stability of persistence diagrams, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Siu-Wing Cheng , Stefan Funke , Mordecai Golin , Piyush Kumar , Sheung-Hung Poon , Edgar Ramos, Curve reconstruction from noisy samples, Computational Geometry: Theory and Applications, v.31 n.1-2, p.63-100, May 2005
	Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, An integrating approach to meshing scattered point data, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.61-69, June 13-15, 2005, Cambridge, Massachusetts
	Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Siu-Wing Cheng , Yajun Wang , Zhuangzhi Wu, Provable dimension detection using principal component analysis, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Oudot, Learning smooth objects by probing, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Jean-Daniel Boissonnat , Steve Oudot, Provably good sampling and meshing of surfaces, Graphical Models, v.67 n.5, p.405-451, September 2005
	Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, A composite approach to meshing scattered data, Graphical Models, v.68 n.3, p.255-267, May 2006
	Ravikrishna Kolluri, Provably good moving least squares, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008
	Frédéric Chazal , David Cohen-Steiner , André Lieutier, A sampling theory for compact sets in Euclidean space, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Frédéric Chazal , André Lieutier, Topology guaranteeing manifold reconstruction using distance function to noisy data, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Ryan Schmidt , Cindy Grimm , Brian Wyvill, Interactive decal compositing with discrete exponential maps, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Oudot, Learning smooth shapes by probing, Computational Geometry: Theory and Applications, v.37 n.1, p.38-58, May, 2007
	Ravikrishna Kolluri, Provably good moving least squares, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
	Ran Gal , Ariel Shamir , Tal Hassner , Mark Pauly , Daniel Cohen-Or, Surface reconstruction using local shape priors, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	Frédéric Chazal , André Lieutier, Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees, Computational Geometry: Theory and Applications, v.40 n.2, p.156-170, July, 2008
	Tamal K. Dey , Jian Sun, An adaptive MLS surface for reconstruction with guarantees, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
	Chandrajit Bajaj , Samrat Goswami, Multi-component heart reconstruction from volumetric imaging, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Joachim Giesen , Matthias John, The flow complex: A data structure for geometric modeling, Computational Geometry: Theory and Applications, v.39 n.3, p.178-190, April, 2008
	Jochen Süßmuth , Günther Greiner, Ridge based curve and surface reconstruction, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	Mark Pauly , Niloy J. Mitra , Joachim Giesen , Markus Gross , Leonidas J. Guibas, Example-based 3D scan completion, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
	M. Samozino , M. Alexa , P. Alliez , M. Yvinec, Reconstruction with Voronoi centered radial basis functions, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
	Andrei Sharf , Thomas Lewiner , Gil Shklarski , Sivan Toledo , Daniel Cohen-Or, Interactive topology-aware surface reconstruction, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007