Perpustakaan triangulasi Delaunay tercepat untuk set poin 3D

26

Yang merupakan perpustakaan tercepat untuk melakukan triangulasi set delaunay dengan jutaan jika poin 3D? Apakah ada juga versi GPU yang tersedia? Dari sisi lain, memiliki voronoi tessellation dari set poin yang sama, akan membantu (dalam hal kinerja) untuk mendapatkan triangulasi delaunay?

Buka jalan
sumber
Sudahkah Anda mencoba implementasi di perangkat lunak CGAL dan TRIANGLE? Keduanya termasuk algoritma , yang (secara teoritis) adalah yang tercepat yang tersedia (walaupun tidak secara paralel). O(nlog(n))
Paul
Jonathan Shewchuk juga memiliki versi streaming untuk 2D yang dapat menangani kumpulan data yang sangat besar jika Anda dapat menambahkan beberapa data tambahan ke aliran Anda. Untuk apa Anda menggunakan ini?
Victor Liu

Jawaban:

13

Untuk menghitung triangulasi tiga dimensi Delaunay (tetrahedralizations, sungguh), TetGen adalah perpustakaan yang umum digunakan.

Untuk kenyamanan Anda, inilah patokan kecil tentang berapa lama waktu yang dibutuhkan untuk menghitung terehedralisasi sejumlah titik acak dari unit cube. Untuk 100.000 poin, dibutuhkan 4,5 detik pada Pentium M. lama

Grafik Mathematica

(Ini dilakukan dengan antarmuka TetGen Mathematica. Saya tidak tahu berapa banyak overhead yang diperkenalkan.)

Mengenai pertanyaan Anda yang lain: jika Anda sudah memiliki hubungan Voronoi, maka mendapatkan triangulasi Delaunay adalah transformasi yang relatif sederhana .

Szabolcs
sumber
10

gStar4D adalah algoritma Delaunay 3D yang cepat dan tangguh untuk GPU. Ini diimplementasikan menggunakan CUDA dan bekerja pada NVIDIA GPU.

Mirip dengan GPU-DT , algoritma ini membangun diagram Voronoi digital 3D terlebih dahulu. Namun, dalam 3D ini tidak dapat digandakan ke triangulasi karena masalah topologi dan geometris. Sebagai gantinya, gStar4D menggunakan informasi lingkungan dari diagram ini untuk membuat bintang-bintang terangkat ke 4D dan melakukan penyebaran bintang pada mereka secara efisien di GPU. Dengan mengekstraksi lambung bawah dari ini, triangulasi 3D Delaunay diperoleh.

The fastest 3D Delaunay implementation is gDel3D, which is a hybrid GPU-CPU algorithm.

It performs parallel insertion and flipping on the GPU. The result is close to Delaunay. It then fixes this result using a conservative star splaying method on the CPU.

Both these methods are robust, so they can handle any kind of degenerate input. They can handle millions of points, if you have GPU memory large enough to hold the intermediate data structures.

Disclosure: I am the author of these algorithms and implementations :)

Ashwin Nanjappa
sumber
Welcome to SciComp.Se, Ashwin! In the interest of full disclosure, you should add that you are the author of this software (see meta.scicomp.stackexchange.com/a/342/1804).
Christian Clason
3

I would recommend trying CGAL http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Section_39.2 , as Paul suggested above. CGAL is a robust and well-supported library that has been around quite some time. I've used it happily in the past, even on point sets with co-linear and co-planar points. I don't know if it's the very fastest today, but it is certainly a good place to start.

The link above also includes some performance numbers: it can do a million points in about 10 seconds, and 10 million in about 1.5 mins.

batty
sumber
Also, could you expand on why you recommend it? Do you have experience with it?
Godric Seer
1

If you already have the voronoi diagram of a set of points, then computing the Delaunay triangulation will only take you O(n). Equivalently, given a voronoi point, you can obtain its Delaunay triangle in O(1). They are dual so try exploiting this situation whenever is possible.

labotsirc
sumber
1

You can try the geogram software that I'm developping: http://alice.loria.fr/software/geogram/doc/html/index.html

It has a parallel algorithm that computes the DT of 14 million vertices in less than 19 seconds on an Intel Core I7 (for 1 million vertices it takes around 0.8 s)

BrunoLevy
sumber
Welcome to SciComp.SE! In the interest of full disclosure (and to show that you know what you are talking about), you should mention that you are the developer of this software.
Christian Clason