10.2 半边数据结构
当实体以边界模型存储时，翼边结构较好地描述了点、边、面 之间的拓扑关系，但它也存在着一些缺陷。因此，人们提出了 一种更完善的数据结构——半边数据结构，简称半边结构。
10.2.1 半边数据结构描述
10.2.2 半边结构程序描述 10.2.3 半边数据结构的具体算法
10.2.1 半边数据结构描 *addhe(e,v,where,sign) Edge *e;
Vertex *v; HalfEdge *where; int { HalfEdge *he; if(where->edg==NULL) he=where; else { sign;
he=(HalfEdge*)new(HALFEDGE,NULL
5种节点Solid、Face、Loop、HalfEdge和Vertex的描述：
① Solid 节点Solid构成一个半边结构引用的根节点。在任意时刻，会 存在几个数据结构引用，为了存取其中的一个，需要指向其Solid节点 的指针。通过指向3个双向链表的指针，Solid节点给出对该模型的面、 边和顶点的访问。所有实体被链接到一个双向链表中，这个表通过指 向该表的后继和前驱实体的指针来实现。
);
where->prv->nxt=he; he->prv=where->prv; where->prv=he; he->nxt=where; } he->edg=e; he->vtx=v; he->wloop=where->wloop; if(sign==PLUS) e->he1=he; else e->he2=he; return(he); }
struct face { Id faceno; /*face identifier*/ Solid *fsolid; /*back pointer to solid*/ Loop *flout; /*pointer to outer loop*/ Loop *floops; /*pointer to list of loops*/ vector feq; /*face equation*/ Face *nextf; /*pointer to next face*/ Face *prevf; /*pointer to previous face*/ }; struct loop { HalfEdge *lege; /*pointer to ring of halfedges*/ Face *lface; /*back pointer to face*/ Loop *nextl; /*pointer to next loop*/ Loop *prevl; /*pointer to previous face*/ };
struct solid { Id Solidno; /*solid identifier*/ Face *sfaces; /*pointer to list faces*/ Edge *sedges; /*pointer to list of vertices*/ Vertex *sverts; /*pointer to list of solid*/ Solid *nexts; /*pointer to next solid*/ Solid *prevs; /*pointer to previous solid*/ };
⑤ Vertex 节点Vertex包含一个由4个浮点数表示的向量，它以齐 次坐标形式表示三维空间的一个点。该节点指向后继顶点和前驱顶 点。
图10.1 半边数据结构节点间的层次关系
使用附加的节点类型Edge来记录信息
① Edge 节点Edge使两个半边相互联系。直观地讲，它将一个全边的 两半组合在一起。它由指向“左”半边和“右”半边的指针组成。边的 双向链表通过指向后继边和前驱边的指针来实现。 ② Half Edge 每个半边包含一个指向其他边的附加指针。 ③ Vertex 每个顶点包含一个附加指针来指向起源于它的某一个半边。 为了表示顶点的标识，以某特殊点做角点的所有小面必须(通过环和半边) 引用那个点对应的Vertex节点。
10.3 欧拉操作
已知多面体的欧拉不变性定理，即对于一个顶点数为v、面数 为f、边数为e的多面体，恒有如下性质： ve+f = 2 （欧拉公式）
为了适应在数据结构中对各数据项的操作，在欧拉公式中引入 另外3个参数： s：实体的个数。 h：实体所含孔的个数。 r：实体中面所含孔(内环)的个数。 于是，欧拉公式扩展为 ve+f=2(sh)+r (扩展的欧拉公式)
10.2.3.2 边上的存取
重要的，有用的宏定义： #define mate(he) ((he= =he->edg->he1)?he->edg>he2:he->edg->he1)
10.2.3.3 半边结构中数据的增删算法 （1） 增加结点new例程
unsigned nodesize[ ]= { sizeof(Solid), sizeof(Face), sizeof(Loop), sizeof(HalfEdge), sizeof(Edge), sizeof(Vertex), 0; };
图10.2 半边的标识法
10.2.2 半边结构程序描述
ypedef float vector[4]; typedef float matrix[4][4]; typedef short Id; typedef struct solid Solid; typedef struct face Face; typedef struct loop Loop; typedef struct halfedge HalfEdge; typedef struct vertex Vertex; typedef struct edge Edge; typedef union nodes Node;
③ Loop 节点Loop描述前面讨论的一个用于连接的边界。它具有一个 指向其他面的指针，一个指向构成边界的半边(Half Edge)之一的指针， 和指向该面的后继Loop和前驱Loop的指针。
④ Half Edge 节点Half Edge表示一个Loop的一条线段。它由在Loop 方向上一个指向其他Loop的指针和一个指向该线段起始顶点的指针 组成。指向Half Edge前驱和后继的指针实现一个Loop的半边(Half Edge)的双向链表，这样，线段的最后顶点可用做后继半边(Half Edge) 的起始顶点。
struct vertex { Id vertexno; /*vertex identifier*/ HalfEdge *vedge; /*pointer to a halfedge*/ vector vcoord; /*vertex coordinates*/ Vertex *nextv; /*pointer to next vertex*/ Vertex *prevv; /*pointer to previous vertex*/ }; /*return values and misc constants*/ union nodes #define ERROR 1 { # define SUCCESS 2 Solid s; #define PI 3.141592653289793 Face f; Loop l; /*node type parameters for memory allocation routines*/ HalfEdge h; # define SOLID 0 Vertex v; # define FACE 1 Edge e; # define LOOP 2 }; # define HALFEDGE 3 #define EDGE 4 #define VERTEX 5
第十章 实体造型中的基本算法 及特征造型
10.1 10.2 10.3 10.4 10.5 10.6 概述 半边数据结构 欧拉操作 基本体元的生成 实体的布尔操作 特征造型
10.1 概述
计算机辅助设计的发展：
1. 二维绘图软件的发展 2. 分离的详细设计软件的发展，并向 CAM延伸 3. 全关联的并行设计软件的发展，并 向初步设计阶段延伸
struct edge { HalfEdge *he1; /*pointer to right halfedge*/ HalfEdge *he2; /*pointer to left halfedge*/ Edge *nexte; /*pointer to next edge*/ Edge *preve; /*pointer to previous edge*/ };
如图10.3(a)中，v=8、e=12、f=6、s=1、h=0，满足扩展的欧拉 公式。图10.3(b)中，v=14、e=21、f=9、s=1、h=1、r=2，也满 足扩展的欧拉公式。
图10.3 两个实体
10.3.1 基本欧拉操作
符号说明： M(make)：增加 K(kill)：删除 V(vertex)：顶点 E(edge)：边 F(face)：面 S(solid)：实体 H(hole)：孔 R(ring)：环
struct halfedge { Edge *edg; /*pointer to parent edge*/ Vertex *vex; /*pointer to starting vertex*/ Loop *wloop; /*back pointer to loop*/ HalfEdge *nxt; /*pointer to next halfedge*/ HalfEdge *prv; /*pointer to previous halfedge*/ };
基本欧拉操作一般包括如下5对： MVFS； Mev；Mef； Mekr； Kfmrh； KVFS； KEV； KEF； KEMR； MFKRH；
1.
MVFS
MVFS生成一个solid，它只包含一个顶点和一个面，没有环和 边。这个面包在顶点的外面。MVFS是用于创建一个实体的初 操作。