# Delaunay Triangulation for 3D Surface Data

I want to do a Delaunay triangulation on scattered 3D surface data. Mathematica itself does it only for 2D through the command DelaunayTriangulation[], which gives a triangulation for points in a plane. I also tried the MathLink package "TetGenLink", which can itself perform a Delaunay triangulation for three-dimensional data. The problem here is that TetGenDelaunay[] produces a triangulation through the inner region of the data, but I can't see how I can manage that the triangulation is only done for the surface (like what is done by MATLAB's DelaunayTri (see this SO question).

-
So, performing a Tetrahedralization and keeping only the surface triangles isn't a valid solution –  belisarius Oct 1 '12 at 12:22
Would you mind supplying a bit of test data? –  Yves Klett Oct 1 '12 at 12:22
Access to some possibly relevant internal routines may be found at Demonstrations here and here. This one might also be useful. –  Daniel Lichtblau Dec 4 '12 at 15:06
@Daniel The last one doesn't work with Mathematica 9. (It does with Mathematica 8.) –  Szabolcs Dec 13 '12 at 15:43
@Daniel & anyone else who might try the demonstration: It seems that the breakage is because of a change from a 0-based indexing to 1-based indexing in the tetgen library (not high level Mathematica) function getFaces. It can be corrected by removing the +1 from getFacesFun@outInst in the ch function in the demonstration source code. –  Szabolcs Dec 13 '12 at 16:05

In Version 10, this can be done elegantly in one line:

SeedRandom[400]
pts = RandomReal[5, {400, 3}];


Then:

surftri = RegionBoundary @ TriangulateMesh @ DelaunayMesh @ pts


We can look inside to see that only the surface triangulation remains:

HighlightMesh[surftri, {Style[0, Directive[PointSize[0.015], Blue]], Style[1, Thin, Black],
Style[2, Opacity[0.7], Cyan]}]


-

As you state, TetGenDelaunay is for a tetrahedralization of the 3D space of the input data, and you'd then need to extract the surface triangulation. So for TetGenDelaunay there is no way around the tetrahedralization. (But I wonder if this is not also the case for DelaunayTri) TetGen is quite efficient, so maybe this is still an option. Perhaps, depending on the purpose of your computation, you could make use of ListSurfacePlot or RegionPlot3D.

In any case, here is how you'd extract the surface from the tetrahedralization:

Needs["TetGenLink"]
data3D = RandomReal[{0, 1}, {1000, 3}];
in = TetGenCreate[];
TetGenSetPoints[in, data3D];
out = TetGenTetrahedralize[in, ""];
coords = TetGenGetPoints[out];
(* issue in TetGen interface, thus + 1 *)
surface = TetGenGetFaces[out] + If[\$VersionNumber < 9.0, 1, 0];
Graphics3D[GraphicsComplex[coords, Polygon[surface]], Boxed -> False]


To set vertex colors you can use:

values = Sqrt[Total[coords^2, {2}]];
cf = ColorData["TemperatureMap"];
vc = DeveloperToPackedArray@(List @@@ (cf[#] & /@ values));
Graphics3D[{Opacity[0.5],
GraphicsComplex[coords, Polygon[surface], VertexColors -> vc]},
Boxed -> False]


-
@J.M. thanks for fixing my poor spelling! –  user21 Oct 1 '12 at 13:26
You're welcome! I initially considered using TetGen too, but I got bogged down in figuring how to pick out the outermost polygons. I didn't know it was this easy! –  Ｊ. Ｍ. Oct 1 '12 at 13:30
@J.M. do you think the documentation would benefit from such an example? –  user21 Oct 1 '12 at 13:31
Looking around, surface triangularization seems to be a quite common task, so yes, I think including such an example in the docs would be nice. –  Ｊ. Ｍ. Oct 1 '12 at 13:35
Hi, it's in SystemFiles/Links/TetGenLink –  user21 Dec 6 '12 at 4:06