## Product Development by Reverse Engineering # Meshing Algorithms

In the previous session, we have learned what Mesh is and the various aspects upon which a mesh can be classified. Mesh generation requires expertise in the areas of meshing algorithms, geometric design, computational geometry, computational physics, numerical analysis, scientific visualization and software engineering to create a mesh tool.

Over the years, mesh generation technology has evolved shoulder to shoulder with increasing hardware capability. Even with the fully automatic mesh generators there are many cases where the solution time is less than the meshing time. Meshing can be used for wide array of applications, however the principal application of interest is the finite element method. Surface domains are divided into triangular or quadrilateral elements, while volume domain is divided mainly into tetrahedral or hexahedral elements. A meshing algorithm can ideally define the shape and distribution of the elements.

A key step of the finite element method for numerical computation is mesh generation algorithms. A given domain is to be partitioned it into simpler ‘elements’. There should be few elements, but some portions of the domain may need small elements so that the computation is more accurate there. All elements should be ‘well shaped’. Let us take a walkthrough of different meshing algorithms based of two common domains, namely quadrilateral/hexahedral mesh and triangle/tetrahedral mesh.

##### Algorithm methods for Quadrilateral or Hexahedral Mesh

Grid-Based Method

The grid based method involves the following steps:

• A user defined grid is fitted on 2D & 3D object. It generates quad/ hex elements on the interior of the object.
• Some patterns are defined for boundary elements followed by forming a boundary element by applying boundary intersection grid.
• This results in the generation of quadrilateral mesh model. Medial Axis Method

Medial axis method involves an initial decomposition of the volumes. The method involves few steps as given below:

• Consider a 2D object with hole.
• A maximal circle is rolled through the model and the centre of circle traces the medial object.
• Medial object is used as a tool for automatically decomposing the model in to simple meshable region.
• Series of templates for the region are formed by the medial axis method to fill the area with quad element. Plastering method

Plastering is the process in which elements are placed starting with the boundaries and advancing towards the centre of the volume. The steps of this method are as follows:

• A 3D object is taken.
• One hexahedral element is placed at boundary.
• Individual hexahedral elements are projected towards the interior of the volume to form hexahedral meshing, row by row and element by element.
• The process is repeated until mesh generation is completed. Whisker Weaving Method

Whisker weaving is based on the concept of the spatial twist continuum (STC). The STC is the dual of the hexahedral mesh, represented by an arrangement of intersecting surfaces, which bisect hexahedral elements in each direction. The whisker weaving algorithm can be explained as in the following steps:

• The first step is to construct the STC or dual of the hex mesh.
• With a complete STC, the hex elements can then be fitted into the volume using the STC as a guide. The loops can be easily determined from an initial quad mesh of the surface.
• Hexes are then formed inside the volume, once a valid topological representation of the twist planes is achieved. One hex is formed wherever three twist planes converge. Paving Method

The paving method has the following steps to generate a quadrilateral mesh:

• Initially a 2D object is taken.
• A node is inserted in the boundary and the boundary node is considered as loop.
• A quadrilateral element is inserted and a row of elements is formed.
• The row of element is placed around the boundary nodes.
• Again this same procedure adopt for next rows.
• Finally quad mesh model is formed.  Mapping Mesh Method

The Mapped method for quad mesh generation involves the following steps:

• A 2D object is taken.
• The 2D object is split into two parts.
• Each part is either a simple 2D rectangular or a square object.
• The simple shape object is unit meshed.
• The unit meshed simple shape object is mapped in its original form and then joined back to form actual object.  ##### Algorithm methods for Triangular and Tetrahedral Mesh

With the quadtree mesh method, square containing the geometric model are recursively subdivided until the desired resolution is reached. The steps for two dimensional quadtree decomposition of a model are as follows:

• A 2D object is taken.
• The 2D object is divided into rectangular parts.
• A Detail tree of divided object is provided.
• The object is eventually converted into triangle mesh. Delaunay Triangulation Method

A Delaunay triangulation for a set P of discrete points in the plane is a triangulation DT such that no points in P are inside the circum-circle of any triangles in DT. The steps of construction Delaunay triangulation are as follows:

• The first step is to consider some coordinate points or nodes in space.
• The condition of valid or invalid triangle is tested in every three points which finds some valid triangle to make a triangular element.
• Finally a triangular mesh model is obtained.

Delaunay Triangulation maximizes the minimum angle of all the angle of triangle and it tends to avoid skinny triangles.  Another very popular family of triangular and tetrahedral mesh generation algorithms is the advancing front method, or moving front method. The mesh generation process is explained as following steps:

• A 2D object with a hole is taken.
• An inner and outer boundary node is inserted. The node spacing is determined by the user.
• An edge is inserted to connect the nodes.
• To start the meshing process, an edge AB is selected and a perpendicular is drawn from the midpoint of AB to point C (where C is node spacing determined by the user) in order to make a triangular element.
• After one element is generated, another edge is selected as AB and a point C is made, but if in case any other node lets point D within the defined radius, then ABC element is cancelled and instead, an element ABD is formed.
• This process is repeated until mesh is generated. Spatial Decomposition Method

The steps for spatial decomposition method are as follows:

• Initially a 2D object is taken.
• The 2D object is divided into minute parts till we get the refined triangular mesh. Sphere Packing Method

The sphere packing method follows the given steps:

• Before constructing a mesh, the domain is filled with circles.
• The circles are packed closely together, so that the gaps between them are surrounded by three or four tangent circles.
• These circles are then used as a framework to construct the mesh, by placing mesh vertices at circle centers, points of tangency, and within each gap while using generated points. Eventually, the triangular mesh is generated.  Source

Singh, Dr. Lokesh, (2015). A Review on Mesh Generation Algorithms. Retrieved from http://www.ijrame.com