形体在计算机内的表示ppt课件

1、3.2形体在计算机内的表示 3.2.1 引言 计算机中表示形体，通常用线框、外表和实体三种模型。 对于任一形体，假设它是3维欧氏空间中非空、有界的封锁子集，且其边境是二维流形即该形体是连通的，我们称该形体为正那么形体，否那么称为非正那么形体。 些非正那么形体的实例(a)有悬面(b)有悬边（c）一条边有两个以上 的邻面（不连通）图3.2.1 非正则形体实例 集合运算并、交、差是构造形体的根本方法。正那么形体经过集合运算后，能够会产生悬边、悬面等低于三维的形体。 Requicha在引入正那么形体概念的同时，还定义了正那么集合运算的概念。正那么集合运算保证集合运算的结果仍是一个正那么形体，即丢弃悬边

2、、悬面等。ABabab图3.2.2 二个二维图形的交产 生一个退化的结果悬边ABABC=AB集合论的求交计算正则集合下的求交运算*C=A*B图3.2.3 集合和正则的交运算 为了可以处置非正那么形体，产生了非正那么外型技术。 九十年代以来，基于约束的参数化、变量化外型和支持线框、曲面、实体一致表示的非正那么形体外型技术已成为几何外型技术的主流。3.2.2 形体表示模型在实体模型的表示中，根本上可以分为分解表示、构造表示和边境表示三大类。1、分解表示将形体按某种规那么分解为小的更易于描画的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都可以直接描画为止。(a)将形体空间细分为小的

3、立方体单元。这种表示方法的优点是简单，容易实现形体的交、并、差计算，但是占用的存储量太大，物体的边境面没有显式的解析表达式，不便于运算。(b)八叉树法表示形体.首先对形体定义一个外接立方体，再把它分解成八个子立方体，并对立方体依次编号为0，1，2，7。假设子立方体单元曾经一致，即为满该立方体充溢形体或为空没有形体在其中，那么该子立方体可停顿分解；否那么，需求对该立方体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。优点主要是：1形体表示的数据构造简单。 2简化了形体的集合运算。只需同时遍历参与集合运算的两形体相应的八叉树，无需进展复杂的求交运算。 3简化了隐藏线

4、或面的消除，由于在八叉树表示中，形体上各元素已按空间位置排成了一定的顺序。 4分析算法适宜于并行处置。八叉树表示的缺陷：占用的存储多，只能近似表示形体，以及不易获取形体的边境信息等。012356712337（a）（b）（c）具有子孙的节点空节点实节点图3.2.4 用八叉树表示形体 2构造表示。通常有扫描表示、构造实体几何表示和特征表示三种。 (a)扫描表示。基于一个基体普通是一个封锁的平面轮廓沿某一途径运动而产生形体。 扫描是生成三维形体的有效方法 用扫描变换产生的形体能够出现维数不一致的问题。 扫描方法不能直接获取形体的边境信息，表示形体的覆盖域非常有限。扫描方向基面回转轴基面基面基面（a）

5、（b）（c）（d）图3.2.5 生成扫描形体的例子（a）（b）（c）（d）图3.2.6 生成扫描体时维数不 一致的情况(b)构造实体几何表示(CSG).经过对体素定义运算而得到新的形体的一种表示方法。体素可以是立方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正那么集合运算并、交、差。CSG表示可以看成是一棵有序的二叉树。其终端节点或是体素、或是形体变换参数。非终端结点或是正那么的集合运算，或是变换平移和/或旋转操作，这种运算或变换只对其紧接着的子结点子形体起作用。差（-）差（-）212平移xxx=体素图3.2.7 CSG表示 CSG树是无二义性的，但不是独一的. CSG表示的优点： 数据构

6、造比较简单，数据量比较小，内部数据的管理比较容易； CSG表示可方便地转换成边境Brep表示； CSG方法表示的形体的外形，比较容易修正。 CSG表示的缺陷： 对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。 对形体的部分操作不易实现，例如，不能对根本体素的交线倒圆角； 由于形体的边境几何元素点、边、面是隐含地表示在CSG中，故显示与绘制CSG表示的形体需求较长的时间。 (c)特征表示 从运用层来定义形体，因此可以较好的表达设计者的意图。从功能上可分为外形、精度、资料和技术特征。特征是面向运用、面向用户的。特征模型的表示依然要经过传统的几何

7、外型系统来实现。不同的运用领域，具有不同的运用特征。在几何外型系统中，根据特征的参数我们并不能直接得到特征的几何元素信息，而在对特征及在特征之间进展操作时需求这些信息。特征方法表示形体的覆盖域受限于特征的种类。特征造型器几何造型器特征模型几何模型用户应用系统图3.2.8 基于特征的造型系统WLHHRHR（a）方块（b）圆柱（c）圆锥图3.2.9 特征形状表示 构造表示的特点： 构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺陷， 但是，便于用户输入形体，在CAD/CAM系统中，通常作为辅助表示方法。 3边境表示BR表示或BRep表示 按照体面环边点的层次，详细记录了构成形体的一

8、切几何元素的几何信息及其相互衔接的拓扑关系。 边境表示的一个重要特点是在该表示法中，描画形体的信息包括几何信息Geometry和拓扑信息Topology两个方面。 拓扑信息描画形体上的顶点、边、面的衔接关系，拓扑信息构成物体边境表示的“骨架。 形体的几何信息犹如附着在“骨架上的肌肉。U图3.2.10 边界表示 Brep表示的优点是： 表示形体的点、边、面等几何元素是显式表示的，使得绘制Brep表示的形体的速度较快，而且比较容易确定几何元素间的衔接关系； 容易支持对物体的各种部分操作，比如进展倒角。 便于在数据构造上附加各种非几何信息，如精度、外表粗糙度等。 Brep表示的缺陷是： 数据构造复杂

9、，需求大量的存储空间，维护内部数据构造的程序比较复杂； Brep表示不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效性、正那么性等。 Brep表示覆盖域大，原那么上能表示一切的形体，而且易于支持形体的特征表示等，Brep表示已成为当前CAD/CAM系统的主要表示方法。3.2.3 形体的边境表示模型 3.2.3.1 边境表示的根本实体边境表示的根本实体 边境模型表达形体的根本拓扑实体包括：边境模型表达形体的根本拓扑实体包括： 1. 顶点顶点 2. 边。边有方向，它由起始顶点和终止边。边有方向，它由起始顶点和终止顶点来界定。边的外形顶点来界定。边的外形Curve由边的由边的几何

10、信息来表示，可以是直线或曲线，几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描曲线边可用一系列控制点或型值点来描画，也可用显式、隐式或参数方程来描画，也可用显式、隐式或参数方程来描画。画。3. 环。环Loop是有序、有向边Edge组成的封锁边境。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。4.面。面Face由一个外环和假设干个内环可以没有内环来表示，内环完全在外环之内。假设一个面的外法矢向外，称为正向面；反之，称为反向面。 面的外形可以是平面或曲面。平面可用平面方程来描画，曲面可用控制多边形或型值点来描画，也可用曲面方程隐式、显式或参数方式来

11、描画。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进展。 5.体。体Body是面的并集。3.2.3.2 边境表示的数据构造 翼边数据构造：在1972年，由美国斯坦福大学Baumgart作为多面体的表示方式提出。 它用指针记录了每一边的两个邻面即左外环和右外环、两个顶点、两侧各自相邻的两个邻边即左上边、左下边、右上边和右下边，用这一数据构造表示多面体模型是完备的，但它不能表示带有准确曲面边境的实体。左下边右下边 右上边左上边边左外环右外环图3.2.11 翼边数据结构 辐射边：为了表示非正那么形体，1986年，Weiler提出

12、了辐射边Radial Edge数据构造。 辐射边构造的形体模型由几何信息和拓扑信息两部分组成。 几何信息有面face、环loop、边edge和点vertex 拓扑信息有模型model、区域region、外壳shell、面援用face use、环援用loop use、边援用edge use和点援用vertex use。 点是三维空间的一个位置 边可以是直线边或曲线边，边的端点可以重合。 环是由首尾相接的一些边组成，而且最后一条边的终点与第一条边的起点重合；环也可以是一个孤立点。外壳是一些点、边、环、面的集合； 外壳是一些点、边、环、面的集合。 区域由一组外壳组成。 模型由区域组成。modelre

13、gionface useloop useedge usevertex usefaceloopedgevertex图3.2.12 辐射边数据结构shellgeometrytopology剖切平面中心线中心线实体图3.2.13 一个用辐射边结构表示的非正则形体模型清华大学国家CAD工程中心开发的几何外型系统GEMS5.0中，采用的数据构造如图体组特征表示单体(零件)面组面线框环环边边顶点曲 面曲 线点实体几何数据实体拓扑数据参数域曲线 该数据构造基于线框、外表、实体和特征一致表示，且具有以下特点： 1采用自顶向下的设计思想。在形体的表示上，遵照了从大到小，分解表示的原那么； 2支持非流形形体的表示

14、； 3实体拓扑数据与几何数据双链表衔接，存放紧凑； 4可以支持特征外型。3.2.3.3 欧拉操作 对于恣意的简单多面体，其面(f)、边(e)、顶点(v)的数目满足 欧拉公式 v - e + f = 2 对于恣意的正那么形体，引入形体的其它几个参数：形体一切面上的内孔总数(r)、穿透形体的孔洞数(h)和形体非连通部分总数(s)，那么形体满足公式： v - e + f = 2(s-h) + r 修正正程中保证各几何元素的数目坚持这个关系式不变，这一套操作就是欧拉操作。 最为常用的几种欧拉操作有： (1)mvsf(v,f)，生成含有一个点的面，并且构成一个新的体。 (2)kvsf，删除一个体，该体仅

15、含有一个点的面。 (3)mev(v1,v2,e)，生成一个新的点v2，衔接该点到已有的点v1，构成一条新的边。 (4)kev(e,v)，删除一条边e和该边的一个端点v。 (5)mef(v1,v2,f1,f2,e)，衔接面f1上的两个点v1、v2，生成一条新的边e，并产生一个新的面。(6)kef(e)，删除一条边e和该边的一个邻面f。(7)kemr(e)，删除一条边e，生成该边某一邻面上的一新的内环。(8)mekr(v1,v2,e)，衔接两个点v1、v2，生成一条新的边e，并删除掉v1和v2所在面上的一个内环。(9)kfmrh(f1,f2)，删除与面f1相接触的一个面f2，生成面f1上的一个内环

16、，并构成体上的一个通孔。(10)mfkrh(f1,f2)，删除面f1上的一个内环，生成一个新的面f2，由此也删除了体上的一个通孔。为了方便对形体的修正，还定义了两个辅助的操作：公共端点。(11)semv(e1,v,e2)，将边e1分割成两段，生成一个新的点v和一条新的边e2。(12)jekv(e1,e2)，合并两条相邻的边e1、e2，删除它们的公共端点。以上十种欧拉操作和两个辅助操作，每两个一组，构成了六组互为可逆的操作。可以证明：欧拉操作是有效的，即用欧拉操作对形体操作的结果在物理上是可实现的；欧拉操作是完备的，即任何形体都可用有限步骤的欧拉操作构造出来。3.2.3.4 集合运算 正那么集与

17、正那么集合运算算子 规定正那么形体是三维欧氏空间中的正那么集合，因此可以将正那么几何形体描画如下： 设G是三维欧氏空间中的一个有界区域，且GbGiG，其中bG是G的n1维边境，iG是G的内部。G的补空间cG称为G的外部，此时正那么形体G需满足： 1bG将iG和cG分为两个互不连通的子空间； 2bG中的恣意一点可以使iG和bG连通； 3bG中任一点存在切平面，其法矢指向cG子空间 4bG是二维流形。 设是集合运算算子交、并或差，R3中恣意两个正那么形体A、B作集合运算：R=AB 运算结果R仍是R3中的正那么形体，那么称为正那么集合算子。 正那么并、正那么交、正那么差分别记为*，*、-*。 分类 Tilove对分类问题的定义为：设S为待分类元素组成的集合，G为一正那么集合，那么S相对于G的成员分类函数为： C(S,G)=S in G，S out G，S on G 其中，S in G=SiG，S out G=ScG，S on G=SbG， 集合运算算法 包括以下几部分： (1)求交：参与运算的一个形体的各拓扑元素求交，求交的顺序采用低维元素向高维元素进展。用求交结果产生的新元素维数低于参与求交的元素对求交元素进展划分，构成一些子元素。 (2)成环：由求交得到的交线将原形体的面进展分割，构成一些新的面环。再加上原形体的悬边、悬点经求交后得到的各子拓扑元素，构成一拓扑元素生成集。