通过vertex split实现progressive mesh

背景

在上一篇文章中,我们依据高斯曲率对mesh进行平滑。但是由于平滑过程中经常会出现过多顶点聚集在一起的情况。另外,对很多顶点做平滑本身也是个相当耗时的操作。所以自然而然的,我们希望减少需要处理的顶点。虽然我们已经有了edge collapse(使用案例见使用Quadric Error Metrics进行mesh简化)但是光化简模型并做平滑本事并没有意义,毕竟我们损失了许多顶点信息。我们真正想做的事情是先减少顶点数->进行平滑操作->再还原出原本那些被删去的顶点,从而还原出整个拓扑结构。
所以,我们需要找出edge collapse的逆操作:vertex split——从一个顶点裂出一条边的两个顶点,并将原来连接至一个顶点的相邻边和点按照原本的结构连接到新的两个顶点上。

关于这个操作的概念,最早是伴随着Hugues Hoppe的Progressive Meshes[1]一文一起提出的。它提出一个progress mesh序列可以表示为从$M^n$到$M^0$的过程,$M^n$即为原始模型,$M^0$则是经过n次edge collapse后化简的模型。这个序列也是可逆的。可以用下面两个过程来表示

回顾edge collapse

Hoppe使用的是VF的链表结构,即只存取保存顶点id的面序列。不过我们使用的half-edge,所以接下来的叙述,我都会以half-edge为背景叙述。
在实现这个operator之前,我们首先要确定它所需要的信息。对于edge collapse操作,它会减去一条边和一个顶点,还会合并中间的边两侧的边(如果我们事先已处理过模型成为triangulated mesh,只包含三角面)(作图!!!)。所以首先我们要记录原始的两个顶点的id和位置,中间的边的id,和两侧的两个面的id,这些都显然可得,所以就不加赘述。

可是两侧的同一个三角的两条腰只能保留其中一个,我们得决定保留哪一条。
我先画出了如下的示意图,所有点线面的id都是依据我实际时候的测试模型的值来,只是为了标记而已。顶点用红色$(vert_ {id})$表示,边用蓝色$[edge_ {id}]$表示,面用绿色$\{face_ {id}\}$表示


之所以设计这样的坍缩方式,是因为我们可以在不影响除坍缩边及其相邻面的情况下完成连接性的重新构建。
先规定如下变量

由于坍缩之后,原始结构中,坍缩边的1-ring 平行的临边集合(图中id为{9,10,11,12,13,14})都有一条指向坍缩后顶点的halfedge,并且我们保持坍缩过程不改变这个结构。所以我们可以利用这个来判断一条halfedge是否不属于要删除的腰。
我们首先遍历坍缩边的两个顶点v0,v1的所有相邻halfedge(放射状,且都是从坍缩边的顶点出发),并找出这条half-edge的next的终点,如果属于v0或v1,我们就知道这属于会被删去的腰中的一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Outward radial halfedges
vector<HalfedgeIter> adjHes = e->AdjHalfedges();
// Outward radial edges
set<EdgeIter> adjEs = e->AdjEdges();

for (auto adjHe : adjHes) {
if (find(adjEs.begin(), adjEs.end(), adjHe->next()->edge()) == adjEs.end())) {
...
}
else {
if (adjHe->next()->twin()->vertex() == v0) {
e0_del = adjHe->next()->edge()->id;
// The existing one should be the edge of other end point
e1_cur = adjHe->edge()->id;
f0_del_id = adjHe->face()->id;
}
else if (adjHe->next()->twin()->vertex() == v1) {
e1_del = adjHe->next()->edge()->id;
// The existing one should be the edge of other end point
e0_cur = adjHe->edge()->id;
f1_del_id = adjHe->face()->id;
}
}
}

这样一来,所有我们删去的点线面的id信息都记录了下来,这将在后面重建时用到。

开始split!

首先根据之前记录的坍缩腰的id来找到对应的边和halfedge,并根据朝向,定义h0_in,h0_out,h1_in,h1_out.图示如下

1
2
3
4
5
6
7
8
9
10
11
VertexCollapseRecord rec = v0->collapseRecords[0];
...
vector<HalfedgeIter> v0_adjHes = v0->AdjHalfedges();
HalfedgeIter h0_in = (*(std::find_if(v0_adjHes.begin(), v0_adjHes.end(),
[rec](const HalfedgeIter&h) {return h->edge()->id == rec.e0_cur_id; })))
->twin();
HalfedgeIter h1_in = (*(std::find_if(v0_adjHes.begin(), v0_adjHes.end(),
[rec](const HalfedgeIter&h) {return h->edge()->id == rec.e1_cur_id; })))
->twin();
HalfedgeIter h0_out = h1_in->twin();
HalfedgeIter h1_out = h0_in->twin();

分离过程可以想象成,将两对half-edge剥开,然后在中间塞入两个三角形

拉开halfedge之后,需要重新链接它们和相邻的halfedge,这一步要特别小心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Setup inner halfedges' connectivity
HalfedgeIter h_e0 = newHalfedge(), h_e0_n = newHalfedge(), h_e0_nn = newHalfedge();
HalfedgeIter h_e1 = newHalfedge(), h_e1_n = newHalfedge(), h_e1_nn = newHalfedge();
h_e0->setNeighbors( h_e0_n, h_e1, v0, e, f0_del);
h_e0_n->setNeighbors( h_e0_nn, h1_in, v1, h1_in->edge(), f0_del);
h_e0_nn->setNeighbors( h_e0, h0_out, h1_in->vertex(),e0_del, f0_del);
h_e1->setNeighbors( h_e1_n, h_e0, v1, e, f1_del);
h_e1_n->setNeighbors( h_e1_nn, h0_in, v0, h0_in->edge(), f1_del);
h_e1_nn->setNeighbors( h_e1, h1_out, h0_in->vertex(),e1_del, f1_del);

// Re-pair existing halfedges with newly created inner ones
h0_out->edge() = e0_del;
h1_out->edge() = e1_del;
h0_in->twin() = h_e1_n;
h0_out->twin() = h_e0_nn;
h1_in->twin() = h_e0_n;
h1_out->twin() = h_e1_nn;

// Setup mesh elements
v0->halfedge() = h_e0;
v1->halfedge() = h_e1;
e->halfedge() = h_e0;
e0_del->halfedge() = h_e0_nn;
e1_del->halfedge() = h_e1_nn;
f0_del->halfedge() = h_e0;
f1_del->halfedge() = h_e1;

还有几个特别容易忘记更新的地方

1
2
3
4
5
6
7
8
9
10
// If h_e0_n->edge() has h0_out as its halfedge, it has trouble...
h_e0_n->edge()->halfedge() = h_e0_n;
h_e1_n->edge()->halfedge() = h_e1_n;

// For h1_in.next() and h1_out, they have v0 as their vertex.
// As we pinch them to the right, they should update their vertex to v1
auto v1hs = v1->AdjHalfedges();
for (auto h : v1hs) {
h->vertex() = v1;
}

collapse序列信息的存储

对于class VertexCollapseRecord,我们可以定义如下的字段

1
2
3
4
5
6
7
8
int v0_id, v1_id, e_id;
int e0_cur_id, e0_del_id, e1_cur_id, e1_del_id;
int f0_del_id, f1_del_id;
Vector3D v1_pos; // position of the other removed vertex
Vector3D v0_pos; // Last position of this vertex

bool isValid = false;
int nextRecOffset = 1;

其中上半部分比较好理解,即我们上面所说的各种id和坐标,用来还原结构的。而下半部分则是用来帮助我们完成坍缩序列记录的,即我们希望坍缩的还原是能够完全按照之前的顺序进行的。

假设坍缩记录会记录两个端点各自的坍缩序列,那么我们势必涉及到要将各自的坍缩记录嵌套起来才能存储。没有什么简单的方法能支持这种嵌套的数据类型,所以我干脆用数组的方式进行嵌套的模拟。思路倒是和用数组的跳转表来表示稀疏邻接矩阵有些相似。
合并的图示如下

id数组的构成如下

这样我们就可以将“嵌套”的顶点id列表存在一个flat的数组中,也不用管理恼人的指针了。每次在split一个顶点的时候,只用先找到active vert或者merged vert的头,读取到它的长度,就可以知道当前顶点的坍缩历史。在创建新顶点完成之后,将这块坍缩历史再更新到新的顶点就好。数据顺序都不会被破坏。

坍缩边时构建id array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Generate collapse info record ////////////////////////
if (v0_colRecs.size() == 0) {
v0_colRecs.push_back(VertexCollapseRecord());
v0_colRecs[0].v0_id = v0_id;
}
if (v1_colRecs.size() == 0) {
v1_colRecs.push_back(VertexCollapseRecord());
v1_colRecs[0].v0_id = v1_id;
}


int nextOffset = 1; // First point to the start of v0 collapseRecords
nextOffset += v0_colRecs[0].nextRecOffset; // Next point to the start of v1 collapseRecords
nextOffset += v1_colRecs[0].nextRecOffset; // Finally point to the end/the start of next collapseRecords subtree
VertexCollapseRecord rec = VertexCollapseRecord(eid, v0_id, v1_id, v0_pos, v1_pos,
e0_cur, e0_del, e1_cur, e1_del, f0_del_id, f1_del_id, nextOffset);
newV->collapseRecords.push_back(rec);
newV->collapseRecords.insert(newV->collapseRecords.end(), v0_colRecs.begin(), v0_colRecs.end());
newV->collapseRecords.insert(newV->collapseRecords.end(), v1_colRecs.begin(), v1_colRecs.end());

在split的时候,把两个部分再解出来。这里我还用了一个isValid来代表这是否是叶子节点,如果是叶子节点,代表这个顶点从没有被合并过,是原始顶点,所以不能split

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
VertexCollapseRecord rec = v0->collapseRecords[0];
VertexCollapseRecord v0_prev_rec = v0->collapseRecords[1];
VertexCollapseRecord v1_prev_rec = v0->collapseRecords[1 + v0_prev_rec.nextRecOffset];

if (rec.isValid == false) {
cout << "Selected vertex doesn't have any collapse info" << endl;
return edges.end();
}

...

v0->collapseRecords.assign(
v0->collapseRecords.begin() + 1,
v0->collapseRecords.begin() + 1 + v0_prev_rec.nextRecOffset);
v1->collapseRecords.assign(
v0->collapseRecords.begin() + 1 + v0_prev_rec.nextRecOffset,
v0->collapseRecords.end());

找寻合适的插入点

有些情况下,我们并不一定要准确的还原merge的顶点的原始位置。例如,我们对模型球面参数化之后,我们希望还原的顶点落在球面上,只是保持原来的相对拓扑关系,并不要求位置一致。于是我们就需要根据其周围顶点的位置,判断哪里是合适的插入位置
首先,我们把3D问题划归到2D平面上。我们假设球面参数化之后,所有顶点都分布潜在球面上且没有交叠的部分,于是我们就可以近似的将相邻点构成的面看出一个微分平面,而这个法线则是这个多边形中每个小三角形的有向面积

1
2
3
4
5
6
7
8
9
10
11
// Get adjective vertices plane's normal
Vector3D N(0., 0., 0.);
for (int i = 0; i < v1_ajdVs.size(); ++i) {
Vector3D vec_pi = v1_ajdVs[i]->position;
Vector3D vec_pj = v1_ajdVs[(i + 1) % v1_ajdVs.size()]->position;
N += cross(vec_pi, vec_pj);
}
if (N.norm() > 1e-5)
N = N.unit();
else
N = Vector3D(0, 1, 0);

通过$point - dot(point, N) * N)$可以将一个点投影到这个微平面上。

B.Mocanu[2]提出的检测合法点需要将平面分割成很多个小点再对所有点进行可见性测试,即如果从新的顶点与之前的顶点相连的边和旧的边有相交即为非法

下面给出了几个合法和非法的例子

这个例子中,主要的问题在于向内凹角的两侧的顶点不容易被新的顶点“看到”,如果我们用半平面交画出范围,可以看到只有中间的重叠颜色才是合法的区域
首先是一个合法的位置

接着是一个非法的位置,这里三角形v1-v0-v6已经flip了,所以是个非法的面

引用

[1] Progressive Meshes [Hugues Hoppe. ACM SIGGRAPH 1996 Proceedings, 99-108]
[2] Direct spherical parameterization based on surface curvature [B. Mocanu, T. Zaharia]