5

Unity を使用していますが、ソリューションは一般的なものにする必要があります。閉じた不規則な多角形の頂点リストを定義するマウス クリックからユーザー入力を取得します。その頂点は、フラット 3D メッシュの外側のエッジを定義します。

Unity でプロシージャルにメッシュを生成するには、すべての頂点とそれらを接続して三角形を形成する方法を指定する必要があります。

したがって、凸多角形の場合は簡単です。頂点が 1、2、3、次に 1、3、4 などの三角形を作成して、孔雀の尾のようなものを形成します。

しかし、凹面ポリゴンの場合はそれほど単純ではありません。内部三角形を見つけるための効率的なアルゴリズムはありますか?

4

3 に答える 3

6

制約付きのDelaunay三角形分割を利用できます（実装は簡単ではありません！）。TriangleおよびCGAL内で優れたライブラリ実装が利用可能であり、効率的なO(n*log(n))実装を提供します。

頂点セットが小さい場合は、耳を切り取るアルゴリズムも可能ですが、必ずしもドロネー三角形分割（通常は最適ではない三角形が生成されます）が得られ、で実行されるとは限りませんO(n^2)。ただし、自分で実装するのは非常に簡単です。

入力頂点は3D空間の平面上に存在するため、平面に投影し、2Dで三角形分割を計算してから、同じメッシュトポロジを3D頂点セットに適用することで2D問題を取得できます。

于 2012-11-13T22:14:06.153 に答える
2

次のように耳クリッピング アルゴリズムを実装しました。

  1. 凸頂点 v が見つかるまで頂点を反復します
  2. 多角形上の任意の点が三角形 (v-1、v、v+1) 内にあるかどうかを確認します。存在する場合は、頂点 v に沿ってポリゴンを分割する必要があり、線から最も離れた点 (v-1、v+1) です。両方のパーティションを再帰的に評価します。
  3. 頂点 v の周りの三角形に他の頂点が含まれていない場合は、三角形を出力リストに追加し、頂点 v を削除します。完了するまで繰り返します。

ノート：

  1. これは、3D 面で作業している場合でも、本質的に 2D 操作です。この問題を 2D で考えるには、絶対値が最大である面の法線のベクトル座標を単純に無視します。(これは、3D 面を 2D 座標に「投影」する方法です)。たとえば、面の法線が (0,1,0) の場合、y 座標を無視して x,z 平面で作業します。
  2. どの頂点が凸状であるかを判断するには、まずポリゴンのワインディングを知る必要があります。これは、多角形の左端 (最小の x 座標) の頂点を見つけることで判断できます (最小の y を見つけることで同点を解消します)。このような頂点は常に凸状であるため、この頂点のワインディングによってポリゴンのワインディングが得られます。
  3. 符号付き三角形の面積方程式を使用して、ワインディングおよび/またはコンベクシティを決定します。http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htmを参照してください。ポリゴンのワインディングに応じて、正の面積 (反時計回りのワインディング) または負の面積 (時計回りのワインディング) のいずれかを持つすべての凸三角形があります。
  4. 三角形の点の式は、符号付き三角形の面積の式から作成されます。参照:点が 2D 三角形にあるかどうかを判断する方法は? .
  5. どの頂点 (v) が線から最も離れているかを判断する必要があるステップ 2 では、三角形 (L0、v、L1) を形成し、どれが最大の面積 (絶対値、 '特定の巻き方向を想定しています)
  6. このアルゴリズムは、自己交差ポリゴンに対して適切に定義されていません。浮動小数点精度の性質により、このようなケースに遭遇する可能性があります。安定性のためにいくつかのセーフガードを実装できます。(このような場合は自己交差を示しており、この頂点に沿ってセットを分割するべきではありません)。パーティションが完全に凹状になっている (つまり、元のポリゴンの巻き方とは異なる巻き方になっている) 状況に遭遇する場合があります。このパーティションは破棄する必要があります。
  7. アルゴリズムは循環的であり、セットの分割を伴うため、格納用の配列で双方向リンク リスト構造を使用すると非常に効率的です。その後、セットを 0(1) に分割できますが、アルゴリズムの平均実行時間は依然として O(n^2) です。最適な実行時間は、実際には何度も分割する必要があるセットです。これにより、比較の数が急速に減少します。
于 2012-11-15T10:42:12.870 に答える
1

凹面ポリゴンを三角測量するためのコミュニティ スクリプトがありますが、個人的には使用していません。著者は、2D だけでなく 3D ポイントでも機能すると主張しています。

問題を 2D に制限したい場合に過去に使用したハックの 1 つは、主成分分析を使用して 3D データで最大の変化の 2 つの軸を見つけ、これらを「X」と「Y」にすることです。

于 2012-11-14T14:54:45.463 に答える