Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Noninterpolatory Hermite subdivision schemes
HTML articles powered by AMS MathViewer

by Bin Han, Thomas P.-Y. Yu and Yonggang Xue;
Math. Comp. 74 (2005), 1345-1367
DOI: https://doi.org/10.1090/S0025-5718-04-01704-1
Published electronically: September 10, 2004

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
  • E. Catmull and J. Clark. Recursive generated B-spline surfaces on arbitrary topological meshes. Comp. Aid. Geom. Des., 10(6):350–355, 1978.
  • A. Cohen, N. Dyn, and D. Levin. Matrix subdivision scheme. Unpublished manuscript, available at http://www.ann.jussieu.fr/~cohen/matrix.ps.gz, 1998.
  • C. de Boor. A Practical Guide to Splines. Number 27 in Applied Mathematical Sciences. Springer-Verlag, New York, 1978.
  • C. de Boor, K. Höllig, and S. Riemenschneider, Box splines, Applied Mathematical Sciences, vol. 98, Springer-Verlag, New York, 1993. MR 1243635, DOI 10.1007/978-1-4757-2244-4
  • 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, DOI 10.1006/acha.2000.0315
  • 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.
  • 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, DOI 10.1090/crmp/018/11
  • Nira Dyn and David Levin, Subdivision schemes in geometric modelling, Acta Numer. 11 (2002), 73–144. MR 2008967, DOI 10.1017/S0962492902000028
  • 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.
  • Bin Han, Approximation properties and construction of Hermite interpolants and biorthogonal multiwavelets, J. Approx. Theory 110 (2001), no. 1, 18–53. MR 1826084, DOI 10.1006/jath.2000.3545
  • Bin Han, Symmetry property and construction of wavelets with a general dilation matrix, Linear Algebra Appl. 353 (2002), 207–225. MR 1919638, DOI 10.1016/S0024-3795(02)00307-5
  • Bin Han, Computing the smoothness exponent of a symmetric multivariate refinable function, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 693–714. MR 1972675, DOI 10.1137/S0895479801390868
  • Bin Han, Vector cascade algorithms and refinable function vectors in Sobolev spaces, J. Approx. Theory 124 (2003), no. 1, 44–88. MR 2010780, DOI 10.1016/S0021-9045(03)00120-5
  • 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.
  • B. Han and T. P.-Y. Yu. Face-based Hermite subdivision schemes. Preprint, available at http://www.rpi.edu/~yut/Papers/dual.pdf, September 2003.
  • B. Han, T. P.-Y. Yu, and B. Piper. Multivariate refinable Hermite interpolants. Mathematics of Computation, 2003. To appear. Preprint available at http://www.rpi.edu/~yut/hyp.pdf.
  • Loïc Hervé, Multi-resolution analysis of multiplicity $d$: applications to dyadic interpolation, Appl. Comput. Harmon. Anal. 1 (1994), no. 4, 299–315. MR 1310654, DOI 10.1006/acha.1994.1017
  • 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. MR 2003322, DOI 10.1137/S0895479801397858
  • 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, DOI 10.1017/S0013091500005903
  • Qingtang Jiang and Peter Oswald, Triangular $\sqrt 3$-subdivision schemes: the regular case, J. Comput. Appl. Math. 156 (2003), no. 1, 47–75. MR 1982935
  • L. Kobbelt. $\sqrt {3}$ subdivision. Computer Graphics Proceedings (SIGGRAPH 2000), 2000.
  • 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.
  • C. T. Loop. Smooth subdivision surfaces based on triangles. Master’s thesis, Department of Mathematics, University of Utah, 1987.
  • J.-L. Merrien, A family of Hermite interpolants by bisection algorithms, Numer. Algorithms 2 (1992), no. 2, 187–200. MR 1165905, DOI 10.1007/BF02145385
  • G. Plonka, Approximation order provided by refinable function vectors, Constr. Approx. 13 (1997), no. 2, 221–244. MR 1437211, DOI 10.1007/s003659900039
  • L. Velho and D. Zorin. 4-8 subdivision. Comp. Aid. Geom. Des., 18(5):397–427, 2001.
  • J. Warren and H. Weimer. Subdivision Methods for Geometric Design: A Constructive Approach. Morgan Kaufmann, 2001.
  • Y. Xue, T. P.-Y. Yu, and T. Duchamp. Hermite subdivision surfaces: Applications of vector refinability to free-form surfaces. In preparation, 2003.
  • 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
Bibliographic Information
  • Bin Han
  • Affiliation: Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
  • MR Author ID: 610426
  • Email: bhan@math.ualberta.ca
  • Thomas P.-Y. Yu
  • Affiliation: Department of Mathematical Science, Rensselaer Polytechnic Institute, Troy, New York 12180-3590
  • MR Author ID: 644909
  • Email: yut@rpi.edu
  • Yonggang Xue
  • Affiliation: Department of Mathematical Science, Rensselaer Polytechnic Institute, Troy, New York 12180-3590
  • Email: xuey@rpi.edu
  • 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)
  • © Copyright 2004 American Mathematical Society
  • Journal: Math. Comp. 74 (2005), 1345-1367
  • MSC (2000): Primary 41A05, 41A15, 41A63, 42C40, 65T60, 65F15
  • DOI: https://doi.org/10.1090/S0025-5718-04-01704-1
  • MathSciNet review: 2137006