Triangulate a non-convex point set

I have a set of points in 3D that define the surface of a non-convex object, I would like to generate some kind of triangulation of these points so as to plot this surface. Any ideas how I might do this?

The convex hull won't work, because my points are on the surface of a non-convex body. I'm aware that the problem of defining a non-convex hull is ill-posed and has no unique solution. One way to go is the alpha-shape, and there is a file on the FEX that does this, but I was wondering if there is another (better) way?

[Sean de Wolski]

Do you know which vertices are connected to each other on the surface.?

[Oliver]

No, that's the reason I want a triangulation. I know that all of the vertices are on the surface, but I don't know the connectivity.

[Sean de Wolski]

alpha shapes...

[Houssem]

Hi,

In my work, i need to get a mesh surface of non-convex 3D object it must verifies the spherical topology (satisfies Euler theorem : V-E+F=2). I have a 3D position of vertices [X Y Z] and faces of a non-convex 3D object.

I used under matlab the function "convhulln" to get spherical topology mesh surface. The obtained mesh surface is satisfied Euler theorem but the object is deformed.

How i can generate a spherical topology mesh surface of non-convex object

Thank you again

[John D'Errico]

I concur with Sean. Alpha shapes are a good solution. CRUST is another, but I don't know if there is a code on the FEX for that. I'm not sure why Oliver resists the idea of alpha shapes. Perhaps he can say why, and we might be able to show him why he is wrong.

If the issue is simply that an alpha shape generates an entire triangulation, and not just the hull, it is trivial to compute that boundary surface for an alpha shape.

[Houssem]

Thank you for your reply,

Alpha shapes has a spherical topology? (satisfies Euler theorem)

Best

[Antonio]

I have the same problem that Oliver has. In my case, alpha-shapes doesn't work. I suppose you are using this file http://www.mathworks.com/matlabcentral/fileexchange/28851-alpha-shapes. Could you help me? I attach the set of points.

[Antonio]

Sorry, you're right, it works. But it's not perfect.

In my case, if I set a low radius, some areas are not shown in the triangulation. But if I set a higher radius, the non-convex edge is distorted.

You can check this problem using my previous attachment.

I hope you could help me a bit...

[Sean de Wolski]

Antonio, the R2014b alpha shape provides the alpha spectrum so you can see all radii that affect the hull.

Answer 1

[Sean de Wolski]

As of MATLAB R2014b, there is now a 2d and 3d alphaShape tool built into MATLAB.

http://www.mathworks.com/help/releases/R2014b/matlab/ref/alphashape.html