网址：http://www.elsevier.nl/locate/entcs/volume61.html13页用Dual De Boor算法丁瑞娜1Nisky Mail PMB-588美国弗吉尼亚州圣托马斯，邮编：00802摘要本文概述了新兴的方法，目前正在调查中，用于构建直纹曲面和实体轨迹的计算机辅助几何设计（CAGD）的背景下。基本原理是用于在平面上或在3维空间中构造B样条曲线的标准De Boor算法[4，2，15但是所有3矢量点的坐标，包括要插值的控制点，现在都是对偶数，而不是实数。当所得的六个节点被解释为P lucker坐标[1 2]时，每个对偶点在三维空间中，将其解释为直线，将每条曲线解释为直纹面。讨论了基于刚体特征的重复曲面的构造方法。本文讨论了用P lucker坐标表示的在屏幕上画极长直线的问题。1引言一个三维曲面是直纹的，如果通过它的每一个点，至少有一条线完全位于曲面内[4]。因此，可以通过沿着合适的空间轨迹承载（直）线来生成直纹表面，由于该轨迹可以在制造中通过直线切割或磨削工具再现，所以该空间轨迹解释了直纹表面在自动化设计中的特定作用。直纹面设计及其应用广泛应用于计算机辅助几何设计（CAGD）[2，15]和工业领域。螺旋由6维矢量组成[7]，当其螺距为零时，螺旋变为直线。De Boor算法是连接对偶世界（螺旋）和真实世界（直纹曲面）的桥梁。最近，结合现实世界和双重世界的设计方法已经发展起来。特别是Bezier曲线和B样条在对偶空间中的应用。Ge[3，14]将B样条应用于1电子邮件地址：lxyzl@hotmail.comc 2002年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。2利用四元数空间中的有理B样条处理曲线逼近问题和路径光顺问题，并分别处理速度光顺问题。Juttler[6]使用RMM（旋转最小化运动）的四元数表示来扫描曲面建模。本文的灵感来自Sprot和Ravani[13]的论文，他们使用螺旋空间中的De Casteliau算法来解决直纹曲面绘制和网格生成问题。本文用De Boor算法改进和发展了他们的方法，并提出了一些新的绘制重复曲面的方法。本文还从任意法向螺旋导出了单位螺旋（画直纹面的工具之一），并给出了一种在屏幕上画螺旋--直纹线的实用计算机表示方法本文的组织结构如下。第二节定义了一个被称为螺旋的数学对象，当它被专门化时，它体现了我们对空间中一般直线的定义和位移规则。单位螺钉，推导出正常的螺丝，包括在内。第3节回顾了De Boor算法。包括几何和功能表示。第四部分是论文的主体部分。它将De Boor算法与旋量理论相结合，用调整的一个基本规则用于对偶空间，实现了对偶DeBoor算法的诞生。它不仅以几何形式表示，用于绘制曲面，而且以函数形式表示，用于下一部分复制曲面的基本表达。第五节给出了一种比真实曲面法更好的对偶曲面法。第六节介绍了一种在计算机屏幕上绘制螺钉的实用方法。结论见第7节。2螺旋理论2.1螺钉的定义一个一般的曲线S^，从它我们可以通过特殊化导出一条线，由两部分组成，一个实3-矢量S，它指示螺旋（的线）的方向，和一个实3-矢量Sp，它通过记录螺旋绕原点的力矩来表示S ^[7，9]。在这些术语中，螺钉形成为（1）S^=S+“Sp=S+“（pS+S0），其中 S0=RS=VS其中“是满足es“2= 0的准标量。这里，p是螺杆的螺距，S0是螺杆的线绕原点的力矩，与S（SS0= 0）正交，并且如图所示从螺杆的原点半径矢量R或{更一般地{从任何点V}导出实部S的长度jSj是螺旋的实量值。图1示出了螺钉的这种几何解释。3pS^S^^SypSROXS0Vz^X^X^SDFig. 1. 几何解释在三维空间中，螺旋S^=（1+“p）S+“S02.2直线是零螺距图二、通过沿着轴S1的平移和旋转来移动直线X1。如图所示，由于螺旋是具有相关联的螺距值p的线，因此，线本身是具有零值螺距的螺旋，即p = 0。给定一个一般的螺旋S^，我们经常需要求出它的单位量值的法线零音高这样一条单位线的推导是很直接的，我们用下面的形式表示它：^s=s+“s0”。 由方程（一）S^=（ 1+“p ） S+“S0什 么 时 候所以，由于“2= 0，我们发现，S^S^=（1+“p）2SS Sso pS^S^=（1+“p）jSj因此，一般螺旋S^归一化到其单位线S^，其形式为：（二）S^^s==1“pS^=jSj1jSj（1“p）[（1 +“p）S+“S0）] =SjSj+“S0jSj在实际应用中，当给定形式为S^=S+“ Sp的螺钉时，可以导出其螺距、原点半径和归一化线为：（三）p=SSp;R=SSp;^s=S+“SppSjSj2jSj2jSjjSj其中最后一个，等价于等式N。 （2）利用第一。我们观察到，当S=0时，螺旋S是一条直线。2.3螺旋或线是对偶3-向量4当n是S^的3-向量时是显式的，S=（Lx; Ly; Lz）和Sp=（Mx; My; Mz），我们证明了螺旋不是简单的实Plucker坐标Lx;Ly;Lz;Mx;My;Mz 的6元组. 它也是一个三维矢量（4）S^=S+“Sp=（LX+“MX;Ly+“My;Lz+“Mz）5我^T^我0^通过对纯转动位移的对偶方程[7]，20^sz^sy3其中每个元素，例如Lx+“Mx等，都是一个对偶数。在这些对偶项中，3-向量量是熟悉的实共-纵坐标获得空间解释。标量积S^1S^2 苏CH3-向量包括对偶角的余弦（参见等式1）。（6）），包括螺钉S^1和S^2之 间的 实 际角 度 和距 离。 当S^1和S^2正交时，S^1S^2=0+“0=0，这些螺钉以适当的角度彼此相交。 类似地，导向器部件S^1和S^2是位于螺杆S^1和S^2的共同螺杆上的螺杆。大多数情况下，螺旋像3-向量一样变换[9]。如果x^i、y^i和y^zi是定义参考系的相互正交的单位线，则x^2=y^2=^z2=1;x^y^=y^^z=^zx^= 0;x^y^=^z;我我我伊伊我我我当在i坐标系中表示时，一般螺旋S^的坐标为2x^T32x^iS^32xi S 32x^iS^3（5）Si=6y^i7S=6y^iS7=6y^iS7+-6y^iS7^zT^ziS^75ziS5746^ziS^57其中，例如，x^iS^=xiSp+x0iS。2.4螺旋的位移在刚刚描述的二元论下，两个给定的实点之间的线性插值点和在螺钉连续移动的位置中的空间类似物，当从某个初始位置a b移出螺钉轴^s时（见图1）。二、通过以下方法将Su ch位移参数化：一个双角^+ d，其中包含实角的旋转和平移的实际距离d，在轴^ s外测量a b。对于这样一个对偶角，我们可以写成：(6)sin^ 罪 + d cos; cos^ cosd sin：螺钉X^从初始位置X^0通过双角^ab移出a，螺旋轴^s=（^sx;^sy;^sz）isgivenby（7） X^=[A^]X^其中[A^]=exp[S^]=[I^]+sin[S^] +（1cos^）[S^]2其中[A^]是由y^和[S^]确定的位移矩阵，[I^]是对偶矩阵，[S^]是由y ^和[S^ ]给定的k-对称矩阵。（8）[S]=6^sz0^sx7^sy^sx075其具有对于任意螺旋S ^的[S^]S^=^sS^的性质。如果位移是纯平移，使得螺旋的初始位置和最终位置平行，则位移矩阵具有特殊形式60Jttr+1r+3点P0和P0根据Pk（t）=（1u）Pk1（t）+uPk1（t）其中[D]表示螺杆X1的平移。第三章德波尔算法本文给出了在2-或3-维空间中生成插值曲线的De Boor算法[4，2，15]从给定的控制点的三维空间是De Casteljau算法的一种形式。后者的基本步骤，对于每个t2[0; 1]，是从连续的第一代（控制）对中插值第二代点P10（九）1P1 =（1t）P0 +tP0其中t 2 [0; 1]0 0 1这一步，逐步应用于连续的几代内的连续点对，最终产生一个单一的点，定义为t。生成的插值曲线由t 2 [0; 1]的所有此类点组成。对于n+1个给定的控制点，De Casteljau算法通过n代来产生曲线，该曲线在其每个点处通过n次加权多项式依赖于每个De Boor算法的一个简单的改进是将插值过程限制在一个较小的控制点子集上，该控制点子集由指定的Mn + 1个控制点组成，从而提供了局部控制来克服这一缺点。Bezier曲线由所有控制点加权由De Boor算法创建的曲线段连续的曲线段被表示为B样条，其被一系列节点t 2 [0; 1;：; tn]划分。如果控制点的一部分被调整，只有B样条曲线的一部分会被改变。B样条曲线比Bezier曲线更灵活。De Boor算法有n + 1个控制点。 M是B样条的阶数。M1是B样条的阶数（代）。节点序列为T=[t0;t1;：;tn+M]几何表示一个点P（ts），B样条曲线t = ts：步骤1：找到一个i，其中ts 2 [ti; ti+1），r = i M + 1。当i M 1时，我们定义r = 0。步骤2：设置P0（ts）=Pj，（j = r;r + 1;：;r + M1）。步骤3：重复插值较低程度的点到较高程度一个直到最终度点（曲线）P（t）= PM1（t）由式sr+M1Sjsj1sjs其中u=tstjj+ M k j ，u2[0; 1]且k =jR.图3举例说明了涉及3个gen的3次B样条的几何形状插值的迭代。 给定的控制点Pr、Pr+1、Pr+2和Pr+3被线性内插到第二代点P1中1r+2，P1 .然后将这些点插值到下一代中，直到nal，P7PPr+3变成了线。特别地，方程的点P0，P0，P1是在给定的时间内的。（9）双重化，单位线X^0、X^0和X^1，则该方程的内部插值被替换通过一个位移n，使其具有方程n的形式X^1=[A^]X^0。（七）、其中线X^1可以从X^0移动到X^0[10]。 它可以显示[8]0R+11Pr+20R+2N（t）N0，4（t）N1，4（t）N2、4N3、4N4、4 N5、4 N6、4N7、4不t0，t1，t2，t3t4 t5 t6 t7 t8，t9，t10，t11图三. 几何解释M= 4的De Boor算法见图4。M=4时的B样条函数表达式在单点P（t s）= P3处实现生成，对于ts 2 [ti; ti+1]，想要的曲线功能表示一阶函数定义为Nk;1（t）=8<：1（tjt tj+1）0（否则）对于M > 1的情况，我们有N（t）=t tkN（t）+ tk+MtN（t）k;Mtk+M1tkk;M1tk+M tk+1k+1;M1B样条曲线的最终方程为nP（t）=XPk Nk;M（t）k=0图4是当M=4时的函数解释示例例如，t2[t3;t4]，曲线v由 P0，P1，P2，P3加权;t2[t6;t7]，曲线v由P3，P4，P5，P6加权。4De Boor算法在对偶空间中的应用De Boor算法的二元化，如图3所示图5是简单明了的。所有控制点及其插值点0 1 00 1 00 0事实上，存在方程的螺旋轴的不同组。（7，8）about0 0 1为了我们的目的，位移必须选择为遵循测地线，P2R+2P（t）P2SP3R+3R+3P1R+1Pr+31P00RPr+38X^0和X^0行。研究发现，这样一条路径是由一个运动提供的，对偶单位球面上表示单位的点之间的路径0 19X10在实三维空间中，将X^1从X^0携带到X^0，且具有常数值JX^0和X^0;即，苏志浩0101）;确定从X^0到X^0的双角αb，0（UP）（向下）一图五. 的几何解释对偶空间De Boor算法（M= 4）见图6。 复制曲面0 0 1在位于共同椎弓根上的螺钉轴s之外的0 1（十）^s=X^0X^0=q（X^0X^02由其确定方程的矩阵[S]。（八）、 通过Eqns。（6）we0 1^=b其中re=cos1（a）和a+b=cos^=X^0X^0sin（）0因为这些是单位线。提供恒定的角速度和线速度从^0 到X^0，它们之间的这个对偶角对于t 2[0; 1]，以t ^的形式插值。故，以德为先。（7）给出了求第二代线X^1的对偶插值算法（十二）X^1=[A^]X^0其中re [A^]=[I^]+sin（t^）[S^] +（1cos（t^））[S^]20 0如果有n + 1个控制螺钉，我们将得到第n代螺钉，这些螺钉构成直纹曲面。(This De Castljue算法）。在De Boor算法中应用类似的 在对偶空间中建立了基本的插值规则。双De Boor算法有n + 1个控制螺钉。M是B螺钉的顺序。M1是B-螺钉的度数（代）纽结序列为T=[t0;t1;：;tn+M]（我们称构成直纹曲面的螺旋为B-螺旋）。几何表示We将找到螺旋X^（ts），其是B-螺旋中的一个螺旋，t =ts。步骤1：找到一个i，其中ts 2 [ti; ti+1），r = i M + 1。当i M 1时，我们定义r = 0。步骤2：设置X^0（ts）=X^j，（j=r; r+1;：; r+M1）。步骤3：从图5中，根据2个螺钉插入一个简单螺钉，Xr+1^0^1Xr+2Xr+2^0Xr+2^2^X（ts）^^2X3XR+3R+3Xr+1^1^X1R+3^X0^0RXr+3BG10Jj1;jj1;jRRr+2R其中j>r，[A^jr]表示B-螺钉由y[X^0，.， X^0]。有^2等式（12）作为：^1r+1 =[A^]X^r. 它是X^1=[A^]X^j1，其中[A^]=exp[u^;^s]=[I^] +sin（u^）[S^j1;j]+（1cos（u^））[S^j1;j]2：从等式 （3）求单位螺旋X^0和X^1。 从等式 （10），我们得到其中h由等式（11）归一化的 （3）awell;从（8），我们得到[S^];从方程。 （11），我们得到u ^= u + ud。由方程（6），我们有sin（u^）= sin（u）+ udcos u和cos（u^）= cos u ud sin u。步骤4：重复将较低度数的螺钉插入较高度数一阶直纹螺旋（直纹面）X^（t）=X^M1（t）给出由式X^k（u）=exp[u^k1;^sk1S]X^k1;R+M1Sj j1;jj1;jJ1其中uk=tstj，u2[0; 1]且k =jR.jtj+ M kt j图的函数表示5、我们有^1r+1^1r+1]X^0;其中[A^1]由yX^0和X^0确定. 所以X^1由yX^0表示，^0r+1r+1. 我们有^2r+2R^2r+2 ^1r+1r+1^2r+2r+1^1r+1R]X^0;其中，[A^2]由X^0，^0r+1 和^0r+2. 它表明r+2是被这些螺丝钉加重 我们有X^jr=[A^jr]X^jr1=[A^jr][A^jr1]：：：[A^1]X^0;jjj1jj1r+1rjrjj r +1个称重控制螺钉。例如，如果j r = 3，则j r +1 = 4，曲线v由yX^0，X^0，X^0，x0。r r+1在ts 2 [ti; ti+1）处，我们有M1r+2r+3r+ M1X^（t）=Y[A^k]X^0= Y[A^jr]X^0：sr+ krk=1J Rj= r+1B型螺钉段由[X^rX^r+M1]表示。在T=[t0;t1;：;Tn+M]内，我们具有+M1（十三）X^（u）=Y[A^jr]X^0其中r = 0; 1; 2;：：：; nM +1：J Rj= r+1XX=[AXX=[A]X=[A][AXXX115重复的表面经常发生的情况是，一片表面被复制，并从原始表面重复延伸到一个非常大的区域。在现实世界中，我们可以使用De Boor算法设计每个音高，然后将它们缝合在一起[15]。这种方法需要考虑边界条件。在对偶世界中，对原曲面进行重复曲面的扩展，不需要重复De Boor算法，在对偶世界中，12De Boor算法用于创建原始曲面。这得益于刚体的特性，“在基于刚体的参考系中，当物体移动时，没有相对速度可检测”[5]。原始直纹曲面是一个刚体，因为它也是一组点，具有任何两个点之间的距离永远不变的属性。如果刚体沿轴平移和旋转，曲面将移动到所需的位置。B型螺钉之间没有相对运动，位移若要生成延伸复制曲面，只需选择一个合适的轴B_x，即B-螺钉中的一个螺钉到复制曲面中其复制螺钉之间的几何路径。让B型螺钉沿此轴移动。 如果位移角为θ= + D，则位移矩阵为[Q^]==exp[^;b^]=[I^]+si n（^）[B^] +（1cos（^））[B^]2（13）、新的表面将被r+ M1D^=[Q^]X^（u）=[Q^] Y[Ajr]X^0jnM+1Jj= r+1r r=0如果第三，第四，...，等等，需要创建曲面，一种方法是，我们用B型螺钉创建所有的复制曲面。轴B^变化所述B型螺钉和复制表面之间的相对位置。 是r+ M1D^=[Q^ ]X^（u）=[Q^] Y[A^jr]X^0jnM+1w wwJj= r+1r r=0另一种方法是，我们插入下一个复制的表面由前一个表面。所以新的曲面方程是w w r+ M1D^=[Q^]D^=Y[Q^]X^（u）=Y[Q^]Y[A^jr]X^0jnM+1w w w1Qq=1q=1QJj= r+1r r=0如果复制的曲面沿彼此相同的轴以相同的对偶角进行插值，则曲面方程将简单地为r+ M1D^=[Q^]wX^（u）=[Q^]wY[A^jr]X^0jnM+1WJj= r+1r=0其中除了B螺钉之外，还创建了w个图6（上图）是将曲面的左侧部分（包括最左侧的8个螺钉）复制到整个图像的示例。旋转和平移都应用于原始曲面。图6（向下）是垂直表面被复制到具有纯旋转角度G的水平位置的示例。6螺钉的屏幕表示如何在电脑屏幕上画出螺丝值得关注。Parkin[11]给出了一个复杂的方法，通过结合螺旋几何和合成13摄影技术这里，另一种有效的方法应用于从三维空间到二维屏幕的投影图像（螺旋）的情况[4]。 螺钉图像应 首先从对偶空间解释为3-三维真实空间，使用世界坐标系。 然后是第三为了将世界坐标螺钉（线）投影到屏幕平面，丢弃三维螺钉表示的分量。最后，我们使用线段算法[4]在屏幕上绘制螺钉如果一个螺旋在i-标架（x^i;y^i;^zi）中，S^iSi+Spi，we可以将其转化为实数（x，y，z）系统S^=S+S0y方程（5）。在三维空间中将螺旋形转化为直线形的参数形式是（十四）l（t）=S S+ tS：其中t是在两个或多个不同值上选择的。通过连接不同的选定点l（ti），螺钉将被绘制为三维空间上的线。但是，如果点远离屏幕，则螺钉不能显示在屏幕上。 应用直线段算法[4]可以有效地解决这一问题。该算法指出，当t2[1;+1]时，由a =（ax;ay）和b=（bx;by）决定的直线上的所有点(15)x（t）= ax+（bxax）t和y（t）= ay+（by ay）t：我们已经从方程（14）中知道螺旋线。我们可以寻找螺钉与屏幕边缘的交点。将两个交点连接后，屏幕上就会绘制出螺纹以下是寻找交点的方法假设屏幕的最左上点是原点。X和Y矢量分量显示在图中。屏幕具有X=宽度和Y =高度尺寸。在图7中，假设螺钉平行于X分量，（螺钉平行于Y = 0）。在这种情况下，从等式（15），可以找到螺钉和屏幕边缘的交点X = 0和X =宽度。然后可以在屏幕上绘制螺钉在图8中，当螺钉平行于Y部件时使用类似的方式（螺钉平行于X =0）。图9、螺杆与Y分量的交点t在Y 2 [0; height]之间。那么螺钉和X组件（Y = 0或Y =高度）的交点s应在X 2 [0;宽度]上找到。在t和s已知之后，可以在屏幕上绘制螺钉，因为st穿过屏幕（如果在此期间没有找到交点，则该线不会穿过屏幕）。在图10中，假设螺钉和Y分量的交点t为Y 2 [0;高度]。然后，应找到螺钉和Y分量（在X =宽度处）的交点s，以便通过穿过屏幕的st来显示螺钉。S S014OXyOXy见图7。螺钉为平行Y型组件图8.第八条。螺钉为平行X组件OSX不Sy不OSX不Sy见图9。交点t在Y2[0; height]之间见图10。交点t在Y2[0;height]之外有时，上述算法仍然不能在屏幕上显示螺钉，因为螺钉位置可能不在屏幕附近。Ausanne变换[1，4]将调整螺钉的位置并将螺钉移动到屏幕附近。这两种方法的结合将保证螺钉通过并显示在屏幕上。该方法也可以应用于任何“行”屏幕表达。图11和图12显示了当使用双De Boor算法绘制直纹曲面时，使用上述方法在屏幕上显示的图图11示出了两个控制螺钉不平行时的内插螺钉图12所示为控制螺钉平行时的内插螺钉7结论本文的基础是提出一个解决方案，用于计算机辅助几何设计（CAGD）中的新兴方法，用于基于计算机的6维刚体运动插值，指定的控制15图十一岁当控制螺钉不平行时，见图12。当控制人员平行地点直纹曲面生成的对偶De Boor算法是将实数De Boor算法应用于对偶空间而得到的。以直纹曲面为例，应用旋量理论和对偶De Boor算法对直纹曲面进行了复曲面法的推广。螺钉的屏幕表示方法是在屏幕上用细线表示螺钉这些螺丝是划线，并形成了直纹面的基本组成部分，这些直纹面是用对偶法绘制的。所讨论的方法具有直接的应用，例如，在电影制作的领域中，其中需要基于计算机生成运动序列的连续图像帧。该方法也可用于规划和生产的光滑的身体轨迹。8致谢作者感谢Ian A.悉尼大学的帕金在撰写这篇论文时说。她还要感谢维尔京群岛大学的Douglas Iannucci博士和Foxboro Australia Pty. Ltd.协助校对。引用[1] Angel，Edward. 计算机制图.北京市出版社[2] Farin，G.（1988年）。计算机辅助几何设计的曲线和曲面：实用指南。学术出版社，马萨诸塞州波士顿[3] Ge，Q.J.和Larochelle，P.M.（1997年）。NURBS运动的代数运动逼近及其在球面机构综合中的应用 Proc.16NATO ASI on Computational Methods in Mechanisms2，Varna，Bulgaria，June 16-28，pp. 269-278。[4] Hill，F.S. Jr.（1990年）。计算机制图.纽约麦克米伦出版公司。[5] Hunt，K.H.（1978年）。机构的运动学几何。牛津大学出版社.[6] 贾特勒湾（1998年）。旋转最小化球形运动。Proc. Sixth InternationalWorkshop on Advances in Robot KineticsStrobl，Austria，June- July，1998，Kluwer Academic Publishers，pp. 413-422[7] McCarthy，J. M.（1990年）。理论运动学导论。麻省理工学院出版社，剑桥，马萨诸塞州。[8] Park，F.Ravani，B.（1995年）。黎曼流形和李群上的贝塞尔曲线ASME机械设计，117pp. 36比40[9] 洛杉矶帕金（1997年）。有限位移螺旋几何与正交矩阵变换的统一。机械师马赫理论32（8）pp. 975-991[10] 洛杉矶帕金（1998年a）。具有对称性的刚体有限位移的正切螺旋线线性系统。Proc.第六届机器人Kinetics Strobl进展国际研讨会，奥地利，1998年6月至7月，Kluwer学术出版社，pp.317-326[11] 洛杉矶帕金（1998年b）。基于螺旋的计算机图形学。出现：机械师马赫。理论[12] Plucker，J. （1865年）。 一种新的空间几何。 腓 Trans. 罗伊 S oc。，155：725-791.[13] Sprott，K. Ravani，B. 1997年：《Ruled Surfaces，Lie groups，and meshgeneration》。ASME设计自动化会议，1997年9月14-17日，加利福尼亚州萨克拉门托，DAC-3996。[14] 斯里尼瓦桑和Ge，Q.J.（1997）。有理B样条运动的微调。ASME设计自动化会议，1997年9月14-17日，加利福尼亚州萨克拉门托，DAC-3984。[15] Yamaguchi，Fujio. 计算机辅助几何设计中的曲线和曲面。施普林格出版社，柏林。
