如何处理算法“通过二次误差最小化进行网格简化”中的三角形折叠

Question

最近我正在实现QEM网格简化算法，该算法最初来自Michael Garland和Paul S. Heckbert的论文Surface Simplification Using Quadric Error Metrics。

根据该算法，我们应该为每条边计算一个收缩成本，并将所有边放入一个最小堆中，以便每次选择代价最小的边进行收缩。然而，收缩可能会导致相邻的三角形折叠，即在收缩前后法线发生90度以上的变化。折叠现象可以通过以下示例可视化:

假设我们选择的最小成本边是V1V2，我们将要缩小它。 我们预见到收缩将导致V1和V2合并在一起，如图所示。 更重要的是，如果我们将三角形Tri(ABV2)的范数定义为cross_product(V2A, V2B)，我们可以发现这个范数从向外指向向内指向。 这不是我们想要的。 文章说，如果遇到这种情况，我们应该“惩罚”这个操作，即将一个大数添加到V1V2的成本中，以使V1V2不再是堆顶部，这意味着它此时不会被选中。 相反，我们将选择下一个最小成本的边。

该算法可以用以下伪代码编写：

while (number_of_left_edges > Pre_defined_number)
{
    Edge e = EdgeHeap.top();
    if (Check_edge_will_cause_foldover(e))
    {
         e.cost += A_VERY_LARGE_NUMBER;
         EdgeHeap.update();
    }
    else
    {
         e.Contract();
         Do_something_on_incident_triangles(e.Triangles);
         EdgeHeap.pop();
    }
}

然而，我遇到了一个非常棘手的问题。如前所述，当我发现一条边 E1 的收缩可能会导致一些三角形的折叠时，我增加了其成本并将其放回堆中，然后选择另一条边 E2，但仍然发现它会引起折叠。诸如此类。我没有找到可以进一步收缩的边，因此循环无限继续，并且实际上没有任何边被简化。

有人能给我任何关于算法的提示，以解决这个问题吗？非常感谢！

- C. Wang

---

我知道这个问题很旧了，但你有找到解决方案吗？我也对这个问题感到困惑。在所示的示例中，一个解决方案可能是删除从B到V1V2的边，并添加一条新的边来填补涉及A的结果孔。 - jms

Answer 1

这里的好解决方案是在从最小堆中提取边缘并在其被收缩之前检查可能的正常反转（折叠）。如果检查失败，则无论如何不会对该边进行惩罚，而只是暂时跳过它，并且在邻居之一被收缩后，它可以随后出现在最小堆中。

检查可以用伪代码实现，如下所示：

//average normal of the mesh region around the edge being checked before contraction
Vector3 beforeNormal = ...
// now check all triangles to appear after contraction
for ( afterTri : ... )
   if ( dot( norm(afterTri), beforeNormal ) < 0 )
       return //check failed
return //check passed

这种方法是通过实现MeshLib来完成的，它基于同一篇论文，拥有快速和高质量的网格简化模块。在MRMeshDecimate.cpp文件中对应的代码为

auto n = Vector3f{ sumDblArea_.normalized() };
for ( const auto da : triDblAreas_ )
    if ( dot( da, n ) < 0 )
        return {};

- Fedor