11

パフォーマンス上の理由から GLU を使用する前に、最初にそのようなアルゴリズムを実装しようとしたので、好奇心からこの質問をしています。

私は一般的なアルゴリズム (Delaunay、Ear Clipping がよく言及されます) を調べましたが、GLU がどのようにその仕事を常にうまく行っているのか理解できないようです。

そのテーマに関する興味深い論文や記事を持っている人はいますか?

4

1 に答える 1

18

ソースの横にいくつかのメモがあります：

これは非常に簡単な概要です。ソースコード自体には、かなりの量の追加ドキュメントがあります。

ロバストなテッセレーションの目標

テッセレーション アルゴリズムは基本的に 2D アルゴリズムです。最初にすべてのデータを平面に射影します。私たちの目標は、投影されたデータを堅牢にテセレートすることです。次に、同じトポロジー テッセレーションが入力データに適用されます。

トポロジー的に、出力は常にテッセレーションである必要があります。入力がわずかでも非平面である場合、ある角度から見たときにいくつかの三角形は必然的に後ろ向きになりますが、目標はこの影響を最小限に抑えることです。

アルゴリズムには、入力データと独自の計算の数値エラーをクリーンアップする機能が必要です。これを行う 1 つの方法は、上で定義したように許容範囲を指定し、ライン スイープ プロセス中に入力と出力をクリーンアップすることです。少なくとも、アルゴリズムは、一致する頂点、エッジに付随する頂点、および一致するエッジを処理する必要があります。

アルゴリズムのフェーズ

  1. ポリゴン法線 N を見つけます。
  2. 頂点データを平面に投影します。法線に対して垂直である必要はありません。
    N との内積が最大になる座標軸に垂直な平面に射影できます。
  3. ライン スイープ アルゴリズムを使用して、平面を x モノトーン領域に分割します。任意の垂直線は、多くても 1 つの間隔で x モノトーン領域と交差します。
  4. x-monotone 領域を三角測量します。
  5. 三角形をストリップとファンにグループ化します。

法線ベクトルを見つける

ポリゴン法線を見つける一般的な方法は、ポリゴンが 3 つの座標軸に沿って投影されたときに符号付き面積を計算することです。等高線は縮退することなくゼロ領域を持つことができるため、これを行うことはできません (ボウタイなど)。

頂点データが等高線にどのように接続されているかを無視して、平面を頂点データに適合させます。理想的には、これは最小二乗フィットになります。ただし、この目的では、法線の精度は重要ではありません。代わりに、大きく離れた 3 つの頂点を見つけ、それらが形成する三角形の法線を計算します。頂点は、三角形が、入力頂点を使用して形成される三角形の最大面積の少なくとも 1/sqrt(3) 倍の面積を持つように選択されます。

輪郭は法線の方向に影響します。法線を計算した後、符号付き輪郭領域の合計が負でないことを確認し、必要に応じて法線を反転します。

頂点の投影

3 つの座標軸の 1 つに垂直な平面に頂点を投影します。これにより、元の入力データとアルゴリズムによって処理されたデータとの間の変換ステップが削除されるため、数値の精度が向上します。プロジェクションは入力データも圧縮します。投影後の頂点間の 2D 距離は、元の 2D 距離よりも小さくなる場合があります。ただし、法線との内積が最大になる座標軸を選択すると、圧縮係数は最大で 1/sqrt(3) になります。

法線の精度はそれほど重要ではありませんが (とにかく座標軸に垂直に投影しているため)、 計算の堅牢性は重要です。たとえば、ほとんど線に沿って位置する多くの頂点と、線から十分に離れた 1 つの頂点 V がある場合、通常の計算では V を使用する必要があります。そうしないと、結果がガベージになります。

ポリゴンの法線に対して垂直に投影する利点は、計算された交点が理想的な位置にできるだけ近くなることです。この動作を取得するには、TRUE_PROJECT を定義します。

ラインスイープ

メッシュ、イベント キュー、エッジ ディクショナリの 3 つのデータ構造があります。

メッシュは、現在の分解のトポロジを記録する「クワッド エッジ」データ構造です。詳細については、インクルード ファイル「mesh.h」を参照してください。

イベント キューは、すべての頂点 (元の頂点と計算された頂点の両方) を保持するだけで、x 座標が最小の頂点 (およびその中で y 座標が最小の頂点) をすばやく抽出できるように整理されています。

エッジ ディクショナリは、スイープ ラインとポリゴンの領域との現在の交点を記述します。これは、スイープ ラインと交差するエッジを現在の交差順序で並べ替えたものです。エッジのペアごとに、それらの間のモノトーン領域に関する情報を保存します。これらは「アクティブ領域」と呼ばれます (現在のスイープ ラインが交差しているため)。

基本的なアルゴリズムは、各頂点を処理しながら左から右にスイープすることです。メッシュの処理された部分 (スイープ ラインの左側) は平面分解です。各頂点を交差するときに、メッシュとエッジ ディクショナリを更新し、新しく隣接するエッジのペアをチェックして、それらが交差するかどうかを確認します。

頂点は、任意の数のエッジを持つことができます。頂点がマージされ、交点が計算されると、多くのエッジを持つ頂点が作成されます。未処理の頂点 (スイープ ラインの右側) の場合、これらのエッジは頂点の周りで特定の順序ではありません。処理された頂点の場合、トポロジーの順序は幾何学的な順序と一致する必要があります。

頂点処理は 2 つのフェーズで行われます。最初に処理するのは左向きのエッジです (これらのエッジはすべて現在エッジ ディクショナリにあります)。これには以下が含まれます。

  • ディクショナリから左向きのエッジを削除します。
  • 必要に応じてメッシュを再リンクして、イベント頂点の周りのこれらのエッジの順序が辞書内の順序と一致するようにします。
  • 巻き数に応じて、終了領域 (左方向の 2 つのエッジの間にある領域) を「内側」または「外側」としてマークします。

左向きのエッジがなく、イベントの頂点が「内部」領域にある場合は、エッジを追加する必要があります (領域を単調な断片に分割するため)。これを行うには、イベントの頂点を、含まれている領域の上端または下端の右端の端点に結合するだけです。

次に、右向きのエッジを処理します。これには以下が含まれます。

  • エッジ ディクショナリにエッジを挿入します。
  • 新しく作成されたアクティブ領域の巻き数を計算します。
    これは、ディクショナリをたどるときに交差する各エッジの曲がりを使用して、段階的に計算できます。
  • 必要に応じてメッシュを再リンクして、イベント頂点の周りのこれらのエッジの順序が辞書内の順序と一致するようにします。
  • 交差および/またはマージについて、新しく隣接するエッジをチェックします。

右向きのエッジがない場合は、1 つ追加して、包含領域を単調な断片に分割する必要があります。この場合、いずれかの包含エッジの左端右エンドポイントにエッジを追加するのが最も便利です。ただし、後でこれを変更する必要がある場合があります (詳細については、コードを参照してください)。

不変条件

これらは、スイープ中に維持される最も重要な不変条件です。頂点がスイープ ラインと交差する順序を定義する関数 VertLeq(v1,v2) と、スイープ イベント位置 "loc" で e1 が e2 より下にあるかどうかを示す関数 EdgeLeq(e1,e2; loc) を定義します。この関数は、{e1,e2} の一番左端と {e1,e2} の一番左端の間のスイープ イベント位置でのみ定義されます。

エッジ ディクショナリの不変条件。

  • 隣接するエッジの各ペア e2=Succ(e1) は、スイープ イベントの任意の有効な位置で EdgeLeq(e1,e2) を満たします。
  • EdgeLeq(e2,e1) も (有効なスイープ イベントで) ある場合、e1 と e2 は共通のエンドポイントを共有します。
  • ディクショナリ内の各 e について、e->Dst は処理されていますが、e->Org は処理されていません。
  • 各エッジ e は VertLeq(e->Dst,event) && VertLeq(event,e->Org) を満たします。ここで、「event」は現在のスイープ ライン イベントです。
  • 長さゼロのエッジ e はありません。

  • 左右の終点が同じエッジは 2 つありません。メッシュ (処理された部分) の不変条件。

  • スイープ ラインの左側のメッシュ部分は、平面グラフです。飛行機に埋め込む方法があります。

  • 長さがゼロの処理済みエッジはありません。
  • 処理された 2 つの頂点が同じ座標を持つことはありません。
  • 各「内側」領域は単調です。VertLeq(v1,v2) に従って、単調増加する頂点の 2 つのチェーンに分割できます。
    • 非不変: これらのチェーンは、数値エラーにより (わずかに) 交差する場合がありますが、アルゴリズムの動作には影響しません。

スイープの不変条件。

  • 頂点に左向きのエッジがある場合、これらは頂点の処理時にエッジ ディクショナリに存在する必要があります。
  • エッジが「fixUpperEdge」とマークされている場合 (これは ConnectRightVertex によって導入された一時的なエッジです)、関連付けられた頂点から右に向かう唯一のエッジです。(これは、これらのエッジが必要な場合にのみ存在することを意味します。)

堅牢性

アルゴリズムの堅牢性の鍵は、上記の不変条件、特にエッジ ディクショナリの正しい順序を維持することです。これは次の方法で実現します。

  1. 最大速度ではなく最大精度の数値計算を記述します。

  2. エッジ交差計算の結果についてまったく仮定を行わない - 十分に縮退した入力の場合、計算された位置は乱数よりもはるかに優れているわけではありません。

  3. 数値エラーが不変条件に違反する場合は、必要に応じてトポロジーを変更して元に戻します (つまり、メッシュ構造を再リンクします)。

三角測量とグループ化

三角測量を行う前にライン スイープを終了します。これは、モノトーン領域が完成した後でも、さらに頂点がマージされるため、その頂点データがさらに変更される可能性があるためです。

すべてのモノトーン領域を三角形分割した後、三角形をファンとストリップにグループ化します。私たちは貪欲なアプローチを使用してこれを行います。三角形分割自体は、プリミティブの数を減らすために最適化されていません。計算された三角形分割の合理的な分解を得ようとするだけです。

于 2012-10-12T04:58:44.377 に答える