25
$\begingroup$

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of the same set of points, would help (in terms of performance) for getting the delaunay triangulation?

$\endgroup$
  • $\begingroup$ Have you tried the implementations in the CGAL and TRIANGLE softwares? Both include $O(nlog(n))$ algorithms, which are (theoretically) the fastest available (albeit not in parallel). $\endgroup$ – Paul Apr 23 '12 at 17:58
  • $\begingroup$ Jonathan Shewchuk also has a streaming version for 2D that can handle ridiculously large datasets if you can add some extra data to your stream. What are you using this for? $\endgroup$ – Victor Liu Apr 24 '12 at 10:27
12
$\begingroup$

For computing three-dimensional Delaunay triangulations (tetrahedralizations, really), TetGen is a commonly used library.

For your convenience, here's a little benchmark on how long it takes to compute the terehedralization of a number of random points from the unit cube. For 100,000 points it takes 4.5 seconds on an old Pentium M.

Mathematica graphics

(This was done with Mathematica's TetGen interface. I don't know how much overhead it introduces.)

Regarding your other question: if you already have the Voronoi tessellation, then getting the Delaunay triangulation is a relatively simple transformation.

$\endgroup$
10
$\begingroup$

gStar4D is a fast and robust 3D Delaunay algorithm for the GPU. It is implemented using CUDA and works on NVIDIA GPUs.

Similar to GPU-DT, this algorithm constructs the 3D digital Voronoi diagram first. However, in 3D this cannot be dualized to a triangulation due to topological and geometrical problems. Instead, gStar4D uses the neighborhood information from this diagram to create stars lifted to 4D and performs star splaying on them efficiently on the GPU. By extracting the lower hull from this, the 3D Delaunay triangulation is obtained.

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 :)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also, could you expand on why you recommend it? Do you have experience with it? $\endgroup$ – Godric Seer Jul 25 '13 at 18:02
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Christian Clason Jul 11 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.