半边折叠

Question

我目前正试图实现一种半边折叠算法，以执行增量重建。我正在处理一个流形网格。请考虑以下简单的网格：

目标是将a折叠成b。

但在这种情况下，会导致非流形网格

我希望避免这种情况。我的问题是：

在折叠之前如何做到这一点，即在折叠之前进行检查以确定折叠操作是否安全？

我已经尝试了Hoppe的标准（链条件），但似乎两者都得到了满足。此外，a和b的1环的唯一相交点是c，因此只有一个点，因为它是边界边缘。

总的来说，我还需要执行哪些检查以避免非法折叠？

现在，我有以下标准：

• 如果a和b都是边界顶点，则边ab必须是边界边缘
• a、b和相邻于边ab的三角形的第三个顶点必须是有效的三角形（链条件）
• 如果与边ab相邻的三角形是边界三角形，则如果a在边界边上，则不要折叠
• 如果a-1环和b-1环的交集不等于二（或对于边界边缘为一），则不要折叠

- peacer212

---

我投票关闭此问题，因为它似乎涉及一般数学/几何问题，而不是根据[帮助中心]定义的编程问题。 - TylerH

这是一个很棒的例子。感谢您的说明。 - Justin Meiners

Answer 1

您可能想要查看这篇论文：

Tamal Dey、Herbert Edelsbrunner、Sumanta Guha和Dmitry Nekhayev。保持拓扑性的边缩减。

我不确定您所指的是Hoppe的哪篇论文（渐进网格？），但Tamal Dey的链接条件与您所述的条件不同。直观来说，如果满足一个边ab可折叠，那么

one-ring(a) intersected with one-ring(b) == one-ring(ab).

对于一条边ab，它的一环是与ab共享面的其他顶点的集合。此外，在Tamal Dey的链接条件中，您需要考虑嵌入空间的维数（即，2D和3D中的边的链接条件不同）。许多其他工作使用此链接条件来折叠边缘而不产生拓扑错误。

令人困惑的是，从您的示例中我无法确定它是3D还是2D的带边界网格，或者它有多“平面”。这些因素决定了生成的网格是否具有“折叠”，例如，在2D中，三角形bcd被认为是折叠的，但如果网格不是平面的，则可能是正常的3D网格。

- danielyan86129

---

感谢您的回答，我提出这个问题已经有一段时间了。这个例子只是简单的二维情况，除了 c 之外的所有顶点都是边界顶点。快速浏览一下条件： one-ring(a) = {b,c,d}, one-ring(b)={a,c,e}, one-ring(ab)={c}，这意味着 one-ring(a) intersected one-ring(b) = {c} = one-ring(ab)，所以即使 bcd 折叠，条件也会被满足，对吗？ - peacer212

是的，在这种情况下，即使存在几何折叠，链接条件仍应得到满足。问题在于此条件只旨在保持拓扑不变，而非避免几何伪影。为了防止三角形折叠，我认为您需要将受影响的顶点向外微调，例如重新计算顶点c作为其一环的加权和，或实际上延迟折叠那些会导致大变形的边缘。 - danielyan86129

这也是边缘坍塌或网格简化框架的工作原理，使用几何错误为每个边缩并分配优先级。我也在做类似的事情，但几何失真不是我的关注点，因为我只折叠长度为0的边缘。希望这个讨论有所帮助。 - danielyan86129

再次感谢您的帮助。那么有没有办法事先检查折叠操作是否会导致折叠呢？我看过几个库这样做，但大多数在操作后执行检查，并在折叠的情况下将其反转。一年前，在Matlab的增量重网格化上下文中，我做过这件事，并为此编写了一个OpenMesh包装器，如果有帮助的话，可以在https://github.com/christopherhelf/isotropicremeshing找到它。 - peacer212

@danielyan86129，我的建议仅适用于几何失真，对于非流形面，还有其他检查需要进行。 - vcloarec