# Help with triangulation algorithms

Hi,
I have a set of points that I’d like to make a surface out of and render it. Any suggestions on an algorithm to do it? Possibly an open source/free implementation?

Most of my searches returned stuff like Delaunay triangulation, but it’s shown only for 2D, and I don’t understand how to apply it in 3D.

Thanks.

Maybe search for “convex hull generation”. Don’t know much about that myself.

Jan.

Well a convex hull does not necessarily pass through the points. Especially if the shape is concave. The convex hull of a banana is an oval.

That’s how I understand it…

These keyword seem to deal with what you want to do :

point cloud to surface reconstruction

It is used on medical imaging, 3D laser scanning, etc.

Edit: for a simple case, this might do the job :
http://www.maths.dundee.ac.uk/~heikman/index.html?/~heikman/tools/java/triangulation.html

You might also want to look at this:
http://research.microsoft.com/~hoppe/

Complex stuff, but worth researching if you’re serious about surface reconstruction.

Delaunay triangulations can be applied to 3D without too much difficulty.

However, many 3D problems can be represented as 2.5D, that is, using the assumption of very few points with different z coords having the same xy coords. In that case, you can just use a 2D Delaunay implementation to handle it.

Thanks for the suggestions. Still reading the different material on the subject.