网格结构

网格结构包含面、边、点

• 与图结构不同（只有点和边）
• 一个面对应多个边，多个顶点
• 一条边对应两个面，两个顶点
• 一个顶点对应多条边，多个面

引入半边（有向边），对应一个Target顶点
边对应两个半边

面对应三个半边
点对应多个（出/入）半边
能有效局部遍历、支持动态的局部操作（缩减和细分顶点等）

网格结构分解为4种基本对象：面、边、顶点和半边。半边是基石

半边包含了网格的连接信息

• 一条边看做两条半边HalfEdges（twins），除了边界边（只属于一个面的边）
• 每个半边都是有向边，从source指向target
• 按右手规则规定所属面，即半边朝向的逆时针围成的面
  -

半边Half-Edge

• 创建一个新的HE

  • 对应一个面
  • 对应一条边
  • 对应一个顶点（target）
  • 使用裸指针

• Public方法

  • 下一条边（Next）
  • 上一条边（Prev）
  • 对边（Twin）

• 释放HE原则：owner releases it

  • 用智能指针共享

class HalfEdge
{
public:
private:
	Face *m_face;
	Edge *m_edge;
	Vertex *m_target;

	HalfEdge *m_prev;
	HalfEdge *m_next;

	int m_hid;
};

边Edge

边对应两个半边。边接边的第二个半边为空。

class Edge
{
public:
private:
	SmartP<HalfEdge> m_hes[2];
	std::string m_sProperty;
	int m_eid;
};

面Face

面对应多个半边

只存一条半边：按右手规则。一条半边决定了“环路”走向。

class Face
{
public:
private:
	SmartP<HalfEdge> m_first;
	std::string m_sProperty;
	int m_fid;
};

顶点Vertex

一个顶点对应多条出边和多条入边。只存一条入边（拓扑信息），坐标值（几何信息）

class Vertex
{
public:
private:
	SmartP<HalfEdge> m_inEdge;
	Point m_point;
	bool m_boundry;
	std::string m_sProperty;
	int m_vid;
};

使用半边网格结构

Check Boundary Edge

判断边界边：第二条半边是空的

bool Edge::IsBoundary() const
{
	return m_hes[1].Empty();
}

Check Boundary Face

判断边界面：如果有一条边是边界边

bool Face::IsBoundary() const
{
	HalfEdge *he = GetFirstEdgePtr();
	do
	{
		if(he ->Twin() == nullptr)
		{
			return true;
		}
		he = he->Next();
	}while (he != GetFirstEdgePtr());
	return false;
}

Local Rotations – HalfEdge旋转操作

对一条半边定义旋转操作

• he -> clw_rotate_about_target(): //红线
  • he -> Next()->Twin()
  • 比如从$[v_4,v_3]到[v_6,v_3]$
• he -> ccw_rotate_about_target(): //蓝线
  • he -> Twin()->Prev()
  • 比如从$[v_6,v_5]到[v_3,v_5]$
• he -> clw_rotate_about_source(): //黄线
  • he ->Twin()->Next()
  • 比如从$[v_3,v_2]到[v_3,v_1]$
• he -> ccw_rotate_about_source(): //绿线
  • he -> Prev()->Twin()
  • 比如从$[v_1,v_3]到[v_1,v_4]$
    

Local Rotations – Boundary Vertex

对边界顶点定义旋转操作
$v_4$->most_clw_in_halfedge()：对于顶点$v_4$，返回半边[$v_3,v_4$]
$v_4$->most_ccw_in_halfedge(): 对于顶点$v_4$，返回半边[$v_6,v_4$]
$v_4$->most_clw_out_halfedge(): 对于顶点$v_4$，返回半边[$v_4,v_1$]
$v_4$->most_ccw_out_halfedge(): 对于顶点$v_4$，返回半边[$v_4,v_3$]

迭代器

迭代器模式让用户在不知道内部实现的基础上，对容器内每个数据元素进行遍历。
std::vector<int>::iterator it = myvector.begin()
it != myvector.end()
++it
比如给定一个Vertex，遍历其所有

• 出边：Vertex::OutHalfEdgeIterator
• 入边：Vertex::InHalfEdgeIteratr
• 面：Vertex::FaceIterator
• for(Vertex::FaceIterator it(&v);!it.end();++it)

判断边界点：对应的某条HalfEdge是边界边。需要通过绕着Target，旋转遍历所有入边。
在Mesh里预处理，统一设置

void Mesh::LabelBoundaryVertices()
{
	for(auto it = m_edges.begin();it != m_edges.end();++it)
	{
		Edge *edge = *it;
		if(edge -> IsBoundary())
		{
			HalfEdge *he = edge -> GetHalfEdgePtr(0);
			he -> Target() -> SetBoundary(true);
		}
	}
}

寻找网格边界

• 先找到一个未访问过的半边（边界边）
• 再找这个半边对应的Target顶点v（边界点）
  • 找对应的出边（most_clw_out_halfedge）
  • 继续这个步骤，直到下一个满足的出边已被访问过
• 直到所有半边都访问过

保存边界边，用OpenGL绘制

通过面法向量计算顶点法向量

$F(v)$指顶点$v$的邻接面
常熟${\alpha }_f$的设置方法：

1. 常量${\alpha }_f=1$
2. 面的面积${\alpha }_f=|f|$
3. 夹角${\alpha }_f={\theta }_f$

glNormal3f(n.x, n.y, n.z);

计算面的面积

对三角面的边向量进行外积

float ObjHelper::ComputeFaceArea(Sufe::Face *f)
{
	HalfEdge *he = f -> GetFirstEdgePtr();
	Point pt[3];
	for(int i = 0;i < 3;++i)
	{
		pt[i] = he -> Target() -> GetPoint();
		he = he -> Next();
	}
	Point up = Cross(pt[2] - pt[0], pt[1] - pt[0]);
	return up.Norm()/2.0f;
}

网格细化和简化

Mesh subdivision网格细化

1. 遍历和调整旧顶点

• 新位置v’暂存在顶点自身
• 内部顶点$v^{\prime }=(1-nu)v+u{\sum }_{i=1}^n{v}_i$，u是权重
  
• 边界顶点$v^{\prime }=\frac{3}{4}v+\frac{1}{8}(v_1+v_2)$
  

2. 遍历边，插入和调整新顶点

• 新位置暂存在对应边

• 内部新顶点$v^{\prime }=\frac{3}{8}(v_1+v_2)+\frac{1}{8}(v_3+v_4)$
  

• 边界新顶点$v^{\prime }=\frac{1}{2}(v_1+v_2)$
  

3. 遍历旧面，创建新的细分网格：对原来网格每个面，生成四个面，每个面的卫视按之前计算的位置
   遍历边，对每条旧边：

• Split操作：对每个旧边上的新顶点（任意次序），创建和所在三角形对角顶点的边
• Flip操作：对所有连接新旧顶点的新边执行Flip操作