Najszybsze biblioteki triangulacji Delaunaya dla zestawów punktów 3D

Która jest najszybszą biblioteką do przeprowadzania delangijskiej triangulacji zbiorów z milionami punktów 3D? Czy dostępne są również wersje GPU? Z drugiej strony, mając teselację voronoi tego samego zestawu punktów, pomógłby (pod względem wydajności) uzyskać triangulację delaunay?

Do obliczania trójwymiarowych triangulacji Delaunaya (tak naprawdę tetraedralizacji), TetGen jest powszechnie stosowaną biblioteką.

Dla Twojej wygody poniżej przedstawiamy, jak długo trzeba obliczać terehedralizację wielu losowych punktów z kostki jednostkowej. Za 100 000 punktów stary Pentium M. zajmuje 4,5 sekundy

^{(Dokonano tego za pomocą interfejsu TetGen Mathematiki. Nie wiem, ile to narzuca.)}

Jeśli chodzi o twoje drugie pytanie: jeśli już masz teselację Voronoi, to uzyskanie triangulacji Delaunaya jest stosunkowo prostą transformacją .

gStar4D to szybki i niezawodny algorytm 3D Delaunay dla GPU. Jest implementowany przy użyciu CUDA i działa na procesorach graficznych NVIDIA.

Algorytm ten, podobnie jak GPU-DT , konstruuje najpierw cyfrowy schemat Voronoi 3D. Jednak w 3D nie można go sprowadzić do triangulacji z powodu problemów topologicznych i geometrycznych. Zamiast tego gStar4D wykorzystuje informacje o sąsiedztwie z tego diagramu do tworzenia gwiazd podniesionych do 4D i wykonuje na nich efektywne rozrzucanie gwiazd na GPU. Po wydobyciu z tego kadłuba uzyskuje się triangulację 3D Delaunay.

Najszybszą implementacją 3D Delaunay jest gDel3D , który jest hybrydowym algorytmem GPU-CPU.

Wykonuje równoległe wstawianie i przerzucanie na GPU. Wynik jest zbliżony do Delaunaya. Następnie naprawia ten wynik przy użyciu konserwatywnej metody rozrzucania gwiazd na procesorze.

Obie te metody są solidne, więc mogą obsługiwać dowolny rodzaj zdegenerowanych danych wejściowych. Mogą obsłużyć miliony punktów, jeśli pamięć GPU jest wystarczająco duża, aby pomieścić pośrednie struktury danych.

Ujawnienie: Jestem autorem tych algorytmów i implementacji :)

Poleciłbym wypróbowanie CGAL http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Section_39.2 , jak zasugerował powyżej Paul. CGAL to solidna i dobrze obsługiwana biblioteka, która istnieje już od dłuższego czasu. Korzystałem z tego z radością w przeszłości, nawet na zestawach punktów z punktami współliniowymi i współpłaszczyznowymi. Nie wiem, czy dziś jest najszybszy, ale z pewnością jest to dobre miejsce, aby zacząć.

Powyższy link zawiera również niektóre wyniki: może zarobić milion punktów w około 10 sekund i 10 milionów w około 1,5 minuty.

Jeśli masz już schemat voronoi zbioru punktów, to obliczenie triangulacji Delaunaya zajmie ci tylko O ​​(n). Odpowiednio, biorąc pod uwagę punkt voronoi, możesz uzyskać jego trójkąt Delaunay w O (1). Są podwójne, więc staraj się wykorzystywać tę sytuację, kiedy tylko jest to możliwe.

Możesz wypróbować oprogramowanie geograficzne, które rozwijam: http://alice.loria.fr/software/geogram/doc/html/index.html

Ma równoległy algorytm, który oblicza ID 14 milionów wierzchołków w mniej niż 19 sekund na Intel Core I7 (dla 1 miliona wierzchołków zajmuje to około 0,8 s)