If I have a set of 3d points (AKA point cloud) what is the best way to determine the groups of 3 points (triangles) I should make, to create a surface reconstruction?
+7
A:
Delaunay Triangulation is your friend! There are lots of resources available about it if you Google the term, and the math/logic behind it isn't too tough. Making it FAST is a bit harder (but totally do-able), but that depends entirely on your requirements.
Toji
2009-11-30 14:13:47
+1 Happy 2000! I spent a nice few moments googling around "computational geometry" and "voronoi". It seems the main advantage of Delaunay Triangulation is the constraint that angles be modest, which avoids some of the skinny triangles in a simpler Voronoi tessellation. Adding "java" to the google search turns up plenty of libraries and so on.
Ewan Todd
2009-11-30 14:36:50
If I were implementing this from scratch, out of curiosity, I'd start with one of the simpler algorithms here, perhaps "divide and conquer": http://en.wikipedia.org/wiki/Delaunay_triangulation#Algorithms
Ewan Todd
2009-11-30 14:39:17
Last time I implemented it was for a pre-process, so it could be as slow as I wanted. Turned out a simple brute force was fast enough for most of my needs at the time. I recommend implementing the brute force version at least once, just to get a feel for how it works. Then optimize away! (Oh, and If I recall correctly this algorithm is just BEGGING to be multi-threaded.)
Toji
2009-11-30 14:49:02