The proposed algorithm to generate three dimensional meshes of tetrahedra is based on an advancing front technique, given a domain with its boundary discretized into triangular faces. The algorithm is also applied to fracture problems, where it is necessary to correctly deal with face duplication. The algorithm implementation is always being improved with the addition of new features to improve its robustness and versatileness.

To explain how the algorithm works, an hypothetical example of a cube with a crack inside is showed. This example confirms the applicability of the process also to fracture problems. The figure below shows the model with a crack inside it.


For the generation of internal nodes, two approaches are used. In the a priori approach, the nodes are generated in the center of the cells of an octree, generated based on the boundary faces of the model. Those nodes will be used to generate the mesh and also reflect a gradation of how the mesh will grow. The figures below show the initial model, its generated octree and the internal points.

inter no pts inter

The process goes trough all model in an advancing front way: a face from the current front (that, in the beginning, is the boundary) is taken as a base face; all nodes are ranked to this face based on a chosen metric; the best node for the face that passes the geometrical tests, that is, that does not intercept any of the faces of the elements already created, is accepted; a new tetrahedral element is included in a list of elements, the base face is deleted from the front and the new three faces are included in the front, if they are not already there, or are deleted from it, if they already exist. The figure shows a base face and the best node chosen.


The second approach, called a posteriori, follows the same basic advancing front algorithm, but the internal nodes are generated as the front advances. For each base face, an ideal point is found, having the octree as a density function, and a search is performed for a valid existing node close to the ideal point. If no such node exists, the ideal point is converted to a new node, if the new tetrahedron is valid, and the front is update in the same way.

When it's not possible to advance any more face, some elements close to the front are deleted, to allow the formation of a bigger void region, for the generation of new elements in a different way. This process is called back-tracking procedure.

The figure shows the generated mesh for this example.


The figures that follow show some examples generated with the a priori technique described before.

cyl tor console

This figure shows a mesh for a gear model using the a posteriori approach.

2013 freitas mesh2

This video and the video below show the generation of meshes using the a posteriori approach.

You need to a flashplayer enabled browser to view this YouTube video

More information about this technique can be found in:

[1] Miranda, A.C.O. ; Cavalcante-Neto, J.B. ; Martha, L.F. . An Algorithm for Two-Dimensional Mesh Generation for Arbitrary Regions with Cracks.. In: SIBGRAPI'99 (XII Brazilian Symposium on Computer Graphics and Image Processing), 1999, Campinas, Brazil. Proceedings of the XII Brazilian Symposium on Computer Graphics and Image Processing. Campinas: IEEE Computer Society, 1999. v. 1. p. 29-38.
[2] Cavalcante-Neto, J.B. ; Wawrznek, P.A. ; Carvalho, M.T.M. ; Martha, L.F. ; Ingraffea, A.R. . An Algorithm for Three-Dimensional Mesh Generation for Arbitrary Regions with Cracks. Engineering with Computers, Springer-Verlag London Limited, v. 17, n.1, p. 75-91, 2001.
[3] Cavalcante-Neto, J.B. ; Wawrznek, P.A. ; Martha, L.F. ; Ingraffea, A.R. . A Strategy for Improving the Robustness of Three-dimensional Advancing-front Algorithms. In: CILAMCE 2005 (XXVI Iberian Latin-American Congress on Computational Methods in Engineering), 2005, Guarapari. Proceedings of the XXVI Iberian Latin-American Congress on Computational Methods in Engineering. Guarapari: ABMEC/AMC, 2005. v. 1. p. 1-14.
[4] Cavalcante-Neto, J.B. ; Martha, L.F. ; Wawrznek, P.A. ; Ingraffea, A.R. . A Back-tracking Procedure for Optimization of Simplex Meshes. Communications in Numerical Methods in Engineering, John Wiley & Sons Ltd., v. 21, n.1, p. 711-722, 2005.

Our research on the parallelization of this algorithm can be found here.