Meshing

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.

model

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.

metric

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.

mesh

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.

This techinique is the parallelization of the serial advancing front algorithm described here.

This technique uses a coarse octree to decompose the domain and a serial advancing front technique to generate the mesh in each subdomain concurrently. This coarse octree is generated based on a finer octree, used to help estimate the processing load associated with each subdomain.

apriori

Two approaches for the generation of the mesh between subdomains are used. In the a priori approach, this interfacing mesh is generated before the generation of the meshes inside the subdomains.

apriori2

In the a posteriori approach, the generation of the interfacing mesh is a consequence of a shifting of the subdomains to a Cartesian direction, and a reapplication of the mesh generation procedure. Several shifts in several directions are applied, until no more mesh can be generated.

aposteriori aposteriori2

In both approaches, the interfacing mesh is improved in a final step.

apriori4 aposteriori3

This video shows the generation of a two-dimensional triangular mesh using the a priori approach. The a posteriori approach can be seen in the video below, as well as this video (2D) and this other video (3D).

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

More information about this technique can be found in:

[1] Teixeira, D.N. ; Freitas, M.O. ; Cavalcante-Neto, J.B. ; Vidal, C.A. . A Technique for Parallel Mesh Generation Using a priori Quadtree's Inter-Cell Discretization. In: CILAMCE 2011 (XXXII Congresso Ibero Latino Americano de Métodos Computacionais em Engenharia), 2011, Ouro Preto. Anais do XXXII Congresso Ibero Latino Americano de Métodos Computacionais em Engenharia. Rio de Janeiro: ABMEC, 2011. v. 1. p. 1-19.
[2] Freitas, M.O. ; Cavalcante-Neto, J.B. ; Vidal, C.A. ; Martha, L.F. ; Wawrznek, P.A. ; Ingraffea, A.R. . A Parallel Technique for Two-Dimensional Mesh Generation for Arbitrary Regions with Cracks. In: CILAMCE 2011 (XXXII Congresso Ibero Latino Americano de Métodos Computacionais em Engenharia), 2011, Ouro Preto. Anais do XXXII Congresso Ibero Latino Americano de Métodos Computacionais em Engenharia. Rio de Janeiro: ABMEC, 2011. v. 1. p. 1-20.
[3] Freitas, M.O. ; Wawrznek, P.A. ; Cavalcante-Neto, J.B. ; Vidal, C.A. ; Martha, L.F. ; Ingraffea, A.R. . A distributed-memory parallel technique for two-dimensional mesh generation for arbitrary domains. Advances in Engineering Software (1992), v. 59, p. 38-52, 2013.