{"topic":{"id":14047,"title":"2.11 中调用 collapse_edge 时会卡住","slug":"topic","categoryId":56,"createdAt":"2024-12-20 10:36:25.516167","bumpedAt":"2024-12-20 11:57:19.921098","views":234,"postsCount":7,"highestPostNumber":7,"likeCount":0,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"// 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_e…","deletedAt":null,"isAnonymous":false,"category":{"id":56,"name":"计算机图形学","slug":"cg","color":"92278F"},"author":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null},"tags":[]},"posts":[{"id":44821,"postNumber":1,"raw":" // Collapse short edges.\n tmp=this->edges.head;\n while(1){\n if(tmp->length()<4.0/5.0*aver_len){\n collapse_edge(tmp);\n }\n if(tmp==this->edges.tail){\n break;\n }\n else{\n tmp=tmp->next_node;\n }\n }\n以上，这是我在循环体中调用 collapse_edge 的代码，为了避免干扰，我将其他三个操作都注释掉了，在 2.8 中 collapse 是完全可以运行没有异常的，可是在仅仅执行 62 次 collapse 操作后，程序就卡死了，经过检测，是在低 63 次 collapse 的删除点操作时卡死的，请问有解决这个问题的思路吗","cooked":"

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

\n","createdAt":"2024-12-20 10:36:25.89849","updatedAt":"2024-12-20 10:38:40.538287","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":128,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":44823,"postNumber":2,"raw":"每次都会在同一个地方卡住，这是我 collapse_edge 函数对不在边界的边的处理：\n可见，在开头和结尾会输出参与此次操作的半边 id，然后成功删除点后会输出 vertex，删除其他元素同理\n![image|576x499](/uploads/image/30/20/30203cae2094b7eac2413e783fb9354b61bb67d7b6279eacb0f1dc1d7d030719.avif)","cooked":"

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

\n","createdAt":"2024-12-20 11:21:20.744983","updatedAt":"2024-12-20 11:21:20.744983","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":73,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":44824,"postNumber":3,"raw":"这是我卡死前的命令行输出，显示卡死前并没有删除 vertex，但是已经进入了 collapse_edge 函数\n[Halfedge Mesh] [info] not on_boundar:35897,9465,35936,9464,35938,9462,35937,35905,21345,35939,35941\n\n[Halfedge Mesh] [info] not on_boundar:21374,9472,35948,9471,35950,9470,35949,21373,9494,35951,35953\n\n[Halfedge Mesh] [info] vertex\n\n[Halfedge Mesh] [info] face\n\n[Halfedge Mesh] [info] edge\n\n[Halfedge Mesh] [info] halfedge\n\n[Halfedge Mesh] [info] not on_boundar:21374,9472,35948,9471,35950,9470,35949,21373,9494,35951,35953\n\n[Halfedge Mesh] [info] not on_boundar:35943,9494,9496,35984,35951,35952,9474,9469,35987,35986,10081\n\n[Halfedge Mesh] [info] vertex\n\n[Halfedge Mesh] [info] face\n\n[Halfedge Mesh] [info] edge\n\n[Halfedge Mesh] [info] halfedge\n\n[Halfedge Mesh] [info] not on_boundar:35943,9494,9496,35984,35951,35952,9474,9469,35987,35986,10081\n\n[Halfedge Mesh] [info] not on_boundar:10057,9496,35984,9494,35986,9493,35985,10056,35951,35987,35989","cooked":"

这是我卡死前的命令行输出，显示卡死前并没有删除 vertex，但是已经进入了 collapse_edge 函数
\n[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

\n","createdAt":"2024-12-20 11:23:20.62826","updatedAt":"2024-12-20 11:23:20.62826","replyToPostNumber":2,"replyCount":0,"likeCount":0,"wordCount":96,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":44825,"postNumber":4,"raw":"请注意在你执行坍缩的时候，`edges` 这个链表也会同步改变。如果某一次 `collapse_edge` 时，把当前 `tmp` 的 `next_node` 也删掉了，那下一次就会遍历到一条已经从半边网格中被删除的边，这时候再去执行 `collapse_edge(tmp)`，就完全不知道会操作些什么东西了，陷入死循环或者直接 segment fault 都是有可能的。","cooked":"

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

\n","createdAt":"2024-12-20 11:28:25.918128","updatedAt":"2024-12-20 11:28:25.918128","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":110,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1381,"username":"greyishsong","name":"greyishsong","avatarUrl":"/uploads/image/da/bc/dabc731b0311f59850625bbeb55ed969fcfac0430c5ef0f68441e5466b7aa496.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":44828,"postNumber":5,"raw":"void HalfedgeMesh::erase(Edge* e)\n{\n erased_edges[e->id] = edges.release(e);\n}\n这是 erase 函数，它实际上是调用了 edges 的 release 函数\nNode* LinkedList::release(Node* node)\n{\n if (node == nullptr || !this->size) {\n return nullptr;\n }\n --this->size;\n if (!this->size) {\n // Erase the last element in the list\n this->head = nullptr;\n this->tail = nullptr;\n } else if (node == this->head) {\n // Erasure for the head node\n this->head = this->head->next_node;\n this->head->prev_node = nullptr;\n } else if (node == this->tail) {\n // Erasure for the tail node\n this->tail = this->tail->prev_node;\n this->tail->next_node = nullptr;\n } else {\n // Otherwise a general erasure\n node->prev_node->next_node = node->next_node;\n node->next_node->prev_node = node->prev_node;\n }\n return node;\n}\n这是 release 函数，我们可以看到，在这个过程中，tmp 虽然从链表中被剔除，但是它的内存并没有释放，同时，tmp 的 next_node 也没有改变，所以调用 tmp->next_node 理应是合法的，同理，按照您所说，collapse_edge 会百分之一百从链表中删除传入的元素，那么这个程序从 collapse 第一个节点时就会卡死，应该不至于到第 63 次 collapse 才卡死","cooked":"

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

\n","createdAt":"2024-12-20 11:35:35.980111","updatedAt":"2024-12-20 11:37:37.291231","replyToPostNumber":4,"replyCount":2,"likeCount":0,"wordCount":239,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":44829,"postNumber":6,"raw":"考虑到原函数逻辑不完善，有卡住的风险，于是对 HalfedgeMesh::isotropic_remesh() 中对 collapse 的调用做了一点改进： \n tmp=this->edges.head;\n int is_tail=0;\n while(1){\n if(tmp==this->edges.tail){\n is_tail=1;\n }\n if(tmp->length()<4.0/5.0*aver_len){\n collapse_edge(tmp);\n }\n if(is_tail==1){\n break;\n }\n else{\n tmp=tmp->next_node;\n }\n }\n但结果依然卡死，正如一开始提问说到的，问题出现在第 63 次 collapse 操作时删除点的操作之前","cooked":"

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

\n","createdAt":"2024-12-20 11:46:14.083749","updatedAt":"2024-12-20 11:46:14.083749","replyToPostNumber":5,"replyCount":0,"likeCount":0,"wordCount":92,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6108,"username":"2214312040","name":"奔","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":44830,"postNumber":7,"raw":"嗯确实不存在 segment fault 的可能，但死循环本来也不需要真的把元素的内存释放掉才会发生。因为被删除之后这个元素的 `next_node` 就没意义了，你按 `next_node` 继续遍历有可能就跑出有效的链表范围，然后试图去 collapse 一个已经被删掉的边。这时候你操作的元素之间到底是什么链接关系完全没有保证，指针指来指去又绕成环了也是有可能的。\n\n或者简单点说，你用 `next_node` 一边遍历一边删除本来就是一种不正确的做法，这不是普通的单链表或者双链表，你做的也不仅仅是链表的删除操作。","cooked":"

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

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

\n","createdAt":"2024-12-20 11:57:19.921098","updatedAt":"2024-12-20 11:58:51.239154","replyToPostNumber":5,"replyCount":0,"likeCount":0,"wordCount":201,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1381,"username":"greyishsong","name":"greyishsong","avatarUrl":"/uploads/image/da/bc/dabc731b0311f59850625bbeb55ed969fcfac0430c5ef0f68441e5466b7aa496.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":1,"hasUrlPostNumber":false}