《计算机图形学3.ppt》由会员分享，可在线阅读，更多相关《计算机图形学3.ppt（84页珍藏版）》请在三一办公上搜索。
1、计算机图形学Computer Graphics,第三章.几何造型,Geometric Modeling,3.1 几何模型的概念,1.模型:表示对象的数据的组合及数据间的关系，由数据和程序过程混合组 成，并按一定的数据结构存储在数据库中。2.几何模型：描述对象的形状、大小、位置等几何和拓扑信息的组合。3.几何造型：通过点、线、面和立体等几何元素的定义、几何变换、集合运算构建实际存在或想象中的形体模型，是确定物体形状和其它几何特征方法的总称。它包括三个方面：1)表示（Representation)：对实际存在的形体进行数学描述。2)设计（Design)：创建一个新的形体，调整变量满足既定目标。3)
2、图形表示（Rendering):直观形象的表示出所建模型的图形。,3.2 表示形体的坐标系,世界坐标系（WCS：World Coordinate System）用户坐标系(UCS：User Coordinate System)观察坐标系（VCS：Viewing Coordinate System）规格化的设备坐标系（NDCS：Normalized Device Coordinate System）设备坐标系（DCS：Device Coordinate System）,坐标变换,3.3 几何元素的定义,1）点,几何造型中的最基本元素。自由曲线、曲面及其它几何形体均可用有序点集表示。用计算机存储、
3、处理、输出形体的实质就是对点集及其连接关系的处理。,三维直角坐标系中的点用x,y,z或x(t),y(t),z(t)表示,齐次坐标用n+1维表示，即x,y,z,h)或x,y,h。,二维用x,y或x(t),y(t)表示。,点的表示：,2）边,两个邻面（正则形体）或多个邻面（非正则形体）的交线。,直线边由其端点（起点和终点）定界；,曲线边由一系列型值点或控制点表示，也可用显式、隐式方程表示。,2）边,3.3 几何元素的定义,3）面,形体上一个有限、非零的区域，由一个外环和若干个内环界定其范围。面有方向性，一般用其外法矢方向作为该面的正向。,3.3 几何元素的定义,4）环,环是有序、有向边组成的面的封
4、闭边界。有内外之分，外环确定面的最大外边界，其边按逆时针方向排序。内环确定面中孔或凸台的边界，其边按顺时针方向排序。,3.3 几何元素的定义,5）体,由封闭表面围成的空间，也是三维欧式空间中非空、有界的封闭子集，其边界是有限面的并集。,非正则形体,正则形体,3.3 几何元素的定义,6）体素,可以用有限个尺寸参数定位和定形的体。常有三种定义形式：,（1）从实际形体中选择出来的一组单元实体，如长方体、圆柱体、球体等。,（2）由参数定义的一条（或一组）截面轮廓线沿一条（或一组）空间参数曲线作扫描运动而产生的形体。,3.3 几何元素的定义,形体（Object),外壳(Sell),面(Face),环(L
5、oop),边(Edge),点(Vertex),v1,v2,v3,v4,v5,v6,v7,v8,e1,e2,e3,e10,e11,e12,.,Cube,f1,f2,f3,f4,f5,f6,e4,在计算机中定义几何形体将几何元素按六个层次结构表示。,3.4 定义形体的层次结构,3.5.形体的三种模型,1线框模型 wire frame model2表面模型 surface model3实体模型 solid model,1）曲面模型和实体模型均能以线框、消隐、小平面着色、平滑明暗和仿真等类型中的任何一种方式显示。2）线框模型则只能以线框类型方式显示。3）不同的三维模型在需要的时候可以转化。,关于三维模
6、型与模型的显示类型,三维模型从模型本身的内部数据来描述形体，是形体的本质属性。,模型的显示类型形体的外在表现形式。,实体模型 曲面模型,曲面模型 线框模型,*转化过程不能逆转。曲面模型不能转化为实体模型，因为它所包含的信息比实体模型少。线框模型也不能转化为曲面模型，因为它包含的信息比曲面模型少。,3.6 常用的几何造型方法,线框模型、表面模型和实体模型是一种广义的概念。从用户角度看，形体表示以特征表示和构造的实体几何表示（CSG）较为方便；从计算机对形体的存储管理和操作运算角度看，以边界表示（BRep）最为实用。为了适合某些特定的应用要求，形体还有一些辅助表示方式，如单元分解表示和扫描表示。比
7、较常用的造型方法：,1.边界表示法（Boundary Representation Scheme）,通过描述形体的边界来表示一个形体，将形体的边界分成有限个“面”（faces）或“片”（patches），并使每个“面”或“片”由一组边和顶点来确定边界。,2.扫描表示法（Sweep）,扫描表示法是将一个面域沿某一轨迹移动，以形成特定的几何形体，它是生成形体（或零件）的基本方法。,3.构造实体几何法（CSG）Constructive Solid Geometry,构造实体几何法将简单的形体经过正则集合运算构成复杂形体。一个复杂形体的CSG表示可以看成是一颗有序的二叉树。树的根结点：整个复杂形体，终
8、端结点（叶结点）：体素、形体 运动的变换参数。非终端结点（中间结点）：正则集合运算，或形体的几何变换。,3）通过对简单实体进行交（INTERSECT）、差（SUBTRACT）、并（UNION）等布尔运算和切割（SLICE），生成复杂三维实体。,1.三维实体造型的基本方法,1）对简单三维实体可直接创建，如长方体、圆柱、圆球、圆锥等。,2）用户先创建二维封闭区域（REGION），再通过拉伸（EXTRUDE）和旋转（REVOLVE）等操作生成三维实体。,3.7 三维实体造型案例,熟练掌握三维实体造型的基本方法及用户坐标系（UCS）等命令是构造三维实体模型的关键，,2.坐标系（UCS）,a)WCS坐标
9、(二维空间),c)UCS坐标 绕x轴旋转90,1）在绘制二维图形时，用户只在XOY平面上绘制，Z值为0。X、Y箭头表示当前坐标系统的X轴、Y轴的正方向，Z轴的正向则遵守右手定则。,3.7 三维实体造型案例,a),b),c),要在空间的其他平面上绘制图形时，设计者要自己设立用户坐标系。UCS命令用于在3D空间建立用户坐标系，允许设计者自己设置新原点和在三维空间内旋转实体的XY参考平面。,3.7 三维实体造型案例,AutoCAD的3D 命令沿常见几何体（长方体、圆锥体、球体、圆环体、楔体和棱锥体）的外表面创建三维多边形网格。用 3D 命令构造多边形网格对象时，最后得到的对象表面可以隐藏、着色和渲染
10、。,3.常见几何形体3D造型,4.将二维图形拉伸为实体,在AutoCAD中，使用Draw(绘图)/Solids(实体)/Extrude(拉伸)命令，可以将2D对象沿z轴或某个方向拉伸成实体。拉伸对象可以是任何2D封闭多段线（3顶点数500)、圆、椭圆、封闭样条曲线和面域。,1)沿Z轴方向拉伸对象,默认情况下，可以沿Z轴方向拉伸对象。指定拉伸的高度和倾斜角度。高度值和角度值可为正或负。拉伸的绝对值不大于90度，默认值为0度。如果倾斜角度或拉伸高度较大，将无法进行拉伸。,2）通过指定路径拉伸对象,1）拉伸路径可以是开放的，也可以是封闭的，并且路径不能与被拉伸对象共面。如果路径中包含曲线，则该曲线应
11、不带尖角。,2）如果路径是开放的，则路径的起点应与断面在同一个平面内。,3）如果路径是一条样条曲线，则样条的一个端点应与拉伸对象所在平面垂直。,4）如果路径中包含相连但不相切的段，则在连接点处，拉伸会沿段的角平分面斜接此连接点。,5）如果沿路径拉伸多个对象，则Extrude(拉伸)命令会确保它们最后终止于同一平面。,5.将二维图形旋转成实体,在AutoCAD中，还可以使用Draw(绘图)/Solids(实体)/Revolve(旋转）命令，将2D对象绕某一轴旋转生成实体。用于旋转的2D对象可以是封闭多段线、多边形、圆、椭圆、封闭样条曲线、圆环以及封闭区域。包含在块中的对象、有交叉或自干涉的多段线
12、不能被旋转，并且每次只能旋转一个对象。,6.布尔运算,在AutoCAD中，用户可以对三维基本实体进行并集、差集、交集、干涉4种布尔运算来创建复杂实体。,求并运算：用实体或面域之和产生一个实体。工具条：Union,求差运算：用实体或面域之差产生一个实体。工具条：Subtract,求交运算：用实体或面域的相交部分产生一个实体。工具条：Intersect,选择Modify(修改)/Solids Editing(实体编辑)/Union(并集)命令，可以组合多个实体生成一个新实体。,6.布尔运算,选择Modify/Solids Editing/Subtract(差集)命令，可以从一些实体中去掉另一些实体
13、，从而得到一个新的实体。,6.布尔运算,应用实例一：,建立如图所示机件的三维模型,绘制矩形,绘制和陈列复制圆,拉伸图形,移动并旋转坐标系,对实体求并集和差集,绘制圆柱体,绘制圆柱体,绘制长方体,剖切圆柱体,绘制圆柱体,绘制长方体,对实体求差集,消隐,未消隐,3.2.6 常用的几何造型方法,线框模型、表面模型和实体模型是一种广义的概念，并不反映形体在计算机内部，或对最终用户而言所用的具体表示方式。从用户角度看，形体表示以特征表示和构造实体几何表示CSG较为方便；从计算机对形体的存储管理和操作运算角度看，以边界表示B-rep最为实用；根据形体的形成特点还有一些方便实用的表示方法：单元分解表示法；扫
14、描表示法；旋转表示法；网格表示法；,1.基本体素表示法,基本体素表示法用一组参数来定义一簇形状类似但大小不同的物体。这种方法通过对已有的形体作线性变换来产生形体，是最直接的方法。适用于表示工业上已定型的标准件.,2.空间位置枚举法,空间位置枚举法将空间分割成均匀的立方体网格，每个立方体大小相等，方向相同，互不重叠，可用其中心坐标或某个角坐标来确定。根据实体所占据网格的位置来定义实体的形状和大小，相应的数据结构为三维数组，每一数组元素对应一空间位置，若此位置为实体所占据，则数组元素值相应地为1，否则为零。,3.单元分解法,单元分解法克服了空间位置枚举法冗余度大的缺点，它允许将实体表示成一些形状相
15、同但大小不同的基本体积单元的组合，这些体积单元不一定是立方体，也不一定固定在某些确定的空间位置上，例如，可将物体内部的相邻区域合并成较大的立方体以节省存贮量。任意两个基本体积单元要么完全分离，要么沿一条线或一个小面精确地在一个角点相连.,4.扫描表示法,扫描表示法是根据二维或三维形体沿某一曲线（通常为直线或圆弧）推移时的外轮廓的轨迹来定义形体。扫描表示法易于理解和执行，特别适用于生成工业上常用的柱面体和旋转体，它在实体造型系统中常用作简单的造型输入手段。扫描表示法需要两个分量：一个是被扫描的形体，称之为基体；另一个是形体运动的路径。基体可以是曲线、表面、立体；路径可以由解析表达式来定义。,5.
16、构造实体几何法（Constructive Solid Geometry）,构造实体几何法采用基本体素的并、交、差组合来表示实体，简称CSG法.通常用正则集合运算(构造正则形体的集合运算)来实现这种组合，其中可配合执行有关的几何变换。形体的CSG表示可看成是一棵有序的二又树，其终端结点或是体素，或是刚体运动的变换参数。非终端结点或是正则的集合运算，或是刚体的几何变换，这种运算或变换只对其紧接着的子结点(子形体)起作用。CSG树可定义为：,CSG树：=体素叶子CSG树正则集合运算结点CSG树CSG树刚体运动结点刚体运动变量,6.边界表示法 Boundary Representation,形体的边界
17、表示就是用面、环、边、点来定义形体的位置和形状。边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系拓扑信息，以便直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。直接建立边界模型是很繁琐的，在实践中常常采用CSG方法建立实体模型，显示时再转化为边界模型。,表示形体的点、边、面等几何元素是显式表示的，使得绘制B-Rep表示形体的速度较快，而且比较容易确定几何元素间的连接关系；对形体的B-Rep表示可有多种操作和运算。,数据结构复杂；需要大量的存储空间，维护内部数据结构的程序比较复杂；修改形体的操作比较难以实现；B-Rep表示并
18、不一定对应一个有效形体，即需要有专门的程序来保证B-ReP表示形体的有效性、正则性等。,边界表示法,B-Rep表示就需要对定义形休的面、环、边、点及其属性进行存取、直接查找、间接查找和逆向查找等操作。,边界表示法造型过程中，经常有下列操作，需要有一个较好的数据结构来支持。从一个点查找与该点相连的所有边；从一条边查找到该边的邻面及其邻接边；从一个面开始查找其上的外环和内环等。,7.八叉树表示法,八叉树表示法是四叉树表示法在三维空间的推广，也可以看成是空间位置枚举法和单元分解法的一种改进，提高和简化了物体之间的并、交、叉运算的手段，加快了物体真实感的显示速度和有限元网格剖分的速度。,在空间中定义一
19、个能够包含所表示形体的立方体，立方体的三条棱边分别与x,y,z轴平行，边长为2n。,若立方体内空间完全由所表示的形体所占据，则形体可用这个立方体予以表示，否则将立方体等分为八个小块，每块仍为一个小立方体，其边长为原立方体边长的1/2。将这八个小立方体依序编号为0，1，2，7.,若某一小立方体的体内空间被所表示的形体全部占据，则将此立方体标识为“FULL”；若它与所表示形体无交，则该立方体被标识为“EMPTY”；否则将它标识“PARTIAL”，并再等分成八个小块，如此分割下去。形体在计算机内可表示为一棵八叉树,为了描述八叉树的结点，给每个结点定义了如下的10个存储域：,其中：1是描述该结点性质的
20、域，也叫结点标志域，可以为FULL、EMPTY或PARTIAL；2是指向父节点的指针，若为根节点时，该域为0；310分别是指向八个子节点的指针，若为终端节点时，这些域的状态为空（EMPTY）。,8.混合造型法,为了扩大造型系统的覆盖域，常需要在不同的表示形式之间进行转换，CSG方法表示可以转化为R-rep表示和单元分解表示模型，边界模型能转化为分解模型。但以上转化过程不能逆转，即分解模型不能转化为其他模型，边界模型不能转化为CSG模型。,混合表示是指在CSG和R-rep双表示形式的基础上再扩充单元分解表示(如二维形体的四叉树表示、三维形体的八叉树表示)、扫描表示等。,近年来大型的CAD系统都采
21、用混合表示方法。在混合造型系统中，模型首先以CSG方法构造和存储，在显示时同时生成边界描述模型，在计算物理特性时则可能计算单元分解模型供临时使用。,CSG与B-Rep的混合模型表示法 用CSG作为高层次抽象的数据模型用B-Rep作为低层次的具体的表示形式。CSGG树的叶子结点除了存放传统的体素的参数定义，还存放该体素的B-Rep表示。CSG树的中间结点表示它的各子树的运算结果。用这样的混合模型对用户来说十分直观明了，可以直接支持基于特征的参数化造型功能，而对于形体加工分析所需要的边界、交线、表面显式表示等，又能够由低层的B-Rep直接提供。,9.特征表示法,特征表示是从应用层来定义形体，可以较
22、好的表达设计者的意图，为制造和检验产品提供技术依据和管理信息。从功能上可分为形状、精度、材料和技术特征。,1）形状特征：体素、孔、槽、键、凸台等。,2）精度特征：尺寸公差、形位公差、表面粗造度等。,3）材料特征：材料种类、硬度、热处理方法等。,4）技术特征：加工、安装、检验的技术要求。,形状特征单元是一个有形的几何实休，是一组可加工表面的集合，其BNF范式可定义为：,形状特征,形状持征单元：=体素I形状特征单元 集合运算 形状持征单元 I 体素集合运算体素I体素 集合运算 形状持征单元I形状特征单元集合运算 形状持征过度单元；体素：=长方体I圆柱体I球体I圆锥体I棱锥体I棱柱体I棱台体I圆环体
23、I楔形体I圆角体I；集合运算：=并I交I差I反；,形状持征过渡单元：=外圆角I内圆角I倒角。,（1）扫描特征,扫描特征是生成形体（或零件）的基本方法。其原理就是数学上的点动成线、线动成面、面动成体。空间的有界平面沿着一定的路径运动将生成实体特征。这是所有的三维造型系统中最重要的造型方法。利用扫描特征可以很容易地生成体素，如圆柱、环、球等。,截面沿其法向直线运动生成实体的造型方法。直线扫描的过程类似于用模具挤出具有各种各样截面的型材，线切割加工也能产生类似的形状，因而它是最基本、最常用的特征之一。,直线扫描(Extrude),回转扫描(Revolve),一个截面绕着草绘面内的一个中心线回转所形成
24、的特征。,路径扫描(sweep),一种在直线扫描和回转扫描基础上扩充的造型特征，它是由一个截面沿着一条指定路径扫描而成的。可以认为直线扫描和回转扫描都是路径扫描的特例。,3.3.欧拉运算,三维空间的正则形体，其点(V)、边(E)、面(F)的个数满足欧拉公式：,如果把三维封闭空间分割成C个多面体，其顶点、边、面和多面体个数满足公式：,图中的多面体是6个，故V-E+F-C9-20+18-6l,3.3.1 正则形体几何元素个数的欧拉公式,欧拉公式给出了点、边、面、体、洞、穴之间的平衡关系,V-E+F-C1,V-E+F2,对于n维空间，可以令N0，N1，Nn-1分别为该空间中0维，1维，(n-1)维的
25、几何元素，则此时的欧拉公式为：N0-N1+N2-=1-(-1)n 3维空间n=3,则 N0-N1+N2-=1-(-1)3=2,V形体的顶点数,E 棱边数,F 面数,H 形体表面上的空穴数,P 穿透形体的孔洞数,B 形体个数,有孔洞形体相应的欧拉公式:,V-E+F-H2(B-P),3.3.2欧拉操作,对点、边、环进行的7对(增、删对应)操作，用此操作构造实际形体 函数形式中用表示输入量，用表示输出量；并用A表示一个形体、V表示一个点、E表示一条边、L表示一个环。,1产生一条边及一个环(MEL).MEL(A、E、L2、L1、V1、V2),2删除一条边及一个环(KEL).KEL(A、E1、L2、L1
26、、V1、V2),3产生一个顶点及一条边(MVE).MVE(A、V1、E1、E2、X、Y、Z),在具有子环的父环中增加一条边,欧拉操作是通过对点、边、环的增、删操作来构造形体。,4删除一个点及一条边(KVE).KVE(A、V1、E1、E2、x、y、z),5 删除一个子环，产生一个父环(KCLMPL)。KCLMPL(A、L1、L2),6删除一个父环，产生一个子环(KPLMCL)KPLMCL(A、L1、L2),7产生条边及一个点(MEV)。MEV(A、E1、V1、V2、x、y、z),欧拉操作造型实例,A0是空体、是树根,A1是定义输入的长方体体素,将环L1分为两个环L1和L2，并产生A12体,对L1
27、进行拉伸产生体A13,对E1边进行倒角产生形体A14,对环L2进行拉伸产生A21体,对A13体的环L3进行拉伸产生体A31,3.4 求交算法,在几何造型中要大量地进行求交计算。例如，对形体进行集合运算必须先进行形体表面的求交计算，求剖面线、投影线等，也要进行求交计算。常用的三种基本几何元素是点、边、面。在这些几何元素之间进行求交运算的目的在于判别它们之间的重合、相交、相离等位置关系。在相交的情形求出交点、交线、交面。求交计算是造型系统最核心的一部分。它的准确性与效率直接影响造型系统的可靠性与实用性。按几何元素的维数来划分，求交算法可分为三类：1）点与点或边或面的求交计算，2）线与点或边或面的求
28、交计算，3）面与点或边或面的求交计算。实际只有六种：点点点边，点面边边，边面，面面。由于计算机内浮点数有误差，求交计算必须引进容差。当两个点的坐标值充分接近时，即被认为是重合的点，直观地说，点可看作半径为的球，边可看作半径为的园管，面可看作厚度2的薄板。一般取106，或更小的数。,3.4.1.点与各几何元素的求交计算,点与另一点相交。就是判断这两点是否重合只要判断两点之间的距离是否小于即可。,点与线段相交。就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：(1)直线段，(2)圆锥曲线段(主要是圆弧)，(3)参数曲线(主要是Bezier，B样条与NURBS曲线)。,点与面的求交
29、。设点坐标为P（x,y,z)，平面方程为ax+by+cz+do。则点到平面的距离为:,若d,则认为点在平面上。在造型系统中，通常使用平面上的有界区域（多边形）作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。判断平面一个点是否包含在同平面的一个多边形内有许多种算法，常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。,假设判断点为P0，多边形顶点按顺序排列为P1 P2 Pn。如图所示。令ViPi-P0，i1，2，n，Vn+1Vi。那么，P0在多边形内的充要条件是叉积(i1，2，n)的符导相同。叉积判断法仅适
30、用于凸多边形。当为凹多边形时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面的两种方法。,(1)叉积判断法,假设某平曲上有点P。和多边形P1 P2 P3 P4 P5，如图所示。将点P0分别与Pi相连，构成向量ViPi P0。假设角 如果，则点Po在多边形之外。如果，则点Po在多边形之内。ai可通过下列公式计算:,(2)夹角之和检验法,当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。做法是从判断点作一射线，再求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。当射线穿过多边形顶点时，必须特殊对待。正确的方法是，若共享顶点的两边在射线
31、的同一侧，则交点计数加2，否则加1。具体计数时，当一条边的两个端点y值都大于yo，即边处于射线上方时，计数加1，否则不加。,(3)交点计数检验法,3.5.集合运算,对于正则形体集合，可以定义正则集合算子。设(OP)是集合运算算子(如并，交、差)如果对于En中任意两个正则形体A、B，RAOPB 仍为En中的正则形体则称OP为正则集合算子。正则并、正则交、正则差，分别记为 U、。,求交操作用每一个形体分割另一个形体。每个形体用一个区域(region)表示。每个region 含有若干个shell，而每个shell含有若干个面。这里将要介绍的求交算法把形体A中每个shell的每个元素与另一形体B中每个
32、shell的每个元素进行求交。算法可以用类C语言描述如下：,(1)求交,在几何造型系统中，相当于一个子程序(或函数)，其输入是指向A，B的数据结构的指针，其输出是表示新形体R的数据结构的指针。注意，这里的R可能代表多个形体。正则运算保证了运算结果的有效性。例如，两个封闭的正则形体仍是同一欧氏空间的封闭正则形体。注意通常的集合运算不是正则运算。但是一个实用的造型系统仅有正则运算的功能是不够的。例如计算三维实体的断面图，需要用平面(E2中形体)与它作交运算。计算用CSG表示的实体的光线跟踪图形时，需要用直线(E1中形体)与实体作求交计算。就是对两个三维形体本身进行并、交、差运算时，也经常需要进行点
33、是否在线(E1元素）上、面(E2元素)上、体(E3元素)内判断、以及线面求交、面面求交等同维和不同维元素之间的运算。所以，20世纪80年代以后人门把注意力转向如何用统一的数据结构，用统一的算法来支持上述所有的不同维几何元素以及进行它们之间的操作运算。产生了一些非正则形体表示方法(如辐射边结构)，以及相应的形体操作算法。,正则形体通过集合运算的结果可以产生悬面、悬边、甚至悬点。通过对集合运算正则化(即每当出现悬面、悬边、悬点，就把它删除)，固然可以保证结果的正则性，但也有一些问题。例如，对于非正则形体，如扫描体的扫描轮廓线、扫描路径、形体中心轴等不能用统一的数据结构表示，形体集合运算产生的非正则
34、形体有时是有用的结果。例如两个形体的交是个悬面，说明它们接触在那个面，我们需要能返回那个面，而不是过早将它删除。这就导致人们考虑用统一的数据结构来表示非正则形体，用统一的算法来进行非正则形体之间的集合运算。1986年由weiler提出了非正则形体的一种表示法：辐射边结构(radial edge structure)及其集合运算的算法。辐射边结构使用统一的数据结构来表示形体的线框模型、表面模型和实体模型，既比传统的正则形体表示法提供了更强的形体定义功能，又使形体运算如集合运算、局部操作等能够用更简单的、统一的算法来实现。,3.5.1 三维几何元素的集合运算,2）基本操作,像辐射边结构这样用于表示
35、非正则形体的数据结构，其数据元素之间的关系是非常错综复杂的。这就要求有一组基本操作，把高层的运算与数据结构的实现细节分隔开来，以保证造型数据的致性。,这些基本操作叫做NMT(NonManifold Topology)非正则拓扑算子。包括l 7个基本操作用于非正则形体的构造与修改。这组持定的算子具有四个持点：(1)算子本身具有基本功能，(2)算子可以用于构造更复杂的算子或操作；(3)使造型过程显得方便简单；(4)算子与正则形体操作、欧拉操作是兼容的，也可以说是这些操作的推广。,通用算子：既可以处理正则形体也可以处理非正则形体。专门用于处理非正则形体的算子。专门用于处理正则形体的算子。,求交 一个
36、形体中的所有几何元素与另一个形体的所有几何元素进行求交。把交点与交线作为几何元素保存下来，并通过拓扑元素使这些几何元素被两个形体所共享。,A和B表示两个形体。在进行集合运算之前，必须先进行共面、共线、共点等判断。若发现二者有共享的几何元素，则把两形体中相应的拓扑元素合并为一。对两个形体的集合运算可分为三步操作：,归并 这个步骤将决定哪些元素作为结果保留，哪些元素被丢弃。是取是舍取决于集合运算的类型为并、交、差。,分类 把每个形体经求交后被适当分割的几何元素与另一形体进行分类。以决定这些元素是包含于(in)另一形体，还是在另一形体之外(out)，还是在另一形体边界上(on)。,1)若两个面都是平
37、面则对两个面的平面方程进行比较。(1)如果两个面共面，则问题转化为两个平面区域边界的求交问题。两个区域所共享的子区域由两个区域所共享的环所围成。(2)如果两个面不共面而它们的包围盒相交则通过计算求出它们的 交线。如果交线不同时与两个面的包围盒相交，则说明这两个面上 的环不可能相交，故无需再进行环求交。这个检测判断可避 免许多无谓的求交计算。,在每次面和面求交之后，所得的交点沿交线方向进行排序。当这些交点(新点或原有点的引用)被排序之后，构成一个有序的交点表。然后，修改这两个面共享交点表上的拓扑元素。利用交点表确定交线的哪些子线段被两个面共享。被共享的子线段被加到每个面上。,当两个面不共面，且可
38、能相交时，面A的每条边与面B求交，面B的每条边与面A求交。,当两个面的包围盒相交时，使用面面求交算法对两个面进行求交计算。,通过求交操作，每个shell中的所有元素都相对于另一shell进行了分类，每个面、环、边、点都被分为in(在另一shell内)，on(在另一shell边界表面上)，或out(在另一shell之外)，A中所有元素相对于B进行分类。然后，B中的所有元素相对于A进行分类。,(2)分类,集合运算的第三个步骤是归并。当shell A和shell B中的所有拓扑元素都被分类之后，需要归并分类的结果以决定保留哪些元素、删除哪些元素。首先把两个形体中所有元素都打上八个组合分类标记之一：元
39、素原来所属的形体总是分类为on，形体A的元素标记为：(on A)(in B)，(on A)(on B shared)，(on A)(on Bantishared)、(on A)(out B)，形体B的元素标记为：(in A)（on B)，(on A shared)(on B)，(on A antishared)(on B)，（out A)(on B)这里8个标记实际上只代表6钟不同的情况。,(3)归并,两对平行扫描体(剖面线)，因中每条边代表与剖面相交的那个面。,三种常用的集合运算并、交、差对分类结果取舍的规则,差运算：AB 即在造型过程中保留A中那些仅在A中的元素；删除那些既在A中，又在B中
40、的元素；并删除B中的所有元素。,并运算：A U B 交运算保留那些同时属于A和B的元素。,交运算：AB 含意为保留在A之外或在B之外的所有拓扑元素，并删除新形体内部的结构或冗余元素。也就是说，对于实体造型来说，并运算可以理解为：,A B,B A,AB,AB,3.6 常用的其他造型方法,前面讨论了点、线、面几何元素经过并、交、差集合运算构造维数一致的正则形体和维数不一致的非正则形体的求交及分类算法。下面介绍几种常用的其他造型方法：,分数维(Fractal)法,特征(Feature)法,三维重建法（从二维线框信息或二维图象信息构造三维形体）,这些方法具有一定的专用性，且原理与集合运算不一致，但运用
41、这些方法可以扩大传统几何造型方法的覆盖域和速度。,3.6.1 分数维(Fractal）造型,欧氏几何的主要描述工具是直线、平滑的曲线、平面及边界整齐的平滑曲面，这些工具在描述一些抽象图形或人造物体的形态时是非常有力的，但对一些复杂的自然景象形态（诸如山、树、草、火、云、浪等）就显得无能为力了，这是由于从欧氏几何来看，它们是极端无规则的。为了解决复杂图形生成，分数维(Fractal)造型应运而生。,1904年Helge Von Koch研究了一种他称为雪花的图形，他将一个等边三角形的三边都三等分，在中间的那一段上再凸起一个小正三角形，这样一直下去，理论上可证明这种不断构造成的雪花周长是无穷，但其
42、面积却是有限的。,雪花与海岸线的共同特点是都有细节的无穷回归测量尺度的减少都会得到更多的细节。这就是复杂现象的自相似性。为了定量地刻划这种自相似性，引入了分数维(Fractal)概念，这是与欧氏几何个整数维相对应的。,20世纪60年代开始，Benoit BMandelbrot重新研究了这个问题，并将雪花与自然界的海岸线、山、树等自然景象联系起来找出了其中的共性，并提出了分数维(Fractal)的慨念。,设N为每一步细分的数目，S为细分时的放大(缩小)倍数，则分数维D定义为：以雪花为例，它的每一步细分线段的个数为4，而细分时的放大倍数为13，则雪花边线的分数维D 如果我们按欧氏几何的方法，将一线
43、段四等分，则N4，S14，D1；如将一正方形16等分，此时N16，S14，则D2。,分数维的引入，为研究复杂形体提供了全新的角度，使人们从无序中重新发现了有序，许多学科像物理、经济、气象等都将分数维几何学作为解决难题的新工具。计算机图形学也从中受到启发，并形成了以模拟自然界复杂景象、物体为目标的分数维造型。,1）分数维的概念,分数维造型是利用Fratal几何学的自相似性，采用各种模拟真实图形的模型，使整个生成的景象呈现出细节的无穷回归性质的方法。随机插值生成图形 迭代函数反复生成图形 按严格文法有规律生成图形等。,2）分数维造型的模型,(1)随机插值生成图形,用对分线段加个方向的扰动产生海岸线
44、图。,用随机模型构造山的例子,若扰动对象不是直线段而是三角形。一个三角形取每边的中点，对每点的法向高度进行扰动，这样无限次做下去就会产生山峦的图形。,(2)正规文法 该模型是为模拟植物而引入的。其基本思想是用正规文法生成结构性强的植物的拓扑结构，再通过进一步几何解释来形成逼真的画面。,用正规文法字符表示树枝,用正规文法线段表示树枝,用正规文法构造树枝实例,3.6.2 特征(Feature)造型,特征造型系统实现模式,一般造型系统采用特征交互定义方式来支持系统的持征信息。在这种结构中，设计人员首先进入传统的实体造型系统，通过系统支持的几何形体操作构造出所需零件的几何形体，随后再进入特征定义系统，
45、通过交互的定义操作将高层的特征信息附加到已有的几何模型之上。这种方式实现较为简单，但设计效率较低，特征交互定义繁琐，而且与几何模型无必然联系，当零部件形状发生变化时其特征交互定义工作必须重新进行。,(1)特征交互定义,这种方式系统的基本模型如图。在这种结构中，设计人员首先通过传统实体造型系统建立零部件的几何模型，然后通过一个针对特定领域的特征自动识别系统从几何模型中将所需的特征识别出来。这种方式避免了用户繁琐的特征交互定义工作，提高了设计的自动化程度。但是内于特征自动识别过程是一个复杂的模式匹配过程，对于复杂零件识别过程需花费大量的工作、时间，此外对于一些复杂特征，系统不能保证能够识别出来。,
46、(2)持征自动识别,直接从传统实体造型系统构造的几何模型中,自动识别所需特征存在一定的困难，一种解决途径就是在纯几何模型与特征模型之中引入与特定应用无关的元持征，即形状特征。形状特征是表示特定形状以及构造方式的特征，如挤压特征、提伸特征，这种特征没有特定的应用含义，在不同的应用场合可被赋予不同的含义。首先用户通过支持形状特征及操作的形状特征造型系统构造出零件的形状特征模型，随后根据不同的应用场合，形状特征模型被解释成更高层的应用特征模型。这种方式消除了特征自动识别所带来的复杂匹配过程，具有较高的效率及系统可扩充性，因而被许多系统所采用。但是由于在构造形状特征模型中，面对用户的是缺乏实际含义的形状特征与操作，缺少更高层次的设计概念及操作支持，因而还不能很好地支持实际的设计工作。,(3)特征自动重构,在基于特征的造型系统中，系统通过支持具有特定应用含义的特征为用户提供了高层次的符合实际工程设计过程的设计概念和方法，其基本系统结构如图。它大幅度地提高了用户设计效率和设计质量；同时也避免了特征的自动识别、重构。此外，在设计过程中还可方便地进行设计特征的合法性检查、特征相关性检查以及组织更复杂的特征。这种方式也是目前特征造型系统的最高实现方式。,(4)基于特征的造型系统,
