2

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

根据算法，我们应该contraction cost为每条边计算a，并将所有边放入一个最小堆中，这样每次我们都以最小的成本选择一条边来收缩。然而，收缩可能导致入射三角形折叠，即在收缩前后范数变化超过90度。折叠现象可以通过以下示例进行可视化：

假设我们获得最小成本的边是V1V2，并且我们即将收缩它。如图所示，我们预计收缩将导致V1并V2合并在一起。更重要的是，如果我们将三角形的范数定义Tri(ABV2)为cross_product(V2A, V2B)，我们可以发现这个范数的方向从指向外变为向内。这不是我们想要的。论文中说，如果遇到这种情况，我们应该“惩罚”这个操作，即在 's 的成本上增加一个大数，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，但仍然发现它会导致折叠。如此等等。我没有发现一条边可以再收缩，从而使循环无限继续，实际上没有一条边可以简化。

有没有人可以给我关于算法的任何提示，以便解决问题？太感谢了！

在此处输入图像描述

4

0 回答 0