三维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 }

View Code

（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 }

View Code

这里列出的伪代码是上课讲解的一部分，后面会附上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

View Code

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上的一个面上内环，并形成体上一个通孔
    
};

View Code

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 }

View Code

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 }

View Code

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 }

View Code

　　其实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 }

View Code

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 }

View Code

扫成操作：

 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 }

View Code

总结

　　这里我认为比较复杂的操作就是mef，kemr的操作，其实只要理解了半边的结构的本质，自己画画拓扑结构图，多多注意Loop的走向，这些问题都是可以迎刃而解的。

　　这里有一个求是鹰的效果图，其中的点是我用Catia在草图中画好，然后导出坐标来用，扫成实现了最后的效果图，总过有5个实体对象，求是鹰、1、8、9、7。

实体模型图：

线框模型图：

　　总体来说，仅仅实现了半边结构和欧拉操作的基本功能，不存在特别难懂和实现很费力的地方，出现的小bug调试调试也可以比较轻松的解决，具体实现的过程也学习了不少别人的实现，看到也有写成交互式，通过描绘封闭二维直线区域，指定扫成方向和距离的版本，这些实现的效果都是很不错。但是，自己动手实践的过程能够发掘出很多问题，比如对于Glut的使用，欧拉操作以及模型实现过程中的调试等。中间的代码的细节讲的不是很细，源代码工程请戳这里，brp的格式文件就是solid模型文件。

　　第一行记录模型vertex个数n，以及num操作个数m，然后n行都是顶点坐标，再接下来m行是相关操作。