2011-10-25 40 views

答えて

10

GPUには注意してください:Delaunay三角測量には方向性テストが必要です。浮動小数点演算ではこれらは正しく動作しないため、GPUを使用している 問題に対処するのは難しいかもしれません。また、メモリ管理も重要です。

http://www.geom.at/fade2d/html/は、最も速い堅牢な シングルスレッド実装の1つです。

17

2Dドロネー三角形分割

GPU-DT

は、GPUのための最速の2Dドロネー実装です。

GPU パラレルバンディングアルゴリズムを使用して2Dでデジタルボロノイ図を作成します。次に、これを修正して二重にして、2D三角測量を取得します。最後に、GPUでエッジフリッピングを並列実行して、2D Delaunay三角測量を取得します。

3Dドローネ三角形分割

gStar4Dは、GPUのための3Dドローネの迅速かつ堅牢な実装です。

GPU-DTと同様に、このアルゴリズムは3Dデジタルボロノイ図を最初に構築します。しかし、3Dでは、位相幾何学的な問題のために三角測量に二重化することはできません。代わりに、gStar4Dはこのダイアグラムの近傍情報を使用して4Dに持ち上げられた星を作成し、GPU上で効率的にスタースプレイを実行します。これから下部船体を抽出することによって、3D Delaunay三角測量が得られる。

より速い代替方法は、ハイブリッドGPU-CPUアルゴリズムであるgDel3Dです。

GPUでの並列挿入と反転を実行します。結果はDelaunayに近い。その後、CPU上で保守的なスタースプレイ法を使用してこの結果を修正します。

これらの方法はすべて堅牢であるため、あらゆる種類の縮退入力を処理できます。

関連する問題