计算机图形学第八章 三维对象的表示

1、第第8章章 三维对象的表示三维对象的表示内容提要内容提要n表示方法表示方法n多边形表面（多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树（八叉树（Octrees）n分形（分形（Fractal ）n表示方法表示方法n图形三维对象类型不同、材质表面也不同，不存在某一种方图形三维对象类型不同、材质表面也不同，不存在某一种方法可以描述不同的物质的所有特征对象法可以描述不同的物质的所有特征对象n多边形多边形和和二次曲面二次曲面能够为诸如多面体和椭圆体等欧式对象提能够为诸如多面体和椭圆体等欧式对象提供精确的描述供精确的描述n样条曲面样

2、条曲面和和实体几何构造技术实体几何构造技术可用于设计机翼、齿轮及其它可用于设计机翼、齿轮及其它具有曲面的工程结构具有曲面的工程结构n过程式的方法过程式的方法如如分形结构分形结构和和微粒系统微粒系统用来建立地形、云、草用来建立地形、云、草丛和其它自然景物的模型丛和其它自然景物的模型n运用运用相互作用力的基于物理的建模方法相互作用力的基于物理的建模方法，可描述一块布或一，可描述一块布或一个胶状球的非刚体行为个胶状球的非刚体行为n八叉树编码八叉树编码可用于表示对象的内部特征，如医用可用于表示对象的内部特征，如医用CT映像映像n等值面显示等值面显示、体绘制体绘制或或其它可视化技术其它可视化技术可应用到

3、三维离散数可应用到三维离散数据集，从而获得数据的可视表示据集，从而获得数据的可视表示表示方法表示方法n三维对象表示方法通常可分为三维对象表示方法通常可分为2类类u边界表示边界表示（Boundary representations）p使用一组曲面来描述三维对象，这些曲面将对象分为使用一组曲面来描述三维对象，这些曲面将对象分为内部和外部内部和外部p典型例子：多边形平面和样条曲面典型例子：多边形平面和样条曲面u空间区分表示空间区分表示（Space-partitioning representations）p用来描述内部性质，将包含一个对象的空间区域分成用来描述内部性质，将包含一个对象的空间区域分成一

4、组较小的、非重叠的连续实体（通常是立方体）一组较小的、非重叠的连续实体（通常是立方体）p三维对象的一般空间划分描述是三维对象的一般空间划分描述是八叉树表示八叉树表示边界表示方法边界表示方法-图示图示空间区分表示方法空间区分表示方法-图示图示小立方体小立方体(i, j, k)kij内容提要内容提要n表示方法表示方法n多边形表面多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树（八叉树（Octrees）n分形（分形（Fractal ）n多边形表面多边形表面n三维图形中三维图形中运用边界表示的最普遍方式运用边界表示的最普遍方式是是

5、使用一组使用一组包围物体内部的表面多边形包围物体内部的表面多边形n很多图形系统以一组表面多边形来存储物体的描述很多图形系统以一组表面多边形来存储物体的描述u用线性方程描述所有表面，因而会简化并且加速物体的表用线性方程描述所有表面，因而会简化并且加速物体的表面绘制和显示面绘制和显示n某些情况下，多边形表示是惟一可用的某些情况下，多边形表示是惟一可用的u很多图形包也允许以其它方式描述物体很多图形包也允许以其它方式描述物体p如样条曲面，将它转换到多边形表示后加以处理如样条曲面，将它转换到多边形表示后加以处理多边形描述多边形描述因此被称为因此被称为标准图形对象标准图形对象n可以为覆盖对象表面的可以为覆

6、盖对象表面的每一多边形给出一组顶点每一多边形给出一组顶点，以便使，以便使用一组多边形面片描述一个对象用一组多边形面片描述一个对象u这些面片的顶点坐标和边的信息以及每一多边形的表面法向量等其这些面片的顶点坐标和边的信息以及每一多边形的表面法向量等其它信息存入一张表中（参见它信息存入一张表中（参见P106的的3.15节）节）n有些图形软件提供生成有些图形软件提供生成由三角形或四边形组成的多边形网由三角形或四边形组成的多边形网的子程序的子程序n有些软件提供有些软件提供用多边形面片显示立方体、球体或圆柱体等用多边形面片显示立方体、球体或圆柱体等普通形状普通形状的子程序的子程序n多边形表面数据分为两组进

7、行组织多边形表面数据分为两组进行组织u几何表几何表：顶点坐标和用来标识多边形表面空间方向的参数：顶点坐标和用来标识多边形表面空间方向的参数u属性表属性表：指明物体透明度及表面反射度的参数和纹理特征：指明物体透明度及表面反射度的参数和纹理特征多边形表面多边形表面多边形表面多边形表面示例示例顶点表顶点表序号序号点坐标点坐标1x1, y1, z12x2, y2, z23x3, y3, z34x4, y4, z45x5, y5, z5边表边表序号序号顶点号顶点号1v1, v22v2, v33v3, v14v3, v45v4, v56v5, v1多边形面表多边形面表序号序号边序号边序号S1E1, E2,

8、 E3S2E3, E4, E5, E6E1E2E4E5S1v2v1v3v4v5E3E6S2多边形表面多边形表面（Polygon Surfaces）n多边形多边形网格网格 图形系图形系统一般统一般使用使用多多边形网边形网格格对对3D物体进物体进行建模行建模多边形网格多边形网格内容提要内容提要n表示方法表示方法n多边形表面（多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树（八叉树（Octrees）n分形（分形（Fractal ）n曲线和曲面曲线和曲面n曲面边界对象的等式可用参数或非参数形式表示曲面边界对象的等式可用参数或非参数

9、形式表示n计算机图形应用中对象的描述一般都用多边形网格来近似表计算机图形应用中对象的描述一般都用多边形网格来近似表示其表面示其表面u这些对象包括二次曲面、超二次曲面、多项式和指数函数及样条曲面这些对象包括二次曲面、超二次曲面、多项式和指数函数及样条曲面n曲线曲面的生成方法曲线曲面的生成方法u由给定的一组数学函数生成由给定的一组数学函数生成u由给定的一组数据生成由给定的一组数据生成n一旦给定函数，图形包将指定曲线方程投影到显示平面上，一旦给定函数，图形包将指定曲线方程投影到显示平面上，且沿着投影函数路径绘制像素位置且沿着投影函数路径绘制像素位置n由函数式描述而生成的显示曲面的例子有由函数式描述而

10、生成的显示曲面的例子有二次曲面二次曲面和和超二次超二次曲面曲面 (P.334 - P.337)nOpenGL二次和三次曲面函数二次和三次曲面函数(P.337-P.341)二次曲面二次曲面n这类物体由二次曲面的表达式（二次方程）生成。包括球面、这类物体由二次曲面的表达式（二次方程）生成。包括球面、椭球面、环面、抛物面和双曲面椭球面、环面、抛物面和双曲面n球面球面u在笛卡尔坐标系中，中心在原点、半径为在笛卡尔坐标系中，中心在原点、半径为r的球面定义为满的球面定义为满足方程足方程x2+y2+z2=r2的点集的点集(x, y, z)n椭球面椭球面u椭球面可看作球面的扩展：椭球面可看作球面的扩展：3条相

11、互垂直的半径具有不同值条相互垂直的半径具有不同值u中心在原点的椭球面的笛卡尔表达式为中心在原点的椭球面的笛卡尔表达式为1222zyxrzryrx二次曲面二次曲面n环面：汽车轮胎状的对象称为环面：汽车轮胎状的对象称为环面环面或或锚状环锚状环u通常被描述为将圆或椭圆绕该二次曲线（圆或椭圆）之通常被描述为将圆或椭圆绕该二次曲线（圆或椭圆）之外的一个共面轴旋转而得到的表面外的一个共面轴旋转而得到的表面u环面的定义参数是该二次曲线中心到旋转轴之间的距离环面的定义参数是该二次曲线中心到旋转轴之间的距离以及该二次曲线的尺寸以及该二次曲线的尺寸raxialrzy0(0,y,z)y0 x(x,y,z)u图图1所

12、示圆的方程为所示圆的方程为(y-raxial)2+z2=r2。将该圆绕。将该圆绕z轴旋转即可轴旋转即可生成图生成图2所示的环面，其方程为所示的环面，其方程为图图1 圆的方程圆的方程图图2 环面的顶视图环面的顶视图22222rzryxaxial超二次曲面超二次曲面n超二次曲面通过将额外参数插入二次方程形成超二次曲面通过将额外参数插入二次方程形成n超椭圆超椭圆u在椭圆方程中，允许在椭圆方程中，允许x和和y项的指数为变量，即得超椭圆项的指数为变量，即得超椭圆的笛卡尔表达式的笛卡尔表达式122sysxryrxn超椭球面超椭球面u超椭球面的笛卡尔表达式通过在椭球面方程中增加超椭球面的笛卡尔表达式通过在椭

13、球面方程中增加2个指个指数参数得到数参数得到111222222szsssysxrzryrx超椭圆形状如超椭圆形状如P336图图8.6所示所示超椭球面形状如超椭球面形状如P337图图8.7所示所示柔性对象柔性对象n柔性对象指在柔性对象指在一定运动状态下一定运动状态下或在或在它们接近其它对象时它们接近其它对象时会会改改变其表面形状变其表面形状的对象。它们的曲面表面很难用的对象。它们的曲面表面很难用常规形状常规形状表示表示u例如：分子形状在独立存在时可用球形描述，它接近其例如：分子形状在独立存在时可用球形描述，它接近其它分子时会改变其本身的形状（它分子时会改变其本身的形状（P342图图8.9）drd

14、rddrdrbdrbrf330,0)1(23)31()(222p软对象模型软对象模型使用如下函使用如下函数表示数表示p元球模型元球模型将混合对象看成几将混合对象看成几个二次密度函数的复合形式个二次密度函数的复合形式drdrdrdrdrrf0,0949179221)(664422n样条的历史样条的历史u很早的绘图员利用很早的绘图员利用“ducks”和有柔性和有柔性的木条（样条）来绘制曲线的木条（样条）来绘制曲线u木质的样条具有二阶连续木质的样条具有二阶连续u并且通过所有的控制点并且通过所有的控制点样条表示样条表示A Duck (weight)Ducks trace out curven样条：通过

15、一组指定点集而生成平滑曲样条：通过一组指定点集而生成平滑曲线的柔性带线的柔性带n样条曲线在计算机图形学中的含义样条曲线在计算机图形学中的含义u由多项式曲线段连接而成的曲线由多项式曲线段连接而成的曲线u在每段的在每段的边界处边界处满足特定的连续性条件满足特定的连续性条件n样条曲面样条曲面u使用使用2组组正交样条曲线正交样条曲线进行描述进行描述n样条在图形学中的应用样条在图形学中的应用u设计曲线、曲面设计曲线、曲面u汽车车身设计、飞机和航天飞机表面的设计、船体设计汽车车身设计、飞机和航天飞机表面的设计、船体设计以及家庭应用以及家庭应用样条表示样条表示n曲线的产生曲线的产生u给定一组离散的坐标点（控

16、制点），采用给定一组离散的坐标点（控制点），采用插值插值或或逼近逼近方方法之一选取分段连续参数多项式函数，将数据集拟合成法之一选取分段连续参数多项式函数，将数据集拟合成指定的曲线函数指定的曲线函数u根据曲线函数得到曲线的图形根据曲线函数得到曲线的图形n曲线的类型曲线的类型u插值插值样条曲线：选取的多样条曲线：选取的多项式使得曲线通过每个控项式使得曲线通过每个控制点制点u逼近逼近样条曲线：选取的多样条曲线：选取的多项式不一定使曲线通过每项式不一定使曲线通过每个控制点个控制点样条表示样条表示插值插值逼近逼近n插值曲线插值曲线通常用于数值化绘通常用于数值化绘图或指定动画路径图或指定动画路径n逼近曲线

17、逼近曲线一般作为设计工具一般作为设计工具来构造对象形体来构造对象形体凸壳凸壳n凸壳（凸壳（Convex hull）u包含一组控制点的凸多边形边界包含一组控制点的凸多边形边界n将二维曲线的凸壳形状设想成一个围绕控制点位置的拉紧的将二维曲线的凸壳形状设想成一个围绕控制点位置的拉紧的橡皮筋，使每个控制点在凸壳的边界上或者凸壳内（如下图）橡皮筋，使每个控制点在凸壳的边界上或者凸壳内（如下图）n凸壳的作用凸壳的作用u提供了曲线或曲面与包围控制点的区域之间的偏差的测量提供了曲线或曲面与包围控制点的区域之间的偏差的测量u以凸壳为界的样条保证了多项式沿控制点的平滑前进以凸壳为界的样条保证了多项式沿控制点的平滑

18、前进凸壳凸壳曲线的控制图曲线的控制图n对于逼近样条，连接控制点序列的折线通常会显示出来，以对于逼近样条，连接控制点序列的折线通常会显示出来，以提醒设计者控制点的顺序。这组连接线通常称为提醒设计者控制点的顺序。这组连接线通常称为曲线的控制曲线的控制图图n该控制图还可称为该控制图还可称为控制多边形控制多边形或或特征多边形特征多边形n为保证分段参数曲线从一段到另一段平滑过渡，可在连接点为保证分段参数曲线从一段到另一段平滑过渡，可在连接点处要求各种连续性条件处要求各种连续性条件n参数参数连续性条件：两个相邻曲线段在相交处的参数导数连续性条件：两个相邻曲线段在相交处的参数导数相等相等u零阶连续零阶连续(

19、C0连续连续)：简单地表示曲线：简单地表示曲线连接连接u一阶连续一阶连续(C1连续连续)：说明代表两个相邻曲线的方程在相交：说明代表两个相邻曲线的方程在相交点处有点处有相同的一阶导数相同的一阶导数（切线）（切线）u二阶连续二阶连续(C2连续连续)：两个曲线段在交点处有：两个曲线段在交点处有相同的一阶和相同的一阶和二阶导数二阶导数，交点处的切向量变化率相等，交点处的切向量变化率相等参数连续性条件参数连续性条件F(u)f(u)F(1)=f(0)零阶连续零阶连续F(1)=f(0)一阶连续一阶连续F (1)=f (0)二阶连续二阶连续n几何几何连续性条件连续性条件 两个相邻曲线段在相交处的参数导数两个

20、相邻曲线段在相交处的参数导数成比例成比例u零阶连续（零阶连续（G0连续）：与连续）：与0阶参数连续性相同，即两个曲阶参数连续性相同，即两个曲线必在公共点处有线必在公共点处有相同的坐标相同的坐标u一阶连续（一阶连续（G1连续）：表示连续）：表示一阶导数一阶导数在两个相邻曲线的在两个相邻曲线的交点处交点处成比例成比例u二阶连续（二阶连续（G2连续）：表示两个曲线段在相交处的一阶连续）：表示两个曲线段在相交处的一阶和二阶导数均和二阶导数均成比例成比例几何连续性条件几何连续性条件样条描述样条描述n给定多项式的阶和控制点位置后，指定一个具体的样条表达给定多项式的阶和控制点位置后，指定一个具体的样条表达式

21、有式有3个等价方法个等价方法u列出一组加在样条上的边界条件列出一组加在样条上的边界条件u列出描述样条特征的行列式列出描述样条特征的行列式u列出一组混合函数或基函数，确定如何组合指定的曲线几列出一组混合函数或基函数，确定如何组合指定的曲线几何约束，以计算曲线路径上的位置何约束，以计算曲线路径上的位置n样条曲面样条曲面u使用某空间区域中一个控制点网指定使用某空间区域中一个控制点网指定2组正交的样条曲线，组正交的样条曲线，来定义一个样条曲面来定义一个样条曲面n修剪样条曲面修剪样条曲面u图形软件包常提供生成修剪曲线的函数，在样条曲线上挖图形软件包常提供生成修剪曲线的函数，在样条曲线上挖去一部分去一部分

22、n插值样条曲线（三次样条插值）插值样条曲线（三次样条插值）u自然三次样条插值自然三次样条插值uHermite样条插值样条插值uCardinal样条插值样条插值uKochanek_Bartels样条插值样条插值n逼近逼近样条曲线样条曲线uBezier曲线曲线uB_样条曲线样条曲线生成样条曲线的方法生成样条曲线的方法插值样条曲线（三次样条插值）插值样条曲线（三次样条插值）n三次样条插值方法大多用于建立对象运动路径或提供实体表三次样条插值方法大多用于建立对象运动路径或提供实体表示和动画，插值样条有时也用来设计物体形状示和动画，插值样条有时也用来设计物体形状n三次多项式在灵活性和计算速度之间提供了一个

23、合理的三次多项式在灵活性和计算速度之间提供了一个合理的折中折中方案方案：比更高次多项式需要：比更高次多项式需要更少的计算和存储空间更少的计算和存储空间，模拟任，模拟任意曲线形状时比低次多项式意曲线形状时比低次多项式更灵活更灵活n假设有假设有n+1个控制点，其坐标分别为个控制点，其坐标分别为pk=(xk, yk, zk) k=0,1,2, ,n，可用下列方程组来描述拟合每对控制点的参，可用下列方程组来描述拟合每对控制点的参数三次多项式数三次多项式x(u)=axu3+bxu2+cxu+dxy(u)=ayu3+byu2+cyu+dyz(u)=azu3+bzu2+czu+dz在在2条曲线段的条曲线段的

24、“交点交点”处设置足够的边界条件，即可对由处设置足够的边界条件，即可对由n+1个个控制点产生的控制点产生的n条曲线段确定所有系数值条曲线段确定所有系数值自然三次样条自然三次样条n自然三次样条是原始绘图样条的一个数学表达式自然三次样条是原始绘图样条的一个数学表达式u使用公式表示一个自然三次样条时，需要使用公式表示一个自然三次样条时，需要2个相邻曲线段个相邻曲线段在公共边界处有相同的一阶和二阶导数，即具有在公共边界处有相同的一阶和二阶导数，即具有C2连续性连续性n如下图所示，需要拟合如下图所示，需要拟合n+1个控制点，就需要确定个控制点，就需要确定n条曲线段条曲线段和和4n个多项式系数个多项式系数

25、p0pnp1p2p3pkPk+1n每个内部控制点（共每个内部控制点（共n-1个）有个）有4个边界条件：该控制点两侧个边界条件：该控制点两侧的的2个曲线段在该点处有相同的一阶和二阶导数，并且个曲线段在该点处有相同的一阶和二阶导数，并且2条曲条曲线段都要通过该点线段都要通过该点-从而得到由从而得到由4n个多项式系数组成的个多项式系数组成的4n-4个方程个方程系数求解方程分析系数求解方程分析n再给出从第再给出从第1个控制点个控制点p0(起点起点)所得到的方程以及另所得到的方程以及另1个控制点个控制点pn(端点端点)所得的条件。共所得的条件。共2个方程个方程n获取另外获取另外2个方程的方法是：方法个方

26、程的方法是：方法1、在、在p0和和pn处设处设二阶导数为二阶导数为0；方法；方法2、增加两个、增加两个“隐含隐含”的控制点，的控制点，即即p-1和和pn+1 （Cardianl样条）样条）n特点特点u1.只适用于控制点分布比较均匀的场合只适用于控制点分布比较均匀的场合u2.不能不能“局部控制局部控制”，如果控制点中任一个发生了变动，如果控制点中任一个发生了变动，则整条曲线都将受到影响则整条曲线都将受到影响Hermite样条插值样条插值n与自然三次样条不同，与自然三次样条不同，Hermite样条可以局部调整，样条可以局部调整，因为每个曲线段仅依赖于段点约束。如图，如果控因为每个曲线段仅依赖于段点

27、约束。如图，如果控制点制点pk和和pk+1之间的曲线段是参数三次函数之间的曲线段是参数三次函数p(u)，n那么边界条件是那么边界条件是u假设已知端点一阶导数假设已知端点一阶导数Dpk、Dpk+1up(0)=pkup(1)=pk+1up(0)=Dpkup(1)=Dpk+1pkPk+1p(u)=(x(u), y(u), z(u)Bzier曲线和曲面曲线和曲面n法国工程师法国工程师Bzier使用逼近样条为雷诺汽车公司使用逼近样条为雷诺汽车公司设计汽车外形而开发。数学基础简单，容易实现设计汽车外形而开发。数学基础简单，容易实现n Bzier样条在各种样条在各种CAD系统、大多数图形系统、系统、大多数图

28、形系统、相关绘图和图形软件包中有广泛应用相关绘图和图形软件包中有广泛应用n假定给出假定给出n+1个个控制点控制点位置：位置：pk=(xk,yk,zk), k取值范围取值范围为为0到到n，这些坐标值用于合成向量，这些坐标值用于合成向量 P(u), P(u) = Pk* Bk,n(u)nBzier混合函数混合函数Bk,n(u)是是Bernstein多项式多项式Bk,n(u) = C(n,k) * uk*(1-u)n-k其中，其中，C(n,k) = n! / (k!(n-k)!)Bzier 曲线公式曲线公式k=0n0u 1例例1：二次二次Bzier曲线曲线 n由由3个控制点生成个控制点生成uB0,2

29、(u) = (1-u)2uB1,2(u) = 2u(1-u)uB2,2(u) = u2 例例2：三次三次Bzier曲线曲线 n由由4个控制点生成个控制点生成uB0,3(u) = (1-u)3uB1,3(u) = 3u(1-u)2uB2,3(u) = 3u2(1-u)uB3,3(u) = u3 Bzier 曲线例子曲线例子Bzier 曲线生成程序见曲线生成程序见P357-359将将n=2代入公式代入公式Bk,n(u) = C(n,k) * uk*(1-u)n-k得例得例1，将将n=3代入该公式得例代入该公式得例2P0P1P2P0P1P2P3P0P1P2P3P0P1P2P3P4P0P1P2P3(a

30、)(b)(c)(d)(e)由由3个、个、4个和个和5个控制点生成的二维个控制点生成的二维Bzier曲线曲线的例子的例子虚线连接了虚线连接了控制点的位置控制点的位置nBzier多项式次数控制点个数多项式次数控制点个数-1nBzier曲线总是通过第一个和最后一个控制点，即曲线总是通过第一个和最后一个控制点，即曲线在曲线在2个端点处的边界条件是个端点处的边界条件是P(0) = p0, P(1) = pnn任何任何 Bzier曲线总是落在控制点的凸壳（凸多边形曲线总是落在控制点的凸壳（凸多边形边界）内，这些点由边界）内，这些点由Bzier混合函数给出，其值满混合函数给出，其值满足如下关系足如下关系n

31、Bk,n(u) = 1Bzier曲线的特性曲线的特性k=0nn第第1和最后和最后1个控制点重合生成封闭个控制点重合生成封闭Bzier 曲线曲线n多个控制点位于同一位置会对该位置加以更多的权（如下图多个控制点位于同一位置会对该位置加以更多的权（如下图1所示）所示）u下图下图2中，输入一个坐标位置作为中，输入一个坐标位置作为2个控制点，这样产生个控制点，这样产生的曲线更接近该位置的曲线更接近该位置使用使用Bzier曲线的设计技术曲线的设计技术p1p0=p5p4p2p3p0p1=p2p3p4图图1图图2p0p1p2P0P1P2P3零阶参数连续零阶参数连续Bzier曲线的构造曲线的构造一阶参数连续一阶

32、参数连续Bzier曲线的构造曲线的构造 n可使用任意数目的控制点来拟合一条可使用任意数目的控制点来拟合一条 Bzier 曲线，但这需要曲线，但这需要计算更高次的多项式计算更高次的多项式n复杂曲线可由几个较低次数的复杂曲线可由几个较低次数的Bzier曲线段连接而成曲线段连接而成u由于由于Bzier曲线通过端点，因此比较容易匹配曲线段（曲线通过端点，因此比较容易匹配曲线段（0阶连续性）阶连续性）nBzier曲线的另一重要性质：曲线在端点处的切向量位于端点曲线的另一重要性质：曲线在端点处的切向量位于端点和相邻控制点的连线上和相邻控制点的连线上u如下图，新段中控制点如下图，新段中控制点p0和和p1与前

33、段中控制点与前段中控制点pn-1和和pn处于同一直线处于同一直线上上Bzier曲面曲面n可使用两组正交的可使用两组正交的Bzier曲线来设计一个对象曲面曲线来设计一个对象曲面nBzier曲面的参数向量函数可按照曲面的参数向量函数可按照Bzier混合函数混合函数的笛卡尔积形式描述的笛卡尔积形式描述,00( , )( )( )mnj kj mk njkPu vP Bv Bu 其中其中pj,k指定了指定了(m+1)*(n+1)个控制点个控制点Bk,m(v) = C(m,k) * vk*(1-v)m-kBj,n(u) = C(n,j) * uj*(1-u)n-j内容提要内容提要n表示方法表示方法n多边

34、形表面（多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树（八叉树（Octrees）n分形（分形（Fractal ）n实体构造技术实体构造技术n由简单的物体来构成复杂的物体由简单的物体来构成复杂的物体u扫描表示法扫描表示法u结构实体几何法结构实体几何法n扫描表示法扫描表示法u通过平移、旋转及其他对称变换来构造三维对象通过平移、旋转及其他对称变换来构造三维对象u通过指定一个二维形状以及在空间区域内移动该形状的通过指定一个二维形状以及在空间区域内移动该形状的扫描来描述该三维物体扫描来描述该三维物体u可将一组二维基本图形，如圆或矩

35、形等作为菜单选项来可将一组二维基本图形，如圆或矩形等作为菜单选项来提供扫描表示提供扫描表示获得二维图形的其它方法有封闭样条曲线构造和实体剖面片获得二维图形的其它方法有封闭样条曲线构造和实体剖面片实体造型软件包通常提供多种构造技术实体造型软件包通常提供多种构造技术zoyxAn平移扫描平移扫描 二维图形二维图形A沿沿Z轴平移轴平移n旋转扫描旋转扫描 二维图形二维图形A绕绕Z轴旋转轴旋转zByxA扫描表示扫描表示-示例示例结构实体几何法结构实体几何法n通过对两个指定三维对象通过对两个指定三维对象进行并、交或差等集合操进行并、交或差等集合操作产生一个新的三维对象作产生一个新的三维对象的建模方法称为的建

36、模方法称为结构实体结构实体几何几何（Constructive Solid Geometry，CSG）法）法 结构实体几何法结构实体几何法(a) 物体物体A和和B(d)差差(b)并并(c)交交(e)差差结构实体几何法结构实体几何法nCSG的应用开始于三维对象的初始集。称为的应用开始于三维对象的初始集。称为CSG基基本图元，如长方体、棱锥、圆柱体、圆锥体、球体本图元，如长方体、棱锥、圆柱体、圆锥体、球体和某些使用样条曲面的实体和某些使用样条曲面的实体n基本图元可作为基本图元可作为CSG软件包的菜单选项来提供，基软件包的菜单选项来提供，基本图元本身可使用扫描算法、样条构造或其它建模本图元本身可使用扫

37、描算法、样条构造或其它建模程序形成程序形成n使用交互式使用交互式CSG软件包构造对象的过程软件包构造对象的过程u首先选择首先选择2个基本图元并拖到某空间位置个基本图元并拖到某空间位置u指定一个组合操作（并、交或差）创建一个新对象指定一个组合操作（并、交或差）创建一个新对象u该新对象与一个已存在的形体组合生成另一新对象该新对象与一个已存在的形体组合生成另一新对象u继续构造新对象，直到形成所需新对象继续构造新对象，直到形成所需新对象CSG二叉树二叉树nCSG 利用基本体元或体素和每一步新创建的物体的利用基本体元或体素和每一步新创建的物体的组合，构造新物体，直到形成所需的物体。这种方组合，构造新物体

38、，直到形成所需的物体。这种方法可表示成一个二叉树法可表示成一个二叉树内容提要内容提要n表示方法表示方法n多边形表面（多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树八叉树（Octrees）n分形（分形（Fractal ）n八叉树八叉树n三维空间的八叉树编码过程是四叉树编码的二维空间编码方三维空间的八叉树编码过程是四叉树编码的二维空间编码方法的扩展法的扩展u连续将二维空间（通常为正方形）分成连续将二维空间（通常为正方形）分成4等分得到四叉树等分得到四叉树u四叉树的每个节点有四叉树的每个节点有4个数据元素，每个象限在此区域内个

39、数据元素，每个象限在此区域内0321四分象限四分象限四分象限四分象限四分象限四分象限四分象限四分象限0312二维空间的区域二维空间的区域描述四叉树节点的数据元素描述四叉树节点的数据元素p如果一个象限中如果一个象限中所有像素的颜色相同所有像素的颜色相同（均质均质象限），此节点内的数据元素存储该颜色象限），此节点内的数据元素存储该颜色 此外，在数据元素中设定一标记以标明此象限是此外，在数据元素中设定一标记以标明此象限是均质的均质的p否则，此象限称为否则，此象限称为非均质非均质的象限，该象限再的象限，该象限再分成分成4个象限个象限生成四叉树的生成四叉树的算法算法n测试指定区域内赋给对象的测试指定区域

40、内赋给对象的像素颜色强度值，并建立相像素颜色强度值，并建立相应的四叉树编码应的四叉树编码312031200132312013120 如果原区域中每个象限有如果原区域中每个象限有单单一的颜色一的颜色规格，则四叉树只规格，则四叉树只有有一个节点一个节点 对于一个对于一个非均质非均质的区域，连的区域，连续续细分象限，直到所有的象细分象限，直到所有的象限都是同质的限都是同质的大区域中包括一个具有大区域中包括一个具有单一颜色单一颜色（不同于大区域中其它部分的颜色不同于大区域中其它部分的颜色）的小区域）的小区域四叉树四叉树-示例示例312456132519241820212223711 128910141

41、51617具有子孙的节点具有子孙的节点空节点空节点实节点实节点245139107811 12314 15 20 21 16 17 22 23 18 19 24 2516扩展为多扩展为多次划分的次划分的象限区域象限区域 每个单色区域使用一个节点表示，每个单色区域使用一个节点表示，空间区域存在空间区域存在较大的单一颜色区域较大的单一颜色区域时，四叉树编码能时，四叉树编码能节省存储空间节省存储空间 含有含有2n2n个像素的区域，四叉树个像素的区域，四叉树表示表示至多至多有有n层。四叉树中每个节层。四叉树中每个节点点至多至多有有4个直接后代个直接后代n八叉树编码方法将三维空间区域（一般是立方体）分成八

42、叉树编码方法将三维空间区域（一般是立方体）分成8等等分，并且树上每个节点处存储分，并且树上每个节点处存储8个数据元素个数据元素八叉树八叉树n三维空间中的每个元素称为体素或体元，三维空间中的每个元素称为体素或体元，八叉树中的一个体元存储一个均值均质八叉树中的一个体元存储一个均值均质子区域的特征值子区域的特征值n获取八叉树的算法获取八叉树的算法u将三维空间按照前后、左右、上下等分为将三维空间按照前后、左右、上下等分为8个个小立方体，小立方体，u如果小立方体单元均质，则停止分解如果小立方体单元均质，则停止分解u否则，进一步分解为否则，进一步分解为8个子立方体个子立方体u直至所有小立方体单元均质，或已

43、分解到规直至所有小立方体单元均质，或已分解到规定的分解精度定的分解精度7321045601234567描述八叉树节点的数据元素描述八叉树节点的数据元素八叉树八叉树-示例示例八叉树八叉树n可以建立为以任何形式定义的对象生成八叉树的算法，可以建立为以任何形式定义的对象生成八叉树的算法，如多边形网格、曲面片或实体几何构造如多边形网格、曲面片或实体几何构造n对单个对象，利用对象的坐标范围确定一个包围盒对单个对象，利用对象的坐标范围确定一个包围盒（平行六面体）来生成八叉树表示（平行六面体）来生成八叉树表示n一旦对实体建立一个八叉树表示，可应用执行集合操一旦对实体建立一个八叉树表示，可应用执行集合操作的算

44、法作的算法u“并并”操作，新八叉树通过合并同一区域内的每个八叉树构操作，新八叉树通过合并同一区域内的每个八叉树构造造u“交交”操作，寻找操作，寻找2棵输入的八叉树的重叠区域执行交操作棵输入的八叉树的重叠区域执行交操作u“差差”操作，存储仅由一个对象占据，而不被另一对象占据操作，存储仅由一个对象占据，而不被另一对象占据的八等分的八等分八叉树的优缺点八叉树的优缺点n优点优点u可表示任何物体，且表示的数据结构简单可表示任何物体，且表示的数据结构简单u简化了物体的集合运算简化了物体的集合运算p只需同时遍历参加集合运算的两物体相应的八叉树，无需进行只需同时遍历参加集合运算的两物体相应的八叉树，无需进行复

45、杂的求交运算复杂的求交运算u简化了隐藏线（或面）的消除简化了隐藏线（或面）的消除p因为在八叉树表示中，物体上各元素已按空间位置排成了一定因为在八叉树表示中，物体上各元素已按空间位置排成了一定的顺序的顺序u算法适合于并行处理算法适合于并行处理n缺点缺点u没有边界信息，不适于图形精确显示没有边界信息，不适于图形精确显示u对物体进行几何变换困难对物体进行几何变换困难u是物体的非精确表示是物体的非精确表示u占用大量存储。实际上，八叉树表示是以存储空间换取算法的效率占用大量存储。实际上，八叉树表示是以存储空间换取算法的效率BSP树树n利用二叉空间分割树（利用二叉空间分割树（Binary-Space-Pa

46、rtitioning, BSP树），可以每次将一场景根据任意位置和任意树），可以每次将一场景根据任意位置和任意方向的平面分为方向的平面分为2部分部分n相对于使用空间细分法，相对于使用空间细分法，BSP树提供了一种更有效树提供了一种更有效的分割方法：可根据适合对象的空间分布来确定分的分割方法：可根据适合对象的空间分布来确定分割平面的位置和方向割平面的位置和方向n与八叉树的对比与八叉树的对比u每次将空间分成每次将空间分成2部分，而不是部分，而不是8部分部分u可减少场景树的表示深度，从而减少搜索树的空间可减少场景树的表示深度，从而减少搜索树的空间uBSP树可有效识别可视面和使用光线追踪算法对空间进行

47、树可有效识别可视面和使用光线追踪算法对空间进行分割分割内容提要内容提要n表示方法表示方法n多边形表面（多边形表面（Polygon Surfaces）n曲线曲面曲线曲面: Bzier曲线曲线n实体构造技术实体构造技术n八叉树（八叉树（Octrees）n分形分形（Fractal ）nn欧氏几何法欧氏几何法u使用方程描述对象形状的方法使用方程描述对象形状的方法u适用于讨论加工过的对象：具有平滑的表面和规则的形状适用于讨论加工过的对象：具有平滑的表面和规则的形状n分形几何法（分形几何法（Fractal-geometry）u使用过程而不是方程为对象建模使用过程而不是方程为对象建模u能真实地描述自然景物；

48、计算机图形学中，使用分形方法产生自然能真实地描述自然景物；计算机图形学中，使用分形方法产生自然景物以及各种数学和物理系统的可视化景物以及各种数学和物理系统的可视化n分形对象具有分形对象具有2个基本特征个基本特征u每点具有无限的细节每点具有无限的细节u对象整体和局部特性之间的自相似性对象整体和局部特性之间的自相似性n利用一个过程来描述分形物体，该过程为产生物体局部细节利用一个过程来描述分形物体，该过程为产生物体局部细节指定了重复操作指定了重复操作分形分形-欧氏几何法欧氏几何法&分形几何法分形几何法不同放大级别中山的粗不同放大级别中山的粗糙轮廓表面糙轮廓表面图图1 远看的山远看的山图图2

49、近看的山近看的山图图3 更近看的山更近看的山n如果放大一连续的欧氏形状，如果放大一连续的欧氏形状，不管其有多复杂，最终可得到不管其有多复杂，最终可得到平滑的放大图像平滑的放大图像n放大分形对象，则会连续地看放大分形对象，则会连续地看到原图中出现更多的细节到原图中出现更多的细节u从图从图1到图到图3的越来越近的位置观的越来越近的位置观察山，会明显地看见类似的锯齿察山，会明显地看见类似的锯齿形状形状u再靠近一些观察山，一个个突出再靠近一些观察山，一个个突出物和石块的小细节会出现在眼前物和石块的小细节会出现在眼前u再靠近一些，可看见岩石的轮廓，再靠近一些，可看见岩石的轮廓，石子、沙子等石子、沙子等轮

50、轮廓廓显显示示得得更更弯弯曲，曲，更更倾倾斜斜分形几何法的特点和用途分形几何法的特点和用途n通过选择一个分形的局部，并且在同样大小的观察区内显示，通过选择一个分形的局部，并且在同样大小的观察区内显示，可得到分形对象的放大显示可得到分形对象的放大显示u对分形对象的该部分再进行构造操作，可得到放大级的增加的细节对分形对象的该部分再进行构造操作，可得到放大级的增加的细节-重复这一过程，可显示越来越多大的细节重复这一过程，可显示越来越多大的细节n因为构造过程包含无穷性，并且分形对象没有确定大小，所因为构造过程包含无穷性，并且分形对象没有确定大小，所以考虑越来越多细节时，对象的大小趋于无限以考虑越来越多

51、细节时，对象的大小趋于无限n可使用一个被称为可使用一个被称为“分形维数分形维数”的数字来描述对象细节的变的数字来描述对象细节的变化。该数字不一定是整数化。该数字不一定是整数-有时被称为分数维数有时被称为分数维数n分形几何法的用途分形几何法的用途u分形表示用于模拟岩层、云、水、树以及其它植物、羽毛、毛皮和分形表示用于模拟岩层、云、水、树以及其它植物、羽毛、毛皮和各种表面纹理各种表面纹理u分形模型用于星体分布、河流、月球陨石坑、雨地，以及表示股市分形模型用于星体分布、河流、月球陨石坑、雨地，以及表示股市变化、音乐、交通流量、人口资源利用、数字分析技术收敛区域的变化、音乐、交通流量、人口资源利用、数

52、字分析技术收敛区域的边缘边缘名称名称“分形分形”的基础的基础n对一个空间区域中的点重复使用指定的变换函数，即可生对一个空间区域中的点重复使用指定的变换函数，即可生成一个分形对象成一个分形对象n假设假设P0(x0, y0, z0)是选定的初始点，每次重复变换函数是选定的初始点，每次重复变换函数F的计的计算，可生成细节后继层算，可生成细节后继层P1=F(P0), P2=F(P1), P3= F(P2)n变换函数一般可应用于给定的点集，或将变换函数应用于变换函数一般可应用于给定的点集，或将变换函数应用于基本函数的初始集上，如直线、曲线、颜色区或表面基本函数的初始集上，如直线、曲线、颜色区或表面n变换

53、函数可定义为几何变换（对称、平移、旋转），或者变换函数可定义为几何变换（对称、平移、旋转），或者利用非线性变换和统计决策参数来建立利用非线性变换和统计决策参数来建立n虽然分形对象在虽然分形对象在定义上定义上包含无限的细节包含无限的细节，但是我们只运用，但是我们只运用有限次变换函数，使得显示的对象具有有限维数。增加变有限次变换函数，使得显示的对象具有有限维数。增加变换次数以产生更多的细节时，过程性表示将接近换次数以产生更多的细节时，过程性表示将接近真正的真正的“分形分形”n包括在包括在最终图形显示中的细节数量最终图形显示中的细节数量依赖于依赖于重复执行的次数重复执行的次数和和显示系统的分辨率显示

54、系统的分辨率分形生成过程分形生成过程分形分形-示例示例科赫雪花科赫雪花(Von koch snowflake)分形分形-示例示例图图1树形生成元及对应曲线树形生成元及对应曲线图图2分形分类分形分类n自相似自相似分形：组成部分是整个物体的收缩形式分形：组成部分是整个物体的收缩形式u分为分为2类：类：“确定确定自相似分形自相似分形”和和“统计统计自相似分形自相似分形”u前者从初始形状开始，对整个物体应用缩放参数前者从初始形状开始，对整个物体应用缩放参数s来构造物体的子来构造物体的子部件；对子部件使用相同的缩放参数部件；对子部件使用相同的缩放参数s构造其子部件；或者使用不构造其子部件；或者使用不同的

55、缩放因子构造对象的不同收缩部分同的缩放因子构造对象的不同收缩部分u后者对收缩部分使用随机变量。使各部分具有相同的统计性质。统后者对收缩部分使用随机变量。使各部分具有相同的统计性质。统计自相似分形常用于模拟树木、灌木和其他植物计自相似分形常用于模拟树木、灌木和其他植物(彩页彩页P12)n自仿射自仿射分形：组成部分由不同坐标方向上的不同缩放因子分形：组成部分由不同坐标方向上的不同缩放因子sx、sy、sz形成。也可引入随机变量，获得随机自仿射分形形成。也可引入随机变量，获得随机自仿射分形u岩层、水和云是应用随机自仿射分形构造方法的典型例子岩层、水和云是应用随机自仿射分形构造方法的典型例子(彩页彩页P

56、13)n不变分形不变分形集：由非线性变换形成集：由非线性变换形成(彩页彩页P14)u自平方分形自平方分形u自逆分形：由自逆过程形成自逆分形：由自逆过程形成分形分类分形分类-示例示例植物植物(彩页彩页P12)岩层岩层(彩页彩页P13)曼德勃罗集曼德勃罗集 (Mandelbrot set)朱利亚集朱利亚集 (Julia set)四元数分形四元数分形(Quartic fractals)分形分类分形分类-不变分形集不变分形集示例示例彩页彩页P14分形的维数分形的维数n分形的维数：分形对象的细节变化可以使用数字分形的维数：分形对象的细节变化可以使用数字D描述，描述，D称为分形维数称为分形维数uD是对象粗

57、糙性或细碎性的度量是对象粗糙性或细碎性的度量u对象有较大的锯齿形时，其分形维数较大对象有较大的锯齿形时，其分形维数较大n生成分形对象时与分形维数相关的生成分形对象时与分形维数相关的2种方法种方法u建立一个使用选定的建立一个使用选定的D值的交互过程值的交互过程u从构造对象的特性来确定分形维数从构造对象的特性来确定分形维数n计算计算D以拓扑学中定义的维数概念为基础以拓扑学中定义的维数概念为基础分形的维数分形的维数n1nLLDE=1, s= , n=2n1L11nsAnAA DE=2, n=4211ns VnVV 12nsDE=3, n=8311ns 13ns下面表示缩放因子下面表示缩放因子s与单位

58、线段、正方与单位线段、正方形和立方体的再分数目形和立方体的再分数目n之间的关系之间的关系1因此，确定性自相似分形维数因此，确定性自相似分形维数D = ln n / ln(1/s) 其中：其中：n是再分数目、是再分数目、s是缩放因子是缩放因子分形的维数分形的维数n对于每一个物体，子部分数目与缩放因子的关系式是对于每一个物体，子部分数目与缩放因子的关系式是nsD=1 n求得求得D的表达式为：的表达式为：D=ln n/ln (1/s) n对于不同部分由不同的缩放因子构造而成的自相似分形那么对于不同部分由不同的缩放因子构造而成的自相似分形那么分形维数可由下列关系式得到分形维数可由下列关系式得到其中：其

59、中：sk是第是第k个子部分的缩放因子个子部分的缩放因子1DksK=1, 2, 3, , nn上面考虑了简单物体的细分，如果有曲线和曲面物体的复杂上面考虑了简单物体的细分，如果有曲线和曲面物体的复杂的形状的物体，确定子部分的结构和性质会更加复杂的形状的物体，确定子部分的结构和性质会更加复杂n对于一般物体的形状，可以采用拓扑覆盖方法，该方法对于一般物体的形状，可以采用拓扑覆盖方法，该方法是采用简单形状来逼近物体的子部分是采用简单形状来逼近物体的子部分拓扑覆盖拓扑覆盖n拓扑覆盖一般用于将常见形状的几何性质扩充到非标准形状拓扑覆盖一般用于将常见形状的几何性质扩充到非标准形状u如：如：Hausdorff

60、-Besicovitch维数的方式是运用球或圆的覆维数的方式是运用球或圆的覆盖方法进行扩充，一般的方法是采用方框覆盖（盖方法进行扩充，一般的方法是采用方框覆盖（box-convering）方法进行估算，该方法利用了正方形或平行）方法进行估算，该方法利用了正方形或平行六面体六面体绿色区域区域面积，可以通过小的绿色区域区域面积，可以通过小的覆盖正方形面积之和进行估算覆盖正方形面积之和进行估算方框覆盖方法过程方框覆盖方法过程n1) 首先确定物体坐标范围（即覆盖物体的矩形区域）首先确定物体坐标范围（即覆盖物体的矩形区域）n2)然后利用给定的缩放因子然后利用给定的缩放因子s将物体分成很多小框将物体分成很多小框覆