Noninterpolatory Hermite subdivision schemes

Han, Bin; Yu, Thomas; Xue, Yonggang

doi:10.1090/S0025-5718-04-01704-1

Noninterpolatory Hermite subdivision schemes
HTML articles powered by AMS MathViewer

by Bin Han, Thomas P.-Y. Yu and Yonggang Xue PDF

Math. Comp. 74 (2005), 1345-1367 Request permission

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.