×

Reconstruction of implicit curves and surfaces via RBF interpolation. (English) Zbl 1372.65050

Summary: Representation of curves and surfaces is a basic topic in computer graphic and computer aided design. In this paper we focus on theoretical and practical issues in using radial basis functions (RBF) for reconstructing implicit curves and surfaces from point clouds. We study the conditioning of the problem and give some insight on how the problem parameters and the results have to be taken in order to achieve meaningful solutions and avoid artifacts. Moreover, a strategy for decreasing the conditioning of the problem is suggested and a general framework for preconditioning and solving the problem, even for large datasets, is also provided.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65D05 Numerical interpolation
65F08 Preconditioners for iterative methods
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

Matlab; PETSc; rbf_qr; PetRBF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balay, S.; Gropp, W.; McInnes, L. C.; Smith, B. F., PETSc, the Portable, Extensible Toolkit for Scientific Computation, 2-17 (1998), Argonne National Laboratory
[2] Berger, M.; Tagliasacchi, A.; Seversky, L.; Alliez, P.; Levine, J.; Sharf, A.; Silva, C., State of the art in surface reconstruction from point clouds, (EUROGRAPHICS Star Reports, vol. 1 (2014)), 161-185
[3] Boyer, E.; Petitjean, S., Curve and surface reconstruction from regular and non-regular point sets, (Proceedings, vol. 2. Proceedings, vol. 2, IEEE Conference on Computer Vision and Pattern Recognition, 2000 (2000), IEEE)
[4] Buhmann, M. D., Radial Basis Functions: Theory and Implementation, Cambridge Monographs on Applied and Computational Mathematics, vol. 12 (2003), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1004.65015
[5] Calakli, F.; Taubin, G., SSD: Smooth Signed Distance Surface Reconstruction, Computer Graphics Forum, vol. 30 (7) (2011), Blackwell Publishing Ltd
[6] Carr, J. C.; Fright, W. R.; Beatson, R. K., Surface interpolation with radial basis functions for medical imaging, IEEE Trans. Med. Imaging, 16, 1, 96-107 (1997)
[7] Carr, J. C.; Beatson, R. K.; Cherrie, J. B.; Mitchell, T. J.; Fright, W. R.; McCallum, B. C.; Evans, T. R., Reconstruction and representation of 3D objects with radial basis functions, (Proc. of the 28th Annual Conf. on Computer Graphics and Interactive Techniques (2001), ACM), 67-76
[8] Cavoretto, R.; De Rossi, A., A trivariate interpolation algorithm using a cube-partition searching procedure, SIAM J. Sci. Comput., 37, A1891-A1908 (2015) · Zbl 1327.65022
[9] Cavoretto, R.; De Rossi, A.; Perracchione, E., Efficient computation of partition of unity interpolants through a block-based searching technique, Comput. Math. Appl., 71, 12, 2568-2584 (2016) · Zbl 1443.65009
[10] Cavoretto, R.; De Rossi, A.; Perracchione, E.; Venturino, E., Robust approximation algorithms for the detection of attraction basins in dynamical systems, J. Sci. Comput., 68, 1, 395-415 (2016) · Zbl 1344.65118
[11] Cazals, F.; Giesen, J., Delaunay triangulation based surface reconstruction: ideas and algorithms, (Effective Computational Geometry for Curves and Surfaces (2006)), 231-276 · Zbl 1116.65022
[12] Cuomo, S.; Galletti, A.; Giunta, G.; Starace, A., Surface reconstruction from scattered point via RBF interpolation on GPU, (Federated Conference on Computer Science and Information Systems. Federated Conference on Computer Science and Information Systems, FedCSIS 2013 (2013)), 433-440
[13] Cuomo, S.; Galletti, A.; Giunta, G.; Marcellino, L., A novel triangle-based method for scattered data interpolation, Appl. Math. Sci., 8, 133-136, 6717-6724 (2014)
[14] Cuomo, S.; Galletti, A.; Giunta, G.; Marcellino, L., A Class of Piecewise Interpolating Functions Based on Barycentric Coordinates, Ricerche di Matematica (2014), Springer · Zbl 1303.41002
[15] Cuomo, S.; Galletti, A.; Giunta, G.; Marcellino, L., Piecewise Hermite Interpolation via Barycentric Coordinates: In Memory of Prof. Carlo Ciliberto, Ricerche di Matematica (2015), Springer · Zbl 1326.41003
[16] Deparis, S.; Forti, D.; Quarteroni, A., A rescaled localized radial basis function interpolation on non-cartesian and nonconforming grids, SIAM J. Sci. Comput., 36, A2745-A2762 (2014) · Zbl 1312.41006
[17] Fasshauer, G. F., Meshfree Approximation Methods with MATLAB (2007), World Scientific Publishing: World Scientific Publishing River Edge, NJ, USA · Zbl 1123.65001
[18] Fasshauer, G.; McCourt, M., Stable evaluation of Gaussian radial basis function interpolants, SIAM J. Sci. Comput., 34, A737-A762 (2012) · Zbl 1252.65028
[19] Fornberg, B.; Larsson, E.; Flyer, N., Stable computations with Gaussian radial basis functions, SIAM J. Sci. Comput., 33, 869-892 (2011) · Zbl 1227.65018
[20] Franke, R., Scattered data interpolation: tests of some methods, Math. Comput., 38, 157, 181-200 (1982) · Zbl 0476.65005
[21] Frisken, S. F.; Perry, R. N.; Rockwood, A. P.; Jones, T. R., Adaptively sampled distance fields: a general representation of shape for computer graphics, (Proc. of the 27th Annual Conf. on Computer Graphics and Interactive Techniques (2000), ACM Press/Addison-Wesley Publishing Co.), 249-254
[22] Heryudono, A.; Larsson, E.; Ramage, A.; von Sydow, L., Preconditioning for radial basis function partition of unity methods, J. Sci. Comput., 67, 3, 1089-1109 (2016) · Zbl 1342.65105
[24] Klein, J.; Zachmann, G., Point cloud surfaces using geometric proximity graphs, Comput. Graph., 28, 6, 839-850 (2004)
[25] Levoy, M.; Pulli, K.; Curless, B.; Rusinkiewicz, S.; Koller, D.; Pereira, L.; Ginzton, M.; Anderson, S.; Davis, J.; Ginsberg, J.; Shade, J.; Fulk, D., The digital Michelangelo project: 3d scanning of large statues, (Proc. of the 27th Annual Conf. on Computer Graphics and Interactive Techniques. Proc. of the 27th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH ’00 (2000), ACM Press/Addison-Wesley Publishing Co.), 131-144
[26] Liu, Shengjun; Wang, C. L., Quasi-interpolation for surface reconstruction from scattered data with radial basis function, Comput. Aided Geom. Des., 29, 435-447 (2012) · Zbl 1250.65026
[27] Macedo, I.; Gois, J. P.; Velho, L., Hermite interpolation of implicit surfaces with radial basis functions, (XXII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI) (2009)), 1-8
[28] Mücke, P.; Klowsky, R.; Goesele, M., Surface reconstruction from multi-resolution sample points, (Proceedings of Vision, Modeling, and Visualization (VMV). Proceedings of Vision, Modeling, and Visualization (VMV), Berlin, Germany, October 4-6 (2011)), 4-6
[29] Ohtake, Y.; Belyaev, A.; Seidel, H. P., 3D scattered data approximation with adaptive compactly supported radial basis functions, (Proceedings. Proceedings, Shape Modeling Applications, 2004 (2004), IEEE)
[30] Pouderoux, J.; Gonzato, J. C.; Tobor, I.; Guitton, P., Adaptive hierarchical RBF interpolation for creating smooth digital elevation models, (Proc. of the 12th Annual ACM International Workshop on Geographic Information Systems. Proc. of the 12th Annual ACM International Workshop on Geographic Information Systems, GIS ’04 (2004), ACM), 232-240
[31] Safdari-Vaighani, A.; Heryudono, A.; Larsson, E., A radial basis function partition of unity collocation method for convection-diffusion equations arising in financial applications, J. Sci. Comput., 341-367 (2015) · Zbl 1325.65139
[32] Schall, O.; Samozino, M., Surface from scattered points, (A Brief Survey of Recent Developments. A Brief Survey of Recent Developments, 1st International Workshop on Semantic Virtual Environments (2005)), 138-147
[34] Turk, G.; Dinh, H. Q.; O’Brien, J. F.; Yngve, G., Implicit surfaces that interpolate, (SMI 2001 International Conf. on Shape Modeling and Applications (2001), IEEE), 62-71
[35] Wendland, H., Fast evaluation of radial basis functions: methods based on partition of unity, (Approximation Theory X: Wavelets, Splines, and Applications (2002), Vanderbilt University Press), 473-483 · Zbl 1031.65022
[36] Wendland, H., Scattered Data Approximation, Cambridge Monographs Applied Computational Mathematics, vol. 17 (2005), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1075.65021
[37] Yao, G.; Duo, J.; Chen, C. S.; Shen, L. H., Implicit local radial basis function interpolations based on function values, Appl. Math. Comput., 265, 91-102 (2015) · Zbl 1410.65026
[38] Yokota, R.; Barba, L. A.; Knepley, M. G., PetRBF - a parallel O(N) algorithm for radial basis function interpolation with Gaussians, Comput. Methods Appl. Mech. Eng., 199, 25-28, 1793-1804 (2010) · Zbl 1231.65026
[39] Zhang, W.; Wu, Z., Shape-preserving MQ-B-Splines quasi-interpolation, (GMP2004: Proceedings of Geometric Modeling and Processing (2004)), 85-92
[40] Zhao, H. K.; Osher, S.; Fedkiw, R., Fast surface reconstruction using the level set method, (Proc. IEEE Workshop on Variational and Level Set Methods in Computer Vision. Proc. IEEE Workshop on Variational and Level Set Methods in Computer Vision, 2001 (2001), IEEE), 194-201
[41] Zhu, Shengxin; Wathen, A. J., Convexity and solvability for compactly supported radial basis functions with different shapes, J. Sci. Comput., 63, 3, 862-884 (2015) · Zbl 1320.65025
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.