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

  • ©Powei Feng and Joe Warren




    Discrete bi-Laplacians and biharmonic b-splines



    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

ACM Digital Library Publication: