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

afas · January 11, 2019, 3:48am

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?

Gnimuc · January 11, 2019, 4:05am

There is a package for 2D Delaunay:

and JuliaPolyhedra has serveral packages for convex hull:

Currently I use marching cubes for meshing 3D pointclouds.

tkoolen · January 11, 2019, 4:18am

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

stevengj · January 11, 2019, 4:33am

There is already a Julia package wrapping Qhull:

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

tkoolen · January 11, 2019, 4:44am

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

mkborregaard · January 11, 2019, 7:59am

There’s a 4-year-old issue with a suggested implementation: 3D Delaunay · Issue #8 · JuliaGeometry/VoronoiDelaunay.jl · GitHub

Gnimuc · January 11, 2019, 1:09pm

so currently the solution is to use TetGen.jl?

sdanisch · January 11, 2019, 2:03pm

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:

github.com

JuliaGeometry/TetGen.jl/blob/master/src/TetGen.jl#L45


      
          module TetGen
          using DocStringExtensions
          using TetGen_jll
          
          
using GeometryBasics
          using GeometryBasics: Polygon, MultiPolygon, Point, LineFace, Polytope, Line,
              Simplex, connect, Triangle, NSimplex, Tetrahedron,
              TupleView, TriangleFace, SimplexFace, LineString, Mesh, TetrahedronP, TriangleP,
              NgonFace, Ngon, faces, coordinates, metafree, meta, faces
          
          

          
using Printf
          
          
using StaticArrays
          
          

          
include("cpptetgenio.jl")
          include("jltetgenio.jl")
          include("rawtetgenio.jl")
          include("meshes.jl")
          include("api.jl")
          
          

          
export tetrahedralize
          export tetunsuitable
          export TetGenError
          export RawTetGenIO, facetlist!, RawFacet
          export numberofpoints,numberoftetrahedra,numberoftrifaces,numberofedges
          export volumemesh,surfacemesh
          
          
end # module

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

afas · January 14, 2019, 10:15pm

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

afas · January 14, 2019, 10:17pm

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

pablosanjose · April 24, 2019, 12:04pm

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

fverdugo · March 4, 2020, 4:07pm

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!

evetion · March 9, 2021, 7:47am

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