代数双曲三角中的一组正交基.doc

李亚娟 邓重阳：内心细分法中调整切向的新方法内心细分法中调整切向的新方法*本课题得到国家自然科学基金(11026107, 60473130, 61003194,）资助。李亚娟（1977)，女，讲师，主要研究领域为计算机辅助设计与图形学。Email: ；邓重阳(1976),男,博士,副教授, 硕士生导师, 主要研究领域为计算机辅助几何设计,计算机图形学.李亚娟 邓重阳（杭州电子科技大学理学院 杭州 310018）摘 要：内心细分法是一种基于双圆弧插值的非线性细分方法, 其极限曲线具有保形、保圆、光顺等优点。给定初始点列及其切向, 内心细分法的每一个细分步骤分为两个阶段：首先根据老点及其切向确定新点及其临时切向, 然后调整临时切向用于下一步细分。本文对内心细分法中切向调整的方法进行了改进，使其计算简单、几何意义明显。大量的数值实例验证了极限曲线的G2连续性及光顺性与细分参数选择之间的关系。关键词：非线性细分方法 曲线插值 保形 保圆中图法分类号：TP391A new method for adjusting tangent vectors of the incenter subdivision schemeLi Ya-juan Deng Chong-yang(School of Science，Hangzhou Dianzi University,Hangzhou，310018, China )Abstract In Incenter subdivision scheme is a kind of non-linear subdivision scheme based on biarc interpolation. The advantages of the subdivision scheme including shape preserving, circle precision, fair limit curve. Given the initial point array and initial tangent vectors, there are two steps in each subdivision steps: firstly the new points and the provisional tangents should be determined, then the provisional tangents are adjusted for the next step. In this paper, we improve the method of modificaiton of the provisional tangents, with simple computation and the Obvious geometrical meaning. The relations between G2 continuous and fairness of the limit curves and the selection of parameter in subdivision process are examined by numerical examples.Keywords: non-linear subdivision scheme; curve interpolation; shape preserving; circle precision离散数据插值是计算机辅助设计(CAD)及计算机辅助制造(CAM)中一个比较活跃的研究领域1。最近，插值型细分方法以其简单、高效等优良性质在快速生成插值曲线方面引起越来越多的注意，并且已广泛应用于CAD、CAM、几何造型(GM)、计算机图形学(CG)等相关领域。以四点插值细分法2及其推广34为代表的线性细分方法规则简单，易于实现，而且容易分析其收敛性、光滑性，但较难控制极限曲线的形状。比如，在其极限曲线上有多余拐点及人为痕迹等5。针对四点插值细分法的这些缺陷，一方面，Marinov等5，Cai6，Dyn等7，金建荣等8提出了四点插值细分法的改进形式，使之具有局部可调68或保凸57等性质；另一方面，出现了一些非线性910及基于几何51112的细分方法。这些方法具有一些新的性质，比如容易推广到曲面9，能达到保形(凸)的要求5101112等，但其极限曲线只能达到G1连续。除收敛性及光滑性外，保形性也是曲线设计中的一个重要问题。由于保形性通常被认为是一个非线性或几何问题，所以用线性细分方法得到的细分曲线通常难以达到保形的要求。例如，线性细分方法一般只能在函数型数据713的条件下达到保形的要求。而基于几何的细分方法达到保形的要求相对比较容易。Dyn 等11，Yang12，Marinov等5都提出过基于几何的保形(凸)细分方法。在曲线设计中，光顺性往往是比保形性更高的要求。一条平面曲线是光顺的，除了保形(没有多余拐点)外，还要求曲率连续且变化较均匀(曲率极值点少)14(第218页)。上述提到的保形细分方法达不到曲率连续的要求，更谈不上曲率变化较均匀。三进制四点插值细分方法3能得到曲率连续的曲线，但不保形；而且从基函数的图象来看，其曲率变化是不均匀的(参见第3节的数值实例)。Kobblet15基于曲线能量最小化提出的变分细分方法得到的极限曲线可以认为是曲率连续、曲率变化较均匀，但不具备保形性。Deng和Wang基于双圆弧插值给出了一种具有保形性、保圆性和光顺性的非线性细分方法内心细分法16。该方法由于新加点为切线与边夹角平分线的交点, 即三角形的内心而得名。内心细分法中每个细分步骤中都要调整所有点的切向。内心细分法对于任意给定的初始数据具有保形性；如果所有的初始点取自圆弧段，则极限曲线就是该圆弧段；通过细分过程中的参数调节能得到光顺的极限曲线。缺点是每个细分步骤中切向调整的方法比较复杂，计算量偏大, 而且几何意义不明显。本文对内心细分法中切向调整的方法进行了改进，使其计算大大简化，并具有明显的几何意义，同时继承了其保形性、保圆性和光顺性的优点。1.细分过程1.1 内心细分法相关记号先介绍内心细分法的相关知识和记号16。给定初始点列，初始切向为过三点的圆在处的单位切向量。其中，若三点共线，则；对开曲线的端点，取为过三点的圆在处的单位切向量；末端点的初始切向取法类似。记细分次后的新点为，从到与从到的有向角分别为,，根据，边可以分为如下三类(见图1)：定义1 若，边为凸边；若，边为拐边；若，边为直边。为了叙述方便，先考虑初始边仅含凸边和拐边的情况，的情形在1.5节处理。点也可以分成两类：定义2 若，点为凸点；若，点为拐点。1.2 预处理在细分过程之前，先对进行预处理：若初始边是拐边，在之间插入新点 ，这里由用户给定。在第3节的数值实例中我们取=0.5。处的切向为：旋转矩阵。此时拐边被两个凸边，取代，而成为拐点(见图1(b)。经过预处理步骤后初始边中没有拐边，预处理后的初始数据我们仍记为。图1. 边的分类 (a) 凸边 (b)拐边 (c) 直边1.3 新点计算内心细分法每一次细分步骤中，都要计算一次新点。我们仍然沿袭内心细分法16中新点的细分规则，令，定义为与的平分线的交点，这里是的反向延长线。对每个，定义一个临时的切向，(见图1(a)。记从到及从到的角分别为，由的定义我们有 (1) (2)由式(1)(2)知存在圆弧段分别插值。注1: 若三点共线，则由定义知三点共线。所以若为拐点,则三点共线。注2: 由(1)(2)两式及定义2知，细分步骤中第k+1层与第k层所包含的拐点数相同。1.4 切向调整的新方法内心细分法16每一次细分步骤中，新点确定之后，都要给出临时切向，并计算新切向。但是切向调整的方法非常复杂，需要调整两个参数值，没有明确的几何意义（详见16第2.3节），我们提出一种切向调整的新方法，计算简单，几何意义明显。设过相邻三点的圆为，圆在处的单位切向量为。则处的新切向定义如下： (3)其中 ，且在拐点处(见图2)。图2 计算的切向 (a)凸点 (b) 拐点图2 计算的切向 (a)凸点 (b) 拐点注3: 若三点共线，即为拐点，退化为直线，则(见图2(b)。注4: 对于拐点，由(1)(3)两式，的夹角为，=。故的夹角= =，因此。注5: 对于开曲线的起点，其切向定义为，即关于的中垂线对称，末端点的切向可用类似的方法定义。若=，由平面几何知识及定义可知，在插值的圆上，且其临时切向与一致，从而。由此易知切向调整之后，同样具有保圆性：定理1 若所有的初始点及初始切向取自圆弧段,则极限曲线就是。为使极限曲线曲率连续，相邻两点的离散曲率须趋向于相等。按临时切向，插值的圆弧段与插值的圆弧段相切于，一般情况下，它们的半径不相等。所以若对所有均取，则极限曲线为G1连续的圆弧样条曲线。若对所有均取，则极限曲线的曲率虽然连续，但会剧烈波动，我们试验的很多例子证实了这一点.所以我们把取为的线性组合，这样可以使极限曲线连续且变化较均匀。更深入的讨论可参见第3节。对凸点,因为总是位于的同侧,而介于之间，由定义2易知与所包含的拐点数一样多，结合注2可知：定理2 由1.1-1.4节所定义的细分方法得到的极限曲线具有保形性.1.5 插入直线段 由1.4节的注4，拐点处的极限切向可用初始切向显式表示。利用这一结论，我们可以用与几何细分法16同样的方法，在细分曲线中光滑地插入直线段。若，则为直边，只需选取处的初始切向为即可，这里为从到的有向角(见图3(a)。时同样可插入直线段(见图3(b)。 图3 计算直边的切向 (a) 初始边 (b) 中间边2收敛性与光滑性记,首先我们有:定理3 对于第1节定义的细分方法，。证明：由(1)(2)两式知，。从而 ,，有。递推可得：， (4)故。这里表示不超过的最大整数。定理4 对于第1节定义的细分方法,其极限曲线收敛。证明：令为细分次后的控制多边形，我们来计算与间的距离。由定理3，存在，使得当时。记 是对应于边的新点，由正弦定理，。所以 。到边的距离为 .记，结合定理3有。因此，多边形序列是柯西序列，从而一致收敛。又每一个多边形都是分段线性曲线，故极限曲线连续。 定理5对于由第1节定义的细分方法，其极限曲线G1连续。证明：由于间的夹角小于，的夹角，因此间的夹角小于2。故有 (5)从而，即连续。又对每一点,结合(4)我们有.因此 是柯西序列，从而一致收敛。故极限曲线G1连续.3实例与分析本节给出几何细分法构造保形插值曲线的几个具体实例。为了更好地了解极限曲线的质量，我们同时画出了曲线上每点处的离散曲率(过相邻三点的圆的半径)，并与内心细分法16、三进制四点法3进行了比较。在效果图中初始控制顶点与控制多边形用黑色多边形表示，细分曲线用红线表示，离散曲率用绿线表示。从多次试验中我们得出，当时得到的曲线效果最好：曲率连续，曲率极值点少。当曲线的曲率波动较大，有较多的曲率极值点；而时，虽然曲率极值点少，但收敛速度较慢。我们选择了一些有代表性的初始点列来检验本文的细分方法。例1和例2中初始点列组成一个封闭多边形；例3(图6)的初始多边形是一个普通的凸多边形；例4(图7)的初始多边形是含拐点的开多边形；例5(图8)的初始多边形是边长分布较均匀的凸多边形；例6(图9)的初始多边形有一个内角较大，接近于。从效果图看，极限曲线都较为光顺。记为的离散曲率的差，。我们把例1-6中及的变化情况总结在表1中。从表1可以看出,当时，的收敛速度逐渐稳定于，当时，的收敛速度逐渐稳定于，当时，的收敛速度逐渐稳定于。这说明当时极限曲线是曲率连续的，但若太小，收敛较慢；若太大，收敛不一定快，且曲率的波动较大。在实际应用中，应选在0.25左右为宜，这时有较快的收敛速度，极限曲线也较为光顺，与参数调整好之后内心细分法效果基本相同。 (a) (b) (c) (d)(e)图4 例1 (a) 本文细分方法() (b) 内心细分法(c) 本文细分方法()(d) 本文细分方法()(e)三进制四点法(a) (b) (c) (d)(e)图5 例1 (a) 本文细分方法() (b) 内心细分法(c) 本文细分方法()(d) 本文细分方法()(e)三进制四点法 (a) (b)图6 例3 (a) 本文细分方法 (b) 内心细分法(a) (b)图7 例4(a) 本文细分方法 (b) 内心细分法 (a) (b)图8 例5 (a) 本文细分方法 (b) 内心细分法 (a) (b)图9 例6 (a) 本文细分方法 (b) 内心细分法4. 结论本文对几何细分法中切向调整的方法进行了改进，使算法变得简单有效，几何意义明显，并保留了原算法的保形性、保圆性、光顺性等优点。数值实例表明通过调整细分参数可以得到光顺的细分曲线，因而在设计高质量的插值曲线方面有较好的应用前景。参 考 文 献1 Ohtake Y, Belyacv A, Seidel HP. Interpolatory subdivision curves via diffusion of normals. Computer graphics international, 2003.2 Dyn, N, Levin D, Gregory JA. A 4-point interpolatory subdivision scheme for curve design. Computer Aided Geometric Design, 1987,4(3):257-268.3 Hassan MF, Ivrissimitzis IP, Dodgson NA, Sabin MA. An interpolating 4-point C2 ternary stationary subdivision scheme. Computer Aided Geometric Design, 2002,19(1), 1-18.4 Dyn N, Floater MS, Hormann K. A C2 four-point subdivision scheme with fourth order accuracy and its extensions. in Mathematical Methods for Curves and Surfaces: Tromso 2004, Daehlen M, Morken K, Schumaker LL(eds.), 2002:145-156.5 Marinov M, Dyn N, Levin D. Geometrically controlled 4-point interpolatory schemes. in: Advances in Multiresolution for Geometric Modeling, Dodgson NA, Floater MS, Sabin MA(eds), Springer-Verlag, 2004.6 Cai ZJ. Modified four-point scheme and its application. Computer Aided Geometric Design, 1998,15(2):251-260.7 Dyn N, Kuijt F, Levin D, van Damme R. Convexity preservation of the four-point interpolatory subdivision scheme. Computer Aided Geometric Design, 1999,16(8):789-792.8 Jin JR, Wang GZ. A non-uniform 4 point interpolatory subdivision scheme to construct curve. Applied Mathematics: A Journal of Chinese University, 2000,15(1):97-100. (in Chinese with English abstract)9 Aspert N, Ebrahimi T, Vandergheynst P. Non-linear subdivision using local spherical coordinates. Computer Aided Geometric Design, 2003,20(3):165-187.10 Ding YD, Hua XJ. Preserving-convexity and fractal properties of a nonlinear subdivision scheme. Journal of Software, 2000,11(9):1263-1267. (in Chinese with English abstract)11 Dyn N, Levin D, Liu DY. Interpolatory convexity-preserving subdivision schemes for curves and surfaces. Computer-Aided Design, 1992,24(4): 211-216.12 Yang XN. Normal based subdivision scheme for curve design. Computer Aided Geometric Design, 2006,23(4):243-260.13 LeMehaute A, Utreras FI. Convexity-preserving interpolatory subdivision. Computer Aided Geometric Design, 1994,11(1):17-37.14 Su BQ, Liu DY. Computational Geometry-Curve and surface Modeling. Academic Press, Boston,1989.15 Kobbelt L. A variational approach to subdivision. Computer Aided Geometric Design, 1996,13(8):609-630.16 Deng CY, Wang GZ. Incenter subdivision scheme for curve interpolation. Computer Aided Geometric Design, 2010,27(1):48-59附中文参考文献:8金建荣,汪国昭.构造曲线的插值型细分法非均匀四点法.高校应用数学学报,2000,15(1):10丁友东,华宣积.一类非线性细分格式的保凸与分形性质.软件学报,2000,11(9):1263-1267.14 苏步青,刘鼎元.计算几何.上海:上海科学技术出版社,1981.附录：表1 细分过程中曲率差的最大值及其收敛速率k012345678例1(a)0.587.88898761.6744380.70173141.0658590.66584928.3105460.68939418.5155240.65401512.8712210.6951588.4304630.6549855.7438950.6813263.8125660.663760例1(b)0.2587.88898755.5358660.63188732.2196250.58015917.8412870.5537409.5942980.5377585.0576320.5271502.6287940.5197681.3590450.5169840.7063180.519716例1(c)0.12587.88898771.6613530.81536257.5895080.80363446.1746680.80179037.0094610.80151029.6612090.80144919.0486120.80140415.2635950.80135212.2298640.801297例2(a)0.5229.645926139.0005070.73530079.5422970.82317650.0253280.62891531.4797140.62927621.7993250. 69248814.1146360. 6474809.7136160. 6881956.4341050.662380例2(b)0.25229.645926123.8826870.53945174.0968070.59812141.6192910.56168822.5557430.54195411.94490