A Read on Mesh Algorithm and Mesh Library

Question

I am interested to read and understand the 2D mesh algorithms. A search on Google reveals a lot of papers and sources, however most are too academic and not much on beginner's side.

So, would anyone here recommend any reading sources ( suitable for the beginners), or open source implementation that I can learn from the start? Thanks.

Also, compared to triangular mesh generation, I have more interest in quadrilateral mesh and mix mesh( quad and tri combined).

Answer 1

The first link on your Google search takes you to Jonathan Shewchuk's site. This is not actually a bad place to start. He has a program called triangle which you can download for 2D triangulation. On that page there is a link to references used in creating triangle, including a link to a description of the triangluation algorithm.

There are several approaches to mesh generation. One of the most common is to create a Delaunay triangulation. Triangulating a set of points is fairly simple and there are several algorithms which do that, including Watson's and Rupert's as used in triangle When you want to create a constrained triangulation, where the edges of the triangulation match the edges of your input shape it is a bit harder, because you need to recover certain edges.

I would start by understanding Delaunay triangulation. Then maybe look at some of the other meshing algorithms.

Some of the common topics that you will find in mesh generation papers are

• Robustness - that is how to deal with floating point round off errors.
• Mesh quality - ensuring the shapes of the triangles/tetrahedrons are close to equilateral. Whether this is important depends on why you are creating the mesh. For analysis work it is very important,
• How to choose where to insert the nodes in the mesh to give a good mesh distribution.
• Meshing speed
• Quadrilateral/Hexahedral mesh generation. This is harder than using triangles/tetrahedra.

3D mesh generation is much harder than 2D so a lot of the papers are on 3D generation

Mesh generation is a large topic. It would be helpful if you could give some more information on what aspects (eg 2D or 3D) that you are interested in. If you can give some idea of what you ant to do then maybe I can find some better sources of information.

Answer 2

I second David's answer regarding Jonathan Shewchuk's site as a good starting point.

In terms of open source software, it depends on what you are looking for exactly.

• If you are interested in mesh generation, you can have a look at CGAL's code. Understanding the low level parts of CGAL's code is too much for a beginner. However, having a look at the higher level algorithms can be quite interesting even for a beginner. Also note that the documentation of CGAL is very detailed.
• You can also have a look at TetGen, but its source code is monolithic and is not documented (it is more of an end user software rather than a library, even if it can also be called simply from other programs). Still, it is fairly readable, and the user manual contains a short presentation of mesh generation, with some references.
• If you are also interested in mesh processing, you can have a look at OpenMesh.

More informations about your goals would definitely help providing more relevant pointers.