Smooth surface reconstruction via natural neighbour interpolation of distance functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Smooth surface reconstruction via natural neighbour interpolation of distance functions

Full text

Pdf (1.00 MB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 223 - 232

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Jean-Daniel Boissonnat	INRIA, BP93, 06902 Sophia Antipolis, France
Frédéric Cazals	INRIA, BP93, 06902 Sophia Antipolis, France

Sponsors

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): 121, Citation Count: 45

Additional Information:

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/336154.336208 What is a DOI?

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. Discrete Comput. Geom., 22(4):481-504, 1999.
	2	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]
	3	D. Attali, r-regular shape reconstruction from unorganized points, Computational Geometry: Theory and Applications, v.10 n.4, p.239-247, July 1, 1998 [doi>10.1016/S0925-7721(98)00013-3]
	4	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]
	5	Fausto Bernardini , Chandrajit L. Bajaj , Jindong Chen , Daniel R. Schikore, A triangulation-based object reconstruction method, Proceedings of the thirteenth annual symposium on Computational geometry, p.481-484, June 04-06, 1997, Nice, France [doi>10.1145/262839.263098]
	6	F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using alpha-shapes. In Proc. 9th Canad. Conf. Comput. Geom., pages 193-198, 1997.
	7	Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
	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	J.-D. Boissonnat and F. Cazals. Natural coordinates on a surface. Rapport de recherche, INRIA, 2000. to appear.
	10	J. W. Bruce and P. J. Giblin. Curves and Singularities (2nd edition). Cambridge University Press, New York, 1992.
	11	L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
	12	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]
	13	Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276896]
	14	Tamal K. Dey , Kurt Mehlhorn , Edgar A. Ramos, Curve reconstruction: connecting dots with good reason, Proceedings of the fifteenth annual symposium on Computational geometry, p.197-206, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304972]
	15	H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Inform. Theory, IT-29:551-559, 1983.
	16	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]
	17	A. Fomenko and T. Kunii. Topological Modeling for Visualization. Springer, 1997.
	18	Joachim Giesen, Curve reconstruction, the traveling salesman problem and Menger's theorem on length, Proceedings of the fifteenth annual symposium on Computational geometry, p.207-216, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304973]
	19	Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
	20	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
	21	D. Levin. Mesh-independent surface interpolation. In 4th International Conference on Curves and Surfaces, page 46, 1999. Saint-Malo, France.
	22	Mahmoud Melkemi, A-shapes of a finite point set, Proceedings of the thirteenth annual symposium on Computational geometry, p.367-369, June 04-06, 1997, Nice, France [doi>10.1145/262839.263005]
	23	S. Owen. An implementation of natural neighbor interpolation in three dimensions. Master's thesis, 1992.
	24	J. A. Sethian. Level Set Methods. Cambridge University Press, 1996.
	25	R. Sibson. A vector identity for the Dirichlet tesselation. Math. Proc. Camb. Phil. Soc., 87:151-155, 1980.
	26	R. Sibson. A brief description of natural neighbour interpolation. In V. Barnet, editor, Interpreting Multivariate Data, pages 21-36. John Wiley & Sons, Chichester, 1981.
	27	D. F. Watson. Contouring: A Guide to the Analysis and Display of Spatial Data. Pergamon, 1992.
	28	H.-K. Zhao, S. Osher, B. Merriman, and M. Kang. Implicit, nonparametric shape reconstruction from unorganized points using a variational level set method. Cam report 98-7, UCLA, http://www.math.ucla.edu/applied/cam/index.html, 1998.

CITED BY 46

	Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States
	Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
	Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States
	Sylvain Petitjean, A survey of methods for recovering quadrics in triangle meshes, ACM Computing Surveys (CSUR), v.34 n.2, p.211-262, June 2002
	Tamal K. Dey , Joachim Giesen , James Hudson, Delaunay based shape reconstruction from large data, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
	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
	Pierre Alliez , Mathieu Desbrun, Progressive compression for lossless transmission of triangle meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.195-202, August 2001
	Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Raphaëlle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Mark Foskey , Ming C. Lin , Dinesh Manocha, Efficient computation of a simplified medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
	Anders Adamson , Marc Alexa, Approximating and intersecting surfaces from points, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Niloy J. Mitra , An Nguyen, Estimating surface normals in noisy point cloud data, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Tamal K. Dey , Samrat Goswami, Tight cocone: a water-tight surface reconstructor, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	André Lieutier, Any open bounded subset of Rⁿ has the same homotopy type than its medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Helmut Pottmann , Stefan Leopoldseder, A concept for parametric surface fitting which avoids the parametrization problem, Computer Aided Geometric Design, v.20 n.6, p.343-362, September 2003
	Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Sarah F. Frisken , Ronald N. Perry, Efficient estimation of 3D Euclidean distance fields from 2D range images, Proceedings of the 2002 IEEE symposium on Volume visualization and graphics, October 28-29, 2002, Boston, Massachusetts
	Jean-Marie Morvan , Boris Thibert, Smooth surface and triangular mesh: comparison of the area, the normals and the unfolding, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Tamal K. Dey , Joachim Giesen , Samrat Goswami , Wulue Zhao, Shape dimension and approximation from samples, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.772-780, January 06-08, 2002, San Francisco, California
	X. M. Pardo , V. Leborán , R. Dosil, Integrating prior shape models into level-set approaches, Pattern Recognition Letters, v.25 n.6, p.631-639, 19 April 2004
	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
	Ross Bencina, The metasurface: applying natural neighbour interpolation to two-to-many mapping, Proceedings of the 2005 conference on New interfaces for musical expression, May 26-28, 2005, Vancouver, Canada
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos, Manifold reconstruction from point samples, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005
	J. M. Morvan , B. Thibert, On the approximation of a smooth surface with a triangulated mesh, Computational Geometry: Theory and Applications, v.23 n.3, p.337-352, November 2002
	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
	Nico Kruithof , Gert Vegter, Approximation by skin surfaces, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Yuandong Yang , Oliver Brock , Robert N. Moll, Efficient and robust computation of an approximated medial axis, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Computational Geometry: Theory and Applications, v.35 n.1, p.124-141, August 2006
	Craig Gotsman , Kanela Kaligosi , Kurt Mehlhorn , Dimitrios Michail , Evangelia Pyrga, Cycle bases of graphs and sampled manifolds, Computer Aided Geometric Design, v.24 n.8-9, p.464-480, November, 2007
	Ravikrishna Kolluri, Provably good moving least squares, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008
	Ashraf Hussein, A hybrid system for three-dimensional objects reconstruction from point-clouds based on ball pivoting algorithm and radial basis functions, Proceedings of the 9th WSEAS International Conference on Computers, p.1-9, July 14-16, 2005, Athens, Greece
	Ravikrishna Kolluri, Provably good moving least squares, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	F. Chazal , A. Lieutier, Stability and homotopy of a subset of the medial axis, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	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
	Philip Azariadis , Nickolas Sapidis, Product design using point-cloud surfaces: A recursive subdivision technique for point parameterization, Computers in Industry, v.58 n.8-9, p.832-843, December, 2007
	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 C. Jalba , Jos B. T. M. Roerdink, Efficient Surface Reconstruction using Generalized Coulomb Potentials, IEEE Transactions on Visualization and Computer Graphics, v.13 n.6, p.1512-1519, November 2007
	Gaël Guennebaud , Markus Gross, Algebraic point set surfaces, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	Marc Alexa , Anders Adamson, Interpolatory point set surfaces—convexity and Hermite data, ACM Transactions on Graphics (TOG), v.28 n.2, p.1-10, April 2009
	Geetika Tewari , Craig Gotsman , Steven J. Gortler, Meshing genus-1 point clouds using discrete one-forms, Computers and Graphics, v.30 n.6, p.917-926, December, 2006
	Andrei C. Jalba , Jos B. T. M. Roerdink, Efficient surface reconstruction from noisy data using regularized membrane potentials, IEEE Transactions on Image Processing, v.18 n.5, p.1119-1134, May 2009
	Sung W. Park , Lars Linsen , Oliver Kreylos , John D. Owens , Bernd Hamann, Discrete Sibson Interpolation, IEEE Transactions on Visualization and Computer Graphics, v.12 n.2, p.243-253, March 2006
	Chuan-Chu Kuo , Hong-Tzong Yau, A New Combinatorial Approach to Surface Reconstruction with Sharp Features, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.73-82, January 2006