CG2014_07_三维对象的表示

1、计算机图形学2 27.1 三维对象表示方法概述三维对象表示方法概述7.2 多边形表面多边形表面7.3 二次曲面二次曲面7.4 样条曲线概述样条曲线概述7.5 Hermite样条曲线样条曲线7.6 Bzier曲线和曲面曲线和曲面7.7 B样条曲线和曲面样条曲线和曲面7.8 空间分区表示方法空间分区表示方法7.9 非规则对象表示方法非规则对象表示方法计算机图形学3 37.1.1 三维图形的基本问题三维图形的基本问题7.1.2 数据模型数据模型7.1.3 过程模型过程模型计算机图形学4 41. 在二维屏幕上如何显示三维物体？在二维屏幕上如何显示三维物体？显示器屏幕、绘图纸等是二维的显示器屏幕、绘图纸

2、等是二维的显示对象是三维的显示对象是三维的解决方法解决方法-投影投影三维显示设备正在研制中三维显示设备正在研制中2. 如何表示三维物体？如何表示三维物体？二维形体的表示二维形体的表示-直线段直线段, ,折线折线, ,曲线段曲线段, ,多边形区多边形区域域三维形体的表示三维形体的表示-空间直线段、折线、空间直线段、折线、曲线段曲线段、多边形、多边形、曲面片曲面片计算机图形学5 5线框模型：将形体表示成线框模型：将形体表示成一组轮廓线的集合。一组轮廓线的集合。一般地，画出了形体的棱线与轮廓一般地，画出了形体的棱线与轮廓线就能唯一地表示出来。如图，八线就能唯一地表示出来。如图，八个顶点可以定义一个长

3、方体，但还个顶点可以定义一个长方体，但还不足以识别它，如果定义了棱线，不足以识别它，如果定义了棱线，则无论如何放置长方体都能唯一地则无论如何放置长方体都能唯一地表示了。对于多面体由于其轮廓线表示了。对于多面体由于其轮廓线和棱线通常是一致的，所以多面体和棱线通常是一致的，所以多面体的线模型更便于识别，且简单。的线模型更便于识别，且简单。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4计算机图形学6 6计算机图形学7 7计算机图形学8 8计算机图形学9 9线框模型线框模型用三维线框模型表示三维形体常具有用三维线框模型表示三维形体常具有二

4、义性二义性 由于不存在面的信息，三维线框容易构造出由于不存在面的信息，三维线框容易构造出无效形体无效形体 由于不能表示出曲面的轮廓线，所以不能正由于不能表示出曲面的轮廓线，所以不能正确表示曲面信息确表示曲面信息 无法进行图形的线面消隐。无法进行图形的线面消隐。生成复杂形体时，线框模型要求输入大量的生成复杂形体时，线框模型要求输入大量的数据，加重用户的输入负担。数据，加重用户的输入负担。难以保证数据的统一性和有效性。难以保证数据的统一性和有效性。 两种看法（伞两种看法（伞尖远离视点或尖远离视点或指向视点）指向视点）旋转时出现不旋转时出现不同效果同效果计算机图形学1010计算机图形学1111八叉树

5、模型及八叉树编码示意图八叉树模型及八叉树编码示意图Von koch snowflake计算机图形学1212多边形表面分为两组进行组织多边形表面分为两组进行组织几何表：几何表：顶点坐标和用来标识多边形表面顶点坐标和用来标识多边形表面空间方向的参数空间方向的参数 点表、边表、面表点表、边表、面表属性表：属性表：指明物体透明度及表面反射度的指明物体透明度及表面反射度的参数和纹理特征参数和纹理特征计算机图形学1313顶点表顶点表序号序号点坐标点坐标1x1, y1, z12x2, y2, z23x3, y3, z34x4, y4, z45x5, y5, z5边表边表序号序号顶点号顶点号1v1, v22v

6、2, v33v3, v14v3, v45v4, v56v5, v1多边形面表多边形面表序号序号边序号边序号1E1, E2, E32E3, E4, E5, E6E1E2E4E5S1v2v1v3v4v5E3E6S2计算机图形学1414多边形网多边形网格格 图形系统图形系统一般使用一般使用多边形网多边形网格对格对3D物物体进行建体进行建模模计算机图形学1515计算机图形学1616(a) 线框图线框图 野鸭模型的多边形表示，有野鸭模型的多边形表示，有6656个面片，个面片，3474个顶点。个顶点。(b) 原始法向着色图原始法向着色图(c) 平均法向着色图平均法向着色图计算机图形学1717多边形网格：三

7、维形体的边界通常用多边形多边形网格：三维形体的边界通常用多边形网格（网格（polygon mesh）的拼接来模拟。）的拼接来模拟。球面球面椭球面椭球面环面环面超超二次曲面二次曲面二次曲面二次曲面和和超二次曲面超二次曲面 不能表达复杂的曲线不能表达复杂的曲线和曲面。例如飞机或汽车的流线表面和曲面。例如飞机或汽车的流线表面.使使用用样条样条表示表示计算机图形学1818样条的历史样条的历史很早的绘图员利用很早的绘图员利用“ducks”和有柔性的木条（样条）来绘和有柔性的木条（样条）来绘制曲线制曲线木质的样条具有二阶连续木质的样条具有二阶连续并且通过所有的控制点并且通过所有的控制点A Duck (we

8、ight)Ducks trace out curve计算机图形学1919样条：通过一组指定点集而生成平滑曲线的柔性样条：通过一组指定点集而生成平滑曲线的柔性带带样条曲线在计算机图形学中的含义样条曲线在计算机图形学中的含义由多项式曲线段连接而成的曲线由多项式曲线段连接而成的曲线在每段的边界处满足特定的连续性条件在每段的边界处满足特定的连续性条件样条曲面样条曲面使用两组正交样条曲线进行描述使用两组正交样条曲线进行描述样条样条计算机图形学2020样条在图形学中的应用样条在图形学中的应用设计曲线、曲面设计曲线、曲面汽车车身设计、飞机和航天飞机表面的设计、船体设计汽车车身设计、飞机和航天飞机表面的设计、

9、船体设计以及家庭应用。以及家庭应用。曲线的产生曲线的产生给定一组离散的坐标点，将数据集拟合成指定的曲线函给定一组离散的坐标点，将数据集拟合成指定的曲线函数数根据曲线函数得到曲线的图形根据曲线函数得到曲线的图形计算机图形学2121曲线的类型曲线的类型插值插值样条曲线：选样条曲线：选取的多项式使得曲取的多项式使得曲线通过每个控制点线通过每个控制点逼近逼近样条曲线：选样条曲线：选取的多项式不一定取的多项式不一定使曲线通过每个控使曲线通过每个控制点制点计算机图形学2222n给定一组有序的数据点给定一组有序的数据点P Pi i，i=0, 1, i=0, 1, , n, n，构造一条，构造一条曲线顺序曲线

10、顺序通过这些数据点通过这些数据点，称为对这些数据点进行插，称为对这些数据点进行插值，所构造的曲线称为插值曲线。值，所构造的曲线称为插值曲线。n线性插值：线性插值：假设给定函数假设给定函数f(x)f(x)在两个不同点在两个不同点x1x1和和x2x2的值，用一个线形函数：的值，用一个线形函数：y=ax+by=ax+b，近似代替，称为，近似代替，称为的线性插值函数。的线性插值函数。n抛物线插值抛物线插值: :已知在三个互异点已知在三个互异点 的函数值的函数值为为 ，要求构造一个函数，要求构造一个函数 使抛物线使抛物线 在结点在结点 处与处与 在在 处处 的值相等。的值相等。cbxaxx2)()(x3

11、21,xxx321,yyy) 3 , 2 , 1( ixi)(xfix插值插值计算机图形学2323xyo1y2y)(xfy )(xy 1x2xxyo1y2y)(xfy )(xy 1x2x3x3y(a)(a)(b)(b) 线性插值和抛物插值线性插值和抛物插值计算机图形学2424n逼近：构造一条曲线使之在某种意义下最接近给定的逼近：构造一条曲线使之在某种意义下最接近给定的数据点数据点( (但未必通过这些点但未必通过这些点) )，所构造的曲线称为逼近，所构造的曲线称为逼近曲线。曲线。n在计算数学中，逼近通常指用一些性质较好的函数近在计算数学中，逼近通常指用一些性质较好的函数近似表示一些性质不好的函数

12、。似表示一些性质不好的函数。逼近逼近计算机图形学2525 曲线的逼近曲线的逼近求给定型值点之间曲线上的点称为求给定型值点之间曲线上的点称为曲线的插值曲线的插值。将连接有一定次序控制点的直线序列称为将连接有一定次序控制点的直线序列称为控制多边形控制多边形或或特征多边形特征多边形。计算机图形学2626 曲线的逼近曲线的逼近凸壳的定义凸壳的定义Convex hull 包含一组控制点的凸多边形边界包含一组控制点的凸多边形边界凸壳的作用凸壳的作用提供了曲线或曲面与包围控制点的区域之提供了曲线或曲面与包围控制点的区域之间的偏差的测量间的偏差的测量以凸壳为界的样条保证了多项式沿控制点以凸壳为界的样条保证了多

13、项式沿控制点的平滑前进的平滑前进计算机图形学2727计算机图形学2828光顺光顺(Firing)(Firing)指曲线的拐点不能太多。对平面曲线而指曲线的拐点不能太多。对平面曲线而言，相对光顺的条件是：言，相对光顺的条件是：a. a. 具有二阶几何连续性具有二阶几何连续性(G(G2 2) )；b. b. 不存在多余拐点和奇异点；不存在多余拐点和奇异点；c. c. 曲率变化较小。曲率变化较小。光顺光顺计算机图形学2929假定参数曲线段假定参数曲线段 pi 以参数形式进行描述：以参数形式进行描述：t ,t t)(i1i0tppii 参数连续性参数连续性 几何连续性几何连续性参数连续性与几何连续性参

14、数连续性与几何连续性计算机图形学30301.参数连续性参数连续性0阶参数连续性阶参数连续性记作记作C0连续性，是指曲线的几何位置连接，即连续性，是指曲线的几何位置连接，即)()(0)1()1(1iiiitptp计算机图形学31311阶参数连续性阶参数连续性记作记作C1连续性，指代表两个相邻曲线段的方程在相交点处有连续性，指代表两个相邻曲线段的方程在相交点处有相同的一阶导数：相同的一阶导数：)()()()(0)1()1(10)1()1(1iiiiiiiitptptptp且计算机图形学32322阶参数连续性阶参数连续性，记作，记作C2连续性，指两个相邻曲线段的方程连续性，指两个相邻曲线段的方程在相

15、交点处具有相同的一阶和二阶导数。在相交点处具有相同的一阶和二阶导数。 (a)0阶连续性(b)1阶连续性(c)2阶连续性计算机图形学33332.几何连续性几何连续性0阶几何连续性阶几何连续性，记作，记作G0连续性，与连续性，与0阶参数连续性的定义相同，阶参数连续性的定义相同，满足：满足： 1阶几何连续性阶几何连续性，记作，记作G1连续性，指一阶导数在相邻段的交点处连续性，指一阶导数在相邻段的交点处成比例成比例;2阶几何连续性阶几何连续性，记作，记作G2连续性，指相邻曲线段在交点处其一阶连续性，指相邻曲线段在交点处其一阶和二阶导数均成比例。和二阶导数均成比例。)()(0)1()1(1iiiitpt

16、p计算机图形学3434参数参数连续性条件连续性条件 两个相邻曲线段在相交处的参数导数两个相邻曲线段在相交处的参数导数相等相等零阶连续零阶连续(C0连续连续)：简单地表示曲线：简单地表示曲线连接连接一阶连续一阶连续(C1连续连续)：说明代表两个相邻曲线的方程：说明代表两个相邻曲线的方程在相交点处有在相交点处有相同的一阶导数相同的一阶导数（切线）（切线）二阶连续二阶连续(C2连续连续)：两个曲线段在交点处有：两个曲线段在交点处有相同的相同的一阶和二阶导数一阶和二阶导数，交点处的切向量变化率相等，交点处的切向量变化率相等计算机图形学3535零阶连续零阶连续 一阶连续一阶连续 二阶连续二阶连续F(u)

17、f(u)F(1)=f(0)F(1)=f(0)F (1)=f (0)计算机图形学3636几何几何连续性条件连续性条件 两个相邻曲线段在相交处的参数导数两个相邻曲线段在相交处的参数导数成比例成比例零阶连续（零阶连续（G0连续）：与连续）：与0阶参数连续性相同，阶参数连续性相同，即两个曲线必在公共点处有相同的坐标即两个曲线必在公共点处有相同的坐标一阶连续（一阶连续（G1连续）：表示连续）：表示一阶导数一阶导数在两个相邻在两个相邻曲线的交点处成比例曲线的交点处成比例二阶连续（二阶连续（G2连续）：表示两个曲线段在相交处连续）：表示两个曲线段在相交处的一阶和二阶导数均成比例的一阶和二阶导数均成比例计算机

18、图形学37377.6.1 Bezier曲线的定义曲线的定义 Bezier Bezier曲线的例子曲线的例子计算机图形学3838定义：定义：其中，其中，PiPi构成该构成该BezierBezier曲线的特征多边形曲线的特征多边形Bernstein基函数具有如下形式：基函数具有如下形式：注意：当注意：当k=0，t=0时，时，tk=1，k!=1。 nknkktBENPtp0,0,1 t)()(n,0,1,k 11!)(,knkknknknkttCttknkntBEN计算机图形学3939 （1）正性）正性 （2）端点性质）端点性质 otherwiseniBotherwiseiBnini0)(1) 1

19、(0)0(1)0(, ; 1, 2 , 1),1 , 0(01 , 00)(,nitttBni计算机图形学4040（3）权性）权性 由二项式定理可知：由二项式定理可知：) 1 , 0(1)(0,ttBninininininiinnittttCtB00,1)1()1 ()(计算机图形学4141（4）对称性对称性 因为因为 )()1 (,tBtBninni)1 ()1 ( )1 ()1 (1 )(,)(,tBttCttCtBniiniinininninnnin计算机图形学4242(5）递推性。）递推性。 即高一次的即高一次的Bernstein基函数可由两个低一次的基函数可由两个低一次的Bernst

20、ein调和函数线性组合而成。因为，调和函数线性组合而成。因为，),.,1 , 0( ),()()1 ()(1, 11,nittBtBttBninini)()()1 ()1 ()1 ()1 ()1 ()()1 ()(1, 11,)1()1(111)1(1111,ttBtBttttCttCtttCCttCtBniniiniininiininiinininiinni计算机图形学4343（6）导函数）导函数 （7）最大值。）最大值。 在在 处达到最大值。处达到最大值。;, 1 , 0 ),()()(1,1, 1,nitBtBntBninini Bti n,( )tin计算机图形学4444（8）升阶公式

21、）升阶公式 )(11)()11 ()()(11)()()11 ()()1 (1, 11,1, 1,1,tBnitBnitBtBnittBtBnitBtninininininini计算机图形学4545（9）积分）积分10,11)(ntBni计算机图形学4646 0,1 t )1 ()()(10101 ,kkktPPttBENPtp计算机图形学4747 001201222102202,)(2)2( 0,1 t )1 (2)1 ( )()(PtPPtPPPPtPttPttBENPtpkkk21020010221211)(PPPtttp计算机图形学4848 33,323,213, 103,033221

22、203303,)()()()( 0,1t )1 (3)1 (3)1 ( )()(PtBENPtBENPtBENPtBENPtPttPttPttBENPtpkkk33,323,223,133,0)()1 (3)()1 (3)()1 ()(ttBENtttBENtttBENttBEN计算机图形学4949 三次三次BezierBezier曲线四个曲线四个BezierBezier基函数基函数0 0t tB B0,30,3(t)(t)B B3,33,3(t)(t)B B1,31,3(t)(t)B B2,32,3(t)(t)计算机图形学5050bebeGMTPPPPttttp 0,1 t 00010033

23、036313311)(321023计算机图形学51511端点端点 0, 11,000, )0()0()0( )0()0(PBENPBENPBENPBENPpnnnnnnknkknnnnnnnknkkPBENPBENPBENPBENPp )1 ()1 ()1 ( )1 ()1 (, 11,000,计算机图形学5252 )()()1 ()!) 1(!)!1()1 ()!1() 1()!1()!1()1)()1 ()!( !)(1,1, 1) 1() 1() 1(111,tBENtBENnttknknnttknknnttknttkknkntNBEnknkknkknkkknknknk计算机图形学535

24、3nknkkknnnnnnnknknkktBENPPntBENPPtBENPPtBENPPntBENtBENPntp11, 111, 111, 1121, 00101,1, 1)()()()()()()()()()()()()0(01PPnp)() 1 (1nnPPnp计算机图形学5454三次三次Bezier曲线段在起始点和终止点处的一阶导数为：曲线段在起始点和终止点处的一阶导数为：)(3) 1 ()(3)0(2301PPpPPp计算机图形学5555 三次三次Bezier曲线段在起始点和终止点处的二阶导数为：曲线段在起始点和终止点处的二阶导数为：)()(1() 1 ()()(1()0(1120

25、112nnnnPPPPnnpPPPPnnp )2(6) 1 ()2(6)0(321210PPPpPPPp 计算机图形学5656当当t=0时，时，当当t=1时，时，上式表明：上式表明：2阶导矢只与相邻的阶导矢只与相邻的3个顶点有关，事实上，个顶点有关，事实上，r阶导阶导矢只与（矢只与（r+1）个相邻点有关，与更远点无关。）个相邻点有关，与更远点无关。将将 、 及及 、 代入曲率公式代入曲率公式 ，可以得，可以得到到BezierBezier曲线在端点的曲率分别为：曲线在端点的曲率分别为：)2)(1() 0 (012PPPnnP)2)(1() 1 (21nnnPPPnnP)0(P)0(P) 1 (P

26、) 1 (P3)()()()(tPtPtPtk3011201)()(1) 0 (PPPPPPnnk31121)()(1) 1 (nnnnnnPPPPPPnnk计算机图形学5757（4）对称性。由控制顶点对称性。由控制顶点 构造出的新构造出的新Bezier曲线，与原曲线，与原Bezier曲线形状相同，走向相反。曲线形状相同，走向相反。因为：因为：这个性质说明这个性质说明Bezier曲线在起点处有什么几何性质，曲线在起点处有什么几何性质，在终点处也有相同的性质。在终点处也有相同的性质。),.,1 , 0( ,*niPPinininininiininininniinniittBPtBPtBPtBPt

27、C000,0,* 1 , 0 ),1 ()1 ()()()(*计算机图形学5858niininniininniiniPtBBPtBPtB0*, 00,0,)1 ()1 ()(n nn n0 0, ,- -i in nn ni i, ,i in n- -i i, ,n n0 0n nn n, ,n nn nn n, ,- -i in nn n- -i i, ,n ni in ni i, ,0 0t t) )P P( (1 1B Bt t) )P P( (1 1B Bt t) )P P( (1 1B Bt t) )P P( (1 1B B( (t t) )P PB B( (t t) )P PB B

28、( (t t) )P PB B( (t t) )P PP P( (t t) )计算机图形学59（5）凸包性）凸包性由于由于 ，且，且 ，这一结果，这一结果说明当说明当t在在0，1区间变化时，对某一个区间变化时，对某一个t值，值，P(t)是特是特征多边形各顶点的加权平均，权因子依次是征多边形各顶点的加权平均，权因子依次是 。在。在几何图形上，意味着几何图形上，意味着Bezier曲线曲线P(t)在在 中各点是控中各点是控制点制点Pi i的凸线性组合，即曲线落在的凸线性组合，即曲线落在Pi i构成的凸包之中，构成的凸包之中，如下图所示。如下图所示。ninitB0,1)(), 1 , 0, 10( 1

29、)(0,nittBni)(,tBni 1 , 0t Bezier Bezier曲线的凸包性曲线的凸包性凸包凸包计算机图形学6060（6）几何不变性。这是指某些几何特性不随坐标变）几何不变性。这是指某些几何特性不随坐标变换而变化的特性。换而变化的特性。Bezier曲线位置与形状与其特征多曲线位置与形状与其特征多边形顶点边形顶点 的位置有关，它不依赖坐标系的选的位置有关，它不依赖坐标系的选择。择。), 1 , 0(niPi计算机图形学6161（7）变差缩减性。若）变差缩减性。若Bezier曲线的特征多边形曲线的特征多边形 是一个平面图形，则平面内任意直线与是一个平面图形，则平面内任意直线与C(t)

30、的交点个数的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了变差缩减性质。此性质反映了Bezier曲线比其特征多边曲线比其特征多边形的波动还小，也就是说形的波动还小，也就是说Bezier曲线比特征多边形的折曲线比特征多边形的折线更光顺。线更光顺。nPPP10计算机图形学6262（8）仿射不变性）仿射不变性对于任意的仿射变换对于任意的仿射变换A：即在仿射变换下，的形式不变。即在仿射变换下，的形式不变。)()()(,0,tBPAtBPAtPAniininii计算机图形学63631绘图一段绘图一段Bezier曲线曲线

31、利用定义式利用定义式Bezier曲线的绘制，可以利用其定义式，对参数曲线的绘制，可以利用其定义式，对参数t选取选取足够多的值，计算曲线上的一些点，然后用折线连接足够多的值，计算曲线上的一些点，然后用折线连接来近似画出实际的曲线。随着选取点增多，折线和曲来近似画出实际的曲线。随着选取点增多，折线和曲线可以任意接近。线可以任意接近。计算机图形学6464knCnknknknCknkn 1)!( !1nknkknknkknknkktBENztztBENytytBENxtx0,0,0,)()(0,1 t )()()()(假设给定的四个型值点是假设给定的四个型值点是P0=(1，1)，Pl=(2，3)，P2

32、=(4，3)， P3=(3，1)，则计算结果见下表。，则计算结果见下表。计算机图形学6565t(1-t)33t(1-t)23t2 (1-t)t3P(t)01000(1,1)0.150.6140.3250.05740.0034(1.5058,1.765)0.350.2750.4440.2390.043(2.248,2.376)0.50.1250.3750.3750.125(2.75,2.5)0.650.0430.2390.4440.275(3.122,2.36)0.850.00340.05740.3250.614(3.248,1.75)10001(3,1)计算机图形学6666计算机图形学6767

33、利用曲线性质（几何作图法和分裂法）利用曲线性质（几何作图法和分裂法） 几何作图法几何作图法(de Casteljau算法算法)0P1P2P11P10P20PBezierBezier曲线上的点曲线上的点 抛物线三切线定理抛物线三切线定理计算机图形学6868)3/1(30PP 0 01 11/31/3 几何作图法求几何作图法求BezierBezier曲线曲线 上一点（上一点（n=3n=3，t=1/3t=1/3）0P1P2P3P10P11P12P20P21P计算机图形学6969基于基于Bezier曲线的讨论，我们可以方便地可以给曲线的讨论，我们可以方便地可以给出出Bezier曲面的定义和性质，曲面的

34、定义和性质，Bezier曲线的一些曲线的一些算法也可以很容易扩展到算法也可以很容易扩展到Bezier曲面的情况。曲面的情况。计算机图形学70701Bezier曲面曲面定义：定义：0,10,1v)(u, )()(),(00,minjnjmijivBENuBENPvupBENi,m(u)与与BENj,n(v)是是Bernstein基函数：基函数： jnjjnnjimiimmivvCvBENuuCuBEN)1 ()()1 ()(,依次用线段连接点列中相邻两点所形成的空间网格，称之为依次用线段连接点列中相邻两点所形成的空间网格，称之为特征网格。特征网格。计算机图形学7171计算机图形学72720阶连续

35、性只要求相连接的曲面片具有公共的边界阶连续性只要求相连接的曲面片具有公共的边界曲线。曲线。1阶连续性则要求在边界曲线上的任何一点，两个阶连续性则要求在边界曲线上的任何一点，两个曲面片跨越边界的切线矢量应该共线，而且两切线曲面片跨越边界的切线矢量应该共线，而且两切线矢量的长度之比为常数。矢量的长度之比为常数。计算机图形学7373如右图如右图所示，所示，设两张设两张mn次次Bezier曲面片曲面片分别由控制顶点分别由控制顶点 和和 定义。定义。)()(),()()(),(,00,00,vBuBQvuQvBuBPvuPnjminjmiijminjnjmiij 1 , 0, vuijPijQ),(vu

36、P),(vuQ)0 , 0(P) 1 , 0(P)0 , 1 (Q) 1 , 1 (Q)0 , 0()0 , 1 (QP ) 1 , 0() 1 , 1 (QP u uv v Bezier Bezier曲面片的拼接曲面片的拼接计算机图形学7474 BezierBezier曲面片的拼接曲面片的拼接边界线边界线P0,0Q3,0P3,3(Q0,3)P0,3Q3,3P3,1(Q0,1)P3,0(Q0,0)P3,2(Q0,2)计算机图形学7575Bezier曲线和曲面的不足：曲线和曲面的不足：Bezier曲线或曲面不能作局部修改；曲线或曲面不能作局部修改；Bezier曲线或曲面的拼接比较复杂曲线或曲面的

37、拼接比较复杂计算机图形学7676 B B样条曲线（构造具有局部性的调和函数）样条曲线（构造具有局部性的调和函数） 给定给定n+1n+1个控制点个控制点P P0 0，P P1 1，P Pn n，它们所确定，它们所确定的的k k阶阶B B样条曲线是：样条曲线是： n n0 0i ii iP P( (u u) )k ki i, ,N NP P( (u u) )其中其中N Ni i，k k( (u u) )递归定义如下：递归定义如下： 计算机图形学7777 这里这里u u0 0，u u1 1，u un n+ +k k，是一个，是一个非递减非递减的的序列，称为节点，序列，称为节点，( (u u0 0，u

38、 u1 1，u un n+ +k k) )称为称为节点向量节点向量。定义中可能出现。定义中可能出现 ，这时约定，这时约定为为0 0。 n ni i1 1, ,0 0k k( (u u) ), ,1 1k k1 1, ,i iN N1 1i iu uk ki iu uu uk ki iu u( (u u) )1 1k ki i, ,N Ni iu u1 1k ki iu ui iu uu u( (u u) )k ki i, ,N N其其它它0 0, ,1 1k kn ni i, ,0 01 1i iu uu ui iu u1 1，( (u u) )i i, ,1 1N N0 00 0计算机图形学

39、7878取取n=3，m=3，则，则n+m=6，不妨设节点矢量为：，不妨设节点矢量为：T=(0,1,2,3,4,5,6)： tNmtmktNmkttNtNmkmkmkk1, 11,1 ,11)( 01iti 1)(其它计算机图形学79其它1t0 01)(1 , 0tN2t11t0 2 ) 1()2()( )()2()()(1 , 01 , 01 , 11 , 02, 0tttNtttNtNtttNtN计算机图形学80803t2 )3(212t1 )3)(1(21)2(211t0 21 ) 1(23)(2 )(222, 01 , 03 , 0tttttt tNttNttN基函数由递推转换到直接定义

40、可以把不同段的时间进行移动基函数由递推转换到直接定义可以把不同段的时间进行移动例如：例如：t t在在22，3 3 设置为设置为 t=t-2t=t-2；依次改为；依次改为 t=t-1 t=t-1 ；t=tt=t注意顺序颠倒。即注意顺序颠倒。即t=t-2t=t-2变为变为F F0,3 0,3 。以下相同处理。以下相同处理。计算机图形学81814t3 )4(213t2 )4)(2(21)3)(1(212t1 ) 1(21)(223 , 1tttttttN5t4 )5(214t3 )5)(3(21)4)(2(213t2 )2(21)(223 , 2tttttttN计算机图形学82826t5 )6 (2

41、15t4 )6)(4(21)5)(3(214t3 ) 3(21)(223 , 3tttttttNt tB Bk k, ,3 3( (t t) )2 21 14 43 35 51 1 四段二次四段二次( (三阶三阶) )均匀均匀B样条基函数样条基函数N N0,30,3(t)(t)N N1,31,3(t)(t) N N2,32,3(t)(t)N N3,33,3(t)(t)计算机图形学83831局部支柱性局部支柱性 B样条的基函数是一个分段函数，其重要特征是样条的基函数是一个分段函数，其重要特征是在在参数变化范围内，每个基函数在参数变化范围内，每个基函数在tk到到tk+m的子区间的子区间内函数值不为

42、零，在其余区间内均为零内函数值不为零，在其余区间内均为零，通常也，通常也将该特征称为局部支柱性。将该特征称为局部支柱性。计算机图形学8484 B样条曲线的局部支柱性样条曲线的局部支柱性P P0 0P P1 1P P2 2P P3 3P4P4P P5 5P P6 6P P7 7P P4 4P4P4计算机图形学8585B样条的凸组合性和样条的凸组合性和B样条基函数的数值均大于样条基函数的数值均大于或等于或等于0保证了保证了B样条曲线的凸包性，即样条曲线的凸包性，即B样条曲样条曲线必处在控制多边形所形成的凸包之内。线必处在控制多边形所形成的凸包之内。 t ,t t 1)(1n1 -m0,nkmktB

43、计算机图形学8686 B样条曲线与样条曲线与 Bezier曲线的凸包性比较曲线的凸包性比较B B样条曲线样条曲线BezierBezier曲线曲线BezierBezier曲线曲线B B样条曲线样条曲线m=3m=3m=4m=4m=5m=5(a) B(a) B样条曲线和样条曲线和BezierBezier曲线的凸包比较曲线的凸包比较(b) B(b) B样条曲线和样条曲线和BezierBezier曲线的比较曲线的比较B B样条凸包样条凸包BezierBezier凸包凸包B B样条凸包样条凸包B B样条凸包样条凸包BezierBezier凸包凸包BezierBezier凸包凸包计算机图形学8787定义：定

44、义：1212112212,00( , )( )( )nnk kk mkmkkp u vPNu Nv 控制顶点、控制网格（特征网格）、控制顶点、控制网格（特征网格）、B样条基函数。样条基函数。 B样条曲面具有与样条曲面具有与B样条曲线相同的局部支柱性、凸包性、样条曲线相同的局部支柱性、凸包性、连续性、几何变换不变性等性质。连续性、几何变换不变性等性质。计算机图形学8888B样条曲线包括其特例的样条曲线包括其特例的Bezier曲线都不能精确表示出曲线都不能精确表示出抛物线外的二次曲线，抛物线外的二次曲线，B样条曲面包括其特例的样条曲面包括其特例的Bezier曲面都不能精确表示出抛物面外的二次曲面，

45、而只能曲面都不能精确表示出抛物面外的二次曲面，而只能给出近似表示。给出近似表示。提出提出NURBS方法，即非均匀有理方法，即非均匀有理B样条方法主要是为样条方法主要是为了找到与描述自由型曲线曲面的了找到与描述自由型曲线曲面的B样条方法既相统一、样条方法既相统一、又能精确表示二次曲线弧与二次曲面的数学方法。又能精确表示二次曲线弧与二次曲面的数学方法。计算机图形学8989NURBS曲线的定义曲线的定义NURBS曲线是由分段有理曲线是由分段有理B样条多项式基函数定义的样条多项式基函数定义的nikiinikiinikiiitRPtNtNPtP0,0,0,)()()()(njkjjkiikitNtNtR

46、0,)()()(计算机图形学9090Ri,k(t)具有具有k阶阶B样条基函数类似的性质：样条基函数类似的性质：局部支承性：局部支承性：Ri,k(t)=0，t ti, ti+k权性：权性：可微性：如果分母不为零，在节点区间内是无限次可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处连续可微的，在节点处 (k-1-r)次连续可导，次连续可导，r是该节是该节点的重复度。点的重复度。若若 i=0，则，则Ri,k(t)=0；若若 i=+ ，则，则Ri,k(t)=1；nikiuR0,1)(计算机图形学9191NURBS曲线与曲线与B样条曲线具有类似的几何样条曲线具有类似的几何性质：性质：局部

47、性质。局部性质。变差减小性质。变差减小性质。凸包性。凸包性。在仿射与透射变换下的不变性。在仿射与透射变换下的不变性。在曲线定义域内有与有理基函数同样的可微性。在曲线定义域内有与有理基函数同样的可微性。计算机图形学9292如果某个权因子为零，那么相应控制顶点对曲线没如果某个权因子为零，那么相应控制顶点对曲线没有影响。有影响。若若 ，则当，则当 时，时，Bezier曲线曲线和和非有理非有理B样条曲线样条曲线是是NURBS曲线的特曲线的特殊情况殊情况i,kiitttiPtP)(计算机图形学9393计算机图形学9494NURBS曲面可由下面的有理参数多项式函曲面可由下面的有理参数多项式函数表示：数表示

48、： 1212121122121212112212,00,00( )( )( , )( )( )nnk kk kk mkmkknnk kk mkmkkwPNu Nvp u vwNu Nv计算机图形学9595NURBS曲面可由下面的有理参数多项式函曲面可由下面的有理参数多项式函数表示：数表示：,0,0( )( )( )( )( )nkk mkkk mk mnjj mjp tP Rtw BtRtw Bt计算机图形学9696既为自由型曲线曲面也为初等曲线曲面的精既为自由型曲线曲面也为初等曲线曲面的精确表示与设计提供了一个公共的数学形式，确表示与设计提供了一个公共的数学形式，因此，一个统一的数据库就能够

49、存储这两类因此，一个统一的数据库就能够存储这两类形状信息。形状信息。为了修改曲线曲面的形状，既可以借助调整为了修改曲线曲面的形状，既可以借助调整控制顶点，又可以利用权因子，因而具有较控制顶点，又可以利用权因子，因而具有较大的灵活性。大的灵活性。计算稳定且速度快。计算稳定且速度快。计算机图形学9797NURBS有明确的几何解释，使得它对良好有明确的几何解释，使得它对良好的几何知识尤其是画法几何知识的设计人员的几何知识尤其是画法几何知识的设计人员特别有用。特别有用。NURBS具有强有力的几何配套计算工具，具有强有力的几何配套计算工具，包括节点插入与删除、节点细分、升阶、节包括节点插入与删除、节点细

50、分、升阶、节点分割等，能用于设计、分析与处理等各个点分割等，能用于设计、分析与处理等各个环节。环节。NURBS具有几何和透视投影变换不变性。具有几何和透视投影变换不变性。计算机图形学9898NURBS是非有理是非有理B样条形式以及有理与非有理样条形式以及有理与非有理Bezier形式的合适的推广。形式的合适的推广。需要额外的存储以定义传统的曲线曲面。需要额外的存储以定义传统的曲线曲面。权因子的不合适应用可能导致很坏的参数化，甚权因子的不合适应用可能导致很坏的参数化，甚至毁掉随后的曲面结构。至毁掉随后的曲面结构。某些技术用传统形式比用某些技术用传统形式比用NURBS工作得更好。例工作得更好。例如，

51、曲面与曲面求交时，如，曲面与曲面求交时，NURBS方法特别难于处方法特别难于处理刚好接触的情况。理刚好接触的情况。某些基本算法，例如求反曲线曲面上的点的参数某些基本算法，例如求反曲线曲面上的点的参数值，存在数值不稳定问题。值，存在数值不稳定问题。由简单的物体来构成复杂的物体由简单的物体来构成复杂的物体扫描表示扫描表示结构实体几何法结构实体几何法计算机图形学9999思想：思想： 通过平移、旋转及其他对称变换来构造通过平移、旋转及其他对称变换来构造三维对象三维对象 通过指定一个二维形状以及在空间区域通过指定一个二维形状以及在空间区域内移动该形状的扫描来描述该三维物体内移动该形状的扫描来描述该三维物

52、体计算机图形学100100zoyxA平移扫描平移扫描 二维图形二维图形A沿沿Z轴平移轴平移计算机图形学101101旋转扫描旋转扫描 二维图形二维图形A绕绕Z轴旋轴旋转转zByxA计算机图形学102102思想思想 通过对两个指定三维通过对两个指定三维对象进行并、交或差对象进行并、交或差等集合操作产生一个等集合操作产生一个新的三维对象新的三维对象 计算机图形学103物体物体A和和B差差并并交交差差计算机图形学104104分层树形结构，称为八叉树。分层树形结构，称为八叉树。思想思想 利用实体的空间相关性利用实体的空间相关性优点优点减少了三维物体的存储需求减少了三维物体的存储需求提供了存储有关物体内部

53、信息的方便表示提供了存储有关物体内部信息的方便表示计算机图形学105105四叉树四叉树二维平面二维平面三维空间三维空间八叉树八叉树计算机图形学106106四叉树四叉树数据结构数据结构思想思想 同质象限同质象限10231023计算机图形学107107用于用于二维平面二维平面的分解的分解对二维区域对二维区域递归地等分递归地等分4个小正方形，这个分解过个小正方形，这个分解过程可表示为一棵树，除叶节点，其每个节点都有四程可表示为一棵树，除叶节点，其每个节点都有四个分支，分别表示个分支，分别表示4个小正方形个小正方形若小正方形是同质的，则不必再分解；若小正方形是同质的，则不必再分解；若小正方形是非同质的

54、，则需将它再一分为四若小正方形是非同质的，则需将它再一分为四分解是递归的。分解是递归的。计算机图形学108108例例3120312001230132计算机图形学109109312456132519241820212223711 12891014151617具有子孙的节点具有子孙的节点空节点空节点实节点实节点245139 107811 12314 15 20 21 16 17 22 23 18 19 24 2516计算机图形学110110计算机图形学111111四叉树四叉树二维图的四叉树表示二维图的四叉树表示三维形体的分解三维形体的分解对三维空间进行前后、左右、上下等分为对三维空间进行前后、左右

55、、上下等分为8个小个小立方体，立方体，小立方体单元均质，则停止分解；小立方体单元均质，则停止分解；小立方体单元非均质，需进一步分解为小立方体单元非均质，需进一步分解为8个子立个子立方体方体直至所有小立方体单元均质，或已分解到规定的直至所有小立方体单元均质，或已分解到规定的分解精度为止。分解精度为止。计算机图形学112112236720131375具有子孙的节点具有子孙的节点空节点空节点实节点实节点计算机图形学113113计算机图形学114114二叉空间分割（二叉空间分割（Binary Space Partitioning，BSP）树方法是一种类似于）树方法是一种类似于八叉树的空间分割方法，它每

56、次将一实体用八叉树的空间分割方法，它每次将一实体用任一位置和任一方向的平面分为二部分（不任一位置和任一方向的平面分为二部分（不同于八叉树方法的每次将实体用平行于笛卡同于八叉树方法的每次将实体用平行于笛卡尔坐标平面的三个两两垂直的平面分割）。尔坐标平面的三个两两垂直的平面分割）。欧氏几何法欧氏几何法&分形几何法分形几何法分形基本特征分形基本特征分形生成过程分形生成过程分形分类分形分类分形维数概念分形维数概念计算机图形学115115Euclidean - Geometry Methods - use equations to describe objects which have smoo

57、th surfaces and regular shapes.Fractal - Geometry Methods - use procedures to model natural objects which have irregular or fragmented features.欧氏几何法欧氏几何法&分形几何法分形几何法计算机图形学116116infinite detail at every point 每点具有无限细节每点具有无限细节self-similarity between the object parts and the overall features 对象整体和局部之间对象整体和局部之间的自相似性的自相似性利用一个过程来描述分形物体，利用一个过程来描述分形物体，该过程为产生物体局部细节指定该过程为产生物