2.11 中调用 collapse_edge 时会卡住

学术专区 计算机图形学
1

// Collapse short edges.
tmp=this->edges.head;
while(1){
if(tmp->length()<4.0/5.0*aver_len){
collapse_edge(tmp);
}
if(tmp==this->edges.tail){
break;
}
else{
tmp=tmp->next_node;
}
}
以上，这是我在循环体中调用 collapse_edge 的代码，为了避免干扰，我将其他三个操作都注释掉了，在 2.8 中 collapse 是完全可以运行没有异常的，可是在仅仅执行 62 次 collapse 操作后，程序就卡死了，经过检测，是在低 63 次 collapse 的删除点操作时卡死的，请问有解决这个问题的思路吗

2

每次都会在同一个地方卡住，这是我 collapse_edge 函数对不在边界的边的处理：
可见，在开头和结尾会输出参与此次操作的半边 id，然后成功删除点后会输出 vertex，删除其他元素同理

image
image1028×892 37.5 KB

3

这是我卡死前的命令行输出，显示卡死前并没有删除 vertex，但是已经进入了 collapse_edge 函数
[Halfedge Mesh] [info] not on_boundar:35897,9465,35936,9464,35938,9462,35937,35905,21345,35939,35941

[Halfedge Mesh] [info] not on_boundar:21374,9472,35948,9471,35950,9470,35949,21373,9494,35951,35953

[Halfedge Mesh] [info] vertex

[Halfedge Mesh] [info] face

[Halfedge Mesh] [info] edge

[Halfedge Mesh] [info] halfedge

[Halfedge Mesh] [info] not on_boundar:21374,9472,35948,9471,35950,9470,35949,21373,9494,35951,35953

[Halfedge Mesh] [info] not on_boundar:35943,9494,9496,35984,35951,35952,9474,9469,35987,35986,10081

[Halfedge Mesh] [info] vertex

[Halfedge Mesh] [info] face

[Halfedge Mesh] [info] edge

[Halfedge Mesh] [info] halfedge

[Halfedge Mesh] [info] not on_boundar:35943,9494,9496,35984,35951,35952,9474,9469,35987,35986,10081

[Halfedge Mesh] [info] not on_boundar:10057,9496,35984,9494,35986,9493,35985,10056,35951,35987,35989

4

请注意在你执行坍缩的时候，edges 这个链表也会同步改变。如果某一次 collapse_edge 时，把当前 tmp 的 next_node 也删掉了，那下一次就会遍历到一条已经从半边网格中被删除的边，这时候再去执行 collapse_edge(tmp)，就完全不知道会操作些什么东西了，陷入死循环或者直接 segment fault 都是有可能的。

5

void HalfedgeMesh::erase(Edge* e)
{
erased_edges[e->id] = edges.release(e);
}
这是 erase 函数，它实际上是调用了 edges 的 release 函数
Node* LinkedList::release(Node* node)
{
if (node == nullptr || !this->size) {
return nullptr;
}
–this->size;
if (!this->size) {
// Erase the last element in the list
this->head = nullptr;
this->tail = nullptr;
} else if (node == this->head) {
// Erasure for the head node
this->head = this->head->next_node;
this->head->prev_node = nullptr;
} else if (node == this->tail) {
// Erasure for the tail node
this->tail = this->tail->prev_node;
this->tail->next_node = nullptr;
} else {
// Otherwise a general erasure
node->prev_node->next_node = node->next_node;
node->next_node->prev_node = node->prev_node;
}
return node;
}
这是 release 函数，我们可以看到，在这个过程中，tmp 虽然从链表中被剔除，但是它的内存并没有释放，同时，tmp 的 next_node 也没有改变，所以调用 tmp->next_node 理应是合法的，同理，按照您所说，collapse_edge 会百分之一百从链表中删除传入的元素，那么这个程序从 collapse 第一个节点时就会卡死，应该不至于到第 63 次 collapse 才卡死

6

考虑到原函数逻辑不完善，有卡住的风险，于是对 HalfedgeMesh::isotropic_remesh() 中对 collapse 的调用做了一点改进：
tmp=this->edges.head;
int is_tail=0;
while(1){
if(tmp==this->edges.tail){
is_tail=1;
}
if(tmp->length()<4.0/5.0*aver_len){
collapse_edge(tmp);
}
if(is_tail==1){
break;
}
else{
tmp=tmp->next_node;
}
}
但结果依然卡死，正如一开始提问说到的，问题出现在第 63 次 collapse 操作时删除点的操作之前

7

嗯确实不存在 segment fault 的可能，但死循环本来也不需要真的把元素的内存释放掉才会发生。因为被删除之后这个元素的 next_node 就没意义了，你按 next_node 继续遍历有可能就跑出有效的链表范围，然后试图去 collapse 一个已经被删掉的边。这时候你操作的元素之间到底是什么链接关系完全没有保证，指针指来指去又绕成环了也是有可能的。

或者简单点说，你用 next_node 一边遍历一边删除本来就是一种不正确的做法，这不是普通的单链表或者双链表，你做的也不仅仅是链表的删除操作。