前言念叨
三维CAD建模是秋学期上的课,课程作业是实现边界表示Brep中的半边数据结构,并且实现欧拉操作完成物体的扫成。实现的过程中遇到了许多琐碎的问题,这里就记录一下算法以及一些遇到的小问题。
半边数据结构是C++编写的,不需要用到其他的库,但是显示图形需要借助OpenGL,我又希望添加一些功能所以是在Qt的基础上写的,但是出现了一些奇怪的bug暂时没有解决,希望之后熟练了OpenGL之后可以解决这个小bug。
半边数据结构
- 边界表示Brep:利用边界表示三维物体;描述物体的信息包括几何信息和拓扑信息两个方面,物体的拓扑信息指物体上所有的顶点、棱边、表面的连接方式;几何信息描述物体的大小、尺寸、位置、形状等。
边界表示通常有翼边数据结构、半边数据结构这几种表示形式,半边数据结构是将一条物理边分为两条半边进行表示,通过构建点、边、环、面、体之间的关系建立一个物体。 - 体Solid:物体的表示;
- 点Vertex:物体的顶点;
- 边Edge:物体的物理边;
- 半边HalfEdge:一条物理边对应两条半边;
- 面Face:物体的面;
- 环Loop:将多条边相连闭合可以产生一个新的面,由于每条物理边都有两条半边,因而此时会产生两个环路,一般将环路的外环作为环存储,环的走向应该满足右手坐标系。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859class Solid {public:Solid() :nexts(nullptr), prevs(nullptr), lpNum(0) {}int lpNum;vector<Face*> faceList;vector<Vertex*> vertexList;};class Vertex {public:Vertex(const vector<double>& _coordinate, int _id = -1) {coordinate = _coordinate;id = _id;}Vertex(const vector<double>& _coordinate, const vector<double>& direction, double d, int _id = -1) {coordinate.push_back(_coordinate[0] + direction[0] * d);coordinate.push_back(_coordinate[1] + direction[1] * d);coordinate.push_back(_coordinate[2] + direction[2] * d);id = _id;}vector<double> coordinate;int id;};class Edge {public:Edge(HalfEdge* _lhe, HalfEdge* _rhe) :lhe(_lhe), rhe(_rhe) {}HalfEdge *lhe, *rhe;};class HalfEdge {public:HalfEdge(Vertex* _stv, Vertex *_endv, Loop* _lp = nullptr) :startv(_stv), endv(_endv), wloop(_lp),nxt(nullptr), prv(nullptr), brotherEdg(nullptr), edg(nullptr) {}HalfEdge *nxt, *prv;HalfEdge *brotherEdg;Edge *edg;Loop *wloop;Vertex *startv, *endv;};class Face {public:Face(Solid* _solid = nullptr, int _id = -1) :fsolid(_solid), id(_id){}Solid *fsolid;vector<Loop*> loopList;int id;};class Loop {public:Loop(Face* _face = nullptr, int _id = -1, HalfEdge* _ledge = nullptr) :lface(_face), ledg(_ledge), id(_id) {}Face *lface;HalfEdge *ledg;int id;};
欧拉操作
运用欧拉操作,可以构建三维物体边界表示的拓扑关系。由于操作符合欧拉公式v-e+f=2(s-h)+r因而得名,主要实现的6个操作:
- mvfs:第一步的操作,输入一个顶点,建立新的面、环、体;
- mev:输入一个顶点v2,将已有顶点v1与v2相连,建立一条新的边;
- mef:将已有顶点v1和v2相连,建立新的边、面、环;
- kemr:删除一条桥边e,生成一个新的环;
- kfmrh:删除与面f1贴合的面f2,生成面f1的内环,并生成物体的通孔。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120Solid * EulerOperator::mvsf(const vector<double>& _coordinate){Solid* solid = new Solid();Face* face = new Face(solid, solid->faceList.size());Loop *lp = new Loop(face, solid->lpNum++);Vertex *v = new Vertex(_coordinate, solid->vertexList.size());solid->faceList.push_back(face);solid->vertexList.push_back(v);face->fsolid = solid;face->loopList.push_back(lp);return solid;}HalfEdge * EulerOperator::mev(Vertex * startv, Vertex* endv, Loop * lp){Solid* curSolid = lp->lface->fsolid;solid->vertexList.push_back(endv);HalfEdge* lhe = new HalfEdge(startv, endv, lp);HalfEdge* rhe = new HalfEdge(endv, startv, lp);Edge* edg = new Edge(lhe, rhe);lhe->edg = edg;rhe->edg = edg;lhe->nxt = rhe;rhe->prv = lhe;lhe->brotherEdg = rhe;rhe->brotherEdg = lhe;if (lp->ledg == nullptr) {lhe->prv = rhe;rhe->nxt = lhe;lp->ledg = lhe;}else {HalfEdge* he = lp->ledg;for (; he->endv != startv; he = he->nxt);rhe->nxt = he->nxt;he->nxt->prv = rhe;he->nxt = lhe;lhe->prv = he;}return lhe;}Loop * EulerOperator::mef(Vertex * startv, Vertex * endv, Loop * lp){Solid *curSolid = lp->lface->fsolid;Face *newFace = new Face(curSolid, solid->faceList.size());Loop* newLoop = new Loop(newFace, curSolid->lpNum++);HalfEdge *lhe = new HalfEdge(startv, endv, newLoop);HalfEdge *rhe = new HalfEdge(endv, startv, lp);Edge* edg = new Edge(lhe, rhe);lhe->edg = edg;rhe->edg = edg;lhe->brotherEdg = rhe;rhe->brotherEdg = lhe;HalfEdge *tmphe1 = lp->ledg;HalfEdge *tmphe2 = lp->ledg;for (; tmphe1->startv != endv; tmphe1 = tmphe1->nxt);for (; tmphe2->endv != startv; tmphe2 = tmphe2->nxt);lhe->nxt = tmphe1;lhe->prv = tmphe2;rhe->nxt = tmphe2->nxt;rhe->prv = tmphe1->prv;tmphe1->prv = lhe;tmphe2->nxt = lhe;rhe->prv->nxt = rhe;rhe->nxt->prv = rhe;newLoop->ledg = lhe;for (tmphe1 = lhe; tmphe1->nxt != lhe; tmphe1 = tmphe1->nxt)tmphe1->wloop = newLoop;lp->ledg = rhe;//将面加入体中curSolid->faceList.push_back(newFace);//将环加入面中newFace->loopList.push_back(newLoop);return newLoop;}Loop * EulerOperator::kemr(HalfEdge* lhe){Solid* curSolid = lhe->wloop->lface->fsolid;Edge* curEdg = lhe->edg;Face* newFace = new Face(curSolid, curSolid->faceList.size());HalfEdge* rhe = curEdg->rhe;Loop* newLoop = new Loop(newFace, solid->lpNum++);rhe->nxt->prv = lhe->prv;lhe->prv->nxt = rhe->nxt;curSolid->faceList.push_back(newFace);newFace->loopList.push_back(newLoop);delete curEdg;return newLoop;}void EulerOperator::kfmrh(Face * f1, Face * f2){f1->loopList.insert(f1->loopList.end(), f2->loopList.begin(), f2->loopList.end());for (auto it = f1->fsolid->faceList.begin(); it != f1->fsolid->faceList.end(); it++) {if (*it == f2) {f1->fsolid->faceList.erase(it);break;}}delete f2;}
扫成操作
实现了平移扫成的过程,通过给定移动的方向向量及位移距离计算出物体的顶点。
Bug记录
- 一开始没有把数据结构想明白,主要是没有理解内环和外环的意思,将边围成闭合回路之后会产生内环路和外环路,面的外环应为符合其法向方向的环路,面的内环则与外环的方向相反。
- Qt实现部分,比较琐碎的问题,主要是因为自己不够熟悉,之后需要进一步了解一下各个部件以及之间的一些关系;
- OpenGL实现,这个部分主要使用了gluTess函数画凹多边形以及带孔的图形,但是也遇到了非常多的问题,主要是不太熟悉可编程管线的使用,两个带孔的图形绘制有很大的问题,可能与buffer有关,但是现阶段不够了解OpenGL需要再学习一下之后再来将bug修复;
后记
- 之后编程之前需要先把数据结构和算法理解清楚,并且要把伪代码给写出来,算是对思路进行一整理;
- OpenGL的使用这几天需要补习一下,以防以后使用的时候又要请教别人;
- Qt的部件和结构还不是很了解,也要再学习一下;