10.2 半边数据结构
当实体以边界模型存储时，翼边结构较好地描述了点、边、面之间的拓扑关系，但它也存在着一些缺陷。因此，人们提出了一种更完善的数据结构——半边数据结构，简称半边结构。
10.2.1 半边数据结构描述
定义一个平面模型，它是顶点N、边A和多边形R的一个平面有向图{N,A,R}。为了表示{N,A,R}，将使用一种五级层次的数据结构。它是由5种节点Solid、Face、Loop、HalfEdge和Vertex组成的。各节点描述如下：
① Solid 节点Solid构成一个半边结构引用的根节点。在任意时刻，会存在几个数据结构引用，为了存取其中的一个，需要指向其Solid节点的指针。通过指向3个双向链表的指针，Solid节点给出对该模型的面、边和顶点的访问。所有实体被链接到一个双向链表中，这个表通过指向该表的后继和前驱实体的指针来实现。
② Face 节点Face对应用半边结构表示的多面体的一个小平面。在GS-CAD中，一个Face定义为一个内部连通的平面多边形。将具有多个边界的小面也包括在数据结构中，这样每个小面与一个环表(Loops)相联系，而每个环表示该小面的一条多边形边界曲线。
由于所有小面都表示平面多边形，则一个环(Loop)可指定为“外部”边界，而其他则表示小面的“孔”。这可用两个指向Loop节点的指针实现。一个指向“外部”边界，而另一个指向该面的所有环(Loop)组成的双向链表的首环(Loop)。通常遵循一个约定，称带孔的环(hole loops)为内环(rings)。
面由一个4个浮点数表示的向量表示其平面方程。为了实现一个实体所有小面的双向链表，每个小面包含了指向该表前趋面和后继面的指针。最后的小面有一个指向其他实体的指针。
③ Loop 节点Loop描述前面讨论的一个用于连接的边界。它具有一个指向其他面的指针，一个指向构成边界的半边(Half Edge)之一的指针，和指向该面的后继Loop和前驱Loop的指针。
④ Half Edge 节点Half Edge表示一个Loop的一条线段。它由在Loop方向上一个指向其他Loop的指针和一个指向该线段起始顶点的指针组成。指向Half Edge前驱和后继的指针实现一个Loop的半边(Half Edge)的双向链表，这样，线段的最后顶点可用做后继半边(Half Edge)的起始顶点。
⑤ Vertex 节点Vertex包含一个由4个浮点数表示的向量，它以齐次坐标形式表示三维空间的一个点。该节点指向后继顶点和前驱顶点。图10.1描述了这种层次结构，其中包括了某些指针的C语言名称。
|
|
|
图10.1 半边数据结构节点间的层次关系 |
除了几个多边形引用同一个Vertex节点外，图10.1并没有直接说明各个小面是如何相互联系的。在此将附加一个节点类型来标记面与面的关系，这些关系是用它们的线段标识来表示的。一个有效的平面模型的每一条边是精确地用一条邻边来标识的。因此，每一个半边应精确地用另一个半边相联系。使用附加的节点类型Edge来记录此信息。正如下面所述，添加几个数据项到层次结构的某些节点上来充分开发标识信息。
① Edge 节点Edge使两个半边相互联系。直观地讲，它将一个全边的两半组合在一起。它由指向“左”半边和“右”半边的指针组成。边的双向链表通过指向后继边和前驱边的指针来实现。
② Half Edge 每个半边包含一个指向其他边的附加指针。
③ Vertex 每个顶点包含一个附加指针来指向起源于它的某一个半边。为了表示顶点的标识，以某特殊点做角点的所有小面必须(通过环和半边)引用那个点对应的Vertex节点。
从小面边界信息中分离的标识信息构成一个全翼边节点在3个节点处的划分，使各种特殊情况的表示变得十分自然。例如，在一个小面上出现两次的一条边，应表示为引用同一条边的两个半边,即可认为“右”半边具有正向，而“左”半边具有负向。
|
|
|
图10.2 半边的标识法 |
图10.2将标识信息的表示法形象化，其中也给出了某些所需要的指针的C标识符。Half Edge、Edge和Vertex3个节点构成了整个数据结构的最核心部分。
在此允许只带一个顶点而没有边的空环(empty loop)的特殊情况。在半边数据结构中，空环用一个半边来表示。该半边的顶点指针指向单个顶点，而该半边的边指针是NULL。指向后继和前驱半边的指针引用该半边本身。这种额外的半边不与线段对应。值得注意的是，空环显然不能用图10.1的层次来表示。