How to use delaunay trianglation in 3d points?

Question

I understand how to use delaunay triangulation in 2d points?
But how to use delaunay triangulation in 3d points?
I mean I want to generate surface triangle mesh not tetrahedron mesh, so how can I use delaunay triangulation to generate 3d surface mesh?
Please give me some hint.

Farro

You mean convex hulls? – Hurdle

If you don't just want the convex hull, you need to decide what tetrahedra are inside and outside. Take a look at PowerCrust and related methods. – Grocery

What about using some CGAL shape reconstruction method? doc.cgal.org/latest/Manual/packages.html#PartReconstruction – Conal

Answer 1

There are two meanings of a 3D triangulation. One is when the whole space is filled, likely with tetrahedra (hexahedra and others may be also used). The other is called 2.5D, typically for terrains where the z is a property as the color or whatever, which doesn't influence the resulting triangulation.

If you use Shewchuk's triangle you can get the result.

If you are curious enough, you'll be able to select those tetrahedra that have one face not shared with other tetrahedra. These are the same tetrahedra "joined" with infinite/enclosing points. Extract those faces and you have your 3D surface triangulation.

If you want "direct" surface reconstruction then you undoubtly need to know in advance which vertices among the total given are in the surface. If you don't know them, perhaps the "maxima method" allows to find them out.

One your points cloud consists only of surface vertices, the triangulation method can be any one you like, from (adapted) incremental Chew's, Ruppert, etc to "ball-pivoting" method and "marching cubes" method.

Scratches

Thanks! what I mean is how can I perform 3d Delaunay triangulation(not tetrahedra)?for example, you can triangulate in parameter space and map the triangle in parameter space back to the space where vertices's be – Farro

@Farro The 3D Delaunay condition is that not 4 points lie in the same sphere. I'm afraid this geometric condition doesn't survive the parameter-xyz mapping. Also, is your parameter space a 2D space? If it's a 3D space, how can you avoid tetrahedra? – Scratches

So the triangulation of a closed 3D edge loop of only surface vertices shall use Ruppert or ball-pivoting, etc? – Hokeypokey

Answer 2

To triangulate a 3D point cloud you need the BallPivoting algorithm: https://vgc.poly.edu/~csilva/papers/tvcg99.pdf

Jourdan

Thanks very much! I want to know how to perform 3D Delaunay triangulations?I mean the given points set is x,y,z not x,y – Farro

Answer 3

The Delaunay tetrahedrization doesn't fit for two reasons

• it fills a volume with tetrahedra, instead of defining a surface,

• it fills the convex hull of the points, which is probably not what you expect.

To address the second problem, you need to accept concavities, and this implies that you need to specify a reference scale that tells what level of detail you want. This leads to the concept of Alpha Shapes, which are obtained as a subset of the faces.

Lookup "Alpha Shape" in an image search engine.

Goldsberry