Is there a tool for 3D Delaunay and Voronoi tessellations?

I am currently migrating all my research software to Julia, and so far I am very pleased with the experience and the relative easiness in transporting code.
I have, however, reached a bottleneck cause I can’t seem to be able to find any tool to perform a simple non-constrained Delaunay triangulation in three dimensions. As I would really like not to write a ball-pivot algorithm function myself, I was wondering how is everyone doing this, as Delaunay is one of the most standard geometrical transformations used in 3-d modelling?

3 Likes

There is a package for 2D Delaunay:

and JuliaPolyhedra has serveral packages for convex hull:

Currently I use marching cubes for meshing 3D pointclouds.

Worst case, you can always ccall Qhull or use PyCall.jl with scipy.spatial.Voronoi (which then calls Qhull).

1 Like

There is already a Julia package wrapping Qhull:

(It works via Python; might be nice to eventually have a direct wrapper.)

1 Like

Qhull.jl only wraps the convex hull part of Qhull though.

2 Likes

There’s a 4-year-old issue with a suggested implementation: https://github.com/JuliaGeometry/VoronoiDelaunay.jl/issues/8

2 Likes

so currently the solution is to use TetGen.jl?

Tetgen should work reasonably well, but we still haven’t added nice julia API.
We started to add stuff like parsing the tetgen generated files:


But it’s still incomplete. Any help / revival of the issues would be appreciated

1 Like

Please count me in, as this would be something I will need to implement anyways.

As far as I understand, Qhull only evaluates the convex hull. Couldn’t find any reference to the Delaunay and/or Voronoi tessellations.

This is slightly old, but I just wanted to mention one way to find Delaunay triangulations in arbitrary dimensions N. As explained in Wikipedia, if you know how to compute a convex hull in N+1 dimensions (which is supported by e.g. Polyhedra.jl) you can easily get Delaunay triangulations of N-dimensional points ps... by appending |ps[i]|^2 to each point ps[i], finding the convex hull, and then projecting back to N dimensions by removing the last coordinate in the vertices of the resulting hull mesh.

EDIT: I’m not so sure you can use Polyhedra.jl to decompose a convex hull into its faces in more than 3 dimensions, but you can certainly do it in 3D

In our lab, we have implemented a simple Julia wrapper to Qhull in order to compute Delaunay triangulations in arbitrary dimensions.

We interface with Qhull via ccall (instead of PyCall ), so you don’t need to install scipy in your system, just Qhull itself and a C compiler. Moreover, we are using the re-entrant version of Qhull. Thus, our wrapper should be thread-safe (even though we have not confirmed it).

Hope you find the project useful!

6 Likes

For future reference, I’ve made StarTIN.jl a work-in-progress wrapper around startin a robust Delaunay triangulator, itself written in Rust.

1 Like