三维CAD——基于B_rep的建模操作
内容来自高老师的《三维CAD建模》课，本文就主要介绍半边结构和欧拉操作以及代码实现。
1. 边界表示法及其数据结构
· 拓扑结构
a.拓扑元素：面、边、点、体
b.拓扑关系：9种。V{V},V{E},V{F}; E{V},E{E},E{F}; F{V},F{E},F{F};
· 几何信息(狭义)：描述物体的大小位置和尺寸等信息。点->坐标；边->方程；面->方程；
· 拓扑与集合元素对应关系
Vertex<-->Point； Edge<-->Curve； Face<-->Surface；
2. 翼边数据结构(Wing-Edge)
定义：一组首尾相连封闭二维区域形成一个环(Loop)
拓扑关系选择：E{V},E{E},E{F},V{E}
翼边结构表示：
通过判定Loop在边的左边还是右边，判断绕向来找到Loop上的所有边。
这种边的结构是不满足二维流形的可定向条件。在这个基础上对翼边的结构进行改进，提出了半边结构的思想，满足了可定向性。
半边结构表示：
半边结构在计算机中的数据结构表示：
虚线代表可以生成线框模型：{V},{E},E{V}
带空的环称为(rings)
核心思想：边在三维模型的表达中是一个重要元素，以边为重点来组织数据结构
3. 基于B-rep的建模操作
3.1 欧拉操作
欧拉操作旨在有效的构建B-rep中的拓扑结构(通用、有效)
欧拉公式：V+F-E=2
扩展：V+F-E=2(S-h)+r，其中S是体的个数，h是柄的个数，r是内环的个数
3.2 欧拉操作的设计思想
基于欧拉公式来保证其有效性。希望提供一组通用、完备的B-rep的拓扑生成操作。我的理解是欧拉操作给模型的拓扑生成提供了完备的理论依据。
3.3 欧拉操作的选择(6维空间的5维超平面)
v e f h r s Operator
1 1 0 0 0 0 mev
0 1 1 0 0 0 mef
1 0 1 0 0 1 mvfs
0 -1 0 0 1 0 kemr
0 0 -1 1 1 0 kfmrh
· mvsf（v, f）： 生成含有一个点的面，并且构成一个新的体
· kvsf： 删除一个体，该体仅含有一个点的面
· mev（v1， v2， e）：生成一个新的点e2，连接该点到已有点v1，构造一条新的边
· kev（e， v）：删除一条边和该边的一个端点v
· mef（v1，v2，f1，f2，e）：连接面f1上的两个点v1，v2，生成一条新边e，并产生一个新面
· kef（e）：删除一条边e和该边的一个邻面f
· kemr（e）：删除一条边e，生成该边某一邻面上的新的内环
· mekr（v1，v2，e）：连接两个点v1、v2、，生成一条新的边e，并删除掉v1和v2所在面上一个内环
· kfmrh（f1，f2,）：删除与面f1相接触的一个面f2，生成面f1上的一个内环，并形成体上的一个通孔
· mfkrh（f1，f2）：删除面f1上的一个内环，生成一个新的面f2，由此也删除了体上的一个通孔
两个辅助操作：
· semv（e1，v，e2）：将e1分割成两段，生成一个新的点v和一条新的边e2
· jekv（e1，e2）：合并两条相邻的边e1、e2，删除它们的公共端点
以上欧拉操作仅适用正则形体
3.4 欧拉操作具体功能与实现
（1）mvfs（）：定义一个体、一个面、一个外环、一个点。
伪代码：
1 OBJECT *mvfs()
2 {
3 FACE *f; OBJECT *ob; LOOP *lp; VERTEX *v;//对以上元素开辟空间
4 ob->sfaces = f; f->fsolid = ob;
5 f->floops = lp; lp->lface = f; lp->ledge = NULL;
6 return ob;
7 }
（2）mev（）：构造一个新点，同是构造一条连接新点与一给定点的边
伪代码：
1 HalfEdge *mev(v1, lp)
2 {
3 HalfEdge *he1, *he2, *he;
4 Edge *eg; VERTEX *v2;
5 he1->edge = he2->edge = eg;
6 eg->he1 = he1; eg->he2 = he2;
7 he1->wloop = he2->wloop = lp;
8 he1->startv = v1;
9 he2->startv = v2;
10 he1->next = he2;
11 if (lp->ledge == NULL)
12 he2->next = he1;
13 lp->ledge = he1;
14 else
15 for (he = lp->ledge; he = next->startv != v1; he = he->next)
16 he2->next = he->next;
17 he->next = he1;
18 return he1;
19 }
这里列出的伪代码是上课讲解的一部分，后面会附上C++的源码。
我自己的理解，关键在于弄懂欧拉操作构造实体时候它的Loop环绕向一定要正确，每个拓扑面的关系，根据这个自己可以很容易的实现上面的伪代码。
3.5 欧拉操作的几个讨论
可以证明：欧拉操作是有效的；用欧拉操作对形体操作结果在物理上是可实现的，欧拉操作是完备的，任何形体可在有限步的欧拉操作中构造出来。
· 所有流形体的B-rep，欧拉操作都能构造
· 在拓扑结构上都有效
· 将其正确嵌入3维空间结果一定是流形体
这些都给CAD模型中流形体的构建提供了理论的依据，所以底层的大厦由此慢慢开始建立，就像数学的光辉殿堂一样，理论的强有力的证明为它带来了严谨而且让人信服的意义。
3.6 扫成操作(Sweeping)
日常生活中的物体都是由基本的长方体、圆柱(70%)以及锥、球等形成
扫成体：有一个平面区域(直线段、圆弧、自由曲线围成的二维曲线)，延一条可定的轨迹线，扫描产生三维空间点集
平移扫成(translational sweeping) 轨迹是一条直线。
几何构造：
· 每一个给定点->新点->新边（侧边）
· 每一个给定边->新边->新面（平面，圆柱面、指纹面，自由曲面）
伪代码：
1 Sweep(S:Solid, F:Face, V:Vector, d:Real)
2 begin:
3 L = loop of F;
4 firstv = first Vertex of L;
5 firstup = firstv + d.v;
6 mev(firstv, firstup, newe);
7 prevup = firstup; nextv = next Vertex of L;
8 while (nextv not equal to firstv)
9 begin:
10 up = nextv + d.v;
11 mev(nextv, up, newe);
12 mef(prevup, up, F, newf, newe);
13 prevup = up; nextv = next Vertex of L;
14 end
15 mef(prevup, firstup, F, newf, newe);
16 end
3.7 相关实际实现代码分析
作业的要求是实现实现基本的欧拉操作，完成带孔正则物体的构造。我采用的是Glut作为显示部分，自己编写半边结构和欧拉操作。总体的模块分为HalfEdgeDS负责半边结构的定义和欧拉操作实现，SolidFactoy负责产生实体Solid通过欧拉操作或Sweep扫成，GlutDisplay负责显示得到的Solid模型。
半边结构的定义：
/************************************************************************/
/* Author: Li Xin */
/* Date: 2013-10-19 */
/************************************************************************/
class Solid;
class Face;
class Loop;
class Edge;
class HalfEdge;
class Vertex;
class Point;
//体
class Solid
{
public:
Solid():prevs(NULL), nexts(NULL), sface(NULL), edge(NULL){}
Solid \*prevs;
Solid \*nexts;
Face \*sface; //首面;
Edge \*edge; //用于线框显示的边 };
//面
class Face
{
public:
Face():prevf(NULL), nextf(NULL), fsolid(NULL), floops(NULL){}
Face \*prevf;
Face \*nextf;
Solid \*fsolid;
Loop \*floops; //首环 };
//环
class Loop
{
public:
Loop():prevl(NULL), nextl(NULL), lface(NULL), ledge(NULL){}
Loop \*prevl;
Loop \*nextl;
Face \*lface;
HalfEdge \*ledge;//首边 };
//半边
class HalfEdge
{
public:
HalfEdge():prev(NULL), next(NULL), adjacent(NULL), startv(NULL), endv(NULL), hloop(NULL), edge(NULL){}
HalfEdge \*prev;
HalfEdge \*next;
HalfEdge \*adjacent;
Vertex \*startv;
Vertex \*endv;
Loop \*hloop;
Edge \*edge; //边 };
//边
class Edge
{
public:
Edge():preve(NULL), nexte(NULL), HalfEdge1(NULL), HalfEdge2(NULL){}
Edge \*preve;
Edge \*nexte;
HalfEdge \*HalfEdge1;
HalfEdge \*HalfEdge2; };
//几何点
class Point
{
public:
double coord\[3\];
double\* GetCoord()
{
return coord;
}
void SetCoord(double x, double y, double z);
void SetCoord(Point point);
friend inline istream & operator >> (istream & is,Point & point)
{
is >> point.coord\[0\] >> point.coord\[1\] >> point.coord\[2\];
return is ;
}
friend inline ostream& operator << (ostream & os,Point & point)
{
os << "( " << point.coord\[0\] << ", " << point.coord\[1\] << ", " << point.coord\[2\] << " )";
return os ;
} };
//顶点
class Vertex
{
public:
Vertex():prevv(NULL), nextv(NULL) {}
Vertex \*prevv;
Vertex \*nextv;
Point point; };
class Half_Edge_DS
{
public:
Half\_Edge\_DS():solid(NULL){}
~Half\_Edge\_DS();
//数据结构
Solid \*solid;
//欧拉操作
Solid \* mvfs(Point point, Vertex \*& newVertex); //构造一个体,一个面,一个外环,一个点
HalfEdge \* mev(Vertex \*v1, Point p2, Loop \*lp ); //构造一个新点,同时构造一条连接新点与一给定点的边
Loop \* mef(Vertex \*v1, Vertex \*v2, Loop \*lp);//构造一个边,一个面,一个环
Loop \* kemr(Vertex \*v1, Vertex \*v2, Loop \*lp);//删除一条边构造一个环
void kfmrh(Loop \*outlp, Loop \*lp);//删除一个与面f1相接触的一个面f2，声称面f1上的一个面上内环，并形成体上一个通孔};
mvfs的实现：
1 Solid * Half_Edge_DS::mvfs(Point point, Vertex *& newVertex)
2 {
3 //建立点、面、体、环
4 Solid *newSolid = new Solid;
5 Face *newFace = new Face;
6 Loop *newLoop = new Loop;
7
8 newVertex = new Vertex;
9 //记录初始点的几何信息
10 newVertex->point.SetCoord(point);
11
12 //构建拓扑关系
13 newSolid->sface = newFace;
14 newFace->fsolid = newSolid;
15 newFace->floops = newLoop;
16 newLoop->lface = newFace;
17 newLoop->ledge = NULL;
18 return newSolid;
19 }
mev的实现：
1 HalfEdge * Half_Edge_DS::mev( Vertex *v1, Point p2, Loop *lp )
2 {
3 Solid *solid = lp->lface->fsolid;
4 HalfEdge *he1 = new HalfEdge;
5 HalfEdge *he2 = new HalfEdge;
6 HalfEdge *he = new HalfEdge;
7 Edge *edge = new Edge;
8
9 Vertex *v2 = new Vertex;
10 v2->point.SetCoord(p2);
11
12 he1->edge = he2->edge = edge;
13 edge->HalfEdge1 = he1;
14 edge->HalfEdge2 = he2;
15
16 he1->hloop = he2->hloop = lp;
17 he1->startv = v1;
18 he1->endv = v2;
19 he2->startv = v2;
20 he2->endv = v1;
21
22 he1->adjacent = he2;
23 he2->adjacent = he1;
24
25 if (lp->ledge == NULL)
26 {//First create edge
27 he1->next = he2;
28 he2->prev = he1;
29 he2->next = he1;
30 he1->prev = he2;
31 lp->ledge = he1;
32 }
33 else
34 {//Following create edges
35 for (he = lp->ledge; he->next->startv != v1; he = he->next);
36
37 he1->next = he2;
38 he1->prev = he;
39 he2->next = he->next;
40 he2->prev = he1;
41 he->next->prev = he2;
42 he->next = he1;
43 }
44
45 //Maintain Edge List
46 Edge *curEdge = solid->edge;
47 while (curEdge != NULL && curEdge->nexte != NULL)
48 {
49 curEdge = curEdge->nexte;
50 }
51 if (curEdge == NULL) solid->edge = edge;
52 else
53 {
54 curEdge->nexte = edge;
55 edge->preve = curEdge;
56 }
57
58 return he1;
59 }
mef的实现：
1 Loop * Half_Edge_DS::mef( Vertex *v1, Vertex *v2, Loop *lp )
2 {
3 Solid *solid = lp->lface->fsolid;
4 Face *face = new Face;
5 Loop *loop = new Loop;
6 HalfEdge *he1 = new HalfEdge;
7 HalfEdge *he2 = new HalfEdge;
8 Edge *edge = new Edge;
9
10 //Create HalfEdge and Edge
11 he1->startv = v1;
12 he1->endv = v2;
13 he2->startv = v2;
14 he2->endv = v1;
15 he1->adjacent = he2;
16 he2->adjacent = he1;
17
18 edge->HalfEdge1 = he1;
19 edge->HalfEdge2 = he2;
20 he1->edge = he2->edge = edge;
21
22 //Find the HalfEdge
23 HalfEdge *tmphe1, *tmphe2, *tmphe;
24 for (tmphe = lp->ledge; tmphe->startv != v1; tmphe = tmphe->next);
25 tmphe1 = tmphe;
26
27 for (; tmphe->startv != v2; tmphe = tmphe->next);
28 tmphe2 = tmphe;
29 tmphe = tmphe->next;
30 while (tmphe->startv != v2)
31 {
32 tmphe = tmphe->next;
33 }
34 bool HaveRoll = false;
35 if(tmphe != tmphe2)
36 {
37 HaveRoll = true;
38 tmphe2 = tmphe;
39 }
40
41 //for (tmphe2 = lp->ledge; tmphe2->endv != v2; tmphe2 = tmphe2->next);
42
43 // he1->next = tmphe2->next;
44 // he1->prev = tmphe1;
45 // he2->next = tmphe1->next;
46 // he2->prev = tmphe2;
47 // tmphe1->next->prev = he2;
48 // tmphe1->next = he1;
49 // tmphe2->next->prev = he1;
50 // tmphe2->next = he2;
51
52 he1->next = tmphe2;
53 he1->prev = tmphe1->prev;
54 he2->next = tmphe1;
55 he2->prev = tmphe2->prev;
56
57
58 tmphe1->prev->next = he1;
59 tmphe1->prev = he2;
60
61 tmphe2->prev->next = he2;
62 tmphe2->prev = he1;
63
64 //loop have problem
65 ////////////////////////////////////
66 //Inner loop
67 loop->ledge = he1;
68 //Recur loop
69 lp->ledge = he2;
70
71 //Create A new Face
72 face->floops = loop;
73 face->fsolid = solid;
74 loop->lface = face;
75 //Add Face to Solid
76 Face *tmpFace;
77 for (tmpFace = solid->sface; tmpFace->nextf != NULL; tmpFace = tmpFace->nextf);
78 tmpFace->nextf = face;
79 face->prevf = tmpFace;
80 face->fsolid = solid;
81
82
83 //Maintain Edge List
84 Edge *curEdge = solid->edge;
85 while (curEdge != NULL && curEdge->nexte != NULL)
86 {
87 curEdge = curEdge->nexte;
88 }
89 if (curEdge == NULL) solid->edge = edge;
90 else
91 {
92 curEdge->nexte = edge;
93 edge->preve = curEdge;
94 }
95
96 return loop;
97
98 }
其实mef考虑的时候，有两种情况。1.不带内环，3次mev操作然后mef操作；2.带内环mef，在kemr之前的，这时候在寻找半边的时候需要注意一下半边的方向，这里我写的代码判断复杂了，画一个图分析下，也很好改，这里就不再赘述了。
kemr的实现:
1 Loop * Half_Edge_DS::kemr( Vertex *v1, Vertex *v2, Loop *lp )
2 {
3 Face *face = lp->lface;
4 Solid *solid = face->fsolid;
5 Loop *loop = new Loop;
6
7 HalfEdge *he;
8 //find the half edge
9 for (he = lp->ledge; (he->startv != v2) || (he->endv != v1); he = he->next);
10
11 //get related edge
12 Edge *edge;
13 edge = he->edge;
14
15 //create loop relation
16 he->next->prev = he->adjacent->prev;
17 he->adjacent->prev->next = he->next;
18
19 he->prev->next = he->adjacent->next;
20 he->adjacent->next->prev = he->prev;
21
22 lp->ledge = he->next->prev;
23
24 loop->ledge = he->prev;
25 loop->lface = face;
26
27 //insert the inner loop
28 if (face->floops == NULL)
29 face->floops = loop;
30 else
31 {
32 Loop *tmpLoop;
33 for (tmpLoop = face->floops; tmpLoop->nextl != NULL; tmpLoop = tmpLoop->nextl);
34 tmpLoop->nextl = loop;
35 loop->prevl = tmpLoop;
36 }
37
38 //find edge will delete
39 Edge *tmpEdge = solid->edge;
40 while ( tmpEdge != edge)
41 {
42 tmpEdge = tmpEdge->nexte;
43 }
44 //delete edge
45 if (tmpEdge->nexte == NULL)
46 {
47 tmpEdge->preve->nexte = NULL;
48 }
49 else if(tmpEdge->preve == NULL)
50 {
51 solid->edge = tmpEdge->nexte;
52 tmpEdge->nexte->preve = NULL;
53 }
54 else
55 {
56 tmpEdge->preve->nexte = tmpEdge->nexte;
57 tmpEdge->nexte->preve = tmpEdge->preve;
58 }
59 delete tmpEdge;
60 return loop;
61 }
kfmrh的实现：
1 void Half_Edge_DS::kfmrh( Loop *outlp, Loop *lp )
2 {
3
4 Face *face1 = outlp->lface;
5 Face *face2 = lp->lface; // 要删去的顶面 的环，将它降到底面当内环，删去这个面。
6 //add inner loop to face
7 if (face1->floops == NULL)
8 face1->floops = lp;
9 else
10 {
11 Loop *tmpLoop;
12 for (tmpLoop = face1->floops; tmpLoop->nextl != NULL; tmpLoop = tmpLoop->nextl);
13 tmpLoop->nextl = lp;
14 lp->prevl = tmpLoop;
15 }
16 lp->lface = face1;
17
18 //Find the face to remove
19 Solid *solid = face1->fsolid;
20 Face *tmpFace = solid->sface;
21 while ( tmpFace != face2)
22 {
23 tmpFace = tmpFace->nextf;
24 }
25 //delete Face
26 if (tmpFace->nextf == NULL)
27 {
28 tmpFace->prevf->nextf = NULL;
29 }
30 else if(tmpFace->prevf == NULL)
31 {
32 solid->sface = tmpFace->nextf;
33 tmpFace->nextf->prevf = NULL;
34 }
35 else
36 {
37 tmpFace->prevf->nextf = tmpFace->nextf;
38 tmpFace->nextf->prevf = tmpFace->prevf;
39 }
40 delete tmpFace;
41 }
扫成操作：
1 void SolidFactory::Sweep( Face *face, double vec[3], double d )
2 {
3 Solid *solid = face->fsolid;
4 Loop *loop;
5 HalfEdge *he;
6 Vertex *firstv;
7 Vertex *upvertex;
8 Vertex *prevupvertex;
9 Vertex *nextv;
10 Point uppoint;
11 HalfEdge *uphe;
12 HalfEdge *firstuphe;
13
14 for (loop = face->floops; loop != NULL; loop = loop->nextl)
15 {
16 he = loop->ledge;
17 firstv = he->startv;
18 uppoint.SetCoord(firstv->point.coord[0] + d*vec[0],
19 firstv->point.coord[1] + d*vec[1],
20 firstv->point.coord[2] + d*vec[2]);
21 firstuphe = _HalfEdgeDS->mev(firstv, uppoint, loop);
22 prevupvertex = firstuphe->endv;
23 he = he->next;
24 nextv = he->startv;
25 while (nextv != firstv)
26 {
27 uppoint.SetCoord(nextv->point.coord[0] + d*vec[0],
28 nextv->point.coord[1] + d*vec[1],
29 nextv->point.coord[2] + d*vec[2]);
30 uphe = _HalfEdgeDS->mev(nextv, uppoint, loop);
31 upvertex = uphe->endv;
32 _HalfEdgeDS->mef(upvertex, prevupvertex, loop);
33 prevupvertex = upvertex;
34 he = he->next;
35 nextv = he->startv;
36 }
37 _HalfEdgeDS->mef(firstuphe->endv, prevupvertex, loop);
38 }
39 }
总结
这里我认为比较复杂的操作就是mef，kemr的操作，其实只要理解了半边的结构的本质，自己画画拓扑结构图，多多注意Loop的走向，这些问题都是可以迎刃而解的。
这里有一个求是鹰的效果图，其中的点是我用Catia在草图中画好，然后导出坐标来用，扫成实现了最后的效果图，总过有5个实体对象，求是鹰、1、8、9、7。
实体模型图：
线框模型图：
总体来说，仅仅实现了半边结构和欧拉操作的基本功能，不存在特别难懂和实现很费力的地方，出现的小bug调试调试也可以比较轻松的解决，具体实现的过程也学习了不少别人的实现，看到也有写成交互式，通过描绘封闭二维直线区域，指定扫成方向和距离的版本，这些实现的效果都是很不错。但是，自己动手实践的过程能够发掘出很多问题，比如对于Glut的使用，欧拉操作以及模型实现过程中的调试等。中间的代码的细节讲的不是很细，源代码工程请戳这里，brp的格式文件就是solid模型文件。
第一行记录模型vertex个数n，以及num操作个数m，然后n行都是顶点坐标，再接下来m行是相关操作。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章