Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Noninterpolatory Hermite subdivision schemes

Authors: Bin Han, Thomas P.-Y. Yu and Yonggang Xue
Journal: Math. Comp. 74 (2005), 1345-1367
MSC (2000): Primary 41A05, 41A15, 41A63, 42C40, 65T60, 65F15
Published electronically: September 10, 2004
MathSciNet review: 2137006
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Bivariate interpolatory Hermite subdivision schemes have recently been applied to build free-form subdivision surfaces. It is well known to geometric modelling practitioners that interpolatory schemes typically lead to ``unfair" surfaces--surfaces with unwanted wiggles or undulations--and noninterpolatory (a.k.a. approximating in the CAGD community) schemes are much preferred in geometric modelling applications. In this article, we introduce, analyze and construct noninterpolatory Hermite subdivision schemes, a class of vector subdivision schemes which can be applied to iteratively refine Hermite data in a not necessarily interpolatory fashion. We also study symmetry properties of such subdivision schemes which are crucial for application in free-form subdivision surfaces.

A key step in our mathematical analysis of Hermite type subdivision schemes is that we make use of the strong convergence theory of refinement equations to convert a prescribed geometric condition on the subdivision scheme--namely, the subdivision scheme is of Hermite type--to an algebraic condition on the subdivision mask. The latter algebraic condition can then be used in a computational framework to construct specific schemes.

References [Enhancements On Off] (What's this?)

  • 1. E. Catmull and J. Clark.
    Recursive generated B-spline surfaces on arbitrary topological meshes.
    Comp. Aid. Geom. Des., 10(6):350-355, 1978.
  • 2. A. Cohen, N. Dyn, and D. Levin.
    Matrix subdivision scheme.
    Unpublished manuscript, available at, 1998.
  • 3. C. de Boor.
    A Practical Guide to Splines.
    Number 27 in Applied Mathematical Sciences. Springer-Verlag, New York, 1978.
  • 4. C. de Boor, K. Höllig, and S. Riemenschneider, Box splines, Applied Mathematical Sciences, vol. 98, Springer-Verlag, New York, 1993. MR 1243635
  • 5. David L. Donoho, Nira Dyn, David Levin, and Thomas P. Y. Yu, Smooth multiwavelet duals of Alpert bases by moment-interpolating refinement, Appl. Comput. Harmon. Anal. 9 (2000), no. 2, 166–203. MR 1777125, 10.1006/acha.2000.0315
  • 6. D. Doo and M. Sabin.
    Analysis of the behavoir of recursive division surfaces near extraordinary points.
    Comp. Aid. Geom. Des., 10(6):356-360, 1978.
  • 7. Nira Dyn and David Levin, Analysis of Hermite-interpolatory subdivision schemes, Spline functions and the theory of wavelets (Montreal, PQ, 1996) CRM Proc. Lecture Notes, vol. 18, Amer. Math. Soc., Providence, RI, 1999, pp. 105–113. MR 1676239
  • 8. Nira Dyn and David Levin, Subdivision schemes in geometric modelling, Acta Numer. 11 (2002), 73–144. MR 2008967, 10.1017/S0962492902000028
  • 9. N. Dyn, D. Levin, and J. A. Gregory.
    A butterfly subdivision scheme for surface interpolation with tension control.
    ACM Transaction on Graphics, 9(2), April 1990.
  • 10. Bin Han, Approximation properties and construction of Hermite interpolants and biorthogonal multiwavelets, J. Approx. Theory 110 (2001), no. 1, 18–53. MR 1826084, 10.1006/jath.2000.3545
  • 11. Bin Han, Symmetry property and construction of wavelets with a general dilation matrix, Linear Algebra Appl. 353 (2002), 207–225. MR 1919638, 10.1016/S0024-3795(02)00307-5
  • 12. Bin Han, Computing the smoothness exponent of a symmetric multivariate refinable function, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 693–714 (electronic). MR 1972675, 10.1137/S0895479801390868
  • 13. Bin Han, Vector cascade algorithms and refinable function vectors in Sobolev spaces, J. Approx. Theory 124 (2003), no. 1, 44–88. MR 2010780, 10.1016/S0021-9045(03)00120-5
  • 14. B. Han, M. Overton, and T. P.-Y. Yu.
    Design of Hermite subdivision schemes aided by spectral radius optimization.
    SIAM Journal on Scientific Computing, 25(2):643-656, 2003.
  • 15. B. Han and T. P.-Y. Yu.
    Face-based Hermite subdivision schemes.
    Preprint, available at, September 2003.
  • 16. B. Han, T. P.-Y. Yu, and B. Piper.
    Multivariate refinable Hermite interpolants.
    Mathematics of Computation, 2003.
    To appear. Preprint available at
  • 17. Loïc Hervé, Multi-resolution analysis of multiplicity 𝑑: applications to dyadic interpolation, Appl. Comput. Harmon. Anal. 1 (1994), no. 4, 299–315. MR 1310654, 10.1006/acha.1994.1017
  • 18. Rong-Qing Jia and Qingtang Jiang, Spectral analysis of the transition operator and its applications to smoothness analysis of wavelets, SIAM J. Matrix Anal. Appl. 24 (2003), no. 4, 1071–1109 (electronic). MR 2003322, 10.1137/S0895479801397858
  • 19. Rong Qing Jia and Charles A. Micchelli, On linear independence for integer translates of a finite number of functions, Proc. Edinburgh Math. Soc. (2) 36 (1993), no. 1, 69–85. MR 1200188, 10.1017/S0013091500005903
  • 20. Qingtang Jiang and Peter Oswald, Triangular √3-subdivision schemes: the regular case, J. Comput. Appl. Math. 156 (2003), no. 1, 47–75. MR 1982935
  • 21. L. Kobbelt.
    $\sqrt{3}$ subdivision.
    Computer Graphics Proceedings (SIGGRAPH 2000), 2000.
  • 22. L. Kobbelt, T. Hesse, H. Prautzsch, and K. Schweizerhof.
    Interpolatory subdivision on open quadrilateral nets with arbitrary topology.
    In Proceedings of Eurographics '96, Computer Graphics Forum 15, pages 409-420, 1996.
  • 23. C. T. Loop.
    Smooth subdivision surfaces based on triangles.
    Master's thesis, Department of Mathematics, University of Utah, 1987.
  • 24. J.-L. Merrien, A family of Hermite interpolants by bisection algorithms, Numer. Algorithms 2 (1992), no. 2, 187–200. MR 1165905, 10.1007/BF02145385
  • 25. G. Plonka, Approximation order provided by refinable function vectors, Constr. Approx. 13 (1997), no. 2, 221–244. MR 1437211, 10.1007/s003659900039
  • 26. L. Velho and D. Zorin.
    4-8 subdivision.
    Comp. Aid. Geom. Des., 18(5):397-427, 2001.
  • 27. J. Warren and H. Weimer.
    Subdivision Methods for Geometric Design: A Constructive Approach.
    Morgan Kaufmann, 2001.
  • 28. Y. Xue, T. P.-Y. Yu, and T. Duchamp.
    Hermite subdivision surfaces: Applications of vector refinability to free-form surfaces.
    In preparation, 2003.
  • 29. D. Zorin, P. Schröder, and W. Sweldens.
    Interpolating subdivision for meshes with arbitrary topology.
    Computer Graphics Proceedings (SIGGRAPH 96), pages 189-192, 1996.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A05, 41A15, 41A63, 42C40, 65T60, 65F15

Retrieve articles in all journals with MSC (2000): 41A05, 41A15, 41A63, 42C40, 65T60, 65F15

Additional Information

Bin Han
Affiliation: Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1

Thomas P.-Y. Yu
Affiliation: Department of Mathematical Science, Rensselaer Polytechnic Institute, Troy, New York 12180-3590

Yonggang Xue
Affiliation: Department of Mathematical Science, Rensselaer Polytechnic Institute, Troy, New York 12180-3590

Keywords: Refinable function, vector refinability, subdivision scheme, shift invariant subspace, subdivision surface, spline
Received by editor(s): April 15, 2003
Received by editor(s) in revised form: December 10, 2003
Published electronically: September 10, 2004
Additional Notes: The first author’s research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC Canada) under grant G121210654
The second author’s research was supported in part by an NSF CAREER Award (CCR 9984501)
Article copyright: © Copyright 2004 American Mathematical Society