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 !

Grainfield

tetrahedralization… my tongue crawled back in a dark corner and started crying… – Carminacarminative

lcni.uoregon.edu/~dow/Projects/Brain_casting/… might be a good start. Depending on your needs a 3d convex hull might suffice – Jettiejettison

You might want to look at the analogous 2D problem (filling with triangles) first: Delaunay Triangulation. – Cark

this is a good question. However it is not fitted for this site. Try programmers.stackexchange.com or softwarerecs.stackexchange.com – Carminacarminative

Is the requirement to build a tetrahedron from the spheres? Or is the requirement to build a tetrahedron inside the sphere that contains the most points? Also, is it a regular tetrahedron? If the requirement is my first question, the points inside the sphere do not come into the problem scope; only the sphere's location and volume. Also, does the tetrahedron use the sphere's radius as a point? – Dactyl

What's the difference between your issue and the simplified problem: Given 4 points, in 3D space, draw a tetrahedron? – Dactyl

@bolov: No, this question is a fine fit for this site. Neither of those sites are likely to be responsive. – Serenaserenade

How about using marching tetrahedra algorithm? It's similar to marching cubes and it's quite easy to implement. – Congregational

@Congregational Isn't that for finding level-set surfaces? You need a tetrahedralized space for that. OP is trying to make such tetrahedralization in first place. – Hyetography

@emsr: True, I didn't read the question carefully... – Congregational

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.

Serenaserenade

A dt in 2d isn't so hard. After all it's just a bit geometry. – Shaw

@Phpdna: It's easy enough in exact arithmetic. You don't use exact arithmetic if you want your code to go fast. With floating-point arithmetic, you run into the fundamental problem that you need to evaluate predicates on results of arithmetic in a consistent way. Dealing with that is not easy. (Put another way: "I bet I can break your Delaunay triangulation code.") – Serenaserenade

You can also repair a bad triangulation!? – Shaw

@Phpdna: How? And what if it's not a triangulation? And how do you detect "bad"ness? – Serenaserenade

@tmyklebu: just to clarify -- both CGAL and qhull implement fast O(nlog(n)) algorithms. CGAL is also "robust" -- using exact arithmetic and symbolic perturbation (when necessary), ensuring that a valid DT is always produced, even when the input is degenerate. In practice, DT algorithms often exhibit O(n) scaling, so the time to tessellate 100 million points might not be as bad as you think, though it would definitely be measured in minutes, not seconds (doc.cgal.org/latest/Triangulation_3). – Villainy

@DarrenEngwirda: Neat. I guess CGAL must be doing something smarter than the sweep line/complicated data structure idea. (And I was definitely thinking several hours rather than 15ish minutes for the running time.) – Serenaserenade

@tmyklebu: CGAL (as far as I'm aware) is actually just implementing an incremental tessellation based on the Bowyer-Watson algorithm. As per Phpdna's answer, the speed is obtained by inserting the points according to a kind of space-filling curve like ordering. – Villainy

@DarrenEngwirda: OK, that works a lot better than I expected. I don't see how to get an O(n log n) bound on any implementation of Bowyer-Watson, but that isn't very important. – Serenaserenade

Answer 2

I use tetgen for one of my project to do tetrahedralization. It works quite well and fast enough

Harebrained