Error in 3D Delaunay Triangulation

MATLAB doesn't appear to have a nested mesh tool that will mesh a set of surfaces inside another surface, i.e. mesh a cube inside a sphere, the type of meshing needed to say simulate heat conduction from a hot cube into the surrounding air with a spherical boundary.

So, I'm trying to write my own. So far, I've written code that allows me to create a set of surface nodes for the cube and the sphere. However, once I place points inside the cube and perform 3D delaunay triangulation, I get VERY odd results. The resulting tetrahedra don't connect the surface nodes and create very flat tetrahedra with huge circumradii that surely must contain other surface nodes:

So to clarify, left: surface mesh using nodes on the surface. Right: cube containing the surface nodes plus some randomly distributed internal nodes, I've carried out delaunayTriangulation and then plotted the surface faces using the freeBoundary function.

I was expecting that the volume triangulation might not honour the surface mesh, but the resulting volume triangulation just looks completely incorrect. Any tips on how to deal with this would be greatly appreciated.

[KSSV]

I would recommend you to use:

https://in.mathworks.com/matlabcentral/fileexchange/25555-mesh2d-delaunay-based-unstructured-mesh-generation

[Nathan Welch]

"MESH2D is a MATLAB-based Delaunay mesh-generator for two-dimensional geometries". I'm creating a 3D mesh.

Answer 1

[Siju Thomas]

HI Nathan,

You can use the PDE Toolbox to mesh a surface nested within another surface.

An example can be seen here: Sphere in a Cube

[Nathan Welch]

It's not really meshing a nested object. It just creates a cavity.

They then bodge a mesh for sphere by adding a single central point and creating a simple set of elongated tetrahedra for the sphere. This would be awful for a simulation.

If you were to mesh them separately, MATLAB has no ability to align the two sets of surface faces - the cavity surface faces and the spherical surface faces. This again would lead to a terrible mesh for simulation.

If you can see an example of multiple, arbitrary objects that are full meshed, I would love to see it.

Also, can you help with the original question? Why does MATLAB produce this awful triangulation?

[Konstantin Kovalev]

Hi Nathan,

Regarding the example Siju suggested: geometryFromMesh call at the end creates a new geometry and keeps the mesh in the model. However, once you have the geometry available, you can regenerate the mesh with desirable sizing.

Regarding the awful triangulation: Delaunay triangulation creates a convex hull for a given set of points, so boundaries are not respected, unless accidentally. From the image you provided it looks like some points on the surface are missed, most likely because they do not belong to the convex hull.

An alternative tool to recover shapes defined by point clouds is alphaShape. However, in order to generate desired shapes, it needs both the point field and alpha factor to be properly adjusted.

Best Regards,

Konstantin

[Nathan Welch]

Hi Konstantin,

Apologies, I don't understand how that gives a nicely meshed sphere with faces that match up with the meshed cube. Could you give the pseudo-code that would create this?

I'm not really looking to 'recover shapes'. I know the shapes, I have a list of surfaces given by surface patches and surface nodes. I then want to create a mesh that will conform to those shapes, even if the shapes are complex and nested. So far, I've only seen examples that work on simple, non-nested, shapes.

As for the Delaunay triangulation, I include all the points in the volume Delaunay triangulation both the surface and internal nodes. So how can some of the boundary points not belong to the convex hull, when they are used to calculate the convex hull?

[Nathan Welch]

Also, those boundary nodes that are being ignored by the boundary facet tetrahedra, are included in many internal tetrahedra.

They are not being cut out entirely but for some reason they are being ignored for the Delaunay circumsphere test.

I have attached the relevant data if you wish to view the problem yourself.

[Konstantin Kovalev]

Regenerate mesh: after all commands are executed in the Sphere-in-Cube example, just run this:

    msh = generateMesh(model,'Hmax',0.1);

"Recovering" shapes:

I was referring to your workflow in which you create a point field that represents surfaces of interest (cube and sphere) and then use Delaunay triangulation to create tetrahedra. As the input to Delaunay includes points only, we can look at it as "surface reconstruction", i.e. generating a set of tetrahedra whose triangular faces describe the surfaces.

Delaunay:

You have made a very good observation. Most likely those points are slightly off the faces of the cube and that's why they do not belong to convex hull boundary, while referenced by internal tets. Most likely this is the effect of the cube being misaligned with XYZ. You may consider to repeat this with a cube perfectly aligned with Cartesian axes and see if there is a difference.

However, I don't think Delaunay approach will work in this case, as it will not respect the internal surface. It would require a constrained Delaunay triangulation in order to preserve surfaces, and MATLAB currently supports it in 2-D only.

Best Regards,

Konstantin

[Nathan Welch]

I can't seem to run the Sphere-in-Cube example, as the 'boundaryFacets' function only accepts alphaShape arguments not FEMesh arguments - but I am running 2018 MATLAB - though the 2020 help page for 'boundaryFacets' would suggest it only works for alphaShape.

If the Sphere-in-Cube method works, how can I expand it to work with generic shapes that are multiply connected and multiply nested and defined by a series of face patches?

As for the Delaunay - as you say, the points may be just off the boundary due to numerical precision but they are still inside the circumradius of the the awfully thin tets created near the surface - this would suggest that the Delaunay triangulation has failed.

There's not much point trying a nice Cartesian aligned example, as I deliberatly created an asymmetric rotated surface as this is closer to what I need to model the majority of the time.

Answer 2

[Chenglin Li]

HI Nathan, I'm making a concave mesh, and I have some problems,Is your 3D program open source？