Najszybszy dostępny algorytm triangulacji Delaunay dla GPU

Question

Który z nich jest Twoim zdaniem najszybszym algorytmem triangulacji Delaunay dla GPU? Lub bardziej ogólnie, równolegle

Answer 1

Uważaj na GPU: Trójkąty Delaunay wymagają testów orientacyjnych. Nie działają one niezawodnie z arytmetyką zmiennoprzecinkową i może być trudno poradzić sobie z tym problemem za pomocą GPU. Również zarządzanie pamięcią ma kluczowe znaczenie.

Być może warto wypróbować wersję http://www.geom.at/fade2d/html/, która jest jedną z najszybszych, solidnych implementacji jednowątkowych wersji .

Answer 2

triangulacji Delaunay 2D

GPU-DT jest najszybsza realizacja 2D Delaunay dla GPU.

Konstruuje cyfrowy diagram Voronoi w 2D za pomocą GPU Równoległy algorytm pasmowania. Następnie ustala i dualizuje to, aby uzyskać triangulację 2D. Na koniec wykonuje równoległe obracanie krawędzi na GPU w celu uzyskania triangulacji 2D Delaunay.

triangulacji Delaunay 3D

gStar4D jest szybka i solidna realizacja 3D Delaunaya dla GPU.

Algorytm ten, podobnie jak GPU-DT, najpierw konstruuje 3D cyfrowy diagram Voronoi. Jednak w 3D nie można tego dokonać w triangulacji ze względu na problemy topologiczne i geometryczne. Zamiast tego, gStar4D wykorzystuje informacje o okolicy z tego diagramu, aby utworzyć gwiazdy podniesione do 4D i efektywnie je rozdziela na GPU. Wyodrębniając z tego dolny kadłub, uzyskuje się triangulację 3D Delaunaya.

Szybsza alternatywa to gDel3D, który jest hybrydowym algorytmem GPU-CPU.

Umożliwia równoległe wstawianie i odbijanie na GPU. Wynik jest zbliżony do Delaunay. Następnie poprawia ten wynik, stosując zachowawczą metodę rozgrywania gwiazd na procesorze.

Wszystkie te metody są solidne, dzięki czemu mogą obsłużyć wszelkiego rodzaju zdegenerowane dane wejściowe.