研究生计算机图形学-第6章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 几 何造型,第6章 几 何造型,6.1 三维形体的表示形式,6.2 翼边结构与欧拉操作,6.3 求交运算,6.4 集合运算,6.5 特征造型,6.1 三维形体的表示形式,1.线框模型,所谓线框模型就是将客观物体视为三维空间中线段的集合，即用物体轮廓边描述物体的几何形状。对于平面立体，可由轮廓边直接构成；而对于曲面立体，则可用一些线框围成,。图 6.1.1 所示为圆柱体的线框模型，图 6.1.2 所示为一个立方体的线框模型。,图 6.1.1 圆柱体的线框模型,图 6.1.2 立方体的线框模型,用线框模型表示非平面立体，如圆柱体、球体等还存在一些问题。其一是曲面立体的轮廓线将随视线方向的变化而改变；其二是线框模型给出的不是连续的几何信息(只有点和棱边)，不能明确地定义给定点与形体之间的关系(点在形体内部，外部或表面上)。另外，这种方法不能处理求表面交线、消除隐藏线、计算物体重量与惯性矩等物性。因此它的应用范围受到一定的限制。但用这种方法定义形体简单、数据量少、处理方便。所以，目前在少数系统中还有应用，如,AutoCAD 2002,软件中的造型系统仍然有线框造型功能,。,2.表面模型,用有向棱边围成形体的表面所产生的模型称为表面模型，即由面的集合定义形体。表面模型在线框模型的基础上增加了有关面边信息、表面特征、棱边的连接方向等内容。因此可以满足线、面消隐，面与面的求交，产生真实感图形等问题的需要。组成表面模型的面元素一般是平面，但也可以是圆柱面、圆球面等二次曲面，还可以是自由曲面，如双三次,Coons,曲面、,B,zier,曲面和,B,样条曲面。在这种模型中，没有明确定义形体究竟存在于表面的哪一侧，所以在物性计算、有限元分析等应用中，表面模型在形体表示上尚缺,乏完整性。对于图 6.1.2 所示的立体，其面表如表 6.1.3 所示。,图 6.1.3 实体表面外法矢方向的确定,表 6.1.3 面 表,3.实体模型,在表面模型的基础上，对于三维形体存在的一侧给出明确的定义，就解决了实体模型的描述问题。一般规定实体表面外环边的走向沿逆时针方向，以右手法则决定该面的外法矢方向，如图 6.1.3 所示，实体存在于该面外法矢方向相反的一侧，该侧即为实体存在的半空间。若干半空间的交集为所描述的实体。拓扑合法的形体，其相邻两个面的公共棱边,的方向正好相反。,6.1.2 正则形体及欧拉公式,1.,正则形体,形体是三维几何元素，是封闭表面围成的空间，也是欧氏空间,R,3,中非空、有界的封闭子集，其边界是有限面的并集。形体上任意一点的足够小邻域的拓扑上应该是一个等价的封闭圆，也即围绕该点的形体领域在二维空间中可构成一个单连通域。满足这种定义的形体称之为正则形体。只有正则形体才能保证几何造型的可靠性与可加工性。非正则形体如图 6.1.4 所示，图(,a),形体带有悬挂面，图(,b),形体带有悬挂边，图(,c),所示的形体一条,边有两个以上的邻面，图(,d),所示的形体，点,V,的小邻域不是单连通域。,图 6.1.4 非正则形体,2.几何元素之间的连接方式,任何形体的边界都是由与其对应的、较低维的几何元素组成。由顶点定义边，由边定义环，又由若干环(或一个环)组成一个平面，最后由若干平面组成形体。在几何造型中，最基本的几何元素是点(,V)、,边(,E)、,面(,F)，,三种几何元素组合成几种连接方式如图6.1.5所示。这些连接方式仅适用于正则形体。,图 6.1.5 中，,V：V、V:E,和,V：F,等分别表示顶点与顶点、顶点与边和顶点与面等,几何元素之间的相邻性。,图 6.1.5 点、边、面间的连接方式,3.欧拉公式,在几何造型过程中，为了保证每一步所产生的形体拓扑关系都是正确的，需要用欧拉公式进行检验。对于正则形体，其点(,V,)、,边(,E,),和面(,F,),的个数应满足欧拉公式：,V-E+F,=2,(6-1),式(6-,1),只适用于简单的多面体及拓扑同构体，当多面体上有通孔及面上有内环时，上述关系不成立。如果将三维空间中的一个多面体分割成,S,个多面体，则其顶点、边、面和体的欧拉公式将变为,V-E+F-S,=1,在几何造型中，需采用修改后的欧拉公式：,V-E+F-R2,H,-2,S,=0,其中,R,是内环数，,H,是通孔数，,S,是不连接的形体(即多面体)的个数。,用式(6-,2),检验图6.1.6(,a),所示的形体，有,V-E+F-R,+2,H,-2,S,=16-24+10-2+2-2=0,形体符合欧拉关系，造型合理。用式(6-,2),检验拓扑同构体，如图 6.1.6(,b),中的圆柱，将圆柱视为立方体的拓扑变换，上部分的圆柱体与下部分的四棱柱已通过求并成为一组合体，多面体的个数仍然为 1，因此有,V-E+F-R+,2,H,-2,S,=16-24+11-1+0-2=0,满足欧拉关系，形体的拓扑结构是正确的。,(6-2),图6.1.6 符合欧拉公式的形体,图 6.1.7 不符合欧拉公式的形体,值得指出的是：检验一个形体的拓扑关系是否正确，形状是否正确，符合欧拉公式只是,必要条件，而不是充分条件。,6.1.3 常用的形体表示模式,表示形体的线框、表面和实体模型是一种广义的概念，并不反映形体在计算机内具体的表示方式。特征表示的和实体几何构造表示的形体，用户操作比较方便；而以边界表示的形体，则便于计算机存储管理和操作运算。另外，形体还有一些其他的表示方式，如空,间单元表示，扫描变换表示，网格分解表示等。,1.空间单元表示模式,这种模式的单元(元素)是具有空间位置和大小的正方体，每一个单元可由一个点的坐标定位，用单元的中心坐标表示。单元网格的集合构成了空间形体。这种表示是完整的、惟,一的，便于检测。其缺点是数据量大。空间单元表示模式如图 6.1.8 所示。,图 6.1.8 空间单元表示模式,2.网格分解表示模式,这种表示模式是空间单元表示模式的扩展，其离散网格可以是任意大小和形状的立体，但最常用的是正立方体网格。这种表示模式有利于有限元分析及计算。网格单元为球体的算法目前研究与应用也较多。,下面我们讨论网格单元为正方体的八叉树算法。包含形体作一正方体，如图 6.1.9(,a),所示。当然，形体不完全占居正方体空间，所以正方体为一灰结点。将灰结点的正方体分八等份，其编号如图 6.1.9(,b),所示。依次检测八个分体，实体完全不占据的分体为白结点，实体完全占据的分体为黑结点，实体部分占据的分体为灰结点。对灰结点再作八等,份分割，继续检测与再分割，直到达到精度要求的最小单位为止，如图 6.1.9(,c),所示。,图 6.1.9 多面体的八叉树表示,3.边界表示模式,边界表示模式详细记录了拓扑信息，即构成形体的所有几何元素的几何信息及其相互连接关系。以便直接存取构成形体的各顶点、面的边界以及各个面的定义参数，有助于以面、边和点为基础的各种几何运算。,这种表示模式简称为,BRep,模式，构成实体时，按一定的层次结构进行表达：实体模型由若干表面组成，每一个表面由其外环和内环表示，环由棱边沿一定走向围成，而每,个棱边又由相邻两个顶点定义。因此，在数据结构上有面表、环表、边表及顶点表。,BRep,模式有利于图形几何变换与显示，便于生成线图，对形体的表示可以有多种操作。但,BRep,模式也存在一些缺点，其一，数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂；其二，难以实现形体的修改操作；其三，,BRep,模式并不一定对应一个有效形体，也就是说需要专门的程序保证其表示形体的有效性、正则,性等。,4.实体几何构造模式,实体几何构造模式简称,CSG,模式，其含意是任何复杂的形体都可用简单形体(体素)的组合来表示。通常用正则集合运算实现这种组合，其中还可配合执行有关的几何变换。实体几何构造模式构造几何模型分为两步：首先定义形状最简单的体素，如圆柱体、圆锥体、圆球体、立方体、棱锥体等，然后根据需要进行体素间的布尔运算，即求并集、交,集、差集等，从而产生实体几何模型。,我们可以用半空间的集合表示体素，而三维空间的半空间以有向面划分，其数学表达式为,S,ij,=(,x,y,z,)|,F,(,x,y,z,)0,(6-3),式(6-3)中，,S,ij,为半空间，,F,(,x,y,z,)0,为面的方程表达式。可见，,半空间是面上及面一侧点的集合。体素,S,i,可描述为半空间的交集，即,(6-4),对如图 6.1.10 所示的四棱柱，可定义为,S,1,=,S,11,S,12,S,13,S,14,S,15,S,16,还可以定义为如下形式：,S,1,=(,x,y，z,)|,x,1,x,x,m,y,1,y,y,m,z,1,z,z,m,(6-5),对于如图 6.1.11 所示的圆柱，可定义为,S,2,=(,x,y,z,)|,r,2,-(,x-a,),2,-(,y-b,),2,0(,x,y,z,)|0,z,h,(6-,6),基本几何构造模式的数据结构有如下两种：,图 6.1.10 四棱柱半空间集合,图 6.1.11 圆柱半空间集合,1)树形结构,如图 6.1.12 所示，在树形结构中，,P,12,P,22,P,31,P,32,为树叶，而,P,11,、,P,12,是分枝点，由树的最下部开始，在依次增加树叶,的同时，逐步构成形体，其模型可由数学表达式表示为,图 6.1.12 树形结构,2)二层结构,如图 6.1.13 所示，这种结构将并集合运算的结合与交集合运算的结合分为二层，所以,称其为二层结构，它比树状结构更为简单明了。其运算模式为,(6-7),CSG,模式具有表现力强，构型方便，数据结构比较简单等优点。但它不能充分表,示构型物体几何形状的拓扑性质，对物体形状处理工作量大，其应用受到一定限制。,图 6.1.13 二层结构的,CSG,树,5.扫描变换表示模式,一个二维几何图形沿某一轴平移，或绕某一轴旋转，其运动轨迹便产生了一个空间形体。如图 6.1.14 所示为平移扫描变换，图 6.1.15所示为旋转扫描变换。,这种表示模式的优点是物体的形状输入方便，适合于表现二维半形体，但其几何覆盖性较,差。,对于一个几何造型系统，不可能同时采用以上五种表示模式，但也不可能仅采用一种表示模式，一般是根据应用要求和计算机条件，采用以上所述的几种表示模的混合模式。应用于目前一些系统中的混合模式主要有以下几种：,实体几何构造和边界表示模式的混合模式。,实体几何构造和一般扫描变换模式的混合模式。,实体几何构造和扫描变换模式的混合模式。,图 6.1.14 平移扫描变换,图 6.1.15 旋转扫描变换,6.2 翼边结构与欧拉操作,6.2.1 翼边结构,图 6.2.1 为翼边结构的存取关系，图 6.2.2 所示为斯坦福大学早期应用的翼边结构。翼边结构的基本思想是：从形体的边开始查找该边的邻面、邻边、端点及其属性。如在图 6.2.1(,a),中，,E,到,V,的直线箭头表示由边查找点，在图 6.2.1(,b),中，,E,上的圆弧箭头表示,由边查找边等等。,图 6.2.1 翼边结构的点、边、面的存取关系,图 6.2.2 早期应用的翼边结构,通过对翼边结构的不断改进，产生了对称结构，它是以点边、面边为基础的连接关系表。图 6.2.3 所示的是一种典型的对称结构，各域的含义如下：,X、Y、Z：,顶点的空间位置坐标；,VG：,连接到该顶点上一组边的指针；,VGEOM：,顶点的几何坐标参数指针；,NE：,连接下一条边的指针ETPY：,边的类型标志位，“+”表示多边形是从,V,1,到,V,2,，“-”,表示该边的走向是从,V,2,到,V,1,；,EDGON：,一条边的指针；,X,1,：,该边起点坐标的,x,值；,x,：,该边在,X,方向的增量；,Y,1,:,该边起点坐标的,y,值；,y,：,该边在,Y,方向的增量；,Z,1,:,该边起点坐标的,z,值；,z,：,该边在,Z,方向的增量；,NBHD：,表示该边的哪一侧是相应面的标志位(从,V,1,到,V,2,规定为遍历边的正方向),；,V,1,V,2,：,一条边两个端点的指针；,F,1,F,2,:,相邻一条边的两个面的指针；,EGEOM：,一条边几何系数指针；,A、B、C、D,：,面方程系数；,NBHD：,表示面的哪一侧存在实体的标志位；,FGEOM：,该面几何参数指针；,FG：,该面边界边的指针。,图 6.2.3 对称数据结构的实现,6.2.2 欧拉操作,欧拉公式定义了点、边、面、体及洞穴之间的平衡关系，在此，将介绍用点、边、环的增、删操作构造形体的方法。在以下的操作中，点、边、环、体分别用,V、E、L,和,S,表示。,1.,产生一条边和一个环(,MEL),如图 6.2.4(,a),所示，给出一个基本体素长方体,S,，,拾取,L,1,上的点,V,1,V,2,形成一条边,E,1,E,1,边将原环,L,1,分成新环,L,1,和,L,2,，,在这种情况下MEL,产生的环总是父环。,L,1,经过一次,MEL,操作后可能是父环，也可能是子环。如图 6.2.4(,b),所示，,L,1,经过,MEL,操作后，所产生的,L,2,为父环，而,L,1,则为子环。,图 6.2.4,MEL,与,KEL,操作,2.删除一条边及一个环(,KEL),如图 6.2.4 所示，,KEL,为,MEL,的逆操作。在图 6.2.5 中，,L,1,、,L,2,均为父环，,L,3,和,L,4,分别是其中的子环。当删除,E,边时，同时也删除了,L,2,环。结果,L,1,是父环，,L,3,及,L,4,均为其中的子环。也就是说，当删除一条边及一个环后，原来的隶属关,系将会发生变化。图 6.2.5 子环的隶属关系变化,3.产生一个顶点及一条边(,MVE),如图6.2.6所示，在形体,S,的边,E,1,上确定一点,V,1,(,x,y,z,)，,这时原,E,1,被分割,成,E,1,和,E,2,两条边。,图 6.2.6,MVE,及,KVE,操作,4.删除一个点及一条边(,KVE),如图 6.2.6 所示，删除,V,1,，,则,E,1,和,E,2,变成了一条边,E,1,。,5.,产生一条边及一个点(,MEV),如图 6.2.7 所示，,V,1,与,V,2,属于,L,1,环，在,V,1,和,V,2,之间形成一条边,E,1,，,V,2,点的坐标是(,x,y,z,)。,通过这种操作可产生一条新边和一个新点。,6.,删除一条边及一个点(,KEV),如图 6.2.7 所示，通过,KEV,操作后，将删除一条边和一个点。,KEV,是,MEV,的逆操作。,图 6.2.7,MEV,及,KEV,操作,7.将子环变成父环(,KCLMPL),图 6.2.8,KCLMPL,与,KPLMCL,操作,9.产生一条边、删除一个环(,MEKL),图 6.2.9,MEKL,和,KEML,操作,10.删除一条边，产生一个环(,KEML),在图 6.2.9 中，删除边,E,1,后，形成了两个独立的环,L,1,和,L,2,。,此处,L,1,和,L,2,是相同类型的环。这种操作是,MEKL,的逆操作。,11.产生一个点和一条零长度的边(,MVZE),如图 6.2.10(,a),所示，四条边,E,2,、,E,3,、,E,4,、,E,5,均与点,V,2,相连，四个面,F,1,、,F,2,、,F,3,、,F,4,也与点,V,2,相邻。通过,MVZE,操作，用一条零长度的边,E,1,代替点,V,2,，,E,1,的两个端点分别是,V,1,和,V,2,。,这种操作可将原来的非正则形体,正则化。这里需要加以说明的是，,MVZE,操作仅对连接两条以上边的点才有效。,图 6.2.10,MVZE,与,KVZE,操作,12.删除一个点及一条零长度的边(,KVZE),13.用欧拉操作完成造型实例的过程,可用一棵树来描述欧拉操作造型的过程。如图 6.2.11 所示，设,A,0,为一空体，是树根。如果,A,11,是被输入的长方体体素，用以上所述操作生成不同形体的过程如下：,(1)通过,MEL,操作将环,F,1,分成两个环,F,1,和,F,2,，,生成的形体为,A,12,。,(2),对,F,1,进行拉伸操作产生形体,A,13,，,对,A,13,中的边,E,1,倒圆角，,所产生的形体为,A,14,。,(3),如果在,F,1,和,F,2,中选,F,2,进行拉伸操作，则产生,A,21,形体，如果接着对,A,21,形体的,E,2,边进行倒圆角，所产生的形体为,A,22,。,(4),如果对,A,13,形体的,F,3,环进行拉伸，则产生形体,A,31,。,图 6.2.11 欧拉操作造型过程,6.3 求交运算,6.3.1 点与各几何元素求交,判断空间两点是否相交，实际上就是判断两点之间的距离是否小于,。,判断点与线是否相交，就是判断点与线的最短距离是否位于容差范围内。,1.,点与直线段的求交,设一点,P,(,x,y，z,)，,一直线段两端点分别为,P,1,(,x,1,y,1,z,1,),和,P,2,(,x,2,y,2,z,2,)，,则,P,到,P,1,P,2,距离的平方为,d,2,=(,x-x,1,),2,+(,y-y,1,),2,+(,z-z,1,),2,-(,x,2,-,x,1,)(,x-x,1)+(,y,2,y,1,)(,y-y,1,),+(,z,2,-,z,1,)(,z-z,1,),2,/(,x,2,-,x,1,),2,+(,y,2,-,y,1,),2,+(,z,2,-,z,1,),2,(6-8),如果,d,2,2,，,则点在线段上或在其延长线上，到此，还需进一步判断点是否在直线段的有效区间内。我们可以通过对点的坐标分量进行比较来确定，如图 6.3.1 所示。,(1)假设线段两端点的,y,坐标值不等，则，,y-y,1,与,y-y,2,的符号相反时，点,P,在线段的有效区间内。,(2)如果,P,1,P,P,2,三点重合，则要进一步判别,x,坐标分量，即,x-x,1,与,x-x,2,的符号相反时点,P,在线段的有效区间内。其他情况类推。,图 6.3.1 坐标分量的比较,2.点与圆弧的求交,如图 6.3.2 所示，设点的坐标为,P,(,x,y,z,)，,圆弧的中心为,C,(,x,0,y,0,z,0,)，,其半径为,r,，,起始角为,1,终止角为,2,。,1,和,2,均为局部坐标系中与坐标轴,x,的正向的夹角。,圆弧所在平面的方程为,ax+by+,cz,+d,=0,首先判断点,P,是否在该平面上，如果不在，则不相交。如果点,P,在该平面上，就必须,通过坐标变换，即旋转变换，使之成为二维的问题。,圆弧的中心为,C,(,x,0,y,0,)，,对于平面上一点,P,(,x,y,)，,判断点,P是否在圆弧上，可分两步进行：,(1)判断点,P,是否在圆心为,C,，,半径为,r,的圆周上，即判断下式是否成立：,(2),判断点,P,是否在有效的圆弧上，其判别方法与点与直线段的求交方法类似。,图 6.3.2 点与圆弧求交,3.点与有限平面的求交,设一点,P,(,x,y,z,)，,平面的方程为,ax+by+,cz,+d,=0。,则,P,到平面的距离可写成：,如果,D,，,则点在平面上，否则点不在平面上。到此，还需进一步判别点是否落在平面的有效区域内。如果点落在有效区域(有限面)内，则点与该平面相交，否则无交。有限面可以是任意多边形。,一个点是否包含在一个多边形内，其判别算法有多种，如夹角之和检验法，叉积判断法,，以及交点计数检验法等。在此仅介绍交点计数检验法和叉积判断法。,1)交点计数检验法,交点计数检验法适用较广，特别适用于当多边形为凹，甚至在多边形带孔的情况下，点,是否在多边形内的判别。判别方法的基本思想是：从被判断点作一射线至无穷远，即,(,u,0),求射线与多边形相交时交点的个数。如果交点个数为奇数，点在多边形之内；如果交点,个数为偶数，则点在多边形之外。,如图 6.3.3(,a),所示，射线,a,c,d,与多边形相交，其交点数分别为2、2、4，为偶数，可以直接判别,A、C、D,三点均在多边形之外。而射线,b#,e,分别交多边形的交点数为 3 和 1，所以也可直接判断,BE,两点均在多边形内。,如图 6.3.3(,b),所示，射线,f,g,h,i,j,均通过多边形的顶点，这时应另行对待，,不能直接判断相应的点是否在多边形之内。,图 6.3.3 交点计数法,图 6.3.4 交点计数示意图,例如：图 6.3.3(,b),中，射线,f,在边 7 和 8 之上，所以射线,f,与多边形的交点计数为 0；而射线,j,在边 1 与 2 之下，所以射线,j,与多边形的交点计数为 2。两种情况计数均为偶数，可判断,F,和,J,在多边形之外。,射线,h,与3、4 两条边交点计数为 0，与边 6 有 1 个交点，所以交点数为 1+0=1，故,H,在多边形之内。射线,i,与4、5 两条边条计数为 2，与2、3两条边的交点计数为1，交点总数为 2+1=3，,则点,I,在多边形之内。,2)叉积判断法,图 6.3.5 叉积判断法,令,V,i,=P,i,-P,0,(i=,1,2,n),V,n,+,1,=V,1,则多边形包含,P,0,的充要条件是叉积,V,i,V,i,+1,的符号相同(,i,=1,2,n,),。,叉积判断算法如图 6.3.6 所示。,图 6.3.6 叉积判断程序框图,6.3.2 直线与几何元素求交,1.,两直线求交,设两直线段,AB,和,CD,，,其端点分别为,A,(,x,a,y,a,),B,(,x,b,y,b,),和,C,(,x,c,y,c,)、,D,(,x,dy,d,)。,则,AB,的参数方程为,t,1,CD,的参数方程为,1,这时，交点的参数值,t,和,应满足,x,a,+(,x,b,-,x,a,),t,=,x,c,+(,x,d,-,x,c,),y,a,+(,y,b,-,y,a,),t,=,y,c,+(,y,d,-,y,c,),整理后，有,(,x,b,-,x,a,),t,-(,x,d,-,x,c,),=,x,c,-,x,a,(,y,b,-,y,a,),t,-(,y,d,-,y,c,),=,y,c,-,y,a,设,如果,=0，,则线段,AB,与,CD,平行，按无交处理；如果,0，,则可求出,(6-10),当0,t,1，,且0,1,时，,AB,与,CD,相交，如果交点在,AB(,或,CD),的延长线上，则按,无交处理。,2.直线段与曲线段求交,1),直线段与圆弧的交点,设直线段,AB,，,其参数方程为,0,t,1,设圆弧的圆心为,C,(,x,c,y,c,)，,半径为,R,，,其参数方程为,1,2,则交点处的参数,t,应满足,即,(6-11),由,cos,2,+sin,2,=1，,有,令,A,=(,x,b,-,x,a,),2,+(,y,b,-,y,a,),2,B,=2(,x,a,-,x,c,)(,x,b,-,x,a,)+2(,y,a,-,y,c,)(,y,b,-,y,a,),C,=(,x,a,-,x,c,),2,+(,y,a,-,y,c,)2,-,R,2,则有,(6-12),如果,B,2,-4,AC,0，,则式(6-12)有两个实根,t,1,和,t,2,。,在此，如果0,t,k,1，,可令式(6-11)中,t=,t,k,=,k,，,则,1,k,2,成立。由,t=,t,k,或者,=,k,求出直线与圆弧的一个有效交点。否则不是有效交点，而仅为直线与圆弧所在圆的交点，按无交处理。,如果,B,2,-4,AC,=0，,则式(6-12)有重根,t=t,0,，,说明直线段所在直线与圆弧所在圆相切。只有当,t=t,0,满足0,t,0,1，,并且将,t=t,0,代入式(6-11)得,=,0,，,使得,1,0,2,成立，直线段才真正与圆弧相切。,2)直线段与一般二次曲线的交点,同样设直线段,AB,的参数方程为,0,t,1,设一般二次曲线方程为,Ax,2,+,Bxy,+,Cy,2,+,Dx,+,Ey,+F,=0,将直线段方程代入一般二次曲线方程并加以整理，可得,(6-13),3.直线与平面的交点,设一直线过点,Q,(,x,q,y,q,z,q,)，,其方向数为(,l,m,n,)。,空间一平面多边形的顶点序列为(,P,1,P,2,P,n,-1,P,n,P,1,)。,如图 6.3.7,所示。,直线的参数方程为,-,t,0，,且,C,0，,由式(6-34)可得,到此，我们便得到圆柱面与二次曲面的两条交线，即,(,k,=1,2),图 6.3.8 圆柱坐标系,2)圆锥面与二次曲面的交线,图 6.3.9 圆锥面的局部坐标系,圆锥面的参数方程为,(6-35),式(6-35)中，,p,为锥面上任意一点所在圆的半径，,k,=tan,，2,为锥顶角。,将式(6-35)代入式(6-33)并加以整理，得,a,(,),p,2,+,b,(,),p,+,c,(,)=0,其中，,a,(,)=,Ck,2,+,Ek,sin,+,Fk,cos,+,A,cos,2,+,B,sin,2,+,D,sin,cos,b,(,)=,G,cos,+,H,sin,+,Ik,c,(,)=,J,到此，已知,便可求出,p,从而得到交线上的一个点。变动,，,可得交线。,p,的求法和圆,柱面与二次曲面相交时,t,1,t,2,的求法相同，这里不再赘述。,3)两球面的交线,空间两圆球相交，其交线为一圆。因此，圆球与圆球相交可化解为平面与圆球相交。两,圆球的方程可分别写成：,(6-,36),(6-,37),用式(6-36)减式(6-37)，且令,可得,Ax+By+,Cz,+D,=0,(6-,38),6.4 集合运算,6.4.1 正则集合的基本概念,早期的几何造型系统在集合运算中，规定为三维欧氏空间的正则集合，设,G,是,n,维欧氏空间,E,n,中的一个有界区域，则,其中，,bG,是区域,G,的,n,-1,维边界，,iG,是,G,的内部，而设,cG,是,G,的补空间，为,G,的外部。如图6.4.1所示，如果,G,是,E,n,(,n,=1,2,3),中正则形体，其边界应满足以下条件：,(1)边界,bG,一定将内部,iG,和外部,cG,分隔成两个互不连通的,n,维子空间；,(2)删除,bG,上任何一点，则,iG,和,cG,将会成为连通的子空间；,(3)如果,bG,上任何一点,P,处有,n,-1,维切线存在，则其法向,N,p,必指向,cG,子空间。,我们可以定义正则集合算子以解决正则形体集合问题。设,OP,为集合运算算子，对于,E,n,中任意两个正则形体,A、B,的集合，都可写成,R,仍然是,E,n,中的正则形体，正则集合算子,OP,可为正则并、正则交和正则差，分别,记为*,*这里的,R,可代表多个形体。,6.4.2 二维几何元素的集合运算,图 6.4.2 多边形区域的外环与内环,1.两环的并、交、差运算,图 6.4.3 环的并、交、差运算,2.出、入点的判断,图 6.4.4 出、入点的判断,3.运算步骤,(1)算出环,A,和环,B,的所有交点,P,1A,，,P,2A,，,P,nA,及,P,1,B,，,P,2,B,，,P,nB,。,环,A,加上交点便扩展为,A,环，环,B,加上交点便扩展为,B,环。如果没有交点，则,A,=,A,B,=,B,，,然后转向步骤(7)。,(2)决定,A,、,B,中交点的出入特征，并置“未遍历”标志。,(3)取,A,的一个“未遍历”的交点作为首交点，开始建立新环。,(4)对于“并”运算，如果交点特征为“-1”，或者对于“交”运算，如果交点特征为,“+1”，则转向另一环，并对两环中该交点均置“已遍历”标记。,(5)沿着正在进行的环，取下一个点(顶点或交点)。如果是顶点，则继续进行；如果是交点，则判断是否回到首交点。如果没有回到首交点，则转向步骤(4)；如果回到首交点，则转向下一步。,(6)判断是否还有“未遍历”的交点，如果有，则转向步骤(3)，否则进行下一步。,(7),判断所得的新环之间的包含关系，如果没有包含关系就结束；如果有包含关系，最外层的环为外环。在外环之内的环为内环，如果内环走向与外环走向相反，应保留；如,果内环走向与外环走向相同，则删除。,6.4.3 三维形体的正则集合与正则布尔运算,1.基本布尔运算,(1)并集，即逻辑相加，如图 6.4.5 所示。,A,B,=,R,|,R,A,OR,R,B,(2),交集，即逻辑相乘，如图 6.4.6 所示。,A,B,=,R,|,R,A AND,R,B,(3),差集，即逻辑相减，如图 6.4.7 所示。,A-B,=,R,|,R,A AND,R B,(4),补集，即逻辑非，如图 6.4.8 所示。,C,(,A,)=,R,|,R A,图 6.4.5,AB,布尔运算,图 6.4.6,AB,布尔运算,图 6.4.7,A-B,布尔运算,图 6.4.8,C,(,A,),布尔运算图 6.4.9 两个平面的交集,图 6.4.10 两个形体的交集,2.封闭正则集合,为了避免产生非正则集合，需要进行正则布尔运算。在此，我们可先对封闭正则集合进行定义：如果对于形体,X,有,X,=,KiX,，,则可称形体,X,是三维欧氏空间的一个封闭正则集合。其,中,i,表示集合的内部，,K,表示封闭，如图 6.4.11 所示。,图 6.4.11 封闭正则集合的定义,3.正则布尔运算,正则布尔运算有正则并(*)、正则交(*)、正则差(-*)及正则补(,C,*)。,分别定义如下：,A,*,B,=,Ki,(,A,B,),A,*,B,=,Ki,(,A,B,),A,-*,B,=,Ki,(,A-B,)C,*(,A,)=,KiC,(,A,),图 6.4.9(,c),和图 6.4.10(,c),表示了正则交运算的情况。由于非正则集合的悬挂边及悬,挂面被除掉，正则布尔运算生成封闭正则集合，从而保证了构造形体的三维齐性。,6.5 特 征造型,6.5.1 特征的定义、分类及形式化描述,1.,特征的定义,特征是根据其应用形式进行定义的，不同的应用形式形成了不同的特征定义。例如，在形体的建模方面，特征是一组具有特定关系的几何元素或拓扑元素；而在加工方面，特征则被定义为与加工操作和工具有关的零部件形式以及技术特性，以下是几个主要特征的定义：,(1)将设计、分析、计算和加工中使用的几何元素或拓扑元素重新组织，形成更为方便,的设计与加工实体。,(2)具有一定的几何模式，并对应特定机械功能的零件或部件。,(3)产品模型中的一组相关元素，这些元素遵从一系列识别与分类规则；并在产品生命周期中作为具有一定功能的独立实体。,(4)在设计、加工、装配等过程中，进行推理所需的有关零件形状和某些属性的信息集合。,(5)定义机械零件的高级语言或表示方式中的基本元素。,(6)包括材料类型、功能及其他描述信息的零件特性。,所谓特征，是一组具有特定属性的实体。以上罗列的几个定义虽然存在差异，但均反映了一个实际工程中零部件的特定几何形状和特定加工的功能要求。同时为工程技术人员提供了高层次的设计方法和,CIMS,中其他系统的设计意图和手段。特征的引入使造型系统,大大提高了设计效率和质量，同时也消除了,CIMS,各子系统之间的信息孤立情形。,2.特征的分类,在具体应用中，不同的应用观点和方法会产生不同的特征分类标准。,根据零部件的功能，可分为形状特征、精度特征、材料特征、技术特征等。,根据零部件的设计方法，可分为表面特征、形变特征、挤压特征、过渡特征、提拉特征等。,根据零部件整个生命周期，可分为设计特征，加工特征、公差及检测特征、装配特征等。,好的特征分类应包括表示、处理等，应该有助于对特征进行进一步深入的研究。为了实,际应用中的方便，可采用以下基于特征的分类标准：,(1)形状特征具有特定的形状，并对特定功能的零部件局部形状具有整体上的布局。,(2)精度特征包含工程设计和加工过程中使用的尺寸公差、形位公差、表面粗糙度等非几何信息及其检测。,(3)材料特征应包括材料的类型、强度、刚度、延展性等。,(4)装配特征应包含装配件中各零件的相对位置关系、公差与配合、传动关系等。,(5)分析特征有关工程分析方面的特征，如有限元分析中，杆件和板件特征等。,3.特征的形式化描述,为了加深对特征语义的了解，下面简要介绍特征的形式化描述。,1),特征,特征是满足某些约束关系的特征元素的集合(,feature)。,特征包含了特征元素(,featureelements),和约束(,constraints)。,2)特征元素,特征元素是指人们考虑某一特征问题时所关心的一系列属于该特征的主观或客观实体。例如，一个圆柱或圆锥体，其底面是人们看得见摸得着的客观实体，而其轴线则为人们无法触觉的主观实体。特征元素包括特征的几何拓扑元素以及它的内部属性。,特征元素中包含了几何元素或拓扑元素(,geometricortopologicalelement),及特,征参数(,property of feature)。,几何元素包括：,坐标系(,coordimate,system),矢量(,vector),点(,point),曲线(,curve),曲面(,surface),形体(,shape),拓扑元素包括：,顶点(,verter,),边(,edge),环(,path),孔(,loop),面(,face),线框(,shell),实体(,solid),特征参数类型包括：,圆心(,centerof),轴线(,axisof),多边形表面的顶点(,topfaceof),3)约束,约束分为几何约束和非几何约束，是特征元素之间必须满足的关系。几何约束包括特征几何拓扑元素之间必须满足的一系列约束。而非几何约束则为诸如功能等方面的约束。另外，约束还应包括人们处理特征问题时所处的应用背景及其所采用的方式。,几何约束的类型包括：,平行(,parallel),同轴线(,coaxis,),相邻(,adjacent),距离(,havedistancewith),角度(,haveanglewith),非几何约束包括：,功能约束(,functionalconstraint),应用范围约束(,applicationcontext),特征的形式化描述可使人们对特征的含义有进一步的理解，同时也具有较强的应用意义。另外，形式化描述的特点就是特征的层次性。特征从最基本的几何元素开始，通过增加,约束，可形成较高层次的特征，如进一步加强约束，便可再次形成更高层次的特征。,6.5.2 特征造型系统的实现模式,目前，特征造型系统主要采用特征交互定义、特征自动识别、特征自动重构、基于特征的造型四种方法予以实现，这四种方法基本上反映了特征造型的发展过程。,1.,特征交互定义模式,早期的造型系统一般都采用特征交互定义的方式支持系统的特征信息。系统的基本模式如,下：,用户,传统实体造型系统户,零件几何模型,特征附加系统,零件的特征模型,在这种结构中，工程设计人员首先进入传统的实体造型系统，通过系统支持的几何形体操作，构造所需零件的几何形体，然后进入特征定义系统，通过交互的定义操作，将高层的特征信息附加到已有的几何模型上。这种方式虽然较为简单，但存在许多缺点。其一，设计效率低；其二，特征交互定义繁琐；其三，特征定义与几何模型无必然联系,，当零件的形状发生变化时，必须重新进行特征交互定义。,2.特征自动识别模式,特征自动识别系统的模式如下：,用户,传统实体造型系统户,零件几何模型,特征自动识别系统,零件的特征模型,在这种结构中，用“特征自动识别系统”代替了“特征附加系统”，这种方式避免了用户繁琐的特征交互定义工作，自动化程度得以提高。但对于形体复杂的零件，识别过程需要进行大量的操作，花费大量的操作时间。当特征,复杂时，系统不一定能够识别。,3.特征自动重构模式,在纯几何模型与特征模型之中引入与特定应用无关的元特征，即形状特征，可解决直接从传统实体造型系统构造的几何模型中自动识别所需特征存在的问题。引入元特征之后的系,统如下：,用户,传统实体造型系统户,零件几何模型,特征重构系统,零件的特征模型,形状特征是表示特定形状以及构造方式的特征，如挤压特征、