计算机图形学-第九章.教学提纲

1、计算机图形学-第九章.2、目前的造型技术主要有、目前的造型技术主要有：（1）实体造型技术（实体造型技术（Solid Modeling)：将对象分解为一组有限的三维元素的集合，以及施加在这组集合元素上的一组操作。又可分为空间分割表示空间分割表示、结结构实体几何模型（构实体几何模型（CSG）、）、边界模型（边界模型（BReps)。 （2）曲面造型技术（Surface Modeling)用数学函数（如B样条、贝塞尔）描述曲线和曲面，并提供其修改、连接、求交和显示等操作（3）非几何形体的造型技术大多数自然物体，如山石、树木、花草、云、水波、火焰的非规则形体的表达与操作方法1、分形造型的概念、分形造型的

2、概念分形是最近二十多年来发展起来的新学科。分形的原文是 Fractals，是由著名数学家 B . Mandelbrot 于 1975 年用拉丁词根构造的单词，他创立了独立于欧几里德几何学之外的数学方法：分形几何。9.2 非几何形体的造型技术分形具有下面列出的典型几何性质分形具有下面列出的典型几何性质（）分形集都具有任意小尺度下的比例细节，或者说它具有精细的结构。（）分形集不能用传统的几何语言来描述，它既不是满足于某些条件的点的轨迹，也不是某些简单方程的解集。（）分形集具有某种自相似的形式，可能是近似的或统计的自相似。 （）一般说来，分形集的维数是一个分数，所以分形也称为分数维；（）在大多数令人

3、感兴趣的情形下，分形集由非常简单的方法定义，可以用变换的迭代产生。分形的四种构成方法分形的四种构成方法（）基于系统的分形模型（）迭代函数系统模型（）粒子系统模型（）随机插值模型 .Koch 曲线曲线( 1 ) Koch 曲线的生成规则曲线的生成规则Koch 曲线是 Von Koch 于1904年第一次描述的。它的构造是：迭代初始把原线段去掉中间的三分之一，代之以底边在被去线段上的等边三角形的两腰；以后每一步的迭代都是这样的重复。（图例）二、典型的分形模型二、典型的分形模型从以上过程可以清楚地看出，Koch曲线（其它分形集也是如此）可以由简单的 图，称为 生成元 ，迭代产生。在这里，Koch曲线

4、的生成元是：在这里，假如我们约定好记号，就可以把Koch曲线的生成元的构造用一个字符串符号表示出来。设：F从当前点开始，向前移动一距离dL向左（逆时针）转一定角R向右（顺时针）转一定角则Koch曲线的生成元可表示为：T F L F R R F L F （ 60）曲线由把每一折线段反复迭代成缩小比例的三分之一的生成元而成。即字符串T F L F R R F L F 中的每一个 F 又是字符串 T 本身。而每次迭代后，生成的曲线长是原来曲线长的三分之四倍。可见，无数次迭代后，Koch 曲线将变得具有无限长度。并且，Koch 曲线是永远不自相交的。 ( 2 )生成生成Koch 曲线的程序曲线的程序函

5、数 side( )，用于绘制Koch 曲线的生成元，函数中所用的参数为：xa, ya, xb, yb :线段的起点和终点坐标；a : 线段的方向角；n : 迭代次数（递归深度）。void side ( xa, ya, xb, yb, a, n ) int n ; float xa, ya, xb, yb, a ; float x1, y1, x2, y2, x3, y3, dl, a1, a2 ; int xs, ys, xe, ye ; if (n=0) xs=(int)(xa+0.5) ; ys=(int)(ya+0.5) ; xe=(int)(xb+0.5) ; ye=(int)(yb+

6、0.5) ; moveto(xs,480-ys) ; lineto(xe,480-ye); else dl=sqrt(xb-xa)*(xb-xa)+(yb-ya)*(yb-ya) / 3. ; x1=xa+(xb-xa) / 3. ; y1=ya+(yb-ya) / 3. ; side(xa, ya, x1, y1, a, n-1) ; a1=a+AF ; x2=x1+dl*cos(a1) ; y2=y1+dl*sin(a1) ; side(x1, y1, x2, y2, a1, n-1) ;a2=a1-2.*AF ; x3=x2+dl*cos(a2) ; y3=y2+dl*sin(a2) ;

7、 side(x2, y2, x3, y3, a2, n-1) ; side(x3, y3, xb, yb, a, n-1) ; *.Dragon 曲线曲线（）（）Dragon 曲线的生成规则曲线的生成规则变化的起始是一条原始直线段。第一步是将该直线段由中间点隆起，使其变成一个等腰直角三角形的两腰。接下去再分别对两腰作和前面同样的变化，如此不断进行。（图例）不难看出，Dragon 曲线完全是由长度相等的线段组成，且两两相交处都成直角。另外，每次分形后，曲线的长度是原来曲线长度的 2 倍。因此，经过无数次变化，Dragon 曲线也将变成无限长。这一点正符合分形曲线的特点。.其他分形实例其他分形实例

8、用 分形 可以构造很多自然界的形体，下面是几种常见的例子：（）分枝（）分枝 Koch 曲线和Dragon曲线都是连续的，分枝结构是不连续的，它的生成元类似于图例所示。其生成元描述为：F : F L F F R F F * （）粒子模型的图例（）粒子模型的图例 * （）岩石（）岩石这种分形由平面多边形（如三角形、四边形等）用随机插值法迭代生成，可模拟山峦。如图所示：Z取中点在边直线上在中点上加一个随机法向量9.3 实体的定义1、定义：n具有一定的形状（非流体）n具有封闭的边界（表面）n内部连通（上图为非有效实体）n占据有限的空间（有限体积）n经过运算后，仍然是有效的物体2、有关概念： 内点 边界

9、点 取内点运算 i 取闭包运算 c正则运算 r rA = ciA结论：（1）一个物体只能占据有限空间，它是封闭的，具有一定的体积；（2）物体中不允许存在孤立点、悬挂的线或面。3、物体间的正则集合运算n物体间的并（U）、交（ ） 、差（）是造型系统中最基本的手段之一。n集合运算式构造复杂物体的有效方法n为什么需要正则集合运算n普通的集合运算会产生无效物体BA)(*BArBA（1）线框模型将形体表示成一组轮廓线的集合，只存储所画图形的顶点及顶点间的连接关系。优点：优点：适合图形的几何变换和交互显示。简单、处理速度快与形体之间不存在对应关系，是真实物体的高度抽象，缺点：缺点：a、无法实现图形的消隐；

10、b、数据定义的模糊性；c、无法处理曲面的侧影轮廓线；d、复杂物体的数据多、繁，且难以保证有效性和统一性。e、所不适合真实感显示。9.4 实体造型技术(显示)（2）表面模型（曲面造型）将形体表示成一组表面的集合形体与其表面一一对应，着重于准确地描述和控制物体的外形，适合于真实感显示（着色、光照）9.5 八叉树表示空间分割表示常用方法：（1）空间位置枚举法（2）单元分解表示法（3）八叉树表示法1、空间位置枚举法（1）选择一个包含物体的立方体空间，将它均匀划分。其中为小立方体的边长。 三维数组的大小取决于空间分辨()的大小和我们感兴趣的立方体的大小。（2）n用三维数组CIJK表示物体， 数组中的元素

11、与单位小立方体一一对应n当CIJK=1时，表示对应的小立方体被物体占据n当CIJK=0时，表示对应的小立方体没有被物体占据n优点n可以表示任何物体n容易实现物体间的集合运算n容易计算物体的整体性质，如体积等n缺点n占用大量的存储空间，如1024*1024*1024=1Gbitsn没有边界信息，不适于图形显示n对物体进行几何变换困难，如非90度的旋转变换n是物体的非精确表示2、单元分解表示n对空间位置枚举表示的空间分割方法作了改进：单一体素多种体素通过粘合运算：使两个实体在边界面上相接触，但它们的内部不相交。3、八叉树表示：（1）是一种层次数据结构,首先在空间中定义一个能包含所表示物体的立方体。

12、立方体的三条棱边与x,y,z轴平行。若立方体内空间完全由这个立方体予以表示（标识为FULL），否则标识为（PARTIAL）将立方体等分为8等分，依次编号。依此方式判断小立方体的状态（FULL、PARTIAL或EMPTY），若为PARTIAL，则继续分（2）、二维物体的四叉树表示：（3）、三维物体的八叉树表示（例）：（3）、八叉树表示的优、缺点：优点：优点：a.容易实现实体间的正则集合运算；b.简化隐藏线和隐藏面的消除。（消隐算法的核心是排序）c.易于计算物体的体积（或质量）缺点：缺点：占用存储多（如圆柱、球等）解决方法：线性八叉树方法（GARG82）即：采用可变长度的线性结构存储八叉树（如可变

13、长度的一维数组），数组中只存放八叉树中那些状态为F（FULL）的叶结构。888002211qqqmmmmQ（5X、74X，75X）4、三种空间分割方法的比较n空间位置枚举表示粘合在一起表示物体n八叉树表示粘合在一起表示物体n单元分解表示粘合在一起表示物体9.6 物体的边界表示(B-Reps:Boundary Reprensentation)1、概念：（1）物体的边界表示：三维物体可以通过描述它的边界来表示；（2）边界：物体内部与外部点的分界面。2、特点：描述物体的信息包括几何信息和拓扑信息。（1）几何信息：大小、尺寸、位置、形状等，如顶点在三维空间的位置（三维坐标）、棱边的曲线方程、物体表面的

14、曲面方程等；（2）拓扑信息：物体上所有的顶点、棱边、表面间是怎样连接的。3、边界表示法中的数据结构（1）半边结构（以边为核心）为了方便表达拓扑关系。它将一条边表示成拓扑意义上方向相反的两条“半边”边v1v1v2v2左环左半边右环右半边边界表示n 多边形的顶点顺序与法矢量,若规定一个面的外环为逆时针,则内环为顺时针n 空间多边形的平面方程计算n顶点不共面n用最小二乘法求出一张平面，使其距所有顶点的距离之和最小（2）半边数据结构的层次结构多面体prevsnext面prevsnext环prevsnext半边prevsnext半边prevsnext4、欧拉运算（1）对于任意的简单多面体，其面(f)、边

15、(e)、顶点(v)的数目满足欧拉公式欧拉公式： v - e + f = 2.（2）对于任意的正则形体，引入形体的其它几个参数：形体所有面上的内孔总数(r)、穿透形体的孔洞数(h)和不相连接的物体个数(s)，为了保证形体的有效性，则形体须满足广义欧拉公式广义欧拉公式： v - e + f = 2(s-h) + r. (3)基本欧拉操作（I.C.Braid)欧拉操作名说明逆运算mvsf(v,f)输入一初始点v作为构造物体的开始kvsf(s)mev (v1,v2,e)输入一点v2，并构造一条连接v1v2的新 边eKev(s,f,v1,v2)mef(v1,v2,e,f1,f2)构造一条连接v1v2的新

16、 边e，同时构造新面f2，f2与f1通过e相连Kef(s,f,v1,v2)kemr(v1,v2,e)删除v1v2的桥边e，同时构造一个新的内环Mekr(s,f,v1,v2,v3,v4)kfmrh(f1,f2)将表面f1中的内环面f2删除，同时构造f1的一个新内环，生成物体的一个通孔Mfkrh(s,f1,f2,v1,v2)5、Sweep运算将一个二维的平面区域转化为三维立体。常用的Sweep运算有平移式、旋转式和广义式。（参看SolidWorks造型功能）（1）平移式Sweep操作 （2）旋转式sweep操作将一个二维区域绕旋转轴旋转一周广义式sweep操作包括平移和旋转：(SolidWorks举例）广义式Swee操作6、边界表示的优、缺点：（1）优点：精确表示物体表示能力强几何变换容易适于显示处理（2） 缺点表示复杂有效性难以保证集合运算复杂9.7 构造实体几何表示1、将