3.14 NURBS曲线与曲面 B样条方法在表示与设计自由型曲线曲面形状时显示了强大的威力,然而在表示与设计初等曲线曲面时时 却遇到了麻烦。因为B样条曲线包括其特例的 Bezier曲线都不能精确表示出抛物线外的二次曲线,B样条曲 面包括其特例的 Bezier曲面都不能精确表示出抛物面外的二次曲面,而只能给出近似表示。提出 NURBS方法, 即非均匀有理B样条方法主要是为了找到与描述自由型曲线曲面的B样条方法既相统一、又能精确表示二次 曲线弧与二次曲面的数学方法。 NURBS方法的主要优点 (1)既为标准解析形状(即前面提到的初等曲线曲面),又为自由型曲线曲面的精确表示与设计提供了 个公共的数学形式。 (2)修改控制顶点和权因子,为各种形状设计提供了充分的灵活性 (3)具有明显的几何解释和强有力的几何配套技术(包括节点插入、细分、升阶等)。 (4)对几何变换和投影变换具有不变性 (5)非有理B样条、有理与非有理 Bezier方法是其特例 不过,目前应用 NURBS中还有一些难以解决的问题: (1)比传统的曲线曲面定义方法需要更多的存储空间,如空间圆需7个参数(圆心、半径、法矢),而NRBS 定义空间圆需38个参数 (2)权因子选择不当会引起畸变 (3)对搭接、重叠形状的处理很麻烦。 (4)反求曲线曲面上点的参数值的算法,存在数值不稳定问题 3.1.4.1 NURBS曲线的定义 NURBS曲线是由分段有理B样条多项式基函数定义的 O,PN(t) P(t) =∑22(t) o),Nk(t) O, Nk(t) 其中,Rk(t)(i=0,1,…,n)称为k阶有理基函数,Nk(t)是k阶B样条基函数,P1(i=0,1,,n)是特 征多边形控制顶点位置矢量;wi是与P对应的权因子,首末权因子wo,wx>0,其余w0,以防止分母为 零及保留凸包性质、曲线不因权因子而退化为一点:节点矢量为T=[t,t, t,…,tmk],节点个数 是m=n+k+1(n为控制项的点数,k为B样条基函数的阶数)。 T=[a,…;a,t+,…,tn,B,;,/ 对于非周期 NURBS曲线,常取两端节点的重复度为k,即有 在大多数实际应用中,a=0,b=1。P(1)在k1m+1区间上是一个k-1次有理多项式,P()在整条曲线 上具有k-2阶连续性,对于三次B样条基函数,具有C连续性。当n=k-1时,k阶NRBS曲线变成k-1次有 理 Bezier曲线,k阶 NURBS曲线的节点矢量中两端节点的节点重复度取成k+1就使得曲线具有同次有理 Bezier 曲线的端点几何性质 Rk(t)具有k阶B样条基函数类似的性质: (1)局部支承性:R(t)=0,t[t,ti] ∑Rk(u)=1 (2)权性 (3)可微性:如果分母不为零,在节点区间内是无限次连续可微的,在节点处(k-1-r)次连续可导,r 是该节点的重复度 (4)若w=0,则Rk(t)=0: 5)若W=+￥,则Rk(t)=1 (6)若w产+￥,且ji,则R.k(t)=0 计算机图形学第三章(2)第47页共26页
计算机图形学 第三章(2) 第 47 页 共 26 页 3.1.4 NURBS 曲线与曲面 B 样条方法在表示与设计自由型曲线曲面形状时显示了强大的威力，然而在表示与设计初等曲线曲面时时 却遇到了麻烦。因为 B 样条曲线包括其特例的 Bezier 曲线都不能精确表示出抛物线外的二次曲线，B 样条曲 面包括其特例的 Bezier 曲面都不能精确表示出抛物面外的二次曲面，而只能给出近似表示。提出 NURBS 方法， 即非均匀有理 B 样条方法主要是为了找到与描述自由型曲线曲面的 B 样条方法既相统一、又能精确表示二次 曲线弧与二次曲面的数学方法。NURBS 方法的主要优点： （1）既为标准解析形状(即前面提到的初等曲线曲面)，又为自由型曲线曲面的精确表示与设计提供了一 个公共的数学形式。 （2）修改控制顶点和权因子，为各种形状设计提供了充分的灵活性。 （3）具有明显的几何解释和强有力的几何配套技术(包括节点插入、细分、升阶等)。 （4）对几何变换和投影变换具有不变性。 （5）非有理 B 样条、有理与非有理 Bezier 方法是其特例。 不过，目前应用 NURBS 中还有一些难以解决的问题： （1）比传统的曲线曲面定义方法需要更多的存储空间，如空间圆需 7 个参数(圆心、半径、法矢)，而 NURBS 定义空间圆需 38 个参数。 （2）权因子选择不当会引起畸变。 （3）对搭接、重叠形状的处理很麻烦。 （4）反求曲线曲面上点的参数值的算法，存在数值不稳定问题。 3.1.4.1 NURBS 曲线的定义 NURBS 曲线是由分段有理 B 样条多项式基函数定义的： 其中，Ri,k(t)（i=0,1,…,n）称为 k 阶有理基函数，Ni,k(t)是 k 阶 B 样条基函数，Pi（i=0,1,…,n）是特 征多边形控制顶点位置矢量；w i是与 Pi对应的权因子，首末权因子 w 0，w n>0，其余 w i³0，以防止分母为 零及保留凸包性质、曲线不因权因子而退化为一点；节点矢量为 T＝[t0, t1, … , ti, …, tn+k]，节点个数 是 m=n+k+1（n 为控制项的点数，k 为 B 样条基函数的阶数）。 对于非周期 NURBS 曲线，常取两端节点的重复度为 k，即有： ， 在大多数实际应用中，a =0, b =1。P(t)在 区间上是一个 k-1 次有理多项式，P(t)在整条曲线 上具有 k-2 阶连续性，对于三次 B 样条基函数，具有 C 2连续性。当 n=k-1 时，k 阶 NURBS 曲线变成 k-1 次有 理Bezier曲线，k阶NURBS曲线的节点矢量中两端节点的节点重复度取成k+1就使得曲线具有同次有理Bezier 曲线的端点几何性质。 Ri,k(t)具有 k 阶 B 样条基函数类似的性质： （1）局部支承性：Ri,k(t)=0，tÏ[ti, ti+k]； （2）权性： ； （3）可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处 (k-1-r)次连续可导，r 是该节点的重复度。 （4）若 w i=0，则 Ri,k(t)=0； （5）若 w i=+¥ ，则 Ri,k(t)=1； （6）若 w j=+¥ ，且 j¹i，则 Ri,k(t)=0；
(7)若w产1,j=0,1,…,n,则 k(t)=N(t) 是B样条基函数:若w1,j=0,1,…,n,且 7={0 k+1 01,:3)RA()=BA() Bk(t)是 Bernstein基函数。 Rk(t)与Nk(t)具有类似的性质,导致NRBS曲线与B样条曲线也具有类似的几何性质 (1)局部性质。k阶NUBS曲线上参数为 ∈[t,t +/c k-1n+1 P( 点()至多与k个控制顶 点P及权因子 O,(=-k+1,…,) 有关,与其它顶点和权因子无关;另一方面,若移动k次 NURBS 曲线的一个拉制顶点或改变所联系的权因子仅仅影响定义在区同,4+=[t4,m]上那部分曲线 (2)变差减小性质。 3)凸包性,定义在非零节点区间∈[,+]<[1n]上曲线段位于定义它的k1个控制顶点 的凸包内。整条NRBS曲线位于所有定义各曲线段的控制顶点的凸包的并集内。所有权因子 的非负性,保证了凸包性质的成立。 (4)在仿射与透射变换下的不变性。 (5)在曲线定义域内有与有理基函数同样的可微性 (6)如果某个权因子2为零,那么相应控制顶点2对曲线没有影响。 D.→)∞ (7)若 则当 t∈[t1,t1 P(t)=P (8)非有理与有理 Bezier曲线和非有理B样条曲线是 NURBS曲线的特殊情况 3.1.4.2齐次坐标表示 为了便于讨论,我们考虑平面NRBS曲线的情况。如图3.1.34所示,如果给定一组控制顶点 弓=(x1,y)=0,…,n) 及对应的权因子O(=01,…,n) ,则在齐次坐标系xyw中的控制顶 点为F=(x,0,y,)=01…,n) 齐次坐标下的k阶非有理B样条曲线可表示为: P (t)=P Nk(t) 若以坐标原点为投影中心,则得到平面曲线 @,PNk(t, (t) 计算机图形学第三章(2)第48页共26页
计算机图形学 第三章(2) 第 48 页 共 26 页 （7）若 w j=1，j=0,1,…,n, 则 是 B 样条基函数；若 w j=1，j=0,1,…,n，且 则 ，Bi,k(t)是 Bernstein 基函数。 Ri,k(t)与 Ni,k(t)具有类似的性质，导致 NURBS 曲线与 B 样条曲线也具有类似的几何性质： （1）局部性质。k 阶 NURBS 曲线上参数为 的一点 至多与 k 个控制顶 点 Pi及权因子 有关，与其它顶点和权因子无关；另一方面，若移动 k 次 NURBS 曲线的一个控制顶点 Pi或改变所联系的权因子仅仅影响定义在区间 上那部分曲线 的形状。 （2）变差减小性质。 （3）凸包性。定义在非零节点区间 上曲线段位于定义它的 k+1 个控制顶点 的凸包内。整条 NURBS 曲线位于所有定义各曲线段的控制顶点的凸包的并集内。所有权因子 的非负性，保证了凸包性质的成立。 （4）在仿射与透射变换下的不变性。 （5）在曲线定义域内有与有理基函数同样的可微性。 （6）如果某个权因子 为零，那么相应控制顶点 对曲线没有影响。 （7）若 ，则当 时， 。 （8）非有理与有理 Bezier 曲线和非有理 B 样条曲线是 NURBS 曲线的特殊情况。 3.1.4.2 齐次坐标表示 为了便于讨论，我们考虑平面 NURBS 曲线的情况。如图 3.1.34 所示，如果给定一组控制顶点 及对应的权因子 ，则在齐次坐标系 xyw 中的控制顶 点为 。齐次坐标下的 k 阶非有理 B 样条曲线可表示为： 若以坐标原点为投影中心，则得到平面曲线：
P(t) X 图3.1.34平面 NURBS曲线齐次 坐标表示 三维空间的NRS曲线可以类似地定义。即对于给定的一组控制项点1x,y2,z)(=01…,n) 及对应的权因子 (=0,1,…,),则有相应的带权控制点 P=(ox1,C3y,O2,)(=0,…,n) ,定义了一条四维的k阶非有理B样条曲线 () 然后,取它在第四坐标 的超平面上的中心投影,即得三维空间里定义的一条k阶MRs曲线F(t) 这不仅包含了明确的几何意义,也说明,非有理B样条的算法可以推广到NURS曲线,只不过是在齐次坐标 下进行 3.1.4.3权因子的几何意义 由于NRBS曲线权因子w只影响参数区间定义在区间 ]∈lk-1,2zn+上的那部分曲线的形状, 因此,我们只考察整条曲线的这一部分。如果固定曲线的参数t,而使变化,则 NURBS曲线方程变成以 为参数的直线方程,即 NURBS曲线上t值相同的点都位于同一直线上,如图3.1.35所示。我们把曲线与有理 基函数的记号用用如下包含其权因子2为变量的记号替代。因当 O→∞Rk(t;O2>∞)=1 故该直线通过控制顶点,B,N, B分别O1=0,0=1a1≠01 对应曲线上的点,即 B=P(t;a3=0)N=P(t;1),B1=P(t;O1≠01)B=F(t;O1→>) 令 a =Rik(t:w=1),b=Rik(u) 可表示为 M=(1-a)B+a B,=(1-B)B+ap 用a、b可得到下述比例关系: 1-a.1-_PN,BB1 B BN BB 上式是(P,B,N,B)四点的交比,由此式可知: (1)若w;增大活减小,则b也增大或减小,所以曲线被拉向或推离开P;点 (2)若w;增大或减小,曲线被推离或拉向P;(ji)。 计算机图形学第三章(2)第49页共26页
计算机图形学 第三章(2) 第 49 页 共 26 页 三维空间的 NURBS 曲线可以类似地定义。即对于给定的一组控制顶点 及对应的权因子 ，则有相应的带权控制点 ，定义了一条四维的 k 阶非有理 B 样条曲线 ， 然后，取它在第四坐标 的超平面上的中心投影，即得三维空间里定义的一条 k 阶 NURBS 曲线 。 这不仅包含了明确的几何意义，也说明，非有理 B 样条的算法可以推广到 NURBS 曲线，只不过是在齐次坐标 下进行。 3.1.4.3 权因子的几何意义 由于 NURBS 曲线权因子 w i只影响参数区间定义在区间 上的那部分曲线的形状， 因此，我们只考察整条曲线的这一部分。如果固定曲线的参数 t，而使 变化，则 NURBS 曲线方程变成以 为参数的直线方程，即 NURBS 曲线上 t 值相同的点都位于同一直线上，如图 3.1.35 所示。我们把曲线与有理 基函数的记号用用如下包含其权因子 为变量的记号替代。因当 时， 的，故该直线通过控制顶点 ， 分别是 对应曲线上的点，即 ， ， 。 令 a =Ri,k(t; w i=1 )，b = Ri,k(u) N，Bi可表示为： 用 a 、b 可得到下述比例关系： 上式是(Pi，Bi，N，B)四点的交比，由此式可知： （1）若 w i增大活减小，则 b 也增大或减小，所以曲线被拉向或推离开 Pi点； （2）若 w j增大或减小，曲线被推离或拉向 Pj（j¹i）
图3.1.35 NURBS曲线中的权因子的作用 3.1.4.4圆锥曲线的 NURBS表示 若取节点向量为7=[0.0011,则R曲线退化为二次 B曲线,且 (t) (1-t2)o0B+2(1-t)a1+t2B2 (1-t)ao+2(1-t)a1+to2 可以证明,这是圆锥曲线弧方程 002称为形状因子,的值确定了圆锥曲线的类型 时,上式是抛物线弧,∈(1,+∞) 时,上式是双曲线弧 C∈(0,1) 时,上式是椭圆弧。 时,上式退化为一对直线段分 22 ∞ 时,上式退化为连接 2 两点的 直线段,如图3.1.36所示。 双曲线 抛物线 椭圆 B P 图3.1.36圆锥曲线的 NURBS表示 3.1.45 NURBS曲线的修改 NURBS曲线的修改有多种方式,常用的方法有修改权因子、控制点和反插节点 1.修改权因子 权因子的作用是:当保持控制顶点和其它权因子不变,减少或增加某权因子时,曲线被推离或拉向相应顶 点。假定已给k阶(k-1)次NRBS曲线上参数为t的一点S,欲将曲线在该点拉向或推离控制顶点一个 距离d,以得到新点S,可由重新确定相应的权因子O使之改变为O来达到,如图3.137所示 d 1+ ()(Ps 计算机图形学第三章(2)第50页共26页
计算机图形学 第三章(2) 第 50 页 共 26 页 3.1.4.4 圆锥曲线的 NURBS 表示 若取节点向量为 ，则 NURBS 曲线退化为二次 Bezier 曲线，且： 可以证明，这是圆锥曲线弧方程， 称为形状因子， 的值确定了圆锥曲线的类型。 时，上式是抛物线弧， 时，上式是双曲线弧， 时，上式是椭圆弧。 且 时，上式退化为一对直线段 和 ， 时，上式退化为连接 两点的 直线段，如图 3.1.36 所示。 3.1.4.5 NURBS 曲线的修改 NURBS 曲线的修改有多种方式，常用的方法有修改权因子、控制点和反插节点。 1．修改权因子 权因子的作用是：当保持控制顶点和其它权因子不变，减少或增加某权因子时，曲线被推离或拉向相应顶 点。假定已给 k 阶（k-1）次 NURBS 曲线上参数为 t 的一点 S，欲将曲线在该点拉向或推离控制顶点 一个 距离 d，以得到新点 ，可由重新确定相应的权因子 使之改变为 来达到，如图 3.1.37 所示
图3.1.37修改权因子 其,2S=B和S两点间的距离,d有正负之分,若S在和之间,即曲线被拉向顶点和, 为正,反之为负 修改过程是拾取曲线上一点S,并确定该点的参数 t∈[,+] 再拾取控制多边形的一个顶点 它是k+1个控制顶点2-+1,中的一个,即-k+1≤t≤ 便可算出两点间的距离d。若在 直线段S上拾取一个点S”,就能确定替代老权因子O)的新权因子O2,修改后的曲线将通过S”点。 2.修改控制顶点 若给定曲线上参数为2的一点S,方向矢量V和距离d,计算控制顶点2的新位置2,以使曲线上S 点沿V移动距离d到新位置 可表示为 ∑P;(t)+(B+az)k() 于是 F-s=d=p1k()→a= VR.k(t) 由此可得新控制顶点: P +av 3.反插节点 给定制多边形顶点与权因子(=01,…,n)及节点矢量了=[t,,…,m*],就定义了 一条k阶NR曲线,现欲在该多边形的的边上选取一点F,使得F点成为一个新的制项点,这 就是所谓反插节点。P点可按有理线性插值给出: p=(1-)+0+性 于是 +12i+ 所以 计算机图形学第三章(2)第51页共26页
计算机图形学 第三章(2) 第 51 页 共 26 页 其中， 表示 和 两点间的距离，d 有正负之分，若 在 和 之间，即曲线被拉向顶点 和， d 为正，反之为负。 修改过程是拾取曲线上一点 ，并确定该点的参数 ，再拾取控制多边形的一个顶点 ， 它是 k+1 个控制顶点 中的一个，即 ，便可算出两点间的距离 d。若在 直线段 上拾取一个点 ，就能确定替代老权因子 的新权因子 ，修改后的曲线将通过 点。 2．修改控制顶点 若给定曲线上参数为 的一点 S，方向矢量 V 和距离 d，计算控制顶点 的新位置 ，以使曲线上 S 点沿 V 移动距离 d 到新位置 。 可表示为： 于是： 由此可得新控制顶点： 3．反插节点 给定控制多边形顶点 与权因子 及节点矢量 ，就定义了 一条 k 阶 NURBS 曲线。现欲在该多边形的 的边上选取一点 ，使得 点成为一个新的控制顶点，这 就是所谓反插节点。 点可按有理线性插值给出： 于是： 所以
这就是使得成为一个新控制顶点而要插入的新节点 t∈ 制顶点所替代,如图,+使2成为新控制顶点的同时,将有k2个老控制顶点被包括2在内的新控 当插入新节点 图3.1.38使P成为新控制顶点 3.1.4.6非均匀有理B样条( NURBS)曲面 1. NURBS曲面的定义 由双参数变量分段有理多项式定义的 NURBS曲面是: ay Py Ni,p ( u)ng(v) @yN, p u)Ns(v) ∑∑孕码p(,y),v∈[0, 式中”是矩形域上特征网格控制点列,是相应控制点的权因子,规定四角点处用正权因子,即 0,00,0,Om0.其Og≥0NM,Q)gMya(y) 是p阶和q阶的B样条基函数, ,1 是双变量有理基函数 M,()M2(y) pi g(u,v)= 20M N(yi 入节点矢每U=[40,41,…m+]v=[v、.、按deBo递推公式决定,通常具有 面的形式 U=[0,0,…,0 11,…J, 个q个 v=[0,0,…,0,v p个q个 2. NURBS曲面的性质 有理双变量基函数,p,y 与非有理B样条基函数相类似的性质: 计算机图形学第三章(2)第52页共26页
计算机图形学 第三章(2) 第 52 页 共 26 页 这就是使得 成为一个新控制顶点而要插入的新节点。 当插入新节点 使 成为新控制顶点的同时，将有 k-2 个老控制顶点被包括 在内的新控 制顶点所替代，如图 3.1.38 所示。 3.1.4.6 非均匀有理 B 样条（NURBS）曲面 1.NURBS 曲面的定义 由双参数变量分段有理多项式定义的 NURBS 曲面是： 式中 是矩形域上特征网格控制点列， 是相应控制点的权因子，规定四角点处用正权因子，即 ，其余 。 和 是 p 阶和 q 阶的 B 样条基函数， 是双变量有理基函数： 节点矢量 和 按 de Boor 递推公式决定，通常具有 下面的形式： p 个 q 个 p 个 q 个 2.NURBS 曲面的性质 有理双变量基函数 与非有理 B 样条基函数相类似的性质：
(1)局部支承性质:,以9(,y)=0M生[4,2+]vg[y,计+ 22.y)=1 (2)权性: (3)可微性:在每个子矩形域内所有偏导数存在,在重复度为r的u节点处沿u向是p-r-1次连续可微 在重复度为r的v节点处沿v向是q-r-1次连续可德 (4)极值:若p,q1,恒有一个极大值存在 R,(,v) 是双变量B样条基函数的推广 NURBS曲面与非有理B样条曲面也有相类似的几何性质,权因子的几何意义及修改、控制顶点的修改等也 与NRBS曲线类似,这里不在赘述 3.2形体在计算机内的表示 我们已经知道,计算机中表示形体,通常用线框、表面和实体三种模型。线框模型和表面模型保存的三维 形体信息都不完整,只有实体模型才能够完整地、无歧义地表示三维形体。前面我们已经介绍了曲线曲面常 用的的表示形式及其理论基础,从本小节开始,我们介绍实体造型技术的有关问题,主要包括形体在计算机 内的表示、分类求交算法和典型的实体造型系统。 3.2.1引言 实体造型技术的研究可以追到溯到六十年代初期,不过,直到六十年代后半期,有关实体造型的报道仍然 很少。七十年代初期,出现了一些实体造型系统,如英国剑桥大学的 BUILD-1系统,德国柏林工业大学的 COMPAC系统,日本北海道大学的TIPS-1系统和美国罗切斯特大学的PADL-1、PADL-2系统等 这些早期的实体造型系统有一个共同的特点:不支持精确的曲面表示,用多面体表示形体。多面体模型的 优点是数据结构相对简单,集合运算、明暗图的生成和显示速度快。但是,同一系统中存在两种表示:精确 的曲面表示和近似的多面体逼近,违背了几何定义唯一性原则;而且,曲面形体使用多面体模型只是近似表 示,存在误差,若要提高表示精度时,就需要增加离散平面片的数量,庞大数据量影响计算速度和计算机的 存储管理,也是难以接受的。显然,要为了解决这个问题,就需要在几何造型系统中采用精确的形体表示模 六、七十年代,雕塑曲面的研究取得了很大的进展, Coons曲面、 Bezier曲线和曲面、B样条曲线和曲面 等设计方法相继提出,并在汽车、航空和造船等行业得到了广泛的应用。曲面造型系统由于缺乏面片的连接 关系,不仅使曲面的交互修改非常复杂,而且也难于构造封闭的形体。实体造型系统则由于不能有效地处理 复杂曲面,也使其几何造型的覆盖域受到了很大的限制。自然,如何构造能够精确表示形体的几何造型系统, 成了人们研究的目标。1978年,英国 Shape data公司推出了实体造型系统 Romulus,并首次引入了精确的 二次曲面,二次曲面的表示采用了代数方程的形式 八十年代末,出现了 NURBS曲线曲面设计方法,已有的曲线曲面表示方法,如 Bezier方法、B样条方法 等,可以用NRBS方法统一表示,且能精确表示二次曲线曲面。由于 NURBS的强大的表示能力,能够精确表 示形体的几何造型系统,纷纷采用了 NURBS方法,国际标准化组织也已将 NURBS作为定义工业产品形状的唯 数学方法。 早期的几何造型系统还有一个特点,就是只支持正则的形体造型。正则形体集(R-Set)的概念由罗切斯 特大学 Requicha引入造型系统,并为几何造型奠定了初步的理论基础, 为了描述正则形体,引入了二维流形(2- manifold)的概念。所谓二维流形是指这样一些面,其上任 点都存在一个充分小的邻域,该邻域与平面上的圆盘是同构的,即在该邻域与圆盘之间存在连续的1-1映射 对于任一形体,如果它是3维欧氏空间中非空、有界的封闭子集,且其边界是二维流形(即该形体是 连通的),我们称该形体为正则形体,否则称为非正则形体。图3.2.1给出了一些非正则形体的实例 计算机图形学第三章(2)第53页共26页
计算机图形学 第三章(2) 第 53 页 共 26 页 （1）局部支承性质： ，当 或 ； （2）权性： ； （3）可微性：在每个子矩形域内所有偏导数存在，在重复度为 r 的 u 节点处沿 u 向是 p-r-1 次连续可微， 在重复度为 r 的 v 节点处沿 v 向是 q-r-1 次连续可微； （4）极值：若 p，q>1，恒有一个极大值存在； （5） 是双变量 B 样条基函数的推广。 NURBS 曲面与非有理 B 样条曲面也有相类似的几何性质，权因子的几何意义及修改、控制顶点的修改等也 与 NURBS 曲线类似，这里不在赘述。 3.2 形体在计算机内的表示 我们已经知道，计算机中表示形体，通常用线框、表面和实体三种模型。线框模型和表面模型保存的三维 形体信息都不完整，只有实体模型才能够完整地、无歧义地表示三维形体。前面我们已经介绍了曲线曲面常 用的的表示形式及其理论基础，从本小节开始，我们介绍实体造型技术的有关问题，主要包括形体在计算机 内的表示、分类求交算法和典型的实体造型系统。 3.2.1 引言 实体造型技术的研究可以追到溯到六十年代初期，不过，直到六十年代后半期，有关实体造型的报道仍然 很少。七十年代初期，出现了一些实体造型系统，如英国剑桥大学的 BUILD-1 系统，德国柏林工业大学的 COMPAC 系统，日本北海道大学的 TIPS-1 系统和美国罗切斯特大学的 PADL-1、PADL-2 系统等。 这些早期的实体造型系统有一个共同的特点：不支持精确的曲面表示，用多面体表示形体。多面体模型的 优点是数据结构相对简单，集合运算、明暗图的生成和显示速度快。但是，同一系统中存在两种表示：精确 的曲面表示和近似的多面体逼近，违背了几何定义唯一性原则；而且，曲面形体使用多面体模型只是近似表 示，存在误差，若要提高表示精度时，就需要增加离散平面片的数量，庞大数据量影响计算速度和计算机的 存储管理，也是难以接受的。显然，要为了解决这个问题，就需要在几何造型系统中采用精确的形体表示模 型。 六、七十年代，雕塑曲面的研究取得了很大的进展，Coons 曲面、Bezier 曲线和曲面、B 样条曲线和曲面 等设计方法相继提出，并在汽车、航空和造船等行业得到了广泛的应用。曲面造型系统由于缺乏面片的连接 关系，不仅使曲面的交互修改非常复杂，而且也难于构造封闭的形体。实体造型系统则由于不能有效地处理 复杂曲面，也使其几何造型的覆盖域受到了很大的限制。自然，如何构造能够精确表示形体的几何造型系统， 成了人们研究的目标。1978 年，英国 Shape Data 公司推出了实体造型系统 Romulus，并首次引入了精确的 二次曲面，二次曲面的表示采用了代数方程的形式。 八十年代末，出现了 NURBS 曲线曲面设计方法，已有的曲线曲面表示方法，如 Bezier 方法、B 样条方法 等，可以用 NURBS 方法统一表示，且能精确表示二次曲线曲面。由于 NURBS 的强大的表示能力，能够精确表 示形体的几何造型系统，纷纷采用了 NURBS 方法，国际标准化组织也已将 NURBS 作为定义工业产品形状的唯 一数学方法。 早期的几何造型系统还有一个特点，就是只支持正则的形体造型。正则形体集（R-Set）的概念由罗切斯 特大学 Requicha 引入造型系统，并为几何造型奠定了初步的理论基础。 为了描述正则形体，引入了二维流形（2-manifold）的概念。所谓二维流形是指这样一些面，其上任一 点都存在一个充分小的邻域，该邻域与平面上的圆盘是同构的，即在该邻域与圆盘之间存在连续的 1-1 映射。 对于任一形体，如果它是 3 维欧氏空间 中非空、有界的封闭子集，且其边界是二维流形（即该形体是 连通的），我们称该形体为正则形体，否则称为非正则形体。图 3.2.1 给出了一些非正则形体的实例
气 (a)有悬面 (c)一条边有两个以上 (b)有悬边 的邻面(不连通) 图3.2.1非正则形体实例 基于正则形体表示的实体造型形体只能表示正则的三维“体”,低于三维的形体是不能存在的。这样,线框 模型中的“线",表面模型中的“面”,都是实体造型系统中所不能表示的。但在实际应用中,有时候人们希望在 系统中也能处理象形体中心轴、剖切平面这样低于三维的形体,这就要求造型系统的数据结构能统一表示线 框、表面、实体模型 集合运算(并、交、差)是构造形体的基本方法,正则形体经过集合运算后,可能会产生悬边、悬面等低 于三维的形体,如图3.2.2所示。 Requicha在引入正则形体概念的同时,还定义了正则集合运算的概念,正 则集合运算保证集合运算的结果仍是一个正则形体,即丢弃悬边、悬面等,如图3.2.3所示。但是,这些信 息在很多应用中是有用的,不能丢弃,这也要求几何造型系统要能够表示边、面等低于三维的形体。即是说, 几何造型系统要求能够处理非正则形体,于是,产生了非正则造型技术。 A 图3.2.2二个二维图形的交产 生一个退化的结果 A B B 悬边 C=A∩B C=A∩B 集合论的求交计算 正则集合下的求交运算 图3.2.3集合和正则的交运算 计算机图形学第三章(2)第54页共26页
计算机图形学 第三章(2) 第 54 页 共 26 页 基于正则形体表示的实体造型形体只能表示正则的三维“体”，低于三维的形体是不能存在的。这样，线框 模型中的“线”，表面模型中的“面”，都是实体造型系统中所不能表示的。但在实际应用中，有时候人们希望在 系统中也能处理象形体中心轴、剖切平面这样低于三维的形体，这就要求造型系统的数据结构能统一表示线 框、表面、实体模型。 集合运算（并、交、差）是构造形体的基本方法，正则形体经过集合运算后，可能会产生悬边、悬面等低 于三维的形体，如图 3.2.2 所示。Requicha 在引入正则形体概念的同时，还定义了正则集合运算的概念，正 则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等，如图 3.2.3 所示。但是，这些信 息在很多应用中是有用的，不能丢弃，这也要求几何造型系统要能够表示边、面等低于三维的形体。即是说， 几何造型系统要求能够处理非正则形体，于是，产生了非正则造型技术
九十年代以来,基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术 已成为几何造型技术的主流。 3.22形体表示模型 在实体模型的表示中,出现了许多方法,基本上可以分为分解表示、构造表示和边界表示三大类 1.分解表示 分解表示是将形体按某种规则分解为小的更易于描述的部分,每一小部分又可分为更小的部分,这种分解 过程直至每一小部分都能够直接描述为止。分解表示的一种特殊形式是每一小的部分都是一种固定形状(正方 形、立方体等)的单元,形体被分解成这些分布在空间网格位置上的具有邻接关系的固定形状单元的集合,单 元的大小决定了单元分解形式的精度。根据基本单元的不同形状,常用四叉树、八叉树和多叉树等表示方法 分解表示中一种比较原始的表示方法是将形体空间细分为小的立方体单元,与此相对应,在计算机内存中 开辟一个三维数组。凡是形体占有的空间,存储单元中记为1:其余空间记为0。这种表示方法的优点是简单 容易实现形体的交、并、差计算,但是占用的存储量太大,物体的边界面没有显式的解析表达式,不便于运 算,实际上并未采用。 图3.2.4是八叉树表示形体的一个实例。八叉树法表示形体的过程是这样的,首先对形体定义一个外接 立方体,再把它分解成八个子立方体,并对立方体依次编号为0,1,2,…,7。如果子立方体单元已经一致, 即为满(该立方体充满形体)或为空(没有形体在其中),则该子立方体可停止分解:否则,需要对该立方 体作进一步分解,再一分为八个子立方体。在八叉树中,非叶结点的每个结点都有八个分支。八叉树表示法 有一些优点,近年来受到人们的注意。这些优点主要是: (1)形体表示的数据结构简单。 2)简化了形体的集合运算。对形体执行交、并、差运算时,只需同时遍历参加集合运算的两形体相应 的八叉树,无需进行复杂的求交运算 (3)简化了隐藏线(或面)的消除,因为在八叉树表示中,形体上各元素已按空间位置排成了一定的顺 (4)分析算法适合于并行处理 八叉树表示的缺点也是明显的,主要是占用的存储多,只能近似表示形体,以及不易获取形体的边界信息 O具有子孙的节点 口空节点 百百白白白口 口实节点 图3.2.4用八叉树表示形体 2.构造表示 计算机图形学第三章(2)第55页共26页
计算机图形学 第三章(2) 第 55 页 共 26 页 九十年代以来，基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术 已成为几何造型技术的主流。 3.2.2 形体表示模型 在实体模型的表示中，出现了许多方法，基本上可以分为分解表示、构造表示和边界表示三大类。 1．分解表示 分解表示是将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解 过程直至每一小部分都能够直接描述为止。分解表示的一种特殊形式是每一小的部分都是一种固定形状(正方 形、立方体等)的单元，形体被分解成这些分布在空间网格位置上的具有邻接关系的固定形状单元的集合，单 元的大小决定了单元分解形式的精度。根据基本单元的不同形状，常用四叉树、八叉树和多叉树等表示方法。 分解表示中一种比较原始的表示方法是将形体空间细分为小的立方体单元，与此相对应，在计算机内存中 开辟一个三维数组。凡是形体占有的空间，存储单元中记为 1；其余空间记为 0。这种表示方法的优点是简单， 容易实现形体的交、并、差计算，但是占用的存储量太大，物体的边界面没有显式的解析表达式，不便于运 算，实际上并未采用。 图 3.2.4 是八叉树表示形体的一个实例。八叉树法表示形体的过程是这样的，首先对形体定义一个外接 立方体，再把它分解成八个子立方体，并对立方体依次编号为 0，1，2，…，7。如果子立方体单元已经一致， 即为满（该立方体充满形体）或为空（没有形体在其中），则该子立方体可停止分解；否则，需要对该立方 体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。八叉树表示法 有一些优点，近年来受到人们的注意。这些优点主要是： （1）形体表示的数据结构简单。 （2）简化了形体的集合运算。对形体执行交、并、差运算时，只需同时遍历参加集合运算的两形体相应 的八叉树，无需进行复杂的求交运算。 （3）简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元素已按空间位置排成了一定的顺 序。 （4）分析算法适合于并行处理。 八叉树表示的缺点也是明显的，主要是占用的存储多，只能近似表示形体，以及不易获取形体的边界信息 等。 2．构造表示
构造表示是按照生成过程来定义形体的方法,构造表示通常有扫描表示、构造实体几何表示和特征表示三 扫描表 扫描表示是基于一个基体(一般是一个封闭的平面轮廓)沿某一路径运动而产生形体。可见,扫描表示需 要两个分量,一个是被运动的基体,另一个是基体运动的路径:如果是变截面的扫描,还要给出截面的变化 规律。图3.2.5给出了扫描表示的一些例子,(a)是拉伸体(扫描路径是直线),(c)是回转体,(b)、 (d)扫描体的扫描路径是曲线,且(b)是等截面扫描,(d)是变截面扫描。 扫描是生成三维形体的有效方法,但是,用扫描变换产生的形体可能出现维数不一致的问题。如图3.2.6 所示,其中(a)图表示一条曲线经平移(扫描路径是直线)扫描变换后产生了一个表面和二条悬边;(b) 图中一条曲线经平移扫描变换后产生的形体是两个二维的表面间有一条一维的边相连:(c)、(d)图中表 示扫描变换的基体本身维数不一致,因而产生的结果形体也是维数不一致且有二义性。另外,扫描方法不能 直接获取形体的边界信息,表示形体的覆盖域非常有限。 扫描方向 基面 基面 基面 基面 回转轴 图3.2.5生成扫描形体的例子 计算机图形学第三章(2)第56页共26页
计算机图形学 第三章(2) 第 56 页 共 26 页 构造表示是按照生成过程来定义形体的方法，构造表示通常有扫描表示、构造实体几何表示和特征表示三 种。 • 扫描表示 扫描表示是基于一个基体（一般是一个封闭的平面轮廓）沿某一路径运动而产生形体。可见，扫描表示需 要两个分量，一个是被运动的基体，另一个是基体运动的路径；如果是变截面的扫描，还要给出截面的变化 规律。图 3.2.5 给出了扫描表示的一些例子,（a）是拉伸体（扫描路径是直线），（c）是回转体，（b）、 （d）扫描体的扫描路径是曲线，且（b）是等截面扫描，（d）是变截面扫描。 扫描是生成三维形体的有效方法，但是，用扫描变换产生的形体可能出现维数不一致的问题。如图 3.2.6 所示，其中（a）图表示一条曲线经平移（扫描路径是直线）扫描变换后产生了一个表面和二条悬边；（b） 图中一条曲线经平移扫描变换后产生的形体是两个二维的表面间有一条一维的边相连；（c）、（d）图中表 示扫描变换的基体本身维数不一致，因而产生的结果形体也是维数不一致且有二义性。另外，扫描方法不能 直接获取形体的边界信息，表示形体的覆盖域非常有限