2

最近、私は QEM メッシュ単純化アルゴリズムを実装しています。これは、元は Michael Garland と Paul S. Heckbert の論文Surface Simplication Using Quadric Error Metricsからのものでした。

アルゴリズムによれば、contraction costエッジごとに a を計算し、すべてのエッジを最小限のヒープに入れる必要があります。これにより、収縮するための最小コストでエッジを選択するたびになります。ただし、収縮により、入射三角形が折りたたまれる場合があります。つまり、収縮の前後でノルムが 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しましたが、それでも折り返しが発生することがわかりました。などなど。ループが無限に続き、実際にはエッジが単純化されないように、エッジをこれ以上縮小できないことがわかりませんでした。

問題を解決するために、アルゴリズムについてのヒントを教えてくれる人はいますか? どうもありがとう！

ここに画像の説明を入力

4

0 に答える 0