三维CAD建模——基于半边数据结构的基本欧拉操作建模(elar, B_REP)

今年选了高老师的三维CAD建模课，zju选了这课应该就知道最后要做一个程序作业——基于半边数据结构的基本欧拉操作实现建模。要求必须建带有洞的模型。

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：生成含有一个点的面，包括一个空环，并且构成一个新的体

mev：生成一个新的点e2，连接该点到已有点v1，构造一条新的边

mef：连接面f1上的两个点v1，v2，生成一条新边e，并产生一个新面

kemr：删除一条边e，生成该边某一邻面上的新的内环

kfmrh：删除与面f1相接触的一个面f2，生成面f1上的一个内环，并形成体上的一个通孔

主要就是实现这五个欧拉操作就可以了。

下面主要是记录下我在作业中半边数据结构以及基本欧拉操作的实现。

#ifndef __HALF_EDGE_STRUCTURE__
#define __HALF_EDGE_STRUCTURE__

#include <stdlib.h>

struct Solid;
struct Face;
struct Loop;
struct HalfEdge;
struct Vertex;
struct Edge;

struct Solid
{
	int id;
	Face *faces; // list of all faces to construct this solid
	Edge *edges; // list of all edges to construct this solid->to build the frame
	Solid *next;
	Solid *pre;

	int vnum;//the count of all vertexs
	int fnum;//the count of all faces
	int lnum;//the count of all loops


	Solid() : id(0), faces(NULL), edges(NULL), next(NULL), pre(NULL), fnum(0), vnum(0), lnum(0){}
};

struct Face
{
	int id;
	Solid *solid; // the solid which the face belong to
	Loop *out_lp; // out loop of the face--construct the face
	Loop *inner_lp;//inner_lp of the face--inner loop
	Face *next;
	Face *pre;
	int innum;//the count of inner loops

	Face() : id(0), solid(NULL), out_lp(NULL), next(NULL), pre(NULL), inner_lp(NULL), innum(0){}
};

struct Loop
{
	int id;
	HalfEdge *halfedges; // list of all halfeges to construct this loop 
	Face *face; // the face that constructed by this loop
	Loop *next;
	Loop *pre;

	Loop() : id(0), halfedges(NULL), face(NULL), next(NULL), pre(NULL){}
};

struct Edge
{
	HalfEdge *half_l; //the edge's left halfedge
	HalfEdge *half_r; //the edge's right halfedge
	Edge *next;
	Edge *pre;

	Edge() : half_l(NULL), half_r(NULL), next(NULL), pre(NULL){}
};

struct HalfEdge
{
	Edge *edge; //this halfedge belong to which edge
	Vertex *sv; //the start vertex of this halfedge
	Vertex *ev; //the end vertex of this halfedge
	Loop *lp; //pointer to the loop that this halfedge belong to
	HalfEdge *next;
	HalfEdge *pre;
	HalfEdge *brother;

	HalfEdge() : edge(NULL), sv(NULL), lp(NULL), next(NULL), pre(NULL), brother(NULL){}
};

struct Vertex
{
	int id;
	double coordinate[3];//coordinate of the vertex (x, y, z)
	Vertex *next;
	Vertex *pre;

	Vertex(double x, double y, double z) : id(0), next(NULL), pre(NULL)
	{
		coordinate[0] = x;
		coordinate[1] = y;
		coordinate[2] = z;
	}
};

#endif

下面是五种欧拉操作的实现代码

elar_operator.h

#ifndef __ELAR_OPERATOR__
#define __ELAR_OPERATOR__

#include "half_edge_structure.h"
#include <vector>

using namespace std;

class ElarOperator
{
public:
	ElarOperator()
	{
		v_list.clear();
		sweep_list.clear();
		l_list.clear();
	}

	std::vector<Vertex *> getV_list()
	{
		return v_list;
	}

	std::vector<Face *> getSweep_list()
	{
		return sweep_list;
	}

	std::vector<Loop *> getLoop_list()
	{
		return l_list;
	}

	void addEdgeIntoSolid(Edge *edge, Solid *&solid);
	void addFaceIntoSolid(Face *face, Solid *&solid);
	void addLoopIntoFace(Loop *loop, Face *face);
	Solid *mvfs(double point[3], Vertex *&vertex);
	HalfEdge *mev(Vertex *sv, double point[3], Loop *lp);
	Loop *mef(Vertex *sv, Vertex *ev, Loop *lp, bool mark);
	Loop *kemr(Vertex *sv, Vertex *ev, Loop *lp);
	void kfmrh(Face *fa, Face *fb);
	void sweep(double dir[3], double dist);

private:
	std::vector<Vertex *> v_list;
	std::vector<Loop *> l_list;
	std::vector<Face *> sweep_list;
};

#endif

#include "elar_operator.h"
#include <cstdio>

Solid *ElarOperator::mvfs(double point[3], Vertex *&vertex)
{
	Solid *solid = new Solid();
	Face *face = new Face();
	Loop *out_lp = new Loop();
	vertex = new Vertex(point[0], point[1], point[2]);

	vertex->id = solid->vnum;
	out_lp->id = solid->lnum;
	face->id = solid->fnum;

	l_list.push_back(out_lp);
	//printf("%lf %lf %lf\n", vertex->coordinate[0], vertex->coordinate[1], vertex->coordinate[2]);
	v_list.push_back(vertex);//store the vertex by order
	solid->vnum += 1;//increase the num of vertexs
	solid->fnum += 1;//increase the num of faces
	solid->lnum += 1;//increase the num of loops


	solid->faces = face;
	face->solid = solid;

	face->out_lp = out_lp;
	out_lp->face = face;

	return solid;
}


HalfEdge *ElarOperator::mev(Vertex *sv, double point[3], Loop *loop)
{
	Solid *solid = loop->face->solid;
	Edge *edge = new Edge();//create a new edge
	HalfEdge *half_l = new HalfEdge();
	HalfEdge *half_r = new HalfEdge();
	Vertex *ev = new Vertex(point[0], point[1], point[2]);

	ev->id = solid->vnum;
	v_list.push_back(ev);//store the vertex by order
	solid->vnum += 1;//remember to increase the vertex num of the solid

	half_l->sv = sv;
	half_l->ev = ev;
	half_r->sv = ev;
	half_r->ev = sv;

	edge->half_l = half_l;
	edge->half_r = half_r;
	half_l->edge = edge;
	half_r->edge = edge;

	half_r->brother = half_l;
	half_l->brother = half_r;

	half_l->lp = loop;
	half_r->lp = loop;

	//add the new two halfedges into the loop
	if (loop->halfedges == NULL)
	{
		half_l->next = half_r;
		half_r->next = half_l;

		half_l->pre = half_r;
		half_r->pre = half_l;
		loop->halfedges = half_l;
	}
	else
	{
		HalfEdge *thalf = loop->halfedges;
		while (thalf->ev != sv)thalf = thalf->next;
		half_r->next = thalf->next;
		thalf->next->pre = half_r;
		thalf->next = half_l;
		half_l->pre = thalf;
		half_l->next = half_r;
		half_r->pre = half_l;
	}

	//add the edge into the edge list of solid
	addEdgeIntoSolid(edge, solid);
	return half_l;
}

Loop *ElarOperator::mef(Vertex *sv, Vertex *ev, Loop *loop, bool mark)
{
	Solid *solid = loop->face->solid;
	Edge *edge = new Edge();
	HalfEdge *half_l = new HalfEdge();
	HalfEdge *half_r = new HalfEdge();
	Loop *newLoop = new Loop();

	half_l->sv = sv;
	half_l->ev = ev;
	half_r->sv = ev;
	half_r->ev = sv;

	half_r->brother = half_l;
	half_l->brother = half_r;

	half_l->edge = edge;
	half_r->edge = edge;
	edge->half_l = half_l;
	edge->half_r = half_r;


	//add the new two halfedge into the loop
	HalfEdge *thalf = loop->halfedges;
	HalfEdge *tmpa, *tmpb, *tmpc;
	while (thalf->ev != sv)thalf = thalf->next;
	tmpa = thalf;

	while (thalf->ev != ev)thalf = thalf->next;
	tmpb = thalf;

	thalf = thalf->next;
	while (thalf->ev != ev)thalf = thalf->next;
	tmpc = thalf;

	//divide the big loop into two small loop
	half_r->next = tmpa->next;
	tmpa->next->pre = half_r;
	tmpa->next = half_l;
	half_l->pre = tmpa;

	half_l->next = tmpb->next;
	tmpb->next->pre = half_l;
	tmpb->next = half_r;
	half_r->pre = tmpb;
	loop->halfedges = half_l;
	newLoop->halfedges = half_r;
	half_l->lp = loop;
	half_r->lp = newLoop;

	Face *face = new Face();

	newLoop->id = solid->lnum;
	solid->lnum += 1;
	l_list.push_back(newLoop);
	//add face into the face list of solid
	addFaceIntoSolid(face, solid);

	addLoopIntoFace(newLoop, face);

	if (tmpc == tmpb)
	{
		if (mark)//only the face in the bottom 
		{
			sweep_list.push_back(half_l->lp->face);
		}
	}
	else
	{
		sweep_list.push_back(half_r->lp->face);
	}

	//add edge into the edge list of solid
	addEdgeIntoSolid(edge, solid);

	return loop;
}

Loop *ElarOperator::kemr(Vertex *sv, Vertex *ev, Loop *loop)//sv must belong to the outer loop
{
	HalfEdge *tmpa, *tmpb, *hal;
	Face *face = loop->face;
	Loop *inlp = new Loop();
	Solid *solid = loop->face->solid;

	hal = loop->halfedges;

	while (hal->sv != sv || hal->ev != ev)hal = hal->next;
	tmpa = hal;

	while (hal->sv != ev || hal->ev != sv)hal = hal->next;
	tmpb = hal;

	tmpb->pre->next = tmpa->next;
	tmpa->pre->next = tmpb->next;

	loop->face->solid->faces->out_lp->halfedges = tmpa->pre;

	inlp->halfedges = tmpb->pre;
	tmpb->pre->lp = inlp; 

	inlp->id = solid->lnum;
	solid->lnum += 1;
	l_list.push_back(inlp);

	addLoopIntoFace(inlp, tmpa->pre->brother->lp->face);

	delete tmpa;
	delete tmpb;

	return NULL;
}

void ElarOperator::kfmrh(Face *fa, Face *fb)//fa indicate the outface, fb indicate the innerface
{
	Loop *loop = fb->out_lp;
	addLoopIntoFace(loop, fa);
	fa->solid->lnum -= 1;
	fa->solid->fnum -= 1;

	Solid *solid = fa->solid;
	Face *face = solid->faces;
	if (face == fb)
	{
		solid->faces = face->next;
	}
	else
	{
		Face *tf = face;
		while (face != fb && face != NULL)
		{
			tf = face;
			face = face->next;
		}
		tf->next = face->next;
	}
	delete fb;
}

void ElarOperator::sweep(double dir[3], double d)
{
	Vertex *startv, *nextv, *upv, *upprev;
	HalfEdge *he, *suphe, *uphe;
	double point[3];

	vector<Face *>::iterator ite;
	for (ite = sweep_list.begin(); ite != sweep_list.end(); ++ite)
	{

		//solve the first vertex when process the sweeping operator
		Loop *loop = (*ite)->out_lp;
		he = loop->halfedges;
		startv = he->sv;
		point[0] = startv->coordinate[0] + d*dir[0];
		point[1] = startv->coordinate[1] + d*dir[1];
		point[2] = startv->coordinate[2] + d*dir[2];


		suphe = mev(startv, point, loop);//acquire the first down_to_up halfedge
		upprev = suphe->ev;//record the fist up vertex as the pre vertex
		he = he->next;
		nextv = he->sv;

		Loop *lp = loop;

		while (nextv != startv)
		{
			point[0] = nextv->coordinate[0] + d*dir[0];
			point[1] = nextv->coordinate[1] + d*dir[1];
			point[2] = nextv->coordinate[2] + d*dir[2];
			uphe = mev(nextv, point, lp);
			upv = uphe->ev;

			lp = mef(upprev, upv, loop, false);

			upprev = upv;
			he = he->next;
			nextv = he->sv;
		}
		mef(upprev, suphe->ev, loop, false);

	}
}

inline
void ElarOperator::addEdgeIntoSolid(Edge *edge, Solid *&solid)
{
	Edge *te = solid->edges;

	if (te == NULL)solid->edges = edge;
	else{
		while (te->next != NULL)te = te->next;
		te->next = edge;
		edge->pre = te;
	}
}

inline
void ElarOperator::addFaceIntoSolid(Face *face, Solid *&solid)
{
	Face *tface = solid->faces;
	if (tface == NULL)
	{
		solid->faces = face;
	}
	else
	{
		while (tface->next != NULL)tface = tface->next;
		tface->next = face;
		face->pre = tface;
	}
	face->solid = solid;

	face->id = solid->fnum;

	solid->fnum += 1;// increase the num of faces
}

inline
void ElarOperator::addLoopIntoFace(Loop *loop, Face *face)
{
	loop->face = face;

	//there is only one out loop but there may have lots of inner loop
	if (face->out_lp == NULL)
	{
		face->out_lp = loop;
	}
	else
	{
		Loop *tlp = face->inner_lp;
		if (tlp == NULL)face->inner_lp = loop;
		else
		{
			while (tlp->next != NULL)tlp = tlp->next;
			tlp->next = loop;
			loop->pre = tlp;
		}
		face->innum += 1;
	}
}

以上就是简单建了带洞模型，当然可以在体内建更多的洞，建不同形状的洞，这样就完成了作业要求。

各个操作都挺简单，关键是mef的时候要注意选取面环时的法向问题就可以了。用右手规则比划一下就能很容易的确定了。每个洞扫成完成后要记得kfmrh来得到这个洞。

ok，就这些了。

以上代码链接：http://download.csdn.net/detail/iaccepted/8167679

三维CAD建模——基于半边数据结构的基本欧拉操作建模