如何从半边结构中移除边缘？

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 个新生成的半边之间的连接顶点。
• 删除两个面、未使用的顶点和选定的半边。