【机械类毕业论文中英文对照文献翻译】一种约束引导G1连续样条曲线
收藏
资源目录
压缩包内文档预览：
编号：77687070
类型：共享资源
大小：1.18MB
格式：RAR
上传时间：2020-05-07
上传人：柒哥
认证信息
个人认证
杨**（实名认证）
湖南
IP属地：湖南
6
积分
- 关 键 词：
-
机械类毕业论文中英文对照文献翻译
机械类
毕业论文
中英文
对照
文献
翻译
一种
约束
引导
G1
连续
曲线
- 资源描述：
-
【机械类毕业论文中英文对照文献翻译】一种约束引导G1连续样条曲线,机械类毕业论文中英文对照文献翻译,机械类,毕业论文,中英文,对照,文献,翻译,一种,约束,引导,G1,连续,曲线
- 内容简介：
-
一种约束引导G1连续样条曲线D.S.温顺*,B.H. Ong, D.J.沃顿计算机科学部门,温尼伯,加拿大马尼托巴大学R3T 2 n2 接收于2001年12月23日,修订于2002年3月1日,发表于2002年3月5日摘要：本文为画引导G1连续平面样条曲线落在一个封闭的边界提供了一种方法。曲线是由片段的二次多项式(抛物线)和有理的二次方程式论（圆锥曲线),以及加入连续单元切线向量组成。这边界是由直线段和圆弧组成。爱思唯尔的科学有限公司于2002年出版。关键词:引导G1样条曲线;限制曲线1.介绍本文为画引导G1连续平面样条曲线落在一个封闭的边界提供了一种方法。曲线是由片段的二次多项式(抛物线)和有理的二次方程式论（圆锥曲线),以及加入连续单元切线向量组成。这边界是由直线段和圆弧组成。用户运用该类型方法设置解决方案时面临几个问题。如用户可能希望在一个给定的地区设计一条适合的曲线。例如,当设计一个形状被削减的平板材料时；另外，也有用户可能希望设计一个平滑的路径来避免障碍。例如,当设计一个机器人路径时。画约束曲线面临的问题，以前已经有所研究了。在参考文献2中有描述,G2连续的、保持形状的曲线由在给定点插入有理三次曲线组成,给定点可以位于一条线或者几条线的一侧。在参考文献4中,提出直接由Bezier曲线和固定横截面积组成。参考文献5中，提出G2连续曲线由有理的三次曲线,该曲线为在给定点插入得出，给定点可以在任意的多边形中。在参考文献1中,一条C1连续的非参数插入有理曲线(立方线性分子和分母),曲线可以在上面、下面或者折线之间已经被讨论。在参考文献6中,发现了G2连续曲线的由非参数有理三次曲线组成,该曲线躺在一条线的一边,或者二次曲线的一边。在参考文献7中，连续的、形状保留的C1曲线被发现，该曲线与最小曲率插值的三次样条。曲线是在一个限制任意多边形中。在这篇论文中，边界是由直线段和圆弧组成,这不同与其他论文所研究的。这里的曲线是二次,大多数其他结果用三次曲线,二次曲线通常导致简单的理论和简单的算法。最后,这里的曲线是由控制点引导而不是通常运用的插值点。用户通过二次的B样条的控制点和统一的结引导曲线。在最简单的情况下,第三节中,B样条控制多段线不相交的边界。b样条可以表示为一组Bzier曲线。如果一个特定的二次Bzier曲线不与任何的边界相交,它被接受。如果是与任意边界相交,那么取而代之的是理性的二次是Bzier 曲线，该曲线有相同的是zier控制点,但与边界不相交。相同的zier控制点的使用要确保收集的是zier曲线来源于一条连续的G1曲线。第三节中描述的方法总能确定一条不与边界相交的有理的二次曲线(见定理1)。在第四节,B样条曲线控制多段线允许在一些点与边界相交，曲线不穿过边界通常是可以产生的。用户可以操作b样条控制点交互式地使曲线有特定边界，而不是使用本文提供的方法。但是，这里的方法试图帮助用户在这个过程实现部分自动化。这里的方法也可以得到一个曲线,该曲线准确地通过(在计算精度内)边界的一个角落,或者与边界相切。这些结果可能难以实现交互式。这里使用的方法也给更多局部控制只有一个zier段更改为避免越过边界,而调整b样条控制点会导致三个zier段改变。一些等特殊要，例如：对边界的线段画曲线的切线；画一条沿着边界线段的曲线；以及画出第三节结束时讨论边界的尖端。 2。一些关于有理二次zier曲线的结论考虑有理的二次zier曲线函数B(t,w)(参数w)，以及非零区zier控制三角形B0B1B2,0t1,0w随着参数变化，曲线有以下圆锥曲线论:w1时，给出了一个椭圆的一段；w1时，给出了一个抛物线的一段；w1时，给出了一个双曲线的一段3。尽管（）中定义的曲线不允许w0或w趋于无穷大,对于的两个极端是很有益处的。如果这些值是允许的,B(t,0)将为线段B0B2,而B(t,)将是点是点点（见图一）。图1.曲线(1)通过给定点P结论1:曲线(1)的位置。曲线(1)上的点是一种加权平均的控制点B0,B1, B2。对于例(1)中的限制条件,所有的根是有效的,因此所有点B(t,w)是严格控制在三角形B0B1B23(见图2)。图2.曲线(1)充满控制三角形并嵌套结论2:曲线(1)通过一个给定的点。w值通过给定点P的曲线(1)可以找到，如后面描述的那样。 因为所有的点在曲线(1)严格控制三角形内B0B1B2(结果1),P内也必须严格在三角形内。下面的发展发现在(0,1)和w 在t(0,1),得到（，）。由于P - B1,考虑到线的交叉点通过B0和B，（），随着线穿过 B1和P,（）(见图1)。和的值在交叉点是 (2)r和s值在交点一起代表二维向量的标量积。由于P是内部控制三角形B0B1B2、01以及1,给定的t的交叉点也是B(t,0),这允许t的解决方案独立于w3。线段B0B2 来源于公式(1) (3)所以t的二次方程 (4)因为0r1,在t(0,1)有一根。该根从公式(4)可以得到。为了使（）/有效,最后得到 (5)它在(0,1)点，其中0r1。向量B(t,0)P和P B1是平行的,当1时，指向同一方向,或者 (6)在式(6)中替换公式(3)在，得到式(中5)一旦t值被找到，从式(1)中得到相应的积极(见式(7)值w, （8）总结前面的两个结果得到引理1。引理1。如果P是严格内部zier控制三角形B0B1B2,那么是一个独特的曲线(1)通过P点 .如果P不是控制三角形内,那么就没有曲线(1)经过了点，t 和w值联立式(5)、(2)和(8)可以得出。结果3:控制三角形填充和嵌套属性。结论2显示,有一个独特的曲线(1)通过任何严格控制在三角形B0B1B2内部的P 点。这个事实意味着曲线(1)完全填满三角形B0B1B2的内部。事实上曲线(1)通过任何的P点是独一无二，意味着有不同w值的两个曲线(1)不能在控制的三角形内相交，因为交叉点会被一条以上的曲线通过(见图2)。对式(1)求偏导数，w是向量这个向量的方向在w点是恒定的,如此点B(t,w)的轨迹与t和增加w是固定的直线从B(t,0)到B1。因此,随着w从0到1曲线族(1)形成一套嵌套的曲线；w趋向于0 时，曲线(1)往往是线段B0B2的一部分,随着w趋向于时，曲线(1)往往是多线段B0B1和B1B2的一部分。如果曲线(1)在w一定时,那么所有曲线(1)的w值在曲线和折线B0B1B2之间。结果4:曲线(1)是给定的线段的切线。曲线(1)的w值是可以找到的，该曲线是给定线段S0S1(S0和S1是不同的) 的切线，这个结论在后面有描述。它在第四节中描述的方法中使用。这个过程是找到曲线(1)的第一步，该曲线与通过点S0和S1无限线L相切,然后来确定切点是否在线段S0S1上。直线必须通过控制三角形，这对于切线是可能的(见图3)。它现在讨论切线L不能被B0B2割开,也不能通过B1点。曲线(1)是圆锥曲线的一段,圆锥曲线的特性是他们不与任何的切线交叉。曲线(1)连接B0、B2点,所以它将穿过任何切割B0B2的直线;因此,切线L不能切割B0B2。特别值得一提的是,不能通过B1和穿过B0B2。如果L通过B1和不穿过B0B2,那么曲线(1)不能切割，因为不进入控制三角形B0B1B2。因此,切线L不可能通过B1。在后面的计算中,首先检查L是曲线B(t,w)的切线,然后检查切点在线段S0S1上。如果曲线(1)与L相切,然后切点B(t,w)必须在L上,或 （9）方程B(t,w)对t求偏导数，必须与平行,或 （10）使用式1),式(9)可以写成, （11）由，式（）分解出为 （12）对式(12) 两边求叉积，将S1S0代入和联立（9）和（10）得 （13） 式(11)的左边是t的二次方 （14）式(11)和(13)表明,该二次方程对t有双根。因为B1不在L上,代入非零数量分解式(14)的得出 （15）其中： （16）把A、w、C作为二次Bezier曲线的参数，为了使w值有效以及式15在（0，1）有双根，方程必须A0且C0,A0和C0，故分母不为零,。虽然这t值在(0,1),函数P=B(t,w)的切点可能不在线段S0S1上,所以最后一步检查是必要的,即 （19）上面的结果总结为引理2。引理2。如果是Bezier控制三角形B0B1B2有非零区域，无限线L通过极点S0S1但不穿过线段B0B2，B1不在L上,式(16)中的A和C都是都是无意义的,式(19)有意义,那么存在一个独特的曲线(1)与线段S0S1相切。否则,没有曲线(1)与线段S0S1相切。w 和t在切点的值在方程式(17)和(18)得出,A和C在式(16)中给出。结论5:曲线(1)给定的圆弧相切。与给定圆弧相切的w值如后面描述的那样可以找到。圆弧由两个不同的端点S0和S1,以及非零幅度角你从S0和S1(逆时针方向有效)确定。让C成为圆的一部分。过程是首先找到一个曲线(1)与C相切,然后检查切点是否在给定的弧(见图4)。图4.曲线(1)弧S0S1切线于P点如果有意义,让U的单位向量由S1S0方向旋转/2；如果是无意义的,让U的单位向量由S1S0方向旋转-/2 。圆的中心C和半径E是：通过类比结论4,如果曲线(1)与以E为圆心和r为半径的圆切线,那么方程 （20）t存在两解。联立式(1)，式(20)变为 （21）式(21)的左边写成伯恩斯坦形式是： (22)其中 多项式(22)转换成功率形式为 （23）其中切线切线发生在式(22)的t具有双根时；检查双根的方法在附录A中有描述。式(23)中t有双根的条件，D=0 ，其中D的定义在附录A,导致一个w的八阶多项式方程。这里只有与在(0,1)点的t值相对应的有效w值是可以接受的。圆的任意切点,需要检查点是否在弧上。这一过程的结果是一系列曲线(1)的w值(可能是空的)。请注意,曲线(1)可能与弧存在两个切点,可能会有几条曲线(1)与弧相切。只要最大的w值被求出之后,曲线(1)的多重性将不是问题。结果5可以重申以下引理3。引理3。如果Bezier 控制三角形B0B1B2是非零区域,S0和S1是弧的不同端点,弧的角度是非零,w值有效，式（21）中的t存在双根，t在（0,1）处，切点的范围是从S0到S1，并且，至少存在一条曲线（1）与弧S0S1相切。否则,不存在曲线(1)与弧S0S1相切。3.约束曲线绘制问题的解决方案解决约束曲线绘图问题，在这一节中提出的是基于二次b样条有统一的结情况下。在本节中,假定b样条控制多段线与约束边界不相交。一个典型的二次b样条控制多线控制点P0,P1,P2。相应的二次Bezier控制点是:如果二次b样条的控制多段线是封闭的，那么，相应的二次是Bezier控制多线曲线遵循相同的路径;如果二次B样条控制多段线是开放的,那么相应的二次Bezier曲线控制的多段线遵循相同的路径,但略短(在两端)。因此,如果B样条控制多段线与边界不相交,那么对应的Bezier控制多段线与边界也不相交。自此以后,引用的Bezier控制多段线及其相应Bezier曲线，而不是B样条控制多段线和曲线。此外,每个Bezier部分可以单独考虑，因为整体G1的连续性是由Bezier控制多段线保证。图5。二次b样各种权重在讨论算法之前,考虑一个默认的重量w和检查两个简单的案例是有用的。只要有可能,将使用二次曲线(抛物线,w=1) 而不是一个有理的二次曲线(圆锥,w 1)。默认选择似乎能给出“好”的曲线,虽然是有些武断,也可以选择不同。选择w=1确实给用代数方法最简单的曲线。即使不同的选择,它也不会太远离1。图5灰色部分显示了控制多段线和有三种不同的权重值二次B样条；重量w=1给出了曲线的三个中“最好”的曲线。案例1:(边界不进入控制三角形B0B1B2)。在这里,控制三角形完全在边界的一侧(见图6)。因为所有的曲线(1) 完全在三角B0B1B2内,没有一个与边界相交。二次Bezier段和w=1的曲线(1)将用于最后的曲线的一部分。图6。案例1:边界不进入Bezier 控制三角形的B0B1B2图7.案例2:边界穿越线段B0B2案例2:(边界进入控制三角B0B1B2，并与B0B2一部分相交)。自从Bezier控制多段线与边界不相交,Bezier曲线段与边界相交的唯一方式是如果边界切割线段B0B2(见图7)。所有的直线边界段的端点都进入边界。如果边界部分允许该值将优先用w=1。图7.案例2:边界穿越线段B0B2图8。曲线受到一个封闭的边界在图8中,曲线(1)来源于B样条控制点P1,P2和P3，为了避免圆形边界的一部分被切，使用w高于1。曲线(1)来源于B样条曲线的控制点的P3,P4,和P5，为了避免通过边界角与边界相交，使用w值高于1。在这两个案例中，w=1的曲线(1)用灰色表示。在所有的其他部分,w=1给出了不穿过边界的曲线。绕过边界的曲线用黑表示。定理1。如果引导B样条控制多段线与边界不相交,然后由前面的算法得出的G1连续曲线与边界不相交。证明。该定理遵循事实是通过增加足够参量w值，曲线(1)将无限接近Bezier控制多段线B0B1B2。因为Bezier控制多段线与边界不相交,可以找到不与边界相交的整体G1连续的曲线的w值。引理1和3知道可以找到不与曲线（1）相交的边界，该边界有直线和圆弧边界段。特别情况。通过b样条控制点的位置，可以有几种特别结果。为了曲线与边界直线段相切,把两个连续的b样条控制点放在同一边界直线段。这将产生一条切点在两连续两个控制点中点的曲线。在图9中,B样条控制点P1和P2在边界上，并且曲线的切点在P1+P2/2处。为了使曲线在指定点与边界相切,在边界安排两个连续B样条控制点,保证给定的点是它们之间即可。图9。特别features-tangent边界,边界,尖端边界。画一条沿着边界直线段的曲线,只要把超过两个的连续控制点在同一的边界线段。二次B样条产生一些二次Bezier直线段,同时保持G1连续性。在图9中,B样条控制点P4、P5和P6在边界上。其中从（P4+P5）/2到（P5+P6）/2为直线段。强迫一个尖端在边界点,把两个B样条控制点放在边界上。当然,曲线在尖端不会是G1连续曲线。在图9中,B样条控制点P8和P9相同，则尖端就在那一点上。4。延伸允许控制多线穿过边界图10。Extension-allow控制点之外的边界可以有一些b样条控制点在边界外并依然产生不穿过边界的曲线。Bezier的B0和B2点必须保持在边界内而B1可以外。这种情况下,边界通过穿过从线段B0B1到线段B1B2可以部分进入控制三角形B0B1B2。边界在这样的片段给了w参量的上界；让wH最小(参见图10)。与此同时,通过像第三节提到那样穿入穿出线段B0B2，边界的一部分可以进入控制三角形B0B1B2。该部分段放在更低的w参量界限上；让wL成为最大。如果wHwL,那么不可能满足这两个限制,因此不存在曲线曲线(1)穿过边界，并且要求曲线G1厄密数据相匹配。否则存在三例w参量的选择。如果,选择wL；如果，选择wH。总而言之，选择靠近1的值。 一个例子显示曲线完全包含在边界内，如图11。请注意,许多B样条控制点在边界外。图11。Extension-some控制点之外的边界5。结论画一个G1平面曲线,曲线避免了约束边界由直线段和圆弧组成，方法在上面已经得出。曲线是由控制点和由参数二次方程式论和参数有理二次方程式论组成共同引导。一个二次方程必须通过直线边界段解决,而第四阶方程必须通过圆弧边界段解决。致谢作者感谢自然科学和加拿大工程研究理事会对该项研究的资金支持。同时感谢两个匿名的论文裁判,他们的建议帮助提高本文的编写。附录A四阶多项式存在一个零点的多样性条件进行阐述。条件是来自多个零, 多项式的最大公约数和它的衍生品的程度高于0。一般情况下是在一些特殊的情况下发生。一般情况下:让第四度多项式令为r0(t),并让其衍生物令为4 r1(t),其中：并假设a0。如果r0(t)除以r1(t)；结果与变量a组成分数，a作为分母。为了避免这些分数,从一个ar0(t)开始,得其中商q2(t)和余数r2(t)为以及假设A0(见后面附件A=0的情况）。如果r1(t)除以r2(t),结果与3A2组成分数，分母为3A2。为了避免这些分数,从3A2r1(t)开始,得到其中商q3(t)和余数r3(t)为以及假定B0(见后面的附录B=0情况)。如果r2(t)除以r3(t)，将结果与B2组成分数，分母为B 2。为了避免这些分数,从B 2r3(t)开始，得其中商q4(t)和余数r4(t)为其中如果D0，然后r0(t)没有重根；如果D=0，r0(t)在t=-(C/B)处有重根，并且其根为r3(t)A=0情况。如果A=0和ad-bc0,r2(t)是线性的。r1(t)除以r2(t)的余数是常数。如果这个常数非零,那么r0(t)没有多零;如果这个常数为零,那么r0(t)在t=-(ae-bd)/3(ad-bc)处有一个重根。如果A=0和ad-bc0,那么r2(t)是常数ae-bd。如果这个常数非零,那么r0(t)没有多零;如果这个常数为零,那么r0(t)在t=-（b/a）处有四个重根。A0，B=0情况。如果B=0,r3(t)是常数C。如果C非零,那么r0(t)没有多重根;如果C为零,那么r0(t)在r2(t)零点处有多重根。如果r2(t)的两零点相等，那么r0(t)有三重根；如果r2(t)的两零点不相等，那么r0(t)有两重根；参考文献1段Q,徐G,刘A,王X,程F.约束插值运用有理三次样条曲线与线性分母。韩国J 北京:数学1999;6:203-15。2古德曼TNT,Ong波黑,昂斯沃思k .约束插值运用有理的立方样条曲线。在:截至G,编辑。NURBS曲线和曲面设计。费城:暹罗,1991年。59 - 74页。3李表ETY。有理Bezier表示圆锥。在:截至G,编辑。几何建模:算法和新趋势。费城: 暹罗,1987年。3-19页。4诺瓦茨基H,刘D,陆x，整流罩Bezier曲线与约束。计算机辅助Geomet Des 1990；7:43-55。5Ong波黑 ,温顺DS,沃尔顿DJ。约束插值与有理三次曲线。在职。6Ong波黑,昂斯沃思k .非参数约束插值。在: 舒梅克LL Lyche T,编辑。数学方法在计算机辅助几何设计。纽约:学术出版社,1992年版。419 - 30页。7张C、程f .限制一种保形参数曲线与最小曲率插值。预印本。Dereck温顺是马尼托巴大学计算机科学教授，温尼伯,加拿大。1973年马尼托巴湖大学研究样条逼近获得了博士学位。他目前的研究包括利益包括多项式和非多项式样条曲线。他最近在圆弧样条曲线(加工应用程序), 回旋曲线(高速公路路线设计),多项式样条函数 (埃尔米特插值多项式曲线),螺旋(公平的曲线设计)和表面三维造型。Boon-Hua Ong，马来西亚理工大学数学科学学院副教授，马来西亚。她收到了一个二元同步通信和马来西亚大学获得理学硕士学位, 和美国加州大学伯克利分校的数学博士学位。她目前的研究计算机辅助几何设计。德斯蒙德j沃尔顿是马尼托巴大学的计算机科学教授。他在1978年获得了马尼托巴大学博士学位。他的研究兴趣包括计算机图形学的应用,计算机辅助几何设计和CAD/CAM数值分析。沃顿教授花了几年的马尼托巴省部门高速公路和交通,他感兴趣有关高速公路设计的几何问题。他还花了一年时间在加拿大工业技术研究所留学，他对曲线设计CAD应用程序特别有兴趣。 湖 南 科 技 大 学 英文文献翻译学 生 姓 名： 吕小斌 学 院： 机电工程学院 专业及班级： 机械设计制造及其自动化 学 号： 1103010514 指导教师： 黄东兆 2015年 5 月 27日A constrained guided G1continuous spline curveD.S. Meek*, B.H. Ong1, D.J. WaltonDepartment of Computer Science, University of Manitoba, Winnipeg, Canada R3T 2N2Received 23 December 2001; revised 1 March 2002; accepted 5 March 2002AbstractA method for drawing a guided G1continuous planar spline curve that falls within a closed boundary is presented. The curve is composedof segments of quadratic polynomials (parabolas) and rational quadratics (conics) that join with continuous unit tangent vectors. Theboundary is composed of straight line segments and circular arcs.q 2002 Published by Elsevier Science Ltd.Keywords: Guided G1spline curve; Constrained curve1. IntroductionA method for drawing a guided G1continuous planarspline curve that falls within a closed boundary is presented.The curve is composed of segments of quadratic poly-nomials (parabolas) and rational quadratics (conics) thatjoin with continuous unit tangent vectors. The boundary iscomposed of straight-line segments and circular arcs.There are several problems whose solution requires thistype of method. A user may wish to design a curve that fitsinside a given region as, for example, when one is designinga shape to be cut from a flat sheet of material. A user maywish to design a smooth path that avoids obstacles as, forexample, when one is designing a robot path.The problem of drawing constrained curves has beendiscussed previously. In Ref. 2, a G2continuous, shape-preserving curve made of rational cubics that interpolates togiven points and that lies on one side of a line, or severallines, is described. In Ref. 4, fair Be zier curves with fixedcross-sectional area are produced. In Ref. 5, a G2continuous curve made of rational cubics that interpolatesto given points inside an arbitrary polygon is presented. InRef. 1, a C1continuous non-parametric interpolatingrational (cubic numerator and linear denominator) that liesabove, below, or between polylines is discussed. In Ref. 6,a G2continuous curve made of non-parametric rationalcubics that lies on one side of a line, or one side of aquadratic curve is found. In Ref. 7, a C1continuous shape-preserving interpolating cubic spline with minimum curva-ture is produced. The curve is constrained to lie inside anarbitrary polygon.In this paper, the boundary consists of straight linesegments and circular arcs, which is different thanboundaries considered by other papers. The curve here isquadratic, most other results use cubics, and the quadraticgenerally results in simpler theory and simpler algorithms.Finally, the curve here is guided by control points ratherthan by the more commonly used interpolation points.TheuserguidesthecurvewithcontrolpointsofaquadraticB-spline with uniform knots. In the simplest case, Section 3,the B-spline control polyline does not intersect the boundary.A B-spline can be expressed as a set of Be zier curves. If aparticularquadraticBe ziercurvedoesnotintersectanypartofthe boundary, it is accepted. If it does intersect any part of theboundary, then it is replaced by a rational quadratic Be ziercurve that has the same Be zier control points, but which doesnotintersecttheboundary.TheuseofthesameBe ziercontrolpoints ensures that the collection of Be zier curves forms a G1continuous curve. The method described in Section 3 canalways determine a rational quadratic curve that does notintersect the boundary (see Theorem 1). In Section 4, the B-spline control polyline is allowed to intersect the boundaryat some points, and a curve that does not cross the boundarycan often be produced.A user could manipulate the B-spline control pointsinteractively to cause the curve to fall within the boundaryrather than use the method presented in this paper. However,the method here attempts to aid the user by partlyautomating the process. The method here can also give a0010-4485/03/$ - see front matter q 2002 Published by Elsevier Science Ltd.PII: S0010-4485(02)00086-6Computer-Aided Design 35 (2003) 591599/locate/cad1Visiting from Universiti Sains Malaysia, 11800 Penang, Malaysia.*Corresponding author. Tel.: 1-204-474-8681; fax: 1-204-474-7609.E-mail address: dereck_meekumanitoba.ca (D.S. Meek).curve that passes exactly (within computational accuracy)through a corner of the boundary, or that is exactly tangentto the boundary. Those results could be difficult to achieveinteractively. The method used here also gives morelocalized control as only one Be zier segment may bechanged to avoid crossing the boundary, while adjusting aB-spline control point will cause three Be zier segments tochange.Special requirements such as having the curve tangent toa line segment of the boundary, having the curve run along aline segment of the boundary, and having a cusp on theboundary are discussed at the end of Section 3.2. Some results on rational quadratic Be zier curvesConsider the family (parameter w) of rational quadraticBe zier curves B(t,w) with non-zero area Be zier controltriangle B0B1B2,Bt;w Qt;wqt;w1 2 t2B0 2w1 2 ttB1 t2B21 2 t2 2w1 2 tt t2;0 , t , 1; 0 , w , 1;1The members of this family of curves are segments ofconics: w , 1 gives a segment of an ellipse, w 1 gives asegment of a parabola, and w . 1 gives a segment of ahyperbola 3. Although the curves as defined in Eq. (1) donot allow w 0 or w tending to infinity, these two extremew-values are of interest. If these values were allowed, B(t,0)would be the line segment B0B2, while B(t,1) would be thepoint B1(see Fig. 1).Result 1: Location of curves (1). The points on a curve(1) are a weighted average of the control points B0, B1, andB2. With the restrictions on t and w in Eq. (1), all of theweights are positive, so all points B(t, w) are strictly insidethe control triangle B0B1B23 (see Fig. 2).AResult 2: The curve (1) that passes through a given point.The w-value of the curve (1) that passes through a givenpoint P can be found as described later. Since all points onthe curves (1) are strictly inside the control triangle B0B1B2(Result 1), P must be strictly inside as well. Thedevelopment below finds the t in (0,1) and w in (0,1)such that Bt;w P:Since P B1, consider the intersection of the linethrough B0and B2, 1 2 rB0 rB2; with the line throughB1and P, 1 2 sB1 sP (see Fig. 1). The r and s values atthe intersection point arer B12 P B12 B0B12 P B22 B0s B12 B0 B22 B0B12 P B22 B0;2wherestands for the scalar cross product of two-dimensional vectors. Since P is inside control triangleB0B1B2, 0 , r , 1 and 1 , s. The point of intersection fora given t is also B(t,0), and this allows the solution of tindependently of w 3. The line B0B2is from Eq. (1)Bt;0 1 2 t2B0 t2B21 2 t2 t2:3so a quadratic equation for t ist21 2 t2 t2 r:4Since 0 , r , 1, there is exactly one root t in (0,1). Thisroot can be found by writing Eq. (4) as1 2 tt?21 2 rr;solving for 1 2 t=t; which must be positive, and finallysolving for t to givet ffiffirpffiffirpffiffiffiffiffiffiffi1 2 rp;5which is in (0,1) for 0 , r , 1. The vectors B(t,0) 2 P andP 2 B1are parallel and, since 1 , s, are pointing in theFig. 1. Curve (1) passing through a given point P.Fig. 2. Curves (1) filling the control triangle and nested.D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599592same direction, orBt;0 2 PP 2 B1 . 0:6Substitution of formula (3) in Eq. (6) shows that1 2 t2B02 PP 2 B1 t2B22 PP 2 B1 . 0: 7Once the t value in Eq. (5) is found, the uniquecorresponding positive (see Eq. (7) value for w is, fromEq. (1),w 1 2 t2B02 PP 2 B1 t2B22 PP 2 B121 2 ttP 2 B1P 2 B1:8AThe earlier two results are summarized in lemma 1.Lemma 1. If P is strictly inside the Be zier control triangleB0B1B2, then there is a unique curve (1) that passes throughP. If P is not inside the control triangle, then there is nocurve (1) that passes through P. The t- and w-values suchthat Bt;w P are given by Eqs. (5), (2) and (8).Result 3: Control triangle filling and nesting property.Result 2 shows that there is a unique curve (1) through anypoint P strictly inside the control triangle B0B1B2. This factmeans the curves (1) completely fill the interior of thetriangle B0B1B2. The fact that the curve (1) through anypoint P is unique means two curves (1) with different w-values cannot intersect inside the control triangle as anintersection point would be a point through which more thanone curve passes (see Fig. 2).The partial derivative of Eq. (1) with respect to w is thevectorBwt;w 21 2 tt1 2 t2 t2?1 2 t2 2w1 2 tt t2?2B12 Bt;0:The direction of this vector is constant with respect to w, sothe locus of points B(t,w) with fixed t and increasing w is astraight line from B(t,0) to B1. Thus, the family of curves (1)forms a nested set of curves as w moves from 0 to 1; thecurve (1) as w tends to 0 is the line segment B0B2, while thecurve (1) as w tends to 1 is the polyline with segments B0B1and B1B2. If a curve (1) with a certain w is drawn, then allcurves (1) with higher w-values are between that curve andthe polyline B0B1B2.AResult 4: The curve (1) that is tangent to a given linesegment. The w-value of the curve (1) that is tangent to agiven line segment S0S1(S0and S1are distinct) can befound as described later in this Result. This result is used inthe method described in Section 4. The procedure is first tofind a curve (1) that is tangent to the infinite line L throughthe points S0and S1, and then to determine if the point oftangency is in the segment S0S1. The line L must passthrough the control triangle for a tangent to be possible (seeFig. 3).It will now be argued that a tangent line L cannot cutB0B2and cannot pass through B1. Curve (1) is a segment ofa conic and conics have the property that they do not crossany of their tangent lines. The curve (1) joins B0to B2, so itwould cross any line that cuts B0B2; thus, a tangent line Lcannot cut B0B2.In particular, L cannot pass through B1and cross B0B2. IfL passes through B1and does not cross B0B2, then curves (1)cannot be tangent to L because L does not enter the controltriangle B0B1B2. Thus, a tangent line L cannot pass throughB1.In the calculations that follow, first check that L is atangent to the curve B(t,w) and then check that the point oftangency is in the segment S0S1. If a curve (1) is tangent toline L, then the point of tangency B(t,w) must be on L, orBt;w 2 S0 S12 S0 0;9and the partial derivative of B(t,w) with respect to t must beparallel to L, orBtt;w S12 S0 0:10Using Eq. (1), Eq. (9) can be rewritten,Qt;w 2 qt;wS0 S12 S0 0:11Differentiation of the relation qt;wBt;w Qt;w fromEq. (1) with respect to t givesqtt;wBt;w qt;wBtt;w Qtt;w:12Taking the cross product of both sides of Eq. (12) on theright by S12 S0and using Eqs. (9) and (10) givesQtt;w 2 qtt;wS0 S12 S0 0:13The left side of Eq. (11) is the quadratic in t1 2 t2B02 S0 S12 S0 2w1 2 ttB12 S0 S12 S0 t2B22 S0 S12 S0:14Eqs. (11) and (13) show that this quadratic has a double zeroint.SinceB1cannotbeonlineL,(B12 S0) (S12 S0) 0;Fig. 3. Curve (1) tangent to the line segment S0S1at P.D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599593dividing Eq. (14) by this non-zero quantity gives1 2 t2A 2w1 2 tt t2C 0;15whereA B02 S0 S12 S0B12 S0 S12 S0;C B22 S0 S12 S0B12 S0 S12 S0:16Thinking of A, w, and C as the y-values of a quadratic Be ziercurve, and recalling that a positive value for w is required andthatadoublerootofEq.(15)isrequiredin(0,1),itmustbethatA , 0 and C , 0. The condition for a double root isw2 AC or w ffiffiffiffiACp:17The double root occurs att w 2 A2w 2 A 2 C;18wherein the denominator is non-zero because w . 0, A , 0,and C , 0. Although this t-value is in (0,1), the point oftangencyP Bt;w;maynotbeinthelinesegmentS0S1,soa final check is needed, namely,0 ,P 2 S0S12 S0S12 S0S12 S0, 1:19AThe above result is summarized in lemma 2.Lemma 2. If the Be zier control triangle B0B1B2has non-zero area, the infinite line L that passes through the distinctpoints S0and S1does not cross B0B2, B1isnot on L, A and Cin Eq. (16) are both negative, and Eq. (19) is satisfied, thenthere is a unique curve (1) tangent to the line segment S0S1.Otherwise, there is no curve (1) that is tangent to linesegment S0S1. The w-, t-values at the point of tangency aregivenin Eqs. (17) and (18),where Aand Care defined in Eq.(16).Result 5: The curve (1) that is tangent to a given circulararc. The w-value of the curve (1) that is tangent to a givenarc can be found as described later. An arc will be specifiedby two distinct endpoints S0and S1, and by a non-zerosigned sweep angleufrom S0and S1(counterclockwise ispositive). Let C be the circle of which the arc is a part. Theprocedure is first to find a curve (1) that is tangent to C, thentest if the point of tangency is in the given arc (see Fig. 4).Ifuis positive, let U be the unit vector that is a rotation ofp/2 from the direction S12 S0, while ifuis negative, let Ube the unit vector that is a rotation of 2p/2 from thedirection S12 S0. The centre E and radius r of circle C areE S0 S12kS12 S0k2 tanu2?U;r kS12 S0k2 sinu2?:By analogy with Result 4, if a curve (1) is tangent to a circlecenter E and radius r, then the equationBt;w 2 E?Bt;w 2 E? 2 r2 020has a double root in t. Using Eq. (1), Eq. (20) becomesQt;w 2 qt;wE?Qt;w 2 qt;wE? 2 r2qt;w?2 0:21The left hand side of Eq. (21) in Bernstein form isc01 2 t4 4c1w1 2 t3t 2c2 2c3w2?1 2 t2t2 4c4w1 2 tt3 c5t4;22wherec0 B02 EB02 E 2 r2;c1 B02 EB12 E 2 r2;c2 B02 EB22 E 2 r2;c3 B12 EB12 E 2 r2;c4 B12 EB22 E 2 r2;c5 B22 EB22 E 2 r2:Converting to power representation, polynomial (22)becomesa4t4 4a3t3 6a2t2 4a1t a023wherea4 4c3w22 4c1 c4w c0 2c2 c5;a3 22c3w2 3c1 c4w 2 c02 c2;a223c3w22 2c1w c013c2;a1 c1w 2 c0;a0 c0:Tangents occur when Eq. (23) has a double zero in t; amethod for checking for a double zero is described inAppendix A. The condition for Eq. (23) to have a doubleFig. 4. Curve (1) tangent to an arc from S0to S1at P.D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599594zero in t, D 0 where D is defined in the Appendix A, leadsto an eighth degree polynomial equation of even powers inw. Here only positive w-values whose corresponding t-values are in (0,1) are acceptable. For each point oftangency to the circle, a check is made to see if the point isin the arc being considered. The result of this process is a setof possible w-values for curves (1) (the set may be empty).Note that a curve (1) may be tangent to the arc in twoplaces and there may be several curves (1) tangent to the arc.Since the largest w-value will be taken later, thismultiplicity of curves (1) does not cause any difficulty. AResult 5 can be restated in the following lemma 3.Lemma 3. If the area of the Be zier control triangle B0B1B2is non-zero, S0and S1are distinct endpoints of an arc, thesweep angle of the arcuis non-zero, there are positive w-values such that Eq. (21) has a double zero in t for t in (0,1),the points of tangency are in the arc from S0to S1,then thereexist one or more curves (1) that are tangent to the arc fromS0to S1. Otherwise, no curve (1) exists that is tangent to thearc from S0to S1.3. A solution of the constrained curve drawing problemA solution to the constrained curve drawing problempresented in this section is based on a quadratic B-splinewith uniform knots. In this section, assume that the B-splinecontrol polyline does not intersect the constraining bound-ary. A typical segment of the quadratic B-spline controlpolyline has control points P0, P1, P2. The correspondingquadratic Be zier control points are:B0P0 P12;B1 P1;B2P1 P22:If the control polyline of a quadratic B-spline is closed, thenthe control polyline of the corresponding quadratic Be ziercurves follows the same path; if the control polyline of aquadratic B-spline is open, then the control polyline of thecorresponding quadratic Be zier curves follows the samepath, but is slightly shorter (at both ends). Thus, if the B-spline control polyline does not cut the boundary, then thecorresponding Be zier control polyline does not cut theboundary. Henceforth, references will be to the Be ziercontrol polyline and its corresponding Be zier curves ratherthan to the B-spline control polyline and curve. Further-more, each Be zier segment can be considered separatelybecause overall G1continuity is guaranteed from the Be ziercontrol polyline.Before discussing the algorithm, it is helpful to considera default weight w, and to examine two simple cases.Whenever possible, a quadratic curve (parabola, w 1) willbe used rather than a rational quadratic (conic, w 1). Thisdefault choice seems to give nice curves, although it issomewhat arbitrary and could be chosen differently. Thechoice w 1 does give the algebraically simplest curves.Even if a different choice were made, it would probably notbe too far from 1. Fig. 5 shows the control polyline in grayand quadratic B-splines with three different weight values;the weight w 1 gives the nicest curve of the three.Case 1: (boundary does not enter the control triangleB0B1B2). Here, the control triangle is entirely on one side ofthe boundary (see Fig. 6). Since all the curves (1) areentirely inside the triangle B0B1B2, none of them intersectthe boundary. The quadratic Be zier segment, curve (1) withw 1; will be used for part of the final curve.ACase 2: (boundary enters the control triangle B0B1B2bycrossing line segment B0B2). Since the Be zier controlpolyline does not intersect the boundary, the only way theBe zier curve segment can intersect the boundary is if theboundary cuts line segment B0B2(see Fig. 7). For allendpoints of straight-line boundary segments inside theFig. 5. Quadratic B-splines with various weights.Fig. 6. Case 1: boundary does not enter the Be zier control triangle B0B1B2.D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599595control triangle B0B1B2, find curves (1) that pass throughthose endpoints using Result 2. The curve (1) with thehighest w-value will avoid all the straight-line boundarysegments. The curves (1) that are tangent to line segmentsare not considered here because the curves (1) through theend points of any line segment have higher w-values than acurve (1) that is tangent, and later the curve (1) with thelargest w-value is used.For all circular arc boundary segments inside the controltriangle B0B1B2, find curves (1) that pass through theendpoints of those boundary segments and the curves (1)that are tangent to the boundary segments using Results 2and 5 (see Fig. 7). Again, the curve (1) with the highest w-value will avoid all the boundary segments.AAlgorithm. While the quadratic B-spline is beingdesigned with a B-spline control polyline, generate thecontrol points of the corresponding quadratic Be zier curves.For each of the Be zier curves (1), check all boundarysegments that are partly or entirely inside the Be zier controltriangle to determine the w-value of the curve (1) that avoidsall those boundary segments. Let wLbe the largest of all thew-values of the curves thus produced, then w max1;wLis the w-value of a curve (1) that does not intersect any of theboundary segments. Here the preference is to use w 1 ifthe boundary segments allow that value.In Fig. 8, the curve (1) derived from B-spline controlpoints P1, P2, and P3uses a w-value higher than 1 to avoidcutting a circular part of the boundary by being tangent to it.The curve (1) derived from B-spline control points P3, P4,and P5uses a w-value higher than 1 to avoid cutting theboundary by passing through a boundary corner. The curve(1) with w 1 in these two cases is shown in gray. In all theother segments, w 1 gives a curve that does not cross theboundary. The curve that avoids the boundary is shown inblack.Theorem 1. If the guiding B-spline control polyline does notintersect the boundary, then the G1continuous curveproduced by the earlier algorithm does not intersect theboundary.Proof. The theorem follows from the fact that byincreasing the w-parameter sufficiently the curve (1)moves as close to the Be zier control polyline B0B1B2asdesired. Since the Be zier control polyline does notintersect the boundary, w-values can be found so that nosegment of the whole G1continuous curve intersects theboundary. Lemmas 1 and 3 state that a boundary avoidingcurve (1) can be found with both straight line and circulararc boundary segments.ASpecial behavior. There are several special effects thatcan be achieved by the placement of the B-spline controlpoints.To force the curve to be tangent to a straight line segmentof the boundary, put two consecutive B-spline control pointson the same straight line segment of the boundary. This willproduce a curve that is tangent at the midpoint of the twoFig. 8. A curve constrained by a closed boundary.Fig. 7. Case 2: the boundary crosses the line segment B0B2.D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599596consecutive control points. In Fig. 9, the B-spline controlpoints P1and P2are on the boundary and the curve istangent to the boundary at P1 P2=2: To force the curve tobe tangent to the boundary at a given point, arrange twoconsecutive B-spline control points on the boundary so thatthe given point is midway between them.To run the curve along a straight line segment of theboundary, put more than two consecutive control pointsalong the same line segment of the boundary. The quadraticB-spline will yield some quadratic Be zier segments that arestraight lines while maintaining G1continuity. In Fig. 9, theB-spline control points P4, P5, and P6are on the boundary.There is a straight line segment in the curve from P4P5=2 to P5 P6=2:To force a cusp at a boundary point, put a double B-spline control point on the boundary. Of course, the curvewill not be G1continuous at the cusp. In Fig. 9, B-splinecontrol points P8and P9are the same and there is a cusp atthat point.4. Extensionallow the control polyline to cross theboundaryIt is possible to have some B-spline control pointsoutside of the boundary and still produce a curve that doesnot cross the boundary. The Be zier points B0and B2mustremain inside the boundary while B1can be outside. Inthis situation, part of the boundary can enter the controltriangle B0B1B2by crossing from line segment B0B1toline segment B1B2. The segments of the boundary in sucha part give upper bounds on the w-parameter; let wHbethe smallest of them (see Fig. 10). At the same time, thepart of the boundary can enter the control triangle B0B1B2by crossing in and out over the line segment B0B2asmentioned in Section 3. Segments of such a part put lowerbounds on the w-parameter; let wLbe the largest of them.If wH, wL, it is impossible to satisfy both restrictions, sothere is no curve (1) that matches the G1Hermite data andthat does not cross the boundary. Otherwise, there arethree cases for the choice of the w-parameter. If1 , wL# wH, choose wL; if wL# 1 # wH, choose 1;and if wL# wH, 1, choose wH. In brief, the allowableweight closest to 1 is chosen.An example showing a curve contained entirely inside aboundary appears in Fig. 11. Note that many of the B-splinecontrol points are outside the boundary.Fig. 9. Special featurestangent to boundary, run along boundary, cusp onboundary.Fig. 10. Extensionallow control points outside of the boundary.Fig. 11. Extensionsome control points outside of the boundary.D.S. Meek et al. / Computer-Aided Design 35 (2003) 5915995975. ConclusionsA method for drawing a G1planar curve that avoids aconstraint boundary consisting of straight line segments andcircular arcs has been presented. The curve is guided bycontrol points and consists of parametric quadratics andparametric rational quadratics. A quadratic equation mustbe solved for straight line boundary segments, while a fourthdegree equation must be solved for circular arc boundarysegments.AcknowledgmentsThe authors acknowledge the financial support of theNatural Sciences and Engineering Research Council ofCanada for this research. The authors appreciate the usefulcomments from two anonymous referees; their advicehelped improve the presentation of this paper.Appendix AThe condition that a fourth degree polynomial has a zeroof higher multiplicity than one is developed here. Thecondition is derived from the fact that for multiple zeros,the greatest common divisor of the polynomial and itsderivative is of degree higher than 0. The general case isfollowed by some special cases.General case: Let the fourth degree polynomial be r0tand let its derivative be 4r1(t), wherer0t at4 4bt3 6ct2 4dt er1t at3 3bt2 3ct d;and assume a 0. If r0t is divided by r1t; the result willhave fractions with the variable a as a denominator. Toavoid those fractions, start with a r0t to getar0t q2tr1t r2t;where the quotient q2t and remainder r2t areq2t at br2t 23At2 3ad 2 bct ae 2 bd;andA b22 ac:Assume A 0 (see later in the Appendix for case A 0). Ifr1t is divided by r2t; the result will have fractions withdenominators 3A2. To avoid those fractions, start with3A2r1t to get3A2r1t q3t2r2t ar3t;where the quotient q3t and multiple of the remainder r3tareq3t aAt 3bA aad 2 bc?r3t Bt C;andB ae 8bd 2 9c2A 3ad 2 bc2;C 3be 2 cdA ad 2 bcae 2 bd:Assume B 0 (see later in the Appendix for caseB 0). If r2t is divided by r3t; the result will hav
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号