《代数双曲三角中的一组正交基》由会员分享，可在线阅读，更多相关《代数双曲三角中的一组正交基（7页珍藏版）》请在金锄头文库上搜索。
1、李亚娟 邓重阳：内心细分法中调整切向的新方法内心细分法中调整切向的新方法*本课题得到国家自然科学基金(11026107, 60473130, 61003194,）资助。李亚娟（1977)，女，讲师，主要研究领域为计算机辅助设计与图形学。Email: ；邓重阳(1976),男,博士,副教授, 硕士生导师, 主要研究领域为计算机辅助几何设计,计算机图形学.李亚娟 邓重阳（杭州电子科技大学理学院 杭州 310018）摘 要：内心细分法是一种基于双圆弧插值的非线性细分方法, 其极限曲线具有保形、保圆、光顺等优点。给定初始点列及其切向, 内心细分法的每一个细分步骤分为两个阶段：首先根据老点及其切向确定新
2、点及其临时切向, 然后调整临时切向用于下一步细分。本文对内心细分法中切向调整的方法进行了改进，使其计算简单、几何意义明显。大量的数值实例验证了极限曲线的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, Ch
3、ina )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 step
4、s 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 m
5、eaning. 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)中一个比较活
6、跃的研究领域1。最近，插值型细分方法以其简单、高效等优良性质在快速生成插值曲线方面引起越来越多的注意，并且已广泛应用于CAD、CAM、几何造型(GM)、计算机图形学(CG)等相关领域。以四点插值细分法2及其推广34为代表的线性细分方法规则简单，易于实现，而且容易分析其收敛性、光滑性，但较难控制极限曲线的形状。比如，在其极限曲线上有多余拐点及人为痕迹等5。针对四点插值细分法的这些缺陷，一方面，Marinov等5，Cai6，Dyn等7，金建荣等8提出了四点插值细分法的改进形式，使之具有局部可调68或保凸57等性质；另一方面，出现了一些非线性910及基于几何51112的细分方法。这些方法具有一些新的
7、性质，比如容易推广到曲面9，能达到保形(凸)的要求5101112等，但其极限曲线只能达到G1连续。除收敛性及光滑性外，保形性也是曲线设计中的一个重要问题。由于保形性通常被认为是一个非线性或几何问题，所以用线性细分方法得到的细分曲线通常难以达到保形的要求。例如，线性细分方法一般只能在函数型数据713的条件下达到保形的要求。而基于几何的细分方法达到保形的要求相对比较容易。Dyn 等11，Yang12，Marinov等5都提出过基于几何的保形(凸)细分方法。在曲线设计中，光顺性往往是比保形性更高的要求。一条平面曲线是光顺的，除了保形(没有多余拐点)外，还要求曲率连续且变化较均匀(曲率极值点少)14(
8、第218页)。上述提到的保形细分方法达不到曲率连续的要求，更谈不上曲率变化较均匀。三进制四点插值细分方法3能得到曲率连续的曲线，但不保形；而且从基函数的图象来看，其曲率变化是不均匀的(参见第3节的数值实例)。Kobblet15基于曲线能量最小化提出的变分细分方法得到的极限曲线可以认为是曲率连续、曲率变化较均匀，但不具备保形性。Deng和Wang基于双圆弧插值给出了一种具有保形性、保圆性和光顺性的非线性细分方法内心细分法16。该方法由于新加点为切线与边夹角平分线的交点, 即三角形的内心而得名。内心细分法中每个细分步骤中都要调整所有点的切向。内心细分法对于任意给定的初始数据具有保形性；如果所有的初
9、始点取自圆弧段，则极限曲线就是该圆弧段；通过细分过程中的参数调节能得到光顺的极限曲线。缺点是每个细分步骤中切向调整的方法比较复杂，计算量偏大, 而且几何意义不明显。本文对内心细分法中切向调整的方法进行了改进，使其计算大大简化，并具有明显的几何意义，同时继承了其保形性、保圆性和光顺性的优点。1.细分过程1.1 内心细分法相关记号先介绍内心细分法的相关知识和记号16。给定初始点列，初始切向为过三点的圆在处的单位切向量。其中，若三点共线，则；对开曲线的端点，取为过三点的圆在处的单位切向量；末端点的初始切向取法类似。记细分次后的新点为，从到与从到的有向角分别为,，根据，边可以分为如下三类(见图1)：定
10、义1 若，边为凸边；若，边为拐边；若，边为直边。为了叙述方便，先考虑初始边仅含凸边和拐边的情况，的情形在1.5节处理。点也可以分成两类：定义2 若，点为凸点；若，点为拐点。1.2 预处理在细分过程之前，先对进行预处理：若初始边是拐边，在之间插入新点 ，这里由用户给定。在第3节的数值实例中我们取=0.5。处的切向为：旋转矩阵。此时拐边被两个凸边，取代，而成为拐点(见图1(b)。经过预处理步骤后初始边中没有拐边，预处理后的初始数据我们仍记为。图1. 边的分类 (a) 凸边 (b)拐边 (c) 直边1.3 新点计算内心细分法每一次细分步骤中，都要计算一次新点。我们仍然沿袭内心细分法16中新点的细分规
11、则，令，定义为与的平分线的交点，这里是的反向延长线。对每个，定义一个临时的切向，(见图1(a)。记从到及从到的角分别为，由的定义我们有 (1) (2)由式(1)(2)知存在圆弧段分别插值。注1: 若三点共线，则由定义知三点共线。所以若为拐点,则三点共线。注2: 由(1)(2)两式及定义2知，细分步骤中第k+1层与第k层所包含的拐点数相同。1.4 切向调整的新方法内心细分法16每一次细分步骤中，新点确定之后，都要给出临时切向，并计算新切向。但是切向调整的方法非常复杂，需要调整两个参数值，没有明确的几何意义（详见16第2.3节），我们提出一种切向调整的新方法，计算简单，几何意义明显。设过相邻三点的
12、圆为，圆在处的单位切向量为。则处的新切向定义如下： (3)其中 ，且在拐点处(见图2)。图2 计算的切向 (a)凸点 (b) 拐点图2 计算的切向 (a)凸点 (b) 拐点注3: 若三点共线，即为拐点，退化为直线，则(见图2(b)。注4: 对于拐点，由(1)(3)两式，的夹角为，=。故的夹角= =，因此。注5: 对于开曲线的起点，其切向定义为，即关于的中垂线对称，末端点的切向可用类似的方法定义。若=，由平面几何知识及定义可知，在插值的圆上，且其临时切向与一致，从而。由此易知切向调整之后，同样具有保圆性：定理1 若所有的初始点及初始切向取自圆弧段,则极限曲线就是。为使极限曲线曲率连续，相邻两点的
13、离散曲率须趋向于相等。按临时切向，插值的圆弧段与插值的圆弧段相切于，一般情况下，它们的半径不相等。所以若对所有均取，则极限曲线为G1连续的圆弧样条曲线。若对所有均取，则极限曲线的曲率虽然连续，但会剧烈波动，我们试验的很多例子证实了这一点.所以我们把取为的线性组合，这样可以使极限曲线连续且变化较均匀。更深入的讨论可参见第3节。对凸点,因为总是位于的同侧,而介于之间，由定义2易知与所包含的拐点数一样多，结合注2可知：定理2 由1.1-1.4节所定义的细分方法得到的极限曲线具有保形性.1.5 插入直线段 由1.4节的注4，拐点处的极限切向可用初始切向显式表示。利用这一结论，我们可以用与几何细分法16
14、同样的方法，在细分曲线中光滑地插入直线段。若，则为直边，只需选取处的初始切向为即可，这里为从到的有向角(见图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实例与分析本节给出几何细分法构造保形插值曲线的几个具体实例。为了更好地了解极限曲线的质量，我们同时画出了曲线上每点处的离散曲率(
