geometry - GPU で利用可能な最速の Delaunay 三角形分割アルゴリズム

Question

GPU で利用可能な最速の Delaunay 三角形分割アルゴリズムはどれだと思いますか? またはより一般的には、並行して

Answer 1

2D Delaunay 三角形分割

GPU-DTは、GPU の最速の 2D Delaunay 実装です。

GPU並列バンディング アルゴリズムを使用して、デジタル ボロノイ図を 2D で構築します。次に、これを修正して二元化し、2D 三角形分割を取得します。最後に、GPU で並列にエッジ フリッピングを実行して、2D Delaunay 三角形分割を取得します。

3D Delaunay 三角形分割

gStar4Dは、GPU 向けの 3D Delaunay の高速で堅牢な実装です。

GPU-DT と同様に、このアルゴリズムは最初に 3D デジタル ボロノイ図を作成します。ただし、3D では、トポロジーおよび幾何学的な問題により、これを三角形分割に二重化することはできません。代わりに、gStar4D は、このダイアグラムからの近隣情報を使用して、4D にリフトされた星を作成し、GPU 上で効率的に星の散布を実行します。これより下部船体を抽出することにより、3D Delaunay 三角形分割が得られます。

より高速な代替手段は、ハイブリッド GPU-CPU アルゴリズムであるgDel3Dです。

GPU で並列挿入と反転を実行します。結果はドロネーに近い。次に、CPU で保守的な星の広がり方を使用して、この結果を修正します。

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

Answer 2

GPU には注意してください: Delaunay Triangulations には向きのテストが必要です。これらは浮動小数点演算では確実に機能せず、GPU を使用してその問題に対処するのは難しいかもしれません。また、メモリ管理も重要です。

最速の堅牢なシングル スレッド実装の 1 つであるhttp://www.geom.at/fade2d/html/を試してみてください。