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;
            }
        }

Above is the code where I call collapse_edge inside the loop. To avoid interference, I commented out the other three operations. In version 2.8, collapse runs without any exceptions, but after only 62 collapse operations the program hangs. After investigation, it hangs during the point‑deletion step of the 63rd collapse. Any ideas on how to solve this problem?

2

Every time it gets stuck at the same place, this is how my collapse_edge function handles edges that are not on the boundary:

As you can see, at the beginning and the end it outputs the half‑edge IDs involved in this operation, and after successfully deleting a vertex it outputs vertex; deleting other elements works similarly.

image

3

This is the command line output before I got stuck, showing that before the freeze no vertex was deleted, but the collapse_edge function has already been entered
[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

Please note that when you perform a collapse, the edges list will also change synchronously. If during a collapse_edge you delete the next_node of the current tmp, then the next iteration will traverse an edge that has already been removed from the half‑edge mesh. At that point, calling collapse_edge(tmp) again will have unpredictable behavior, potentially leading to an infinite loop or even a segmentation fault.

5

void HalfedgeMesh::erase(Edge* e)
{
erased_edges[e->id] = edges.release(e);
}
This is the erase function, which actually calls the release function of edges.
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;
}
This is the release function. We can see that during this process, although tmp is removed from the list, its memory is not freed, and tmp’s next_node is not changed, so accessing tmp->next_node should be valid. Likewise, according to what you said, collapse_edge will delete the passed element from the list 100%, so this program would get stuck already when collapsing the first node; it should not have to wait until the 63rd collapse to get stuck.

6

Considering that the original function logic is imperfect and there is a risk of getting stuck, a slight improvement was made to the call to collapse in HalfedgeMesh::isotropic_remesh():

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;
}
}

But the result still hangs, as mentioned in the original question; the problem occurs before the point‑deletion operation of the 63rd collapse.

7

Well, indeed there’s no possibility of a segmentation fault, but an infinite loop can occur even without actually freeing the element’s memory. After an element is deleted, its next_node is meaningless; if you continue traversing using next_node, you may go beyond the bounds of the valid list and then try to collapse an edge that has already been removed. At that point, there’s no guarantee about the linking relationship between the elements you’re operating on, and it’s possible for pointers to wander around and form a loop.

Or put more simply, using next_node to traverse while deleting is inherently incorrect. This isn’t a plain singly‑ or doubly‑linked list, and you’re doing more than just a list deletion operation.