Smooth surface reconstruction via natural neighbour interpolation of distance functions. (English) Zbl 1016.68145

Summary: We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates nonuniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in \(\mathbb{R}^3\).


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)


Full Text: DOI


[1] Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discrete Comput. Geom., 22, 4, 481-504 (1999) · Zbl 0939.68138
[2] Amenta, N.; Bern, M.; Kamvysselis, M., A new Voronoi-based surface reconstruction algorithm, (Proc. SIGGRAPH’98. Proc. SIGGRAPH’98, Computer Graphics Proceedings, Annual Conference Series (1998)), 412-415
[3] Attali, D., \(r\)-regular shape reconstruction from unorganized points, Computational Geometry: Theory and Applications, 10, 239-247 (1998) · Zbl 0904.68172
[4] Bajaj, C.; Bernardini, F.; Xu, G., Automatic reconstruction of surface and scalar fields from 3d scans, Comput. Graph., 11, 109-118 (1995), Proc. SIGGRAPH’95
[5] Bernardini, F.; Bajaj, C.; Chen, J.; Schikore, D., Triangulation-based object reconstruction methods, (Proc. 13th Annual ACM Symp. Comput. Geom. (1997)), 481-484
[6] Bernardini, F.; Bajaj, C. L., Sampling and reconstructing manifolds using alpha-shapes, (Proc. 9th Canad. Conf. Comput. Geom. (1997)), 193-198
[7] Bernardini, F.; Mittleman, J.; Rushmeir, H.; Silva, C.; Taubin, G., The ball-pivoting algorithm for surface reconstruction, IEEE Transactions on Visualization and Computer Graphics, 5, 4, 349-359 (1999)
[8] (Bloomenthal, J., Introduction to Implicit Surfaces, Vol. 391 (1997), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA) · Zbl 0948.65014
[9] Boissonnat, J.-D., Geometric structures for three-dimensional shape representation, ACM Trans. Graph., 3, 4, 266-286 (1984)
[10] Boissonnat, J.-D.; Cazals, F., Natural neighbor coordinates of points on a surface, Computational Geometry: Theory and Applications, 19, 155-173 (2001) · Zbl 0988.65018
[11] Brown, J. L., Systems of coordinates associated with points scattered in the plane, Computer-Aided Design, 14, 547-559 (1997) · Zbl 0896.65002
[12] Bruce, J. W.; Giblin, P. J., Curves and Singularities (1992), Cambridge University Press: Cambridge University Press New York · Zbl 0770.53002
[13] Chew, L. P., Guaranteed-quality mesh generation for curved surfaces, (Proc. 9th Annual ACM Symp. Comput. Geom. (1993)), 274-280
[14] Curless, B.; Levoy, M., A volumetric method for building complex models from range images, (Proc. SIGGRAPH’96 (1996)), 303-312
[15] Devillers, O., Improved incremental randomized Delaunay triangulation, (Proc. 14th Annual ACM Symp. Comput. Geom. (1998)), 106-115
[16] Dey, T. K.; Mehlhorn, K.; Ramos, E. R., Curve reconstruction: Connecting dots with good reason, (Proc. 15th Annual ACM Symp. Comput. Geom. (1999)), 197-206 · Zbl 0955.68113
[17] Edelsbrunner, H.; Kirkpatrick, D. G.; Seidel, R., On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, IT-29, 551-559 (1983) · Zbl 0512.52001
[18] Edelsbrunner, H.; Mücke, E. P., Three-dimensional alpha shapes, ACM Trans. Graph., 13, 1, 43-72 (1994) · Zbl 0806.68107
[19] Fomenko, A.; Kunii, T., Topological Modeling for Visualization (1997), Springer: Springer Berlin · Zbl 1120.37300
[20] Giesen, J., Curve reconstruction, the traveling salesman problem and Menger’s theorem on length, (Proc. 15th Annual ACM Symp. Comput. Geom. (1999)), 207-216 · Zbl 0984.65012
[21] Gopi, M.; Krishnan, S.; Silva, C., Surface reconstruction based on lower dimensional localized Delaunay triangulation, (Proc. Eurographics 2000, Vol. 19 (2000)), C467-C478
[22] Hoppe, H.; DeRose, T.; Duchamp, T.; Halstead, M.; Jin, H.; McDonald, J.; Schweitzer, J.; Stuetzle, W., Piecewise smooth surface reconstruction, (Proc. SIGGRAPH’94 (1994)), 295-302
[23] Hoppe, H.; DeRose, T.; Duchamp, T.; McDonald, J.; Stuetzle, W., Surface reconstruction from unorganized points, Comput. Graphics, 26, 2, 71-78 (1992), Proc. SIGGRAPH’92
[24] Levin, D., Mesh-independent surface interpolation, (Proc. 4th International Conference on Curves and Surfaces, Saint-Malo, France (1999)), 46
[25] Melkemi, M., A-shapes and their derivatives, (Proc. 13th Annual ACM Symp. Comput. Geom. (1997)), 367-369
[26] Owen, S. J., An implementation of natural neighbor interpolation in three dimensions, Master’s Thesis (1992), Brigham Young University: Brigham Young University Provo, UT
[27] Piper, B., Properties of local coordinates based on Dirichlet tesselations, Computing, 8, 227-239 (1993) · Zbl 0852.68093
[28] Sethian, J. A., Level Set Methods (1996), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0859.76004
[29] Sherbrooke, E.; Patrikalakis, N.; Wolter, F.-E., Differential and topological properties of medial axis transforms, Graphical Models and Image Processing, 58, 6, 574-592 (1996)
[30] Sibson, R., A vector identity for the Dirichlet tesselation, Math. Proc. Cambridge Philos. Soc., 87, 151-155 (1980) · Zbl 0466.52010
[31] Sibson, R., A brief description of natural neighbour interpolation, (Barnet, V., Interpreting Multivariate Data (1981), Wiley: Wiley Chichester), 21-36
[32] Watson, D. F., Contouring: A Guide to the Analysis and Display of Spatial Data (1992), Pergamon: Pergamon Oxford
[33] Zhao, H.-K.; Osher, S.; Merriman, B.; Kang, M., Implicit, nonparametric shape reconstruction from unorganized points using a variational level set method (1998), Cam Report 98-7, UCLA: Cam Report 98-7, UCLA Los Angeles, CA, http://www.math.ucla.edu/applied/cam/index.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.