A Rule-based Approach to Quadrilateral Mesh Generation

Project director:    Dr. Samuel H. Huang
Student:                 Haixin Wang

Abstract

Mesh generation for geometric models has always been a time-consuming task and depends mostly on the expertise of the analyst or the modeler. The time required to generate meshes has been reduced tremendously by the use of powerful computers and commercially available software, but either the quality of mesh generated is poor or the human expertise required is too much. Various heuristics that analyst and modelers used for block generation are synthesize to form a coherent rule-base.

A software-tool has been developed using the rule-base to automatically decompose a two-dimensional geometry into blocks and generate block topology in very insignificant time. The proposed research is significant because it will dramatically reduce the amount of tedious human interaction required in the area of Finite Element Analysis and Computational Fluid Dynamics.

1. Introduction

The mesh generation process deals with the decomposition of a given domain (geometry) into finite elements in order to facilitate the numerical solution of partial differential equation. The principle application of mesh generation is in the areas of Finite Element Analysis (FEA) and Computational Fluid Dynamics (CFD). The two-dimensional (2D) domains are generally decomposed into triangles and quadrilaterals; whereas three-dimensional (3D) domains are subdivided into tetrahedral and hexahedral shapes. Grid or mesh generation is an interface between domain representation and analysis algorithms. The analysis algorithms require discretization of mathematical representation of physical laws in to finite element equations. The field data being sought is discrete, that is, either averaged over a small cell, called element or is sampled at a point, called grid or mesh point. The generation of the cells and grid points is what constitutes grid or mesh generation.

The quadrilateral (quad) and hexahedral (hex) shaped elements have superior performance to triangle and tetrahedral shaped elements when comparing an equivalent number of degrees of freedom.  Use of quad and hex elements can vastly reduce the number of elements and consequently analysis and post – processing times.

In addition, quad and hex elements are more suited for non-linear analysis as well as situations where alignment of element is important to the physics of the problem, such as in CFD or in simulation of viscous flow involving boundary layers or in simulation of composite materials.

2. The General System Architecture for Rule-based Approach to Quadrilateral Mesh Generation

The system architecture of the software tool is illustrated by a flowchart in the following figure.

The system consists of following sub-systems (functional procedures):

  1. CAD Model: The input for the software tool is a two-dimensional geometry for which block topology need to be created. A CAD model created using CAD software (AutoCAD) is acceptable.
  2. Export in Data-exchange Format: After a desired CAD model is created, it needs to be exported in data-exchange format (dxf), as the software tool can recognize only this format to extract the geometry data. The CAD software converts the geometry data into a text format, with the edge and vertex information.
  3. Geometry Recognition: In this step, the software tool recognizes the CAD model (DXF file). It extracts the edge and vertex information and stores the data in inbuilt data-structure. The data-structure stores information like number of edges, number of vertices, endpoints of edges and co-ordinates of vertices.
  4. Implementing Boundary Conditions: The rules for boundary condition are used to apply the boundary conditions. The basic idea of applying boundary condition is to offset the geometry to get denser meshes near the boundary. As for CFD and FEM analysis, these regions are of utmost importance and fine mesh is desired.
  5. Geometry Bisector: After the boundary conditions are implemented, the user is asked to pick the geometry bisector, with the help of a dialog box. The user has a choice to select any vertex and any edge to divide the geometry. The valid combinations of selection of geometry bisector are vertex-vertex, vertex-edge, edge-vertex and edge-edge. The geometry bisector, if a good selection is made, results in a good flow in the final block topology of the given geometry.
  6. Drawing Projections: After the user picks the geometry bisector, the software tools automatically projects lines on the geometry bisector to decompose the geometry into blocks. After the projections, the newly created vertices on geometry bisector are checked if they can be merged. If the vertices are merged then the data-structure is updated accordingly.
  7. Checking Loops: Implementing the projection rules doesn’t guarantee all-quadrilateral block topology. Some of the blocks are still have more then four edges. In this step all the loops or blocks that are created till now are checked. If only smallest possible loops are considered then there can be only two different loops to have a particular edge. The exception to this case is only when the edge is on the boundary of the geometry, in that case only one loop can have that edge.
  8. Convert to Quadrilateral: The different rules for decomposing polygons with more then four edges are used to get the desired all-quadrilateral block topology.
  9. Create Surface: The rules for decomposing polygons with straight lines are developed, but practically a domain might have curved surfaces too. To deal with this, another step is added to generate piece-wise linear surfaces. The user has an option to select the vertices, which need to be converted to piece-wise linear surfaces. In other words, the user selects different edges and the software tool converts these edges to one single surface.
  10. Generate TIL Codes: This is the last step in developing the block topology for a given domain. This process is fully automated; user only has to specify the path for the generated TIL code file (.fra) and the software tool saves the file. The automatic mesh generation software, like GridPro, needs the block topology for generating meshes.

3. Concluding discussion

For many applications, meshes consisted of quadrilateral and hexahedral elements are better than those consisting of triangular and tetrahedral elements. One of the better ways to generate quadrilateral elements is to use multi-block mesh generation techniques. The shortcoming of commercially available software that uses the multi-block technique to generate meshes is that they require manual creation of the block topology. As can be seen that generating block topology for a domain is very small part of the whole designing process. The time and human expertise required to decompose any given domain and generate block topology is too much.

The software tool developed can automatically decompose any two-dimensional geometry (without any internal feature) and generate block topology for the same in just few seconds and few mouse clicks. The use of the software tool can reduce the expensive process of block generation to a great extent. The rule-based approach to develop block topology consists of rules for different phases of the geometry decomposition. This research contributes the area of multi-block mesh generation with a software tool, which can automatically generate block topology.

4. Directions of the subsequent research work

The software tool and the rule-based system developed can only deal two-dimensional geometries with no internal features. Extension of this approach can be done in the following ways:

  1. Selection of Geometry Bisector: For a selection of geometry bisector to be a good one, the geometry bisector should divide the geometry into two equal or near equal halves and by using this criteria, an iterative algorithm can be developed to determine the endpoints of the geometry bisector. This will reduce the user interaction and more intelligent software tool can be developed.
  2. Geometries with internal features: An extended software tool can be developed, which has rules to decompose geometries with internal features by adding more rules to the rule-base.
  3. Smoothing algorithm: A smoothing algorithm can be added to get good quality of quadrilateral blocks, which depends on following parameters:
    a. Number of edges connected to a vertex
    b. Angle between two edges
    c. Size and shape of block
    d. Merging of vertices
    e. Splitting of vertices
  4. Three-dimensional geometries: A more extended software tool and rule-based system can be developed, which can deal with three-dimensional geometries. The basic idea behind the approach used in this research is that in case of two-dimensional geometry, a line is used to bisect the geometry into two halves and then lines are projected from singular points. This idea can be extended to three-dimensional geometry by first bisecting the geometry or domain into two by a plane (geometry bisector plane) and then projecting planes from different singular edges (edges that doesn’t have four connecting faces) on to the geometry bisector plane. And then semi-decomposed polyhedrons can be decomposed into hexahedral by using corresponding decomposing rules.
  5. Use of Artificial Neural Network: With inclusions of more number of heuristics, which can solve complex geometries, optimization of the heuristic path can be achieved through the use of artificial neural networks.

This report was developed by Mr. Wang and revised by Dr. Shi, February 2002.