algorithm - 如何从半边结构中去除边？

Question

我正在尝试实现一种算法来从半边结构中删除边和顶点。有关插图，请参阅附图:





我知道有像 Openmesh 和 CGAL 等库可以帮助我实现这一目标，但我计划自己实现它。

我原来的想法是这样的:

1. Find out the half edges associated with that edge
2. Find out all the faces associated with each half edge
3. Find out all the edges and vertices corresponds to each face
4. Not sure how to merge them together ie how to merge edge 1 edge 2, vertex 4 and 2 and edge 5 and 4 in the attached graph.
5. Delete all the faces.
6. Delete all the half edges

如果我在正确的轨道上，有人可以提出一些建议吗？

我也在网上做了一些研究，发现网上的一篇文章似乎很有帮助。

这是链接:http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm

在移除边缘部分下，它列出了以下步骤:

1.Remove all of the polygons connected to the edge.
2.Link the half-edges of the edge off from the mesh.
3.Deallocate the edge and its half-edges.

第一个和最后一个对我来说很有意义。但是，我不确定作者所说的将边缘的半边从网格中链接出来是什么意思？有人可以向我解释一下吗？谢谢!

Answer 1

我将这个问题的意思是“如何实现边缘折叠”。
一旦你有一个有效的半边 DS，算法本身就没有那么复杂。

抓取边连接的 2 个顶点

将它们的出半边指针设置为 next选定的半边和对(以避免创建无效指针)

获取下一个半边，上一个将它们设置为新的半边对。

对选定的半边

执行相同操作

选择与半边相对的任一顶点。将其设置为 2 个新生成的半边之间的连接顶点。

删除两个面、未使用的顶点和选定的半边。