“Discrete bi-Laplacians and biharmonic b-splines” by Feng and Warren

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.

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.Google ScholarCross Ref
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. Google ScholarDigital Library
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.Google ScholarCross Ref
4. Buhmann, M. D. 2003. Radial basis functions: theory and implementations, vol. 12. Cambridge Univ Pr. Google ScholarDigital Library
5. Civril, A., Magdon-Ismail, M., and Bocek-Rivele, E. 2006. SDE: Graph drawing using spectral distance embedding. In Graph Drawing, Springer, 512–513. Google ScholarDigital Library
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.Google Scholar
7. De Boor, C. 1978. A Practical guide to splines. Springer, New York.Google Scholar
8. Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete differential forms for computational modeling. Discrete differential geometry, 287–324.Google Scholar
9. do Carmo, M. P. 1976. Differential geometry of curves and surfaces. Prentice-Hall Englewood Cliffs, NJ.Google Scholar
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.Google ScholarDigital Library
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. Google ScholarDigital Library
12. Fleming, W. H. 1977. Functions of several variables. Springer.Google Scholar
13. Freeden, W., and Schreiner, M. 2009. Spherical functions of mathematical geosciences: a scalar, vectorial, and tensorial setup. Springer Verlag.Google Scholar
14. Goldman, R., and Lyche, T. 1993. Knot insertion and deletion algorithms for B-spline curves and surfaces. No. 36. Society for Industrial Mathematics.Google Scholar
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. Google ScholarDigital Library
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.Google Scholar
17. John, F. 1982. Partial Differential Equations. No. v. 1 in Applied Mathematical Sciences. Springer-Verlag.Google Scholar
18. Lipman, Y., Rustamov, R. M., and Funkhouser, T. A. 2010. Biharmonic distance. ACM Transactions on Graphics (TOG) 29, 3, 27. Google ScholarDigital Library
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. Google ScholarDigital Library
20. Loghin, D. 1999. Green’s functions for preconditioning. PhD thesis, Oxford University.Google Scholar
21. Monterde, J., and Ugail, H. 2004. On harmonic and biharmonic Bézier surfaces. Computer Aided Geometric Design 21, 7, 697–715. Google ScholarDigital Library
22. Nay, R. A., and Utku, S. 1972. An alternative for the finite element method. Variational Methods in Engineering 2 (Sept.).Google Scholar
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.Google ScholarCross Ref
24. Rabut, C. 1992. Elementary m-harmonic cardinal B-splines. Numerical Algorithms 2, 1, 39–61.Google ScholarCross Ref
25. Sibson, R. 1981. A brief description of natural neighbour interpolation. Interpreting multivariate data 21, 21–36.Google Scholar
26. Strikwerda, J. C. 2004. Finite difference schemes and partial differential equations. Society for Industrial Mathematics. Google ScholarDigital Library
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. Google ScholarDigital Library
28. Vallet, B., and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Computer Graphics Forum 27, 2, 251–260.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
32. Xu, K., Zhang, H., Cohen-Or, D., and Xiong, Y. 2009. Dynamic harmonic fields for surface processing. Computers & Graphics 33, 3, 391–398. Google ScholarDigital Library
33. Xu, G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design 21, 8, 767–784. Google ScholarDigital Library