三维实体模型中B_Rep或CSG表示法的一种CC++语言的数据结构定义 下载本文

下一条边,余类推。

由于翼边结构边的构造和使用比较复杂,后来在此结构基础上改进,提出了半边数据结构。半边结构已成为边界表示的主流数据结构。

半边数据结构

实体的B-rep表示模型是一非常复杂的模型,要求能够表达出多面体各几何元素之间完整的几何和拓扑关系,并且允许对这种几何和拓扑关系进行修改.在B-rep表示中,体、面、边和顶点是最基本的几何元素,在实体的拼合、显示、分析计算或人机交互过程中,对基本几何元素的下列操作是必不可少的:

.增加或删除体、面、边或顶点;

.已知一个体,查找它的所有面、所有边或所有顶点;

.已知一个面或一个边,查找它所属于的体;

.已知一个面,顺序查找围成它所有边;

.已知一个边,查找交于该边的所有面,或着查找该边的邻边,或者查找该边的两个端点;

.已知一个顶点,查找交于该顶点的所有边或所有面.

以上这些基本操作的效率直接影响着整个实体造型系统的效率。一个B-rep数据结构应当方便、迅速地实现几何元素的这些查询或增删操作.为了查询或操作方便,必须建立各几何元素间的拓扑关系,且引入其它辅助元素,例如在许多B-rep数据结构中具有环结点,用来表示面的内、外封闭边界.在B-rep的数据结构设计时,除了需要考虑时间的因素外,还要考虑空间的因素,即模型所占计算机内存的大小,但往往这两方面是互相矛盾的.要想各个几何元素之间查询迅速,必然要在它们之间建立广泛的联系,这样必然增加存储空间的占用量.反过来也是如此,而半边数据结构就很好的权衡了空间和时间的问题。

在构成多面体的三要素(点、边、面)中,半边数据结构仍以边为核心,但为了方便表达拓扑关系,它将一条边表示成拓扑意义上方向相反的两条“半边”,所以称为半边数据结构,其结构如图:

半边数据结构共包含六个结点:体、面、环、边、半边和顶点.半边是一连接两个顶点并具有一固定方向的线段.一系列首尾相连的半边形成一个环.半边的关系是一个边包含两个相反方向的半边,由这两个半边可以查询交于这个边的两个面。半边的含义如上图所示.半边数据结构的优点是几何元素之间的互相查询非常方便,不足之处是由于结点多占用空间较大。

半边数据结构的六个结点在C语言中被表达成“结构”.结点之间通过结构指针互相联系.这些结点描述如下:

顶点结点:顶点结点是半边数据结构中最底层的结点,实体的几何位置和尺寸最终都由顶点结点来定义.所以,顶点结点必须包含顶点的空间三维坐标值

半边结点:半边结点包含指向前趋半边和后继半边的两个指针.这两个指针形成了一个环内半边的双向链表.半边结点还包含半边所属于的环的指针,以及半边起始顶点的指针.

边结点:边结点包含左右两个半边的指针,通过这两个指针可以查找该边的两个端点以及交于该边的两个面.指向前趋边和后继边的两个指针实现一个实体内边的双向链表.

环结点:因为一个环包含一系列的首尾相接的半边,故环结点是一个指向这些半边其中之一的指针,通过该指针可以查找构成该环的所有半边.环结点还包含指向前趋和后继环的两个指针,用以实现一个面内环的双向链表.另外,环结点还包含指向环所在面的指针.

面结点:因为面是由若干个环围成的内部连通的平面多边形,所以,面结点包含一个环的首指针,用来查找围成它的所有环.因为外环只有一个,为了区分内环和外环,面结点中包含指向它的外环的指针.面的前趋指针和后继指针形成

一个实体内面的双向链表.面结点中还包含指向它所属于的体的指针,用来查询面所属于的实体.面所在平面的方程也是定义完整实体的重要内容,所以,面结点中包含一个四个浮点数的数组,表示其平面方程.

体结点:在半边数据结构中,体结点是各种引用的根结点.从体结点出发,可以搜索任何其它的结点.所以,体结点,包含面、边和顶点的首指针.体结点之间也是通过前趋指针和后继指针形成的双向链表来连接。

从图中可以看出,许多几何元素可以有不同的搜索路径,例如查找实体上的顶点可以有两个路径:一是体→面→环→半边→顶点;二是体→顶点.第二个路径比第一个路径要简捷得多,用来进行实体的平移等整体操作;第一个路径一般用作局部查找。

为了表示非正则形体,1986年,Weiler提出了辐射边(Radial Edge)数据结构。辐射边结构的形体模型由几何信息(Geometry)和拓扑信息(Topology)两部分组成。几何信息有面(face)、环(loop)、边(edge)和点(vertex),拓扑信息有模型(model)。

区域(region)、外壳(shell)、面引用(face use)、环引用(loopuse)、边引用(edge use)和点引用(vertex use)。这里点是三维空间的一个位置,边可以是直线边或曲线边,边的端点可以重合。环是由首尾相接的一些边组成,而且最后一条边的终点与第一条边的起点重合;环也可以是一个孤立点。外壳是一些点、边、环、面的集合;外壳所含的面集有可能围成封闭的三维区域,从而构成一个实体;外壳还可以表示任意的一张曲面或若干个曲面构成的面组;外壳

还可以是一条边或一个孤立点。外壳中的环和边有时被称为“线框环”和“线框

边”,这是因为它们可以用于表示形体的线框图。区域由一组外壳组成,而模型由区域组成。