网格简化：边缘折叠条件

Question

我正在尝试通过一系列边缩减来实现网格简化算法。目前，我正在遍历每个三角形，然后折叠最短的边，并且该算法是稳定的（不会超出界限）。但在某个点之后，它开始创建断裂（孔洞）伪像。如何正确确定边缩减是否可行，以便不会导致非流形伪像（或网格）？

注意：我使用半边数据结构。同时，我不想使用任何外部库，如OpenMesh或CGAL。我有我的理由不使用它们。

- jaykumarark

---

通过折叠边缘，您的意思是将构成该边缘的两个顶点合并为一个顶点，对吗？ - Tim Seguine

是的，你说得对。并且任何依赖于折叠边端点的边缘也被修改为指向新顶点。 - jaykumarark

Answer 1

对于边缘折叠，需要满足两个主要条件：

连通性

在折叠边缘的两侧，只能合并一对边。这可以通过计算两个合并顶点的公共邻居顶点数来检查（必须恰好为两个）。 考虑以下示例，其中红色边正在被折叠：

橙色边和青色边之间的三角形不再是流形。

几何学

在边缘折叠过程中三角形不能翻转。这可以通过计算保留的三角形在翻转前后的法线角度来检查。

以下示例显示了在折叠过程中绿色三角形法线发生翻转的情况：

- Nico Schertler

---

坍塌边有两个关联顶点。 对于这两个顶点，收集相邻的顶点并计算两组顶点的交集。此交集应恰好包含两个顶点。 - Nico Schertler

有人知道这个标准的证明参考吗？正向情况很明显：如果有两个以上的相邻面，很容易证明结果是非流形的。但我很好奇如何证明反向情况，即如果结果是非流形的，则必须存在两个以上的相邻面。（此外，还有一个棘手的问题，如果输入网格是孤立四面体：这个标准仍然成立，但结果会改变拓扑结构：从球变为圆盘）。 - Alec Jacobson

我不太明白为什么需要检查三角形翻转。你能给个例子吗？ - sonofrage

@sonofrage，我为这个案例添加了另一种可视化。 - Nico Schertler

好的，我想你只考虑了2D情况。但对于3D网格来说，即使三角形沿其法线翻转，仍然可能存在有效的网格。 - sonofrage