Discrete bi-Laplacians and biharmonic b-splines

Abstract

Divided differences play a fundamental role in the construction of univariate B-splines over irregular knot sequences. Unfortunately, generalizations of divided differences to irregular knot geometries on two-dimensional domains are quite limited. As a result, most spline constructions for such domains typically focus on regular (or semi-regular) knot geometries. In the planar harmonic case, we show that the discrete Laplacian plays a role similar to that of the divided differences and can be used to define well-behaved harmonic B-splines. In our main contribution, we then construct an analogous discrete bi-Laplacian for both planar and curved domains and show that its corresponding biharmonic B-splines are also well-behaved. Finally, we derive a fully irregular, discrete refinement scheme for these splines that generalizes knot insertion for univariate B-splines.

References

1. Beatson, R. K., and Light, W. A. 1997. Fast evaluation of radial basis functions: methods for two-dimensional polyharmonic splines. IMA Journal of Numerical Analysis 17, 3, 343--372.
2. Boissonnat, J.-D., and Cazals, F. 2001. Natural neighbor coordinates of points on a surface. Computational Geometry 19, 23, 155--173. Combinatorial Curves and Surfaces.
3. Buhmann, M. D., Dyn, N., and Levin, D. 1995. On quasi-interpolation by radial basis functions with scattered centres. Constructive Approximation 11, 239--254.
4. Buhmann, M. D. 2003. Radial basis functions: theory and implementations, vol. 12. Cambridge Univ Pr.
5. Civril, A., Magdon-Ismail, M., and Bocek-Rivele, E. 2006. SDE: Graph drawing using spectral distance embedding. In Graph Drawing, Springer, 512--513.
6. Dahmen, W., Micchelli, C. A., and Seidel, H. P. 1992. Blossoming begets B-spline bases built better by B-patches. Mathematics of computation 59, 199, 97--115.
7. De Boor, C. 1978. A Practical guide to splines. Springer, New York.
8. Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete differential forms for computational modeling. Discrete differential geometry, 287--324.
9. do Carmo, M. P. 1976. Differential geometry of curves and surfaces. Prentice-Hall Englewood Cliffs, NJ.
10. Dyn, N., Levin, D., and Rippa, S. 1986. Numerical procedures for surface fitting of scattered data by radial functions. SIAM Journal on Scientific and Statistical Computing 7, 2, 639--659.
11. Fisher, M., Springborn, B., Schröder, P., and Bobenko, A. I. 2007. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. Computing 81, 2, 199--213.
12. Fleming, W. H. 1977. Functions of several variables. Springer.
13. Freeden, W., and Schreiner, M. 2009. Spherical functions of mathematical geosciences: a scalar, vectorial, and tensorial setup. Springer Verlag.
14. Goldman, R., and Lyche, T. 1993. Knot insertion and deletion algorithms for B-spline curves and surfaces. No. 36. Society for Industrial Mathematics.
15. Hiyoshi, H., and Sugihara, K. 2000. Voronoi-based interpolation with higher continuity. In Proceedings of the sixteenth annual symposium on computational geometry, ACM, New York, NY, USA, SCG '00, 242--250.
16. Jacobson, A., Tosun, E., Sorkine, O., and Zorin, D. 2010. Mixed finite elements for variational surface modeling. Computer Graphics Forum (proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing) 29, 5, 1565--1574.
17. John, F. 1982. Partial Differential Equations. No. v. 1 in Applied Mathematical Sciences. Springer-Verlag.
18. Lipman, Y., Rustamov, R. M., and Funkhouser, T. A. 2010. Biharmonic distance. ACM Transactions on Graphics (TOG) 29, 3, 27.
19. Liu, Y., Chen, Z., and Tang, K. 2011. Construction of iso-contours, bisectors and Voronoi diagrams on triangulated surfaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 99, 1--1.
20. Loghin, D. 1999. Green's functions for preconditioning. PhD thesis, Oxford University.
21. Monterde, J., and Ugail, H. 2004. On harmonic and biharmonic Bézier surfaces. Computer Aided Geometric Design 21, 7, 697--715.
22. Nay, R. A., and Utku, S. 1972. An alternative for the finite element method. Variational Methods in Engineering 2 (Sept.).
23. Neamtu, M. 2007. Delaunay configurations and multivariate splines: A generalization of a result of BN Delaunay. Transactions of the American Mathematical Society 359, 7, 2993--3004.
24. Rabut, C. 1992. Elementary m-harmonic cardinal B-splines. Numerical Algorithms 2, 1, 39--61.
25. Sibson, R. 1981. A brief description of natural neighbour interpolation. Interpreting multivariate data 21, 21--36.
26. Strikwerda, J. C. 2004. Finite difference schemes and partial differential equations. Society for Industrial Mathematics.
27. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. In ACM Transactions on Graphics (TOG), vol. 24, ACM, 553--560.
28. Vallet, B., and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Computer Graphics Forum 27, 2, 251--260.
29. Van De Ville, D., Blu, T., and Unser, M. 2005. Isotropic polyharmonic B-splines: scaling functions and wavelets. Image Processing, IEEE Transactions on 14, 11 (nov.), 1798--1813.
30. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete Laplace operators: no free lunch. In Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP '07, 33--37.
31. Warren, J., and Weimer, H. 2002. Subdivision methods for geometric design: a constructive approach. Morgan Kaufmann series in computer graphics and geometric modeling. Morgan Kaufmann.
32. Xu, K., Zhang, H., Cohen-Or, D., and Xiong, Y. 2009. Dynamic harmonic fields for surface processing. Computers & Graphics 33, 3, 391--398.
33. Xu, G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design 21, 8, 767--784.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Mathematics of computing

  • Probability and statistics

    • Probabilistic representations

      • Nonparametric representations

        • Spline models