资源预览内容
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
亲,该文档总共8页全部预览完了,如果喜欢就下载吧!
资源描述
3. 平时作业完成三维实体模型中B_Rep或CSG表示法的一种C/C+语言的数据结构定义。物体的CSG树表示物体的体素构造表示法(Constructive Solid Geometry, CSG)是用两个物 体间的并、交、差正则集合运算操作生成一个新的物体的方法。CSG表示法:先定义一些形状比较简单的常用体素,如方块、圆柱、圆锥、球、 棱柱等。然后用集合运算并、交、差把体素修改成复杂形状的形体。早期的CSG 模型仅使用代数方程及半空间的概念,体素只支持多面体与二次曲面体,而不支 持表面含有自由曲面的实体。整个模型是棵树结构,最终形体的表面交线与有效 区域没有显式给出,不能直接用于NC加工与有限元分析等后继处理。集合运算构造实体的过程可用二叉树结构表示,称该二叉树为CSG树。树的叶节 点表示体素或带有几何变换参数的体素,非叶节点表示施加于其子节点的正则集 合算子,或称布尔算子。树的根节点表示集合运算的最终结果,也即希望得到的 实体。边界表示法边界表示法(Brep-Boundary Representation)通过描述物体的边界来表示 一个物体。所谓的边界是指物体的内部点与外部点的分界面,定义了物体的边界, 该物体也就被唯一地定义了。如下图:边界表示法一个重要的特点是:描述物体的信息包括几何信息与拓扑信息两 个方面。几何信息是指物体在欧氏空间中的位置、形状和大小;而拓扑信息是指 拓扑元素(顶点、边和表面)的数量及其相互间的连接关系。拓扑信息构成物体 的“骨架”,而几何信息则犹如附着在这一 “骨架”上的“肌肉”。几何信息有面(face)、环(loop)、边(edge)和点(vertex),拓扑信息 有模型(model)、区域(region)、外壳(shell)、面引用(face use)、环引 用(loop use)、边引用(edge use)和点引用(vertex use)。如下图是用辐射 边数据结构表示的一个形体模型,注意其中实体、面、线是用统一的数据结构表 示的。顶点顶点(Vertex)的位置用(几何)点(Point)来表示。点是几何造型中的 最基本的元素,自由曲线、曲面或其它形体均可用有序的点集表示。用计算机存 储、管理、输出形体的实质就是对点集及其连接关系的处理。在正则形体定义中,不允许孤立点存在。边边(Edge)是两个邻面(对正则形体而言)、或多个邻面(对非正则形体而言) 的交集,边有方向,它由起始顶点和终止顶点来界定。边的形状(Curve)由边 的几何信息来表示,可以是直线或曲线,曲线边可用一系列控制点或型值点来描 述,也可用显式、隐式或参数方程来描述。形体中与一条空间曲线相联系,以及 包含其两个端点和引用它的所有环边等信息的拓扑元素称为边。环环(Loop)是有序、有向边(Edge)组成的封闭边界。环中的边不能相交, 相邻两条边共享一个端点。环有方向、内外之分,外环边通常按逆时针方向排序, 内环边通常按顺时针方向排序。面面(Face)由一个外环和若干个内环(可以没有内环)来表示,内环完全在 外环之内。根据环的定义,在面上沿环的方向前进,左侧总在面内,右侧总在面 外。面有方向性,一般用其外法矢方向作为该面的正向。若一个面的外法矢向外, 称为正向面;反之,称为反向面。面的形状(Surface)由面的几何信息来表示, 可以是平面或曲面,平面可用平面方程来描述,曲面可用控制多边形或型值点来 描述,也可用曲面方程(隐式、显式或参数形式)来描述。对于参数曲面,通常 在其二维参数域上定义环,这样就可由一些二维的有向边来表示环,集合运算中 对面的分割也可在二维参数域上进行。体体(Body)是面的并集。在正则几何造型系统中,要求体是正则的,非正则 形体的造型技术将线框、表面和实体模型统一起来,可以存取维数不一致的几何 元素,并可对维数不一致的几何元素进行求交分类,从而扩大了几何造型的形体 覆盖域。几何形体是由封闭表面围成的空间,是欧氏空间中非空、有界的封闭 子集,其边界是有限个面的并集。外壳外壳是一些点、边、环、面的集合,其所含的面集有可能围成封闭的三维区 域,从而构成一个实体;外壳还可以表示任意的一张曲面或若干个曲面构成的面 组;外壳还可以是一条边或一个孤立点。外壳中的环和边有时被称为“线框环” 和“线框边”,这是因为它们可以用于表示形体的线框图。区域由一组外壳组成,而模型由区域组成。正则形体对于任一形体,如果它是三维欧氏空间R3中非空、有界的封闭子集,且其 边界是二维流形(即该形体是连通的),则称该形体为正则形体,否则称为非正则 形体。在这种表示法中,由于物体的点、边和表面以独立对象的形式的存在,所以 可以方便地对物体进行各种局部修改。多面体的顶点、边和表面之间的拓扑关系可用9种不同的形式予以描述:1. 顶点相邻性,表示v-v2. 顶点一边相邻性,表示v-e3. 顶点一面相邻性,表示v-f4. 边一顶点,e-v5. 边边e-e6. 边一面e-f7. 面一顶点f-v8. 面边f-e9. 面一面f-f边界表示的数据结构两种典型的边界表示法数据结构主要包括:翼边结构,双向边表 (DCEL -Doubly Connected Edge List),半边结构,四边结构,辐射边(Radial-Edge) 结构等等。其中半边结构非常适合表示正则形体。翼边结构在顶点、边、表面等组成物体的三要素中,翼边结构以边为中心来组织数据。如下图:Vertex P1,P2;Loop *LeftLoop,*RightLoop;struct Edge *ercw,*ercc,*elcc,*elcw;上图菱边e作为有向线段,其数据结构中包含有两个指针,分别指向e的两 个端点:起点P1和终点P2。此外,e中还设置有两个环指针,分别指向菱边e 所邻接的两表面上的环Loop左和Loop右。这样就确定了菱边e与相邻表面之间 的拓扑关系。为了能从边e出发找到它所在的任一闭合面环上的其他菱边,在e 中又增加了四个边指针ercw、ercc、elcc、elcw, ercc表示e在右面环中沿逆 时针方向所连接的下一条菱边,elcw表示e在左面环中沿顺时针方向所连接的 下一条边,余类推。由于翼边结构边的构造和使用比较复杂,后来在此结构基础上改进,提出了 半边数据结构。半边结构已成为边界表示的主流数据结构。半边数据结构实体的B-rep表示模型是一非常复杂的模型,要求能够表达出多面体各几何 元素之间完整的几何和拓扑关系,并且允许对这种几何和拓扑关系进行修改.在 B-rep表示中,体、面、边和顶点是最基本的几何元素,在实体的拼合、显示、 分析计算或人机交互过程中,对基本几何元素的下列操作是必不可少的:.增加或删除体、面、边或顶点;.已知一个体,查找它的所有面、所有边或所有顶点;.已知一个面或一个边,查找它所属于的体;.已知一个面,顺序查找围成它所有边;.已知一个边,查找交于该边的所有面,或着查找该边的邻边,或者查找该 边的两个端点;.已知一个顶点,查找交于该顶点的所有边或所有面.以上这些基本操作的效率直接影响着整个实体造型系统的效率。一个B-rep 数据结构应当方便、迅速地实现几何元素的这些查询或增删操作.为了查询或操 作方便,必须建立各几何元素间的拓扑关系,且引入其它辅助元素,例如在许多 B-rep数据结构中具有环结点,用来表示面的内、外封闭边界.在B-rep的数据 结构设计时,除了需要考虑时间的因素外,还要考虑空间的因素,即模型所占计 算机内存的大小,但往往这两方面是互相矛盾的.要想各个几何元素之间查询迅 速,必然要在它们之间建立广泛的联系,这样必然增加存储空间的占用量.反过 来也是如此,而半边数据结构就很好的权衡了空间和时间的问题。在构成多面体的三要素(点、边、面)中,半边数据结构仍以边为核心,但 为了方便表达拓扑关系,它将一条边表示成拓扑意义上方向相反的两条“半边”, 所以称为半边数据结构,其结构如图:KA半边数据结构共包含六个结点:体、面、环、边、半边和顶点.半边是一连 接两个顶点并具有一固定方向的线段.一系列首尾相连的半边形成一个环.半边 的关系是一个边包含两个相反方向的半边,由这两个半边可以查询交于这个边的 两个面。半边的含义如上图所示.半边数据结构的优点是几何元素之间的互相查 询非常方便,不足之处是由于结点多占用空间较大。半边数据结构的六个结点在C语言中被表达成“结构”.结点之间通过结构 指针互相联系.这些结点描述如下:顶点结点:顶点结点是半边数据结构中最底层的结点,实体的几何位置和尺 寸最终都由顶点结点来定义.所以,顶点结点必须包含顶点的空间三维坐标值半边结点:半边结点包含指向前趋半边和后继半边的两个指针.这两个指针 形成了一个环内半边的双向链表.半边结点还包含半边所属于的环的指针,以及 半边起始顶点的指针.边结点:边结点包含左右两个半边的指针,通过这两个指针可以查找该边的 两个端点以及交于该边的两个面.指向前趋边和后继边的两个指针实现一个实体 内边的双向链表.环结点:因为一个环包含一系列的首尾相接的半边,故环结点是一个指向这 些半边其中之一的指针,通过该指针可以查找构成该环的所有半边.环结点还包 含指向前趋和后继环的两个指针,用以实现一个面内环的双向链表.另外,环结 点还包含指向环所在面的指针.面结点:因为面是由若十个环围成的内部连通的平面多边形,所以,面结点 包含一个环的首指针,用来查找围成它的所有环.因为外环只有一个,为了区分 内环和外环,面结点中包含指向它的外环的指针.面的前趋指针和后继指针形成 一个实体内面的双向链表.面结点中还包含指向它所属于的体的指针,用来查询 面所属于的实体.面所在平面的方程也是定义完整实体的重要内容,所以,面结 点中包含一个四个浮点数的数组,表示其平面方程.体结点:在半边数据结构中,体结点是各种引用的根结点.从体结点出发, 可以搜索任何其它的结点.所以,体结点,包含面、边和顶点的首指针.体结点之 间也是通过前趋指针和后继指针形成的双向链表来连接。从图中可以看出,许多几何元素可以有不同的搜索路径,例如查找实体上的 顶点可以有两个路径:一是体一面一环一半边一顶点;二是体一顶点.第二个路 径比第一个路径要简捷得多,用来进行实体的平移等整体操作;第一个路径一般 用作局部查找。为了表示非正则形体,1986年,Weiler提出了辐射边(Radial Edge)数据 结构。辐射边结构的形体模型由几何信息(Geometry)和拓扑信息(Topology) 两部分组成。几何信息有面(face)、环(loop)、边(edge)和点(vertex), 拓扑信息有模型(model )o区域(region)、外壳(shell)、面引用(face use)、环引用(loopuse)、 边引用(edge use)和点引用(vertex use)。这里点是三维空间的一个位置, 边可以是直线边或曲线边,边的端点可以重合。环是由首尾相接的一些边组成, 而且最后一条边的终点与第一条边的起点重合;环也可以是一个孤立点。外壳是 一些点、边、环、面的集合;外壳所含的面集有可能围成封闭的三维区域,从而 构成一个实体;外壳还可以表示任意的一张曲面或若干个曲面构成的面组;外壳 还可以是一条边或一个孤立点。外壳中的环和边有时被称为“线框环”和“线框 边”,这是因为它们可以用于表示形体的线框图。区域由一组外壳组成,而模型 由区域组成。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号