Building the tetrahedra of a set of random points - tetrahedralization

Question

I have a set of points (1 million of them, possibly more in the future, like 10 or 100 million) in 3D space that forms a sphere (they fill the sphere - they're not just on the surface) and I would like to build the tetrahedra that connect each sphere to its first neighbours... Looking for tetrahedralization, so far, all I found is :

• algorithms for meshing, but they fill empty spaces as far as I understand, whereas my points are fixed.
• algorithms for surface viewing, which is quite irrelevant
• algorithms for 3D images viewing (in the medical field, mostly) : which is closer but do not quite do the trick.

How can I do this?

2014-08-09 first of, thanks to you all for Your suggestions ! I was - and still am - on holidays and was just passing by to check whether anyone had answered... I am not disappointed !!!! :-) I guess I'll first try CGAL, and will see from there. I have other data calculations on the same set of points in O(n2) that I expect will last about 1 week so a few hours would not be that bad. Minutes would be a dream come true !

Answer 1

You appear to be looking for a Delaunay triangulation algorithm in 3-space.

I hope you don't mind waiting a while, because a Delaunay triangulation of 100 million points is going to take quite some time.

qhull has an n-dimensional Delaunay implementation that you might try. So does CGAL. Both packages will compute the Delaunay triangulation in O(n log(n)) asymptotic time, and CGAL can, with an appropriate choice of geometry kernels, do so in a numerically robust fashion. (That is, it can automatically switch to exact arithmetic for those computations where inexact arithmetic produces an uncertain result.)

I would not recommend trying to implement a fast Delaunay triangulation yourself, even in two dimensions. Terrifying things can happen when you need to evaluate predicates on the results of arithmetic.