第三维几何造型课件

第三维几何造型第三维几何造型1形体的定义几何形体由基本元素点、边、面、体等组成，这些基本元素的定义如下。1．点它是0维几何元素，分端点、交点、切点和孤立点等。但在形体定义中一般不允许存在孤立点。在自由曲线和曲面的描述中常用三种类型的点，即：(1)控制点用来确定曲线和曲面的位置与形状，而相应曲线和曲面不一定经过的点。(2)型值点用来确定曲线和曲面的位置与形状，而相应曲线和曲面一定经过的点。形体的定义几何形体由基本元素点、边、面、体2

(3)插值点

为提高曲线和曲面的输出精度，在型值点之间插入的一系列点。

一维空间中的点用一元组{t}表示；二维空间中的点用二元组{x，y}或{x（t），y（t）}表示；三维空间中的点用三元组{x，y，z｝或{x（t），y（t），z(t)}表示。n维空间中的点在齐次坐标系下用n＋1维表示。点是几何造型中的最基本元素，自由曲线、曲面或其他形体均可用有序的点集表示。用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。

(3)插值点为提高曲线和曲面的输出精度，在型值点之间32．边边是一维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。直线边由其端点（起点和终点）定界；曲线边由一系列型值点或控制点表示，也可用显式、隐式方程表示。

3．面面是二维几何元素，是形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。一个面可以无内环，但必须有一个且只有一个外环。

面有方向性，一般用其外法矢方向作为该面的正向。若一个面的外法矢向外，此面为正向面；反之，为反向面。

2．边3．面面有方向性，一般用其外法矢方向作为该面的4区分正向面和反向面在面面求交、交线分类、真实图形显示等方面都很重要。在几何造型中常分平面、二次面、双三次参数曲面等形式。

4．环环是有序、有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点。

环有内外之分，确定面的最大外边界的环称之为外环，通常其边按逆时针方向排序。而把确定面中内孔或凸台边界的环称之为内环，其边与外环排序方向相反，通常按顺时针方向排序。基于这种定义，在面上沿一个环前进，其左侧总是面内，右侧总是面外。

区分正向面和反向面在面面求交、交线分类、真实图形显示55．体体是三维几何元素，由封闭表面围成的空间，也是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。

为了保证几何造型的可靠性和可加工性，要求形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域。我们把满足这个定义的形体称之为正则形体。不满足上述要求的形体称为非正则形体。

非正则形体的造型技术将线框、表面和实体模型统一起来，可以存取维数不一致的几何元素，并可对维数不一致的几何元素进行求交分类，从而扩大了几何造型的形体覆盖域。

5．体为了保证几何造型的可靠性和可加工性，要求形体上6基于点、边、面几何元素的正则形体和非正则形体的区别如表6.1表所示。

表6.1正则形体和非正则形体的区别几何元素正则形体非正则形体面是形体表面的一部分可以是形体表面的一部分,也可以是形体内的一部分,也可以与形体相分离。边只有二个邻面可以有多个邻面、一个邻面或没有邻面。点至少和三个面(或三条边)邻接可以与多个面(或边)邻接，也可以是聚集体、聚集面、聚集边或孤立点。基于点、边、面几何元素的正则形体和非正则形体的区别如76．体素体素是可以用有限个尺寸参数定位和定形的体，常有三种定义形式。

（1）从实际形体中选择出来，可用一些确定的尺寸参数控制其最终位置和形状的一组单元实体，如长方体、圆柱体、圆锥体、圆环体、球体等。

（2）由参数定义的一条（或一组）截面轮廓线沿一条（或一组）空间参数曲线作扫描运动而产生的形体。

（3）用代数半空间定义的形体，在此半空间中点集可定义为：{(x，y，z)|f（x，y，z）≤0}，此处的f应是不可约多项式，多项式系数可以是形状参数，半空间定义法只适用正则形体。

6．体素（1）从实际形体中选择出来，可用一些确定的尺寸参数8从上述定义中我们知道几何形体有两种重要信息：几何信息和拓扑信息。几何信息是指描述几何元素（如点、线、面等）空间位置和大小的信息，如点的空间坐标值、线段的长度等。拓扑信息是指几何元素之间的相互连接关系的信息。它只反映几何元素的结构关系，而不考虑它们各自的绝对位置，这种关系称为拓扑关系。几何元素之间一共有九种拓扑关系，即面-面相邻性、边-边相邻性、顶点-顶点相邻性、边-面相邻性、顶点-面相邻性、顶点-边相邻性、面-边包含性、面-顶点包含性、边-顶点包含性。从上述定义中我们知道几何形体有两种重要信息：几何信息9形体的存储模型

无论是形体的表示，还是新形体的生成都与其几何信息和拓扑信息有关。只有几何信息没有拓扑信息是不能构成图形的。这两方面的信息如何在计算机中存储和使用，达到既节省计算机的空间资源和时间资源，又能有效地进行各种操作运算，一般是通过研究图形的数据结构来解决。

三维形体在计算机内的3种存储模式决定了形体的3种存储模型：线框模型、表面模型和实体模型。

形体的存储模型无论是形体的表示，还是新形体的生成都10环有内外之分，确定面的最大外边界的环称之为外环，通常其边按逆时针方向排序。0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);1415926/180;else//对组成发生器的每条线段进行递归处理这是因为每一体元都是立方体，且体元各表面分别与三个坐标平面平行。1988年,ISO颁布的STEP(产品模型数据交换标准）标准草案，将形状、容差、材料等特征列为产品信息模型的构成要素，从而使特征造型获得法定地位。x[k]=x[k-1]*x[k-1]*x[k-1]-3*x[k-1]*y[k-1]*y[k-1]+xc;常用办法是用有向边的右手法则确定所在面的外法线的方向（即用右手沿着边的顺序方向握住，大拇指所指向的方向则为该面的外法线的方向）。⑤标示当前点的颜色（根据n的大小）而把确定面中内孔或凸台边界的环称之为内环，其边与外环排序方向相反，通常按顺时针方向排序。{//从数列的最后项起若第k项落在以最后一项为中心若某一小立方体的体内空间全部被所表示的物体占据，则将此立方体标识为“Full”；分形几何造型是利用分形几何学的自相似性，采用各种模拟真实图形的模型，使整个生成的景象呈现出细节的无穷回归性质的方法。fabs(y[KL]-y[KL-k])<BOX)A∩*B=r(A∩B)在两个多边形之间进行并、交、差的运算。1．线框模型（Wireframe

Model）三维线框模型是在二维线框模型的基础上发展起来的。在60年代初期，用户通过逐点、逐线地构造二维线框模型，就能用计算机代替手工绘图。由于图形几何变换和投影变换理论的发展，认识到在计算机内部的存储信息中加上第三维信息，再用不同视向的投影变换，就可以在显示器上显示出不同视向的立体图。因此，三维绘图系统迅速发展了起来。

线框模型采用顶点表和边表两个表的数据结构来表示三维物体，顶点表记录各顶点的坐标值，边表记录每条边所连接的两个顶点。由此可见，三维物体可以用它的全部顶点及边的集合来描述，线框一词由此而来。

环有内外之分，确定面的最大外边界的环称之为外环，通常其边按逆11V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY图6.2和表6.2、表6.3说明了线框模型在计算机内存储的数据结构原理。

图6.2组成长方体的顶点和边

V1V2V3V4V5V6V7V8E8E10E1E2E3E4E12顶点表V1V2V3V4V5V6V7V8x坐标aaaa0000y坐标0bb00bb0z坐标00cc00cc边号E1E2E3E4E5E6E7E8E9E10E11E12起点号V1V2V3V4V5V6V7V8V1V2V3V4终点号V2V3V4V1V6V7V8V5V5V6V7V8表6.2长方体的顶点表

表6.3长方体的边表

顶点表V1V2V3V4V5V6V7V8x坐标aaaa000013线框模型的优点主要是可以产生任意视图，视图间能保持正确的投影关系，这为生成需要多视图的工程图纸带来了很大方便。还能生成任意视点或视向的透视图及轴测图。构造模型时操作简便，在CPU时间及存储方面开销低。

线框模型的缺点也很明显，因为所有棱线全都显示出来，物体的真实形状须由人脑的解释才能理解，因此容易出现二义性。当形状复杂时，棱线过多，也会引起模糊理解。缺少曲面轮廓线。由于在数据结构中缺少边与面、面与体之间关系的信息，即所谓拓扑信息，因此不能构成实体，无法识别面与体，更谈不上区别体内与体外。线框模型的优点主要是可以产生任意视图，视图间能保持正14因此从原理上讲，此种模型不能消除隐藏线，不能作任意剖切，不能计算物性，不能进行两个面的求交，无法生成数控加工刀具轨迹，不能自动划分有限元网格，不能检查物体间碰撞、干涉等。但目前有些系统从内部建立了边与面的拓扑关系，因此具有消隐功能。

尽管这种模型有许多缺点，但由于它仍能满足许多设计与制造的要求，加上上面所说的优点，因此在实际工作中使用很广泛，而且在许多CAD／CAM系统中仍将此种模式作为表面模型与实体模型的基础。线框模型系统一般具有丰富的交互功能，用于构图的图素是大家所熟知的点、线、圆、圆弧、二次曲线、样条曲线、Bezier曲线等。

因此从原理上讲，此种模型不能消除隐藏线，不能152．表面模型（SurfaceModel）这种模型通常用于构造复杂的曲面物体，构形时常常利用线框功能，先构造一线框图，然后用扫描或旋转等手段变成曲面，当然也可以用系统提供的许多曲面图素来建立各种曲面模型。该模型的数据结构原理见图6.3，与线框模型相比，多了一个面表（顶点表和边表与表6.2和表6.3完全相同，面表见表6.4），记录了边、面间的拓扑关系，但仍旧缺乏面、体间的拓扑关系，无法区别面的哪一侧是体内,哪一侧是体外，依然不是实体模型。2．表面模型（SurfaceModel）该模型的数16Xamax≤Xbmin；交运算的规则刚好和并运算的规则相反。在复平面的某一部位上，令C作有规律的变化，对不同的C值进行迭代，如果计算结果达到无穷大，则C被着成白色，否则，着成黑色，这样就能显示出M集的形状。case9:xc=-1.case4:xc=-1.在一般情况下，一个普通物体相应的八叉树可能多达数千个结点。y[k]=2*x[k-1]*y[k-1]+yc;//虚部case9:xc=-1.END};E3E11E7E12MoveTo(LPX,LPY);对于具有孔洞的正则多面体，相应的欧拉公式扩展为：<集合运算><形状特征单元>|<形状特征单元><集合运算><形状特征单元>|<形状特征单元>发生器就是生成复杂分形图形的最小基本图元，如Koch曲线的发生器为图6.7(中、右)的旋转扫描，这个物体可以看作为集合A按绕Z轴旋转的路径B运动而成。对于具有孔洞的正则多面体，相应的欧拉公式扩展为：Mandelbrot分形集CGraphDCg(this);V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZYF1F3F4F2F5F6图6.3长方体的顶点、边和面

Xamax≤Xbmin；V1V2V3V4V5V6V7V817面号F1F2F3F4F5F6边号E1E2E3E4E5E6E7E8E1E10E5E9E2E11E6E10E3E12E7E11E4E9E8E12表6.4长方体的面表

表面模型的优点是能实现以下功能：消隐、着色、表面积计算、二曲面求交、数控刀具轨迹生成、有限元网格划分等。此外擅长于构造复杂的曲面物体，如模具、汽车、飞机等表面。它的缺点是有时产生对物体二义性理解。

面号F1F2F3F4F5F6边号E1E2E3E4E18需要指出的是不仅表面模型中常常包括了线框模型的构图图素，而且表面模型还时常与线框模型一起同时存在于同一个CAD／CAM系统中。表面模型系统中常用的曲面图素有平面、直纹面、旋转面、柱状面、贝塞尔曲面、B样条曲面、孔斯曲面和等距面。

3．实体模型实体模型与表面模型的不同之处在于确定了表面的哪一侧存在实体这个问题。常用办法是用有向边的右手法则确定所在面的外法线的方向（即用右手沿着边的顺序方向握住，大拇指所指向的方向则为该面的外法线的方向）。需要指出的是不仅表面模型中常常包括了线框模型19例如规定正向指向体外，如图6.4所示。如此只须将表6.4的面表改成表6.5的环表形式，就可确切地分清体内体外，形成实体模型了。

体外图6.4有向边确定外法线方向

实体模型的数据结构当然不会这么简单，可能有许多不同的结构。但有一点是肯定的，即数据结构不仅记录了全部几何信息，而且记录了全部点、线、面、体的拓扑信息，这是实体模型与线框或表面模型的根本区别。

例如规定正向指向体外，如图6.4所示。如此只须将表620面号F1F2F3F4F5F6边号E1E2E3E4E8E7E6E5E1E9E5E10E2E10E6E11E3E11E7E12E4E12E8E9表6.5长方体的环表

实体模型成了设计与制造自动化及集成的基础。依靠机内完整的几何与拓扑信息，所有前面提到的工作，从消隐、剖切、有限元网格划分、直到NC刀具轨迹生成都能顺利地实现，而且由于着色、光照及纹理处理等技术的运用使物体有着出色的可视性，使它在CAD／CAM、计算机艺术、广告、动画等领域有广泛的应用。

实体模型的构造方法常用机内存储的体素(Primitive),经集合论中的交、并、差运算构成复杂形体。

面号F1F2F3F4F5F6边号E1E2E3E4E21形体的线框模型、表面模型和实体模型是一种广义的概念，并不反映形体在计算机内部，或对最终用户而言所用的具体表示方式。从用户角度看，形体表示以特征表示和构造的实体几何表示（CSG）较为方便；从计算机对形体的存储管理和操作运算角度看，以边界表示（BRep）最为实用。为了适合某些特定的应用要求，形体还有一些辅助表示方式，如单元分解表示和扫描表示。对于一个几何造型系统不可能同时采用上述五种表示，也不可能只采用一种表示，一般根据应用的要求和计算机条件采用某几种表示的混合方式。6.2三维实体表示方法形体的线框模型、表面模型和实体模型是一种广义22例如，70年代初，美国Rochester大学推出了以CSG表示为基础的PADL-1系统；日本北海道大学推出了以Coons曲面片为边界的TIPS系统；美国MIT大学推出了以线框边界为基础的ADAM系统；美国Stanford大学推出了以欧拉操作为基础的Geomod系统；英国Cambridge大学推出了以边界表示为基础的Build-1系统。目前，国际上应用较广的几何造型系统有IBM公司的CADAM和CATIA；SDRC公司的Geomod；PT公司的Pro/Engineer；SpatialTechnology公司的ACIS；Solidworks公司的Solidworks等。例如，70年代初，美国Rochester大学23构造的实体几何(CSG：ConstructiveSolidGeometry)法的含意是任何复杂的形体都可用简单形体（体素）的组合来表示。通常用正则集合运算（构造正则形体的集合运算）来实现这种组合，其中可配合执行有关的几何变换。

形体的CSG表示可看成是一棵有序的二叉树，称为CSG树。其终端结点或是体素，如长方体、圆柱体等；或是刚体运动的变换参数，如平移参数△x等。非终端结点或是正则的集合运算，一般有交、并、差运算；或是刚体的几何变换，如平移、旋转等。

构造的实体几何法构造的实体几何(CSG：ConstructiveS24自相似的不变集的曲线段，是通过反复用一发生器的相似图形，来取代每一直线段的递归调用过程而建立起来的。由于在数据结构中缺少边与面、面与体之间关系的信息，即所谓拓扑信息，因此不能构成实体，无法识别面与体，更谈不上区别体内与体外。此时，必定有如下四个不等式中的一个得到满足。传统的点集之间的并、交、差运算可能改变点集的正则性质，也就是说，两个正则点集的集合运算的结果可能产生一个非正则点集。E1E10E5E9y[k]=3*x[k-1]*x[k-1]*y[k-1]-y[k-1]*y[k-1]*y[k-1]+yc;5,x_max=1.依此方式，物体在计算机内可表示为一棵八叉树。若将Mandelbrot分形集的迭代式由2次换成3次：实际上，八叉树表示以存储空间换取了算法的时间效率。通常在以边界表示法为基础的几何造型系统中，时常将这两类扫描方法列为输入形体的手段之一，只要在屏幕上设计出所要的一个二维图形，调用系统提供的扫描命令，立即就能形成三维实体，因此成为形体输入的强有力的手段之一。else//对组成发生器的每条线段进行递归处理intcx=320,cy=240;//绘图中点其中，新增的参数H为实体表面的空穴数，B为实体个数，P为穿透实体的孔洞数。{//从数列的最后项起若第k项落在以最后一项为中心GetColor(col[i][1]);计算机图形学也从中受到启发，并形成了以模拟自然界复杂景象、物体为目标的分形几何造型。设逆时针旋转时角度为正，发生器的初始角度为0，图中已标明发生器各段的位置和角度。分形图形中最著名的是Mandelbrot集，这是分形的创始者Mandelbrot在非线性分形领域中作出的杰出贡献。l

1≤n≤2颜色为3号（青色）只有几何信息没有拓扑信息是不能构成图形的。这里，正则集合运算是在传统点集的集合运算基础上附加一定的限制而定义的。传统的点集之间的并、交、差运算可能改变点集的正则性质，也就是说，两个正则点集的集合运算的结果可能产生一个非正则点集。但在实际生活中，两物体并、交、差运算的结果总是产生一新的物体（或一空物体）。为了反映这样一个事实，有必要对传统的点集的集合运算施加一定的限制。为此，对点集的正则集合运算作如下定义：A∪*B=r(A∪B)A∩*B=r(A∩B)A―*B=r(A―B)自相似的不变集的曲线段，是通过反复用一发生器的相似图形，来取25这种运算或变换只对其紧接着的子结点（子形体）起作用。每棵子树（非变换叶子结点）都代表一个集合，表示了其下两个结点组合及变换的结果，它是用算子对体素进行运算后生成的。树根表示了最终的结点，即整个形体。CSG树可能是一颗不完全的二叉树，这取决于用户拼合该物体时所设计的步骤。

CSG树是无二义性的，但不是唯一的，它的定义域取决于其所用体素以及所允许的几何变换和正则集合运算算子。

其中，∪*、∩*、―*分别称为正则并、正则交、正则差，而∪、∩、―则表示传统的点集的并、交、差集合运算，r表示点集正则化算子。这种运算或变换只对其紧接着的子结点（子形体）起作用。26（2）每个CSG表示都和一个实际的有效形体相对应；

（3）CSG表示可方便地转换成BRep表示，从而可支持广泛的应用；（4）比较容易修改CSG表示形体的形状。CSG法的缺点：（1）产生和修改形体的操作种类有限，基于集合运算对形体的局部操作不易实现；（2）由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。

CSG法的优点：（l）数据结构比较简单，数据量比较小，内部数据的管理比较容易；（2）每个CSG表示都和一个实际的有效形体相对应；（3）C27边界表示（BoundaryRepresentation）法详细记录了构成形体的所有几何元素的几何信息及其相互连接关系的拓扑信息，以便直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。如形体线框的绘制、有限元网格的划分、数控加工轨迹的计算、真实感彩色图形的生成等。

所谓边界就是物体内部点与外部点的分界面。形体的边界表示就是用面、环、边、点来定义形体的位置和形状。例如，长方体由六个面围成，对应有六个环，每个环由四条边界定，每条边又由两个端点定义。而圆柱体由上顶面、下底面和圆柱面围成，对应的有上顶面圆环、下底面圆环。

边界表示法边界表示（BoundaryRepresentati28在边界表示法中，为了对记录的顶点、边和平面数据信息进行存储管理，需要选取一定的数据结构。常用的数据结构有：翼边结构、半边结构和多表结构。每种方法均有一定的应用范围和优缺点。其中最简单易用的是采用3个表结构，即顶点表、边表和面表。如图6.3中，长方体由顶点表、边表和面表（表6.2~6.4）描述。

点、边、面之间的连接关系共有9种：V:{V}、V:{E}、V:{F}、E:{V}、E:{E}、E:{F}、F:{V}、F:{E}、F:{F}，如图6.6(P197)所示。

一个简单多面体用边界表示法表示时满足欧拉公式：

V-E+F=2在边界表示法中，为了对记录的顶点、边和平面数据信息进29其中，V、E、F为实体的顶点、边和面数。如一个长方体，V=8，E=12，F=6。对于具有孔洞的正则多面体，相应的欧拉公式扩展为：

V-E+F-H=2（B-P）

其中，新增的参数H为实体表面的空穴数，B为实体个数，P为穿透实体的孔洞数。如一个带一个长方体孔的长方体，V=16，E=24，F=10，H=2，B=1，P=2。

BRep表示的优点是：（1）表示形体的点、边、面等几何元素是显式表示的，使得绘制BRep表示形体的速度较快，而且比较容易确定几何元素间的连接关系；

其中，V、E、F为实体的顶点、边和面数。如一个长方体，V=830（2）修改形体的操作比较难以实现；（3）BRep表示并不一定对应一个有效形体，即需要有专门的程序来保证BRep表示形体的有效性、正则性等。

扫描表示法是指通过平移、旋转及其他对称变换来构造三维物体的方法。一个集合在空间运动就能“扫”成一实体。通常用二维形体及它的运动轨迹来表示扫描生成的物体。有两种扫描方法：平移扫描和旋转扫描。

扫描表示法（2）修改形体的操作比较难以实现；扫描表示法31如图6.7(左)所示的平移扫描，图中A(五边形)是一个二维的多边形，B是一条有向的直线，相当于运动轨迹，A沿着B路径进行扫描运动，则形成图中所示物体。由于路径B的表达很简单，又由于集合A的表示可用A的边界的边来表示，所以平移扫描的表示可减为A集合的二维表示。

图6.7两种扫描形成的实体

如图6.7(左)所示的平移扫描，图中A(五边形)是一32图6.7(中、右)的旋转扫描，这个物体可以看作为集合A按绕Z轴旋转的路径B运动而成。同样，集合A是一个二维形体，可用其边界的边来表示。

通常在以边界表示法为基础的几何造型系统中，时常将这两类扫描方法列为输入形体的手段之一，只要在屏幕上设计出所要的一个二维图形，调用系统提供的扫描命令，立即就能形成三维实体，因此成为形体输入的强有力的手段之一。扫描表示中的二维集合由有界边线组合而成的这个特点，对经过传统训练的绘图人员来说，给了他们一个方便的接口,使他们能在屏幕上得心应手地进行设计。

这两类扫描表示中，只要二维集合A无二义性，实体就不会有二义性。

图6.7(中、右)的旋转扫描，这个物体可以看作为集合33特征表示是从应用层来定义形体，可以较好地表达设计者的意图，为制造和检验产品和形状提供技术依据和管理信息。特征造型是面向制造全过程、实现CAD/CAM集成的重要手段。1988年,ISO颁布的STEP(产品模型数据交换标准）标准草案，将形状、容差、材料等特征列为产品信息模型的构成要素，从而使特征造型获得法定地位。所谓特征是指一个产品模型的相关元素集，是在设计、加工、装配等过程中定义的关于几何形状和其他属性的信息集合。不同的面向应用的观点，形成了各种不同的特征定义，由此也形成了不同的特征分类标准。特征表示法特征表示是从应用层来定义形体，可以较好地表达34从产品的整个生命发展周期来看，特征可分为设计特征、加工特征、分析特征公差及检测特征、装配特征。从功能上看，特征可分为形状特征、精度特征、技术特征、材料特征、装配特征。一般公认的基本特征分为：形状特征：具有特定形状且对应特定功能意义的零件局部形状在整体上的布局。精度特征：在工程设计和加工中使用的形位公差、尺寸公差、表面光洁度等非几何信息，此外还包括检测特征。材料特征：规定了材料类型、强度、延展度、热导度等特征。从产品的整个生命发展周期来看，特征可分为设计35装配特征：包括装配体中各零件的位置关系、公差配合、功能关系、动力学关系等。分析特征：有关部门工程分析方面的特征，如有限元分析中的梁特征和板件特征。上述特征分类中最基本的是形状特征，平常一般说到特征时，主要指形状特征。形状特征单元是一个有形的几何实体，是一组可加工表面的集合。常用的体素定义如图6.1(P191)所示。装配特征：包括装配体中各零件的位置关系、公差36<形状特征单元>::=<体素>|<形状特征单元><集合运算><形状特征单元>|<体素><集合运算><体素>|<体素><集合运算><形状特征单元>|<形状特征单元><集合运算><形状特征过渡单元>；<体素>::=长方体|圆柱体|球体|圆锥体|棱锥体|棱柱体|

棱台体|圆环体|楔形体|圆角体|…；<集合运算>::=并|交|差|放；<形状特征过渡单元>::=外圆角|内圆角|倒角。<形状特征单元>::=<体素>|<形状特征单元><集合运算>37虽然物体之间的并、交、差运算是物体造型的十分有用的手段，然而由于在边界表示中，物体之间的集合运算涉及到两物体上所有表面的求交、比较，由此形成的巨大计算量不仅影响了集合运算的效率，而且由于求交情况复杂，也影响了算法的可靠性。解决的途径有两条，一是改进已有的集合运算算法（特别是其中的求交算法），二是探索物体在计算机内新的表示模式。三维物体的八叉树表示正是这种探索的结果。物体的八叉树表示是一种层次数据结构，是对二维空间中四叉树编码方法的扩展。四叉树将二维区域分成四等分而得，八叉树是将三维区域分成八等分而得。单元分解表示法虽然物体之间的并、交、差运算是物体造型的十分38首先在空间中定义一个能够包含所表示物体的立方体。立方体的三条棱边分别与x,y,z轴平行，边长为2n。若立方体内空间完全由所表示的物体所占据，则物体可用这个立方体予以表示，否则将立方体在x,y,z轴三个方向都分成二等分，整个立方体共等分为八个小块，每块仍为一个小立方体，其边长为原来立方体边长的1/2。将这八个小立方体依序编号为0，1，2，…，7，如图6.9所示。1305467xz图6.9八叉树的结点编码

首先在空间中定义一个能够包含所表示物体的立方39若某一小立方体的体内空间全部被所表示的物体占据，则将此立方体标识为“Full”；若它与所表示物体无交，则该立方体被标识为“Empty”；否则将它标识为“Partial”，并继续分割下去。依此方式，物体在计算机内可表示为一棵八叉树。注意，凡是标识为“Full”或“Empty”的立方体均为终端结点，而标识为“Partial”的立方体为非终端结点。最后，当分割生成的每一小立方体的边长为单位长时，分割即告终止。此时可将每一小立方体标识为“Full”。若某一小立方体的体内空间全部被所表示的物体占据，则将40物体之间的集合运算在八叉树表示中具有十分简单的形式。由定义可知，两物体的并就是这两个物体一共占有的空间，而物体之间的交即它们共同占据的空间。由于物体的八叉树表示就是由它内部含有的大大小小的立方体（称为体元）组成，因此对物体执行并、交、差运算时，只需同时遍历参加集合运算的两物体相应的八叉树，就可以获得拼合体的八叉树，而无需进行复杂的求交运算。

八叉树的数据结构也大大简化了隐藏线和隐藏面的消除。众所周知，各类消隐算法的核心部分是排序，即将待显示的物体上的点、线、面按离观察点的远近排定次序，离观察点近的元素遮挡较远的元素。

物体之间的集合运算在八叉树表示中具有十分简单的形式。41在八叉树表示中，物体上的各元素已按空间位置排成一定顺序，同一层次的八叉树结点组成三维空间中可线性分离的丛。因此可按Schumacker算法，建立丛的优先级树。由于每一层次的八叉树结点均按同一规律编码，因此丛的优先级适用于同一八叉树的所有结点，故其消隐算法的时间复杂度呈线性关系即O(n)，其中n为所要显示物体的体元数目。

计算物体的体积（或质量）则更为简单。实际上，只需从物体的八叉树的根结点开始，逐层计算所表示物体的最大和最小体积（质量）。当标识为“Patial”的体元以“Full”计时得最大体积（质量），若不计入时得最小体积（质量）。由于树的每一层都是在一定精度下对所表示物体的一种近似，因此若所得的最大最小体积（质量）之差小于给定的误差，计算即结束。

在八叉树表示中，物体上的各元素已按空间位置排成一定顺42事实上，由于八叉树中物体由一系列的体元表示，因此对物体的各项操作都可以转化为对体元的操作。体元是一种非常规则的形体（立方体），因此可大大地简化算法。其次，对物体上各体元的操作可以并行处理，这就为实时实体造型和物体的各种实时分析计算以及显示开辟了道路。

采用八叉树表示物体的最大缺点是它占用存储很多。这是因为每一体元都是立方体，且体元各表面分别与三个坐标平面平行。只有当所表示的物体具有相似的形状和位置时，才会获得简洁的八叉树表示。在一般情况下，一个普通物体相应的八叉树可能多达数千个结点。即使像圆柱、球这样规则的物体，如用大大小小的立方体来逼近，相应八叉树上体元的数目也是相当可观的。

事实上，由于八叉树中物体由一系列的体元表示，因此对物43在每一个八叉树结点中，除去一个描述该结点性质的域外，还需存储它指向父结点及八个子结点地址的指针。定义物体的八叉树所需的众多的结点连同描述每个结点的10个存储域，使得物体的八叉树表示在空间花费上十分昂贵。实际上，八叉树表示以存储空间换取了算法的时间效率。

如果每次将空间分成二等分而不是八等分，这种表示方法类似于八叉树表示法，称为BSP（BinarySpacePartitioning）树表示法。BSP树表示法每次将一个物体用任一位置和任一方向的平面分为二部分。在八叉树中，每次将物体用平行于笛卡尔坐标平面的三个两两垂直的平面分割。

在每一个八叉树结点中，除去一个描述该结点性质的域外，44（2）由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。doublex_min=-1.多边形重叠性检验用到了“最小最大试验法”，这种方法也被称为“排斥试验”。3长方体的顶点、边和面对于那些发散的Zk序列的点，根据发散速度的不同，按照给定的规则着上不同颜色的色调，就能显示M集周围的图像。不发散时，与前面相反，什么也不描画，这样一来就可描画出周围有条纹话样的黑色分形集合。环是有序、有向边（直线段或曲线段）组成的面的封闭边界。设逆时针旋转时角度为正，发生器的初始角度为0，图中已标明发生器各段的位置和角度。众所周知，各类消隐算法的核心部分是排序，即将待显示的物体上的点、线、面按离观察点的远近排定次序，离观察点近的元素遮挡较远的元素。MoveTo(LPX,LPY);一般说，二维空间中的一个分数维曲线的维数介于1和2之间；综合运用并、交、差运算，可以完成复杂平面图形的构形。Julia集合可分为Zc为实数、Zc为复数、三次函数和发散区域几种情况。在M集的图像生成中，如果将上述速度比拟为M集的静电场的值，则生成的M集图案就更加壮观，有如一幅山顶湖泊的自然风景画。在一般情况下，一个普通物体相应的八叉树可能多达数千个结点。5,x_max=1.a/=cos(atan(c/a));//a为总节数floatcx,cy,x,y,xx,yy,dx,dy,z,L=4.y[k]=2*x[k-1]*y[k-1]+yc;//虚部环中的边不能相交，相邻两条边共享一个端点。对使用空间细分法而言，BSP树提供了一种更有效的分割，因为可将分割平面的位置和方向按适合于物体的空间属性来确定。与八叉树相比，可以减少树的表示深度，这样减少搜索树的时间。

布尔运算的概念在几何造型中，布尔运算主要用于二维实体和三维实体的复杂造型。三维实体的布尔运算比较复杂，下面仅讨论二维多边形实体的布尔运算。

6.3布尔运算（2）由于形体的边界几何元素（点、边、面）是隐含地表示在CS45多边形的布尔运算指的是；在两个多边形之间进行并、交、差的运算。见图6.10所示。

图6.10多边形的布尔运算

设有两个多边形A和B，它们之间进行布尔运算的结果如下：

多边形的布尔运算指的是；在两个多边形之间进行并、交、46

(a)表示两个多边形A和B并的结果，记作A∩B。其结果中是既有A的部分也有B的部分。

(b)表示A和B进行交运算的结果，记作A∪B。其结果是只有A和B的共同部分。

(c)表示A和B进行差运算的结果，记作A—B。其结果是在A中去掉了B的部分。

任何一个多边形是由顶点和边组成的。我们把描述多边形的数据结构组织成两张数据表：顶点表和边表。

在进行布尔运算的过程中，为了算法处理的方便，我们可以把多边形的边表改为环表。环表是由组成多边形的顶点按一定的顺序连接而成。

多边形的描述(a)表示两个多边形A和B并的结果，记作A∩B。其47因为一个平面多边形可以只有一个外轮廓，如图6.11中的(左)；也可以既有一个外轮廓，又有一个或多个内轮廓(即孔)，如图6.11中的(右)。我们称由外轮廓顶点组成的环为外环；由内轮廓顶点组成的环为内环。并且规定：外环由外轮廓顶点按逆时针方向组成；内环由内轮廓顶点按顺时针方向组成。

所以在图6.11中，外环为

1—2—3—4—5—6—1；内环为

7—8—9—10—7。

12345612345678910图6.11多边形的环表

因为一个平面多边形可以只有一个外轮廓，如图6.11中48在环表中，每相邻两个顶点组成一条有向线段，它的方向与环的方向相同，这些有向线段即是多边形的边。

两个多边形能进行布尔运算的前提是，这两个多边形必须有相互重叠的部分。这可以应用多边形的重叠性检验来判断。

多边形重叠性检验用到了“最小最大试验法”，这种方法也被称为“排斥试验”。在二维图形中，该方法可以用来快速判断两个多边形是否会有可能相互重叠，迅速排除掉不可能相互重叠的情况，从而减少计算工作量，加快图形处理的速度

多边形重叠性检验在环表中，每相邻两个顶点组成一条有向线段，它的方向与49①多边形的最小包含矩形所谓多边形的最小包含矩形，是指在平面上能包含该多边形的最小的矩形。该矩形的四条边分别平行于两坐标轴，所以矩形的位置和大小可以用Xmax，Xmin，Ymax，Ymin四个参数来定义，而这四个参数就是多边形顶点坐标中的极值。见图6.12所示。

YXymaxyminxminxmax图6.12最小包含矩形

①多边形的最小包含矩形YXymaxyminxminxmax图50②重叠性检验为了快速排除两个多边形互不重叠的情况，可以利用多边形的最小包含矩形。见图6.13所示。

(a)(b)(c)图6.13重叠性检验②重叠性检验(a)(b)(c)图6.13重叠性检验51如果两个多边形的最小包含矩形不发生相互重叠，则这两个多边形必定不会相互重叠，见图6.13中的(a)。此时，必定有如下四个不等式中的一个得到满足。即：

Xamax≤Xbmin；

Xamin≥Xbmax；

Yamax≤Ybmin；

Yamin

≥Ybmax。

只有当两个最小包含矩形发生相互重叠的情况下，即上述四个不等式均得不到满足时，这两个小包含矩形所包含的多边形才有可能互相重叠。这里说的也仅仅是有可能，也就是还会有重叠的可能，见图6.13中的(b)。此时为了进一步地确定多边形是否会确实相互重叠，则还要进行更深一步的逐边判断。

如果两个多边形的最小包含矩形不发生相互重叠，则这两个52当两个多边形相互重叠时，分别表示两多边形的两个环相交，其交点将相交的两条有向线段分为两部分：环内部分和环外部分，分别表示处于另一个环的内部或外部。交点分为出点和入点两种：当一个环的有向线段经过交点进入另一环，则该交点称为入点；反之，如果是走出另一环，而该交点称为出点。对于同一个交点，相对于不同的环来说，其出点和入点是不同的。

当两个环由于相交而产生新的交点后，因新交点的加入而使得原来的环扩充了。见图6.14所示。

111234567891012AB图6.14中间扩充环的形成

布尔运算的规则当两个多边形相互重叠时，分别表示两多边形的两个环相交53图中，多边形A的环由原来的1-2-3-4-1，扩充为：1-9(入点)-2-11(出点)-3-4-1；多边形B的环由原来的5-6-7-8-5，扩充为：5-6-7-12(入点)-8-10(出点)-5。

从图中可以对照看出：点9和点10，点11和点12，原本分别为同一个交点，这里由于分别处在两个环上，为了说明的方便，所以分开标识。

在进行布尔运算时，搜索路径应从交点处开始。其运算的规则如下：

图中，多边形A的环由原来的1-2-3-4-1，扩充为54①并运算顺着环的方向搜索，当遇到的交点为入点时，则从该点在另一环上的对应点转入另一环，而沿另一环的方向搜索；当遇到的交点为出点时，则继续顺本环进行。见图6.15所示。

191056712113419(入)211(出)3410(出)56712(入)8图6.15并运算规则

①并运算191056712113419(入)211(出)3455②交运算交运算的规则刚好和并运算的规则相反。当遇到的交点为出点时，则从该点在另一环上的对应点转入另一环，顺另一环的方向进行；如遇到的交点为入点时，则仍沿本环的方向进行。见图6.16所示。

19(入)211(出)3410(出)56712(入)889,10211,12图6.16交运算规则

②交运算19(入)211(出)3410(出)56712(入)56③差运算在进行差运算的时候，首先要将差环的方向倒转过来，然后按照同并运算相同的规则进行处理。见图6.17所示。

419,10811,12319(入)211(出)3410(出)56712(入)8图6.17差运算规则

综合运用并、交、差运算，可以完成复杂平面图形的构形。

③差运算419,10811,12319(入)211(出)3457一个面可以无内环，但必须有一个且只有一个外环。环中的边不能相交，相邻两条边共享一个端点。线框模型采用顶点表和边表两个表的数据结构来表示三维物体，顶点表记录各顶点的坐标值，边表记录每条边所连接的两个顶点。0,RADIAN=0.for(k=1;k<=KL;k++)//计算复数数列VonKoch曲线的具体生成过程中，由源图形和发生器就可以决定曲线的形态。dc.l

1≤n≤2颜色为3号（青色）综合运用并、交、差运算，可以完成复杂平面图形的构形。其中，Z和C都是复数，由各自的实部和虚部组成。由于路径B的表达很简单，又由于集合A的表示可用A的边界的边来表示，所以平移扫描的表示可减为A集合的二维表示。while(k>col[i][0]&&k<=KL)源图形通常是一条直线或一个多边形，在曲线的生成过程中，其变形的规律是将源图形中的直线段用一段折线来代替，此折线称为发生器。voidturn(doubleangle,double&ANGLE)//当前角度旋转形体的CSG表示可看成是一棵有序的二叉树，称为CSG树。for(i=0;i<n_gene;i++)由于在数据结构中缺少边与面、面与体之间关系的信息，即所谓拓扑信息，因此不能构成实体，无法识别面与体，更谈不上区别体内与体外。1．线框模型（WireframeModel）只有几何信息没有拓扑信息是不能构成图形的。5,y_max=1.if(s<4.根据以上我们对多边形布尔运算的分析，可以归纳出简要的算法步骤如下：①建立参加布尔运算多边形的顶点表和环表；②应用多边形重叠性检验，判别两多边形的关系；③求出两多边形边的有效交点，扩充顶点表和环表，并分别标识交点为出点或入点；④以一个交点为出发点，按布尔运算的规则进行搜索；⑤按照搜索经过的路径，在顶点之间连线输出。也可以在搜索的过程中记录下路径，待搜索结束后，按照记录下的路径顶点统一绘线输出。

一个面可以无内环，但必须有一个且只有一个外环。586.4分形几何造型

一直以来，欧氏几何是人们认识自然物体形状的有力工具。欧氏几何的主要描述工具是直线、平滑的曲线、平面及边界整齐的平滑曲面，这些工具在描述一些抽象图形或人造物体的形态时是非常有力的，但对一些复杂的自然景象形态就显得无能为力了，诸如山、树、草、火、云、浪等，如果用直线、圆弧、样条曲线等去建模生成，则其逼真程度就非常差。这是由于从欧氏几何来看，它们是极端无规则的。

6.4分形几何造型一直以来，欧氏几何是人们认识59分形和分形几何造型的概念

为了解决复杂图形生成，分维几何（Fractal）造型应运而生。另外，在科学研究中，对许多非规则对象建模分析，如：星系分布、凝聚生长、渗流、金融市场的价格浮动等复杂对象，都需要一种新的几何学来描述。

对复杂现象的探索早在图形学产生以前就已经开始，可以回溯到1904年。当时HeigeVonKoch研究了一种他称为雪花的图形，他将一个等边三角形的三边都三等分，在中间的那一段上再凸起一个小正三角形，这样一直下去，理论上可证明这种不断构造成的雪花周长是无穷，但其面积却是有限的。分形和分形几何造型的概念为了解决复杂图形生成，分维60这和正统的数学直观是不符的，周长和面积都无法刻划出这种雪花的特点，欧氏几何对这种雪花的描述无能为力。

20世纪60年代开始，曼德布罗特(重新研究了这个问题，并将雪花与自然界的海岸线、山、树等自然景象联系起来，找出了其中的共性。

1973年，曼德布罗特在法兰西学院讲课时，首次提出了分形和分形几何的概念。Fractal（分形或分数维）这个词，是曼德布罗特创造出来的，其原意具有不规则、支离破碎等意义。分形几何是一门以非规则几何形状为研究对象的几何学。

这和正统的数学直观是不符的，周长和面积都无法刻划出这61曼德布罗特曾举了一个海岸线的例子来说明他的理论。假设我们要测量不列颠的海岸线长度，我们可以用一个1000m的尺子，一尺一尺地向前量，同时数出有多少个1000m，这样得到一个长度为L1。然而这样测量会漏掉许多小于1000m的小湾，因而结果不准确。如果尺子缩到1m，那么我们会得到一个新的结果L2，显然L2＞L1。一般来说，如果用长度为r的尺子来量，将会得到一个与r有关的数值L（r）。与Koch的雪花一样r→0，L（r）→∝。也就是说，不列颠的海岸线长度是不确定的，它与测量用的尺子长度有关。

曼德布罗特曾举了一个海岸线的例子来说明他的理论。假设62曼德布罗特注意到Koch雪花与海岸线的共同特点：它们都有细节的无穷回归，测量尺度的减少都会得到更多的细节。换句话说，就是将其中一部分放大会得到与原来部分基本一样的形态，这就是曼德布罗特发现的复杂现象的自相似性。为了定量地刻划这种自相似性，他引入了分数维（Fractal）概念，这是与欧氏几何中整数维相对应的。

分形维数和分形几何造型曼德布罗特注意到Koch雪花与海岸线的共同特点：它们63设N为每一步细分的数目，S为细分时的放大（缩小）倍数，则分数维D定义为：

图6.18用分形几何造型产生雪花

如图6.18所示，以Koch雪花为例，它的每一步细分线段的个数为4，而细分时的放大倍数为1／3，则雪花边线的分数维D=log4/log3=1.2619。如果我们按欧氏几何的方法，将一线段四等分，则N=4，S=1/4，D=1；如将一正方形16等分，此时N=16，线段的放大倍数S=1/4，则D=2。

设N为每一步细分的数目，S为细分时的放大（缩小）倍数64一般说，二维空间中的一个分数维曲线的维数介于1和2之间；三维空间中的一个分数维曲线的维数在1和3之间，而三维空间中的一个分数维曲面的维数在2和3之间。分数维的引入，为研究复杂形体提供了全新的角度，使人们从无序中重新发现了有序，许多学科像物理、经济、气象等都将分数维几何学作为解决难题的新工具。计算机图形学也从中受到启发，并形成了以模拟自然界复杂景象、物体为目标的分形几何造型。分形几何造型是利用分形几何学的自相似性，采用各种模拟真实图形的模型，使整个生成的景象呈现出细节的无穷回归性质的方法。

一般说，二维空间中的一个分数维曲线的维数介于1和2之65

(1)从整体上看，分形几何图形是处处不规则的。例如，海岸线和山川形状，从远距离观察，其形状是极不规则的。

(2)在不同尺度上，图形的规则性又是相同的。上述的海岸线和山川形状，从近距离观察，其局部形状又和整体形态相似，它们从整体到局部，都是自相似的。当然，也有一些分形几何图形，它们并不完全是自相似的。其中一些是用来描述一般随机现象的，还有一些是用来描述混沌和非线性系统的。

分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。与传统的几何学相比,分形几何有这样的特点：

(1)从整体上看，分形几何图形是处处不规则的。例如，海66总之，分形几何与传统的几何完全不同，传统的欧几里德几何的对象具有一定的特征长度和标度，其所描述的是人类生产的工业产品的规则形状，分形几何则是无特征长度与标度的，它擅长描述自然界普遍存在的景物，分形几何的图形具有自相似性和递归性，它比较适于用计算机迭代生成。

典型分形曲线集总之，分形几何与传统的几何完全不同，传统的欧几里德几67

1904年，瑞典数学家VonKoch发现了一种曲线，这种曲线有一个奇怪的特性：它处处连续，但处处不光滑、不可微。因而在当时认为是一种与常规不同的“病态”曲线，即

VonKoch曲线。如果在一个正三角形上按生成规则生成，则曲线形状像一朵雪花，故又称为Koch雪花曲线。VonKoch曲线是一种典型的分形曲线，在分形理论的建立过程中，VonKoch曲线具有重要地位。

1.VonKoch曲线1904年，瑞典数学家VonKoch发现了68voidMSB(cxmin,cxmax,cymin,cymax,nmax)fractal(gene,gene[i][1]*leng/a,a,n_gene,每作一次迭代，新的复数就离开前一复数一段距离，就好象一个点在复平面上跳舞一样。Koch曲线是典型的分形曲线，它具有自相似性。xn+1＝xn2-yn2+Cx（实部）对于那些发散的Zk序列的点，根据发散速度的不同，按照给定的规则着上不同颜色的色调，就能显示M集周围的图像。这里，正则集合运算是在传统点集的集合运算基础上附加一定的限制而定义的。材料特征：规定了材料类型、强度、延展度、热导度等特征。E1E2E3E4在M集的图像生成中，如果将上述速度比拟为M集的静电场的值，则生成的M集图案就更加壮观，有如一幅山顶湖泊的自然风景画。0,0,6,LPX,LPY,ANGLE);VonKoch曲线3长方体的顶点、边和面一个集合在空间运动就能“扫”成一实体。其中，Z和C都是复数，由各自的实部和虚部组成。计算机图形学也从中受到启发，并形成了以模拟自然界复杂景象、物体为目标的分形几何造型。非终端结点或是正则的集合运算，一般有交、并、差运算；20Koch曲线发生器此外擅长于构造复杂的曲面物体，如模具、汽车、飞机等表面。

VonKoch的生成方法如下：首先，从一个简单的图形出发(这个图形称为源图形)，然后按照一定的生成规律不断进行变形，最后可以得到VonKoch曲线。

源图形通常是一条直线或一个多边形，在曲线的生成过程中，其变形的规律是将源图形中的直线段用一段折线来代替，此折线称为发生器。图6.19(左)所示为发生器，图6.19(右)为通过5次递归(N=5)所生成的VonKoch曲线。

图6.19VonKoch曲线,(a)为发生器,(b)为N=5的Koch曲线）

(a)(b)voidMSB(cxmin,cxmax,cymin,69

VonKoch曲线的具体生成过程中，由源图形和发生器就可以决定曲线的形态。源图形为一直线段，生成的曲线如图中所示，可用以绘制海岸线或云彩的边界。如果源图形为一等边三角形，生成的曲线形状与雪花类似，称为Koch雪花曲线。

由Koch曲线的生成过程知道：在极限的情形下，每小段折线的长度趋于无穷小，因而此曲线是一条无处不连续但处处不可微的曲线，其上任一点处，均无确定的切线，曲线的长度趋于无穷。对于闭合多边形的Koch曲线，可以证明它的面积为源多边形的8／5。

VonKoch曲线的具体生成过程中，由源图70

Koch曲线的维数，可用相似维数来定义。由生成曲线的过程可知，从任何一步到下一步，其周长增加为4／3，图6.18（左）中显而易见，整体由四个线段组成，即N=4，a=3，其维数

D=log4／log3=1.2618

Koch曲线是典型的分形曲线，它具有自相似性。其中发生器是由n段直线和确定的二个端点组成。自相似的不变集的曲线段，是通过反复用一发生器的相似图形，来取代每一直线段的递归调用过程而建立起来的。

Koch曲线可以派生为各种形态，用不同的发生器，就可以得到不同类型的结构形态。

Koch曲线的维数，可用相似维数来定义。由生成曲线71下面介绍如何用计算机绘制Koch曲线，算法的基本设计思想是：根据曲线的生成原理，由于它是通过不断细分递归生成的，因此，采用递归调用方法，由发生器产生Koch曲线。算法的具体步骤是：

（1）给出递归深度n；（2）计算发生器递归n次后的最小线元长度d=L／mn,式中L为曲线总长，m为Koch曲线发生器的等分数；（3）确定Koch曲线的起点；（4）执行递归子程序，对发生器的各部分进行递归，并绘出曲线。

下面介绍如何用计算机绘制Koch曲线，算法的基本设计72以维数D=1.2618的Koch曲线为例，曲线的发生器由三等分长度的四个部分组成，中间两段线段的角度为60°，如图6.20所示。

(xn-1,yn-1)(xn,yn)θ图6.20Koch曲线发生器

设逆时针旋转时角度为正，发生器的初始角度为0，图中已标明发生器各段的位置和角度。每一段小的线元，其坐标可由下式确定

(xs,ys)600-1200600以维数D=1.2618的Koch曲线为例，曲线的73

xn=xn-1十d·cosθ

yn=yn-1十d·sinθ其中，θ为小的线元的当前角度。

由于Koch曲线的发生器由图中所示的四部分线段组成，因此，在计算机生成Koch曲线的递归调用中，要分别对这四部分进行递归。

voidturn(doubleangle,double&ANGLE)//当前角度旋转{ANGLE+=angle;ANGLE=ANGLE-(int)ANGLE+(int)ANGLE%360;}以下是生成Koch曲线的VC程序：xn=xn-1十d·cosθ由74voidKoch(doubleleng,intn,intN,double&LPX,double&LPY,double&ANGLE){CGraphDCg(this);doublex,y,RADIAN=ANGLE*3.1415926/180;//角度化弧度

if(n>=N){x=LPX+leng*cos(RADIAN);y=LPY-leng*sin(RADIAN);g.MoveTo(LPX,LPY);g.LineTo(x,y);LPX=x;LPY=y;}else{Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(60.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(-120.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(60.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);}}voidKoch(doubleleng,intn,75voidOnDrawKoch(){doubleLPX=120.0,LPY=240.0;//初始坐标

doubleANGLE=0.0;Koch(400.0,0,6,LPX,LPY,ANGLE);}voidOnDrawKoch()76分形图形中最著名的是Mandelbrot集，这是分形的创始者Mandelbrot在非线性分形领域中作出的杰出贡献。这是通过在复平面中G（Z）=Z2+C的反复迭代而得到的点的序列，其中C和Z都是复数。若Z的初始值取为零，改变C值，再用计算机对每一个点按一定规则着色，即可得到Mandelbrot分形集的计算机图像。

在复平面中，Mandelbrot分形集是通过下述迭代式产生的：

Zn+1

＝Zn2＋C

2.Mandelbrot分形集分形图形中最著名的是Mandelbrot集，这是分形77其中，Z和C都是复数，由各自的实部和虚部组成。其实部和虚部分别为：

xn+1

＝xn2-yn2+Cx

（实部）

yn+1

＝2*xn

*yn+cy

（虚部〕

在迭代中，令初始值Z0=0，也就是Z0=0＋0·i，C≠0，对上述迭代式反复进行迭代，得到的数集，称为Mandellrot集，简称M集。

在迭代过程中，Z的初值永远定为0，用不同的C值反复进行迭代，由此产生的Zk序列有两种情况：

（1）Zk序列自由地朝着无穷大的方向扩散，即发散；（2）Zk序列被限制在复平面的某一区域内，即收敛。

其中，Z和C都是复数，由各自的实部和虚部组成。其实部和虚部分78如果建立一套判断收敛与发散的判断准则，对于那些收敛的Zk序列的点，设置某种颜色的色调，就可以显示M集的计算机图像。对于那些发散的Zk序列的点，根据发散速度的不同，按照给定的规则着上不同颜色的色调，就能显示M集周围的图像。

在迭代计算中，通常是把前一个Z值的输出作为下一个Z值的输入代入Zn+1

←Zn2＋C反复运算，得到一连串的复数。每作一次迭代，新的复数就离开前一复数一段距离，就好象一个点在复平面上跳舞一样。

在M集的计算中，距离是一个重要的概念。在一系列通过迭代计算得出的复数，有的达到无穷大，有的则永远被限制在平面上的某个区域内。如果建立一套判断收敛与发散的判断准则，对于那些收敛的79在复平面的某一部位上，令C作有规律的变化，对不同的C值进行迭代，如果计算结果达到无穷大，则C被着成白色，否则，着成黑色，这样就能显示出M集的形状。若达到无穷大的点，根据其发散的速度的快慢，用不同的色调来表示，就形成一幅奇妙无穷的M集彩色图像。

M集图像生成算法的核心过程如下：①n←0②当n＜100，且|Z|＜2时③Z←Z2＋C④n←n＋1

⑤标示当前点的颜色（根据n的大小）在复平面的某一部位上，令C作有规律的变化，对不同的C80

n从0开始，每迭代一次，n就增加1，只要n＜100，Z的绝对值|Z|＜2，则上述循环就不断地重复进行下去，如果上述两个条件之一得到满足，就退出循环，并根据n按一定的规律着色。根据敛散速度着色是最简单的方法。

z的绝对值也可以取|Z|<100，