一种重构圆锥曲线的Hermite细分方法
|
摘要
随着计算机技术的普及和应用的日益广泛,细分方法在近年来已经成为计算机辅助设计(CAD)和计算机图形学(CG)领域内的一个国际性研究热点。近三十年来已有多种细分方法被相继提出,然而大多数细分方法不能既生成在计算机图形学中广泛应用的特殊曲线,例如圆弧曲线,又存在一个松弛参数能够调整极限曲线的形状。本文介绍了一种两点Hermite插值细分方法,构造出的细分格式可以重构三次多项式、三角函数和双曲函数空间,而且有一个松弛参数可以调整极限曲线的形状。本文首先回顾了细分的发展概况和历史,然后描述了几种比较经典的细分方法,介绍了细分理论分析的一般定义、定理,以及线性Hermite插值细分格式的理论分析结果。本文基于已经给定的两个点的函数值和导数值构造出了一种Hermite插值细分格式,构造过程主要是解线性方程组,如果第k层上的点是所对应函数图像上的点,则新产生的点也要是同一个函数在规定的参数上的点,然后求解满足上述条件的线性方程组,求解细分系数,再利用前面已经介绍的有关渐近一致等价的定理、结论和线性Hermite插值细分格式的理论对构造的细分格式进行了理论分析和证明,找到了与其渐近一致等价的格式。本文构造的细分格式提供了一个松弛参数,当该松弛参数取一定的范围并且任意增大时生成的极限曲线将越来越逼近于对初始数据点进行分片线性插值的函数;当恰当地选择松弛参数不同的初值时,该细分格式能够分别精确生成三次多项式、三角函数和双曲函数,因此,选择特殊的松弛参数初值我们就能够生成所有的圆锥曲线段。最后给出一些实例来说明利用不同的松弛参数初值和改变切向量来生成极限曲线的效果。
With the rapid development and wide application of computer science, subdivision has become a powerful tool in the fields of computer aided design (CAD) and computer graphics (CG). Many subdivision schemes have been proposed in the recent three decades, however, most of them are not capable of both reproducing families of curves widely used in Computer Graphics such as conics, and controlling the shape of the limit curve by a tension parameter. This paper introduces a Hermite-interpolatory subdivision scheme with a tension parameter to control the shapes of the limit curves. The scheme can also represent elements in cubic polynomials, trigonometric functions and hyperbolic functions. This thesis reviews the general situation and history of subdivision at first, and then depicts several kinds of classic subdivision schemes in common use. Based on general theorems and definitions of subdivision, we give the research results of Linear Hermite- interpolatory schemes. By the given two points' values and derivatives, the paper constructs a 2-point Hermite-interpolatory scheme, and the construction process is mainly solving linear system. If the points on the level k belong to a function in the space, then the new points should be on the same function attached to the necessary parameters. Through the linear system we get the subdivision mask, and then we use the theorems and definitions such as asymptotic equivalence and the results of linear Hermite-interpolatory subdivision schemes introduced above to analyze the constructed scheme, at the same time we find a classic scheme which is equivalent to the non-stationary scheme. The subdivision scheme provides users with a tension parameter that can be either arbitrarily increased to tighten the limit curve towards the piecewise linear interpolant between the data points, or appropriately chosen in order to represent the elements in cubic polynomials, trigonometric functions and hyperbolic functions. As a consequence, for special values of tension parameter we can reproduce all conic sections exactly. At last, we illustrate the effects of using different tension parameter and tangent vectors to reproduce subdivision curves.
With the rapid development and wide application of computer science, subdivision has become a powerful tool in the fields of computer aided design (CAD) and computer graphics (CG). Many subdivision schemes have been proposed in the recent three decades, however, most of them are not capable of both reproducing families of curves widely used in Computer Graphics such as conics, and controlling the shape of the limit curve by a tension parameter. This paper introduces a Hermite-interpolatory subdivision scheme with a tension parameter to control the shapes of the limit curves. The scheme can also represent elements in cubic polynomials, trigonometric functions and hyperbolic functions. This thesis reviews the general situation and history of subdivision at first, and then depicts several kinds of classic subdivision schemes in common use. Based on general theorems and definitions of subdivision, we give the research results of Linear Hermite- interpolatory schemes. By the given two points' values and derivatives, the paper constructs a 2-point Hermite-interpolatory scheme, and the construction process is mainly solving linear system. If the points on the level k belong to a function in the space, then the new points should be on the same function attached to the necessary parameters. Through the linear system we get the subdivision mask, and then we use the theorems and definitions such as asymptotic equivalence and the results of linear Hermite-interpolatory subdivision schemes introduced above to analyze the constructed scheme, at the same time we find a classic scheme which is equivalent to the non-stationary scheme. The subdivision scheme provides users with a tension parameter that can be either arbitrarily increased to tighten the limit curve towards the piecewise linear interpolant between the data points, or appropriately chosen in order to represent the elements in cubic polynomials, trigonometric functions and hyperbolic functions. As a consequence, for special values of tension parameter we can reproduce all conic sections exactly. At last, we illustrate the effects of using different tension parameter and tangent vectors to reproduce subdivision curves.
引文
[1] Bezie P.Numerical Control: Mathematics and Applications.London: Wiley, 1972.
[2] de Boor C W. On calculation with B spline. Journal of Approximation Theory, 1972, 6:50-62.
[3] Piegl L,Tiller W.The NURBS Book. New York: Springer, 1997, second ed.
[4] de Rham G. Su rune courbe plane. J Mathem Pures et Appl, 1956,39:25-42.
[5] Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 1978, 10:350-355.
[6] Doo D, Sabin M. Behaviour of recursive devision surfaces near extraordinaty points. Computer-Aided Design, 1978, 10:356-360. Ken Kazama.
[7] Loop C. Smooth subdivision surfaces based on triangeles: Master' s thesis: Department of Mathematics, University of Utah, 1987.
[8] Dyn N, Levin D. A 4-point intepolatory subdivision scheme for curve design. Computer Aided Geometric Design, 1987, 4:257-268.
[9] Dyn N, Levin D, Gregory J A. A butterfly subdivision scheme for surface interpolation with tension control. ACM Transactions on Craphics, 1990, 9(2):160-169.
[10] Dyn N. Subdivision scheme in computer-aided geometric design. Light W, ed. Advances in numerical Analysis, vol.2. Clarendon Press , 1992, 36-104.
[11] W. Dahmen and C. Micchelli. Biorthogonal wavelet expansion. Constr. Approx. 13:294-328,1997.
[12] B. Han and R. Q. Jia. Multivariate refinement equations and convergence of subdivision schemes. SIAM J. Math. Anal. 29:1177-1199, 1998.
[13] A. S. Cavaretta, W. Dehmen, and C. A. Micchelli. Stationary Subdivision. Volume 453 of Memoirs of Ams. American Mathematical Society, 1991.
[14] I. Daubechies. Ten Lectures on Wavelets. SIAM, Philadelphia, 1992.
[15] G. Derfel, N. Dyn. Generalized refinement equations and subdivision process. Journal of Approximation Theory, 80(2):272-297,1995.
[16] N. Dyn and D. levin. Analysis of asymptotically equivalent binary subdivision scheme. J. Mathematical Analysis and Application, 193:594-621,1995.
[17] S. Mallat. Theory for multiresolution signal decomposition: the wavelet representat -ion. IEEE Trans. Patten Anal. Math. Intel. 11:674-693,1989.
[18] B. Han. Computering the smoothness exponent of a symmetric multivariate refinable Function. Preprint, 2001.
[19] R. Q. Jia. The subdivision and transition operators associated with a refinement equation. In K. Jetter F. Fontanella and L. L. Schumaker, editors, Advanced topics in Multivariate Approximation, pages 1-13. World Scientific Publications, 1996.
[20]R.Q.Jia and S.Zhang.Spectral properties of the transition opertator associated to a multivariate refinement equation.Linear Algebra and Applications,292:155-178,1999.
[21]N.Dyn and D.levin.Analysis of Hermite-type subdivision schemes.In C.K.Chui and L.L.Schumaker,editors,Approxition Theory,8,vol.2:Wavelets and Multilevel Approximation,pages 117-224,Singapore,1995.World Scientific.
[22]N.Dyn and D.levin.Analysis of Hermite-interpolatory subdivision schemes.In Proceedings of the workshop:Spline functions and wavelets,1997.
[23]C.Beccari,G.Casciola,L.Romani.A non-stationary uniform tension controlled interpolating 4-point scheme reproducing conics.Comput.Aided Geom.Design,1,2007,1-9.
[24]J.L.Merrien.A family of nermite interpolants by bisection algorithms.Numerical Algnrithms,2,1992,187-200.
[25]N.Dyn,D.Levin.Analysis of asymptotically equivalent binary subdivision scheme -s.[J].Math.Anal.Appl,193,1995,594-621.
[26]樊敏,康宝生.一类Hermite型矢量插值C^1细分曲线的几何特征生成[A].工程图学学报,2006,3:79-83.
[2] de Boor C W. On calculation with B spline. Journal of Approximation Theory, 1972, 6:50-62.
[3] Piegl L,Tiller W.The NURBS Book. New York: Springer, 1997, second ed.
[4] de Rham G. Su rune courbe plane. J Mathem Pures et Appl, 1956,39:25-42.
[5] Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 1978, 10:350-355.
[6] Doo D, Sabin M. Behaviour of recursive devision surfaces near extraordinaty points. Computer-Aided Design, 1978, 10:356-360. Ken Kazama.
[7] Loop C. Smooth subdivision surfaces based on triangeles: Master' s thesis: Department of Mathematics, University of Utah, 1987.
[8] Dyn N, Levin D. A 4-point intepolatory subdivision scheme for curve design. Computer Aided Geometric Design, 1987, 4:257-268.
[9] Dyn N, Levin D, Gregory J A. A butterfly subdivision scheme for surface interpolation with tension control. ACM Transactions on Craphics, 1990, 9(2):160-169.
[10] Dyn N. Subdivision scheme in computer-aided geometric design. Light W, ed. Advances in numerical Analysis, vol.2. Clarendon Press , 1992, 36-104.
[11] W. Dahmen and C. Micchelli. Biorthogonal wavelet expansion. Constr. Approx. 13:294-328,1997.
[12] B. Han and R. Q. Jia. Multivariate refinement equations and convergence of subdivision schemes. SIAM J. Math. Anal. 29:1177-1199, 1998.
[13] A. S. Cavaretta, W. Dehmen, and C. A. Micchelli. Stationary Subdivision. Volume 453 of Memoirs of Ams. American Mathematical Society, 1991.
[14] I. Daubechies. Ten Lectures on Wavelets. SIAM, Philadelphia, 1992.
[15] G. Derfel, N. Dyn. Generalized refinement equations and subdivision process. Journal of Approximation Theory, 80(2):272-297,1995.
[16] N. Dyn and D. levin. Analysis of asymptotically equivalent binary subdivision scheme. J. Mathematical Analysis and Application, 193:594-621,1995.
[17] S. Mallat. Theory for multiresolution signal decomposition: the wavelet representat -ion. IEEE Trans. Patten Anal. Math. Intel. 11:674-693,1989.
[18] B. Han. Computering the smoothness exponent of a symmetric multivariate refinable Function. Preprint, 2001.
[19] R. Q. Jia. The subdivision and transition operators associated with a refinement equation. In K. Jetter F. Fontanella and L. L. Schumaker, editors, Advanced topics in Multivariate Approximation, pages 1-13. World Scientific Publications, 1996.
[20]R.Q.Jia and S.Zhang.Spectral properties of the transition opertator associated to a multivariate refinement equation.Linear Algebra and Applications,292:155-178,1999.
[21]N.Dyn and D.levin.Analysis of Hermite-type subdivision schemes.In C.K.Chui and L.L.Schumaker,editors,Approxition Theory,8,vol.2:Wavelets and Multilevel Approximation,pages 117-224,Singapore,1995.World Scientific.
[22]N.Dyn and D.levin.Analysis of Hermite-interpolatory subdivision schemes.In Proceedings of the workshop:Spline functions and wavelets,1997.
[23]C.Beccari,G.Casciola,L.Romani.A non-stationary uniform tension controlled interpolating 4-point scheme reproducing conics.Comput.Aided Geom.Design,1,2007,1-9.
[24]J.L.Merrien.A family of nermite interpolants by bisection algorithms.Numerical Algnrithms,2,1992,187-200.
[25]N.Dyn,D.Levin.Analysis of asymptotically equivalent binary subdivision scheme -s.[J].Math.Anal.Appl,193,1995,594-621.
[26]樊敏,康宝生.一类Hermite型矢量插值C^1细分曲线的几何特征生成[A].工程图学学报,2006,3:79-83.