“Reconstruction and representation of 3D objects with radial basis functions” by Carr, Beatson, Cherrie, Mitchell, Fright, et al. …

We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair incomplete meshes. An object’s surface is defined implicitly as the zero set of an RBF fitted to the given surface data. Fast methods for fitting and evaluating RBFs allow us to model large data sets, consisting of millions of surface points, by a single RBF — previously an impossible task. A greedy algorithm in the fitting process reduces the number of RBF centers required to represent a surface and results in significant compression and further computational advantages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from non-uniformly sampled data. Holes are smoothly filled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform meshes and we show that the RBF representation has advantages for mesh simplification and remeshing applications. Results are presented for real-world rangefinder data.

1. C. Bajaj, J. Chen, and G. Xu. Modeling with cubic a-patches. ACM Transactions on Computer Graphics, 14(2):103-133, 1995.
2. R. K. Beatson, J. B. Cherrie, and C. T. Mouat. Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration. Advances in Computational Mathematics, 11:253-270, 1999.
3. R. K. Beatson, J. B. Cherrie, and D. L. Ragozin. Fast evaluation of radial basis functions: Methods for four-dimensional polyharmonic splines. SIAM J. Math. Anal., 32(6):1272-1310, 2001.
4. R. K. Beatson and L. Greengard. A short course on fast multipole methods. In M. Ainsworth, J. Levesley, W.A. Light, and M. Marletta, editors, Wavelets, Multilevel Methods and Elliptic PDEs, pages 1-37. Oxford University Press, 1997.
5. R. K. Beatson and W. A. Light. Fast evaluation of radial basis functions: Methods for two-dimensional polyharmonic splines. IMA Journal of Numerical Analysis, 17:343-372, 1997.
6. R. K. Beatson, W. A. Light, and S. Billings. Fast solution of the radial basis function interpolation equations: Domain decomposition methods. SIAM J. Sci. Comput., 22(5):1717-1740, 2000.
7. R. K. Beatson, A. M. Tan, and M. J. D. Powell. Fast evaluation of radial basis functions: Methods for 3-dimensional polyharmonic splines. In preparation.
8. F. Bernardini, C. L. Bajaj, J. Chen, and D. R. Schikore. Automatic reconstruction of 3D CAD models from digital scans. Int. J. on Comp. Geom. and Appl., 9(4- 5):327, Aug & Oct 1999.
9. J. Bloomenthal, editor. Introduction to Implicit Surfaces. Morgan Kaufmann, San Francisco, California, 1997.
10. J. C. Carr, W. R. Fright, and R. K. Beatson. Surface interpolation with radial basis functions for medical imaging. IEEE Trans. Medical Imaging, 16(1):96- 107, February 1997.
11. E. W. Cheney and W. A. Light. A Course in Approximation Theory. Brooks Cole, Pacific Grove, 1999.
12. J. Duchon. Splines minimizing rotation-invariant semi-norms in Sobolev spaces. In W. Schempp and K. Zeller, editors, Constructive Theory of Functions of Several Variables, number 571 in Lecture Notes in Mathematics, pages 85-100, Berlin, 1977. Springer-Verlag.
13. N. Dyn, D. Levin, and S. Rippa. Numerical procedures for surface fitting of scattered data by radial functions. SIAM J. Sci. Stat. Comput., 7(2):639-659, 1986.
14. J. Flusser. An adaptive method for image registration. Pattern Recognition, 25(1):45-54, 1992.
15. L. Greengard and V. Rokhlin. A fast algorithm for particle simulations. J. Comput. Phys, 73:325-348, 1987.
16. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstuction from unorganized points. Computer Graphics (SIGGRAPH’92 proceedings), 26(2):71-78, July 1992.
17. W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3D surface construction algorithm. Computer Graphics, 21(4):163-169, July 1987.
18. C. A. Micchelli. Interpolation of scattered data: Distance matrices and conditionally positive definite functions. Constr. Approx., 2:11-22, 1986.
19. V. V. Savchenko, A. A. Pasko, O. G. Okunev, and T. L. Kunii. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum, 14(4):181-188, 1995.
20. R. Sibson and G. Stone. Computation of thin-plate splines. SIAM J. Sci. Stat. Comput., 12(6):1304-1313, 1991.
21. G. M. Treece, R. W. Prager, and A. H. Gee. Regularised marching tetrahedra: improved iso-surface extraction. Computers and Graphics, 23(4):583-598, 1999.
22. G. Turk and J. F. O’Brien. Shape transformation using variational implicit surfaces. In SIGGRAPH’99, pages 335-342, Aug 1999.
23. G. Turk and J. F. O’Brien. Variational implicit surfaces. Technical Report GIT- GVU-99-15, Georgia Institute of Technology, May 1999.
24. G. Wahba. Spline Models for Observational Data. Number 59 in CBMS-NSF Regional Conference Series in Applied Math. SIAM, 1990.
25. G. Yngve and G. Turk. Creating smooth implicit surfaces from polygonal meshes. Technical Report GIT-GVU-99-42, Georgia Institute of Technology, 1999.