9

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 !

user22744
  • 101
  • 1
  • 5
  • 2
    *tetrahedralization*… my tongue crawled back in a dark corner and started crying… – bolov Aug 03 '14 at 18:44
  • http://lcni.uoregon.edu/~dow/Projects/Brain_casting/Point_cloud_to_mesh.html might be a good start. Depending on your needs a 3d convex hull might suffice – parapura rajkumar Aug 03 '14 at 18:48
  • 1
    You might want to look at the analogous 2D problem (filling with triangles) first: Delaunay Triangulation. – Raedwald Aug 03 '14 at 19:00
  • this is a good question. However it is not fitted for this site. Try http://programmers.stackexchange.com/ or http://softwarerecs.stackexchange.com/ – bolov Aug 03 '14 at 19:19
  • 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? – Thomas Matthews Aug 03 '14 at 20:19
  • What's the difference between your issue and the simplified problem: *Given 4 points, in 3D space, draw a tetrahedron*? – Thomas Matthews Aug 03 '14 at 20:22
  • @bolov: No, this question is a fine fit for this site. Neither of those sites are likely to be responsive. – tmyklebu Aug 03 '14 at 22:38
  • How about using marching tetrahedra algorithm? It's similar to marching cubes and it's quite easy to implement. – Jaa-c Aug 03 '14 at 22:45
  • 1
    @Jaa-c 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. – emsr Aug 03 '14 at 23:25
  • @emsr: True, I didn't read the question carefully... – Jaa-c Aug 04 '14 at 12:14

2 Answers2

2

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.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
  • A dt in 2d isn't so hard. After all it's just a bit geometry. – Micromega Aug 03 '14 at 23:00
  • 1
    @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.") – tmyklebu Aug 03 '14 at 23:05
  • 1
    You can also repair a bad triangulation!? – Micromega Aug 03 '14 at 23:10
  • @Phpdna: How? And what if it's not a triangulation? And how do you detect "bad"ness? – tmyklebu Aug 03 '14 at 23:44
  • 1
    @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 (http://doc.cgal.org/latest/Triangulation_3/). – Darren Engwirda Aug 04 '14 at 01:02
  • @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.) – tmyklebu Aug 04 '14 at 02:29
  • @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. – Darren Engwirda Aug 05 '14 at 14:58
  • @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. – tmyklebu Aug 05 '14 at 15:45
1

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

Guangming Mao
  • 775
  • 1
  • 9
  • 15