Quad-Hex Mesh Generation

[Goal] [Team] [Methodology] [Reports] [Results] [Tool (snapshots)] [References]

This page is to provide details of the project of "Automated FEA/CFD Hexahedral Mesh Generation Using an Integrated Neural Network / Rule-based Method" carried out in Intelligent CAM Laboratory (ICAMS) with the collaboration of Parker Hannifin Corporation, sponsored by Ohio Aerospace Institute.

Introduction

In the aerospace and automotive industries, finite element analysis (FEA) and computational fluid dynamics (CFD) analysis are frequently used to solve a wide range of engineering problems. Mesh generation is a critical starting point for FEA/CFD. Currently, the generation of high quality hexahedral/quadrilateral  meshes for complicated geometries requires tremendous amount of tedious human interaction, which adversely hampers user productivity. Ideally, users would like to obtain a high quality hexahedral//quadrilateral mesh at a few mouse-clicks for whatever complicated geometry they are working on. To achieve this goal, we propose to extract expert knowledge in hexahedral mesh generation from experienced users, using an innovative neural network/rule-based approach. The knowledge extracted will be documented, verified, and then computerized to develop a prototype software tool. The software tool will be used in place of human experts to automatically generate block topology for a given geometry, which is then interfaced with a commercial grid generation software tool (GridPro/az3000) to generate and optimize the final hexahedral/quadrilateral meshes.

Aim and Objective of the Project:

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 two-dimensional (2D) domains are generally decomposed into triangles and quadrilaterals; whereas three-dimensional (3D) domains are subdivided into tetrahedral and hexahedral shapes.

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.

In current stage of research, the activities are focused on the 2D aspect. That is, methodologies and systems will be developed to generate quadrilateral grids. However, the methodologies could be used to hexahedral mesh generation with some revision.

[Back to Top]

Project organization

The research group consists of:

• Dr. Samuel Huang (Principal Investigator)
  Director, Intelligent CAM Systems Laboratory,
  Dept of Mechanical, Industrial and Nuclear Engineering,
  The University of Cincinnati
• Dr. Erlendur Steinthorsson (Co- Principal Investigator)
  Parker Hannifin Corporation
• Mr. Guruprasad Bandekar
  Research Assistant,
  Dept of Mechanical, Industrial and Manufacturing Engineering,
  The University of Toledo,
• Mr. Haixin Wang
  Research Assistant, Intelligent CAM Systems Laboratory,
  Dept of Mechanical, Industrial and Nuclear Engineering,
  The University of Cincinnati
• Dr. Jun Shi
  Research Associate, Intelligent CAM Systems Laboratory,
  Dept of Mechanical, Industrial and Nuclear Engineering,
  The University of Cincinnati
• Mr. Summit Maloo
  (No longer involved in the project after graduation on December 2001)
  Research Assistant, Intelligent CAM Systems Laboratory,
  Dept of Mechanical, Industrial and Manufacturing Engineering,
  The University of Toledo,

The group of industry specialists consists of:

• esteinthorsson@parker.com (Parker Hannifin),
• mbenjamin@parker.com (Parker Hannifin),
• dennis.cronin@asd.bfg.com (B. F. Goodrich), and
• BARKER@aerostructures.bfg.com (B. F. Goodrich).

[Back to Top]

Methodology (Quadrilateral Mesh Generation):

System Architecture and Main Components

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

The system consists of following components (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. 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.
5. 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.
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.

Among them, three components are more complex and important. They are described in details as follows.

Implementing Boundary Conditions

Boundary condition rules, which depend on the angle of the vertices, are used to implement boundary conditions. Steps used to implement boundary conditions are:

1. Find the length of the angle bisector between a vertex and the opposite line for all the vertices
2. Select the minimum length of the angle bisector calculated in the last step and take the one-fifth fraction of it (λ)
3. Calculate the angle of the vertex (θ)
4. Create a new vertex on the angle bisector of the given vertex at a distance of λ from the given vertex
5. If θ<=90 then create two more vertices on the adjacent lines of the given vertex and make the connections as shown in Figure (a) and if θ>90 then make the connections between the new vertex and the given vertex as shown in the Figure (b).
   Figure (a)    Figure (b)
6. vi. Make the connection between all the new vertices in a sequential order

Drawing Projection according to the Geometry Bisector

In this component, the task is to project lines from the new vertices created in the boundary condition step onto the geometry bisector, considering these conditions:

1. Consider only those vertices that have angle more than 90
2. The projection lines should not intersect any other line of the geometry before joining the geometry bisector
3. Projection should be between the two endpoints of the geometry bisector

The steps involved in drawing projections are:

1. Find the intersecting point of the two lines (A), where the first line has one endpoint of the geometry bisector and an adjacent point, the second line has the other endpoint and an adjacent point on the same half of the geometry, which has the first adjacent point
2. For all the vertices that are considered finds the intersecting point between the geometry bisector and the line consisting of point A and the vertex under consideration
3. If the conditions listed above about making the connection are satisfied then a new vertex is created for the point of intersection obtained in step (ii) and connection between the new vertex and the given vertex is done
4. All the above steps are for one half of the geometry only, which has both the adjacent points to the endpoints of the geometry bisector. When all the points that can be considered are covered projection from the other half are carried out.
5. All the conditions stated above are also applied to the vertices that are considered in this step. Next step is to make the connections between the considered point and the point closest to them on the geometry bisector.

Rules in Checking Loops

Rule for Pentagon:

Select the vertex with maximum angle in the polygon and draw a line from the vertex to either of the two points listed below dependent upon the angles obtained by the connection

• The midpoint of the opposite line, or
• The point where the angle bisector of the vertex meets on the opposite line

Figure 3. Rule for Pentagon

Rule for Hexagon:

Select the vertex with the maximum angle in the polygon and draw a line from the vertex to the opposite vertex of the hexagon. If the line before meeting the opposite vertex intersects with any other line of the hexagon then select the vertex which has the second maximum angle and repeat the process.

Figure 4. Rule for Hexagon

[Back to Top]

Project reports*:

• Kick-off Presentation (Oct 5, 2000)
• Quarter 1 Report (Dec 14, 2000)
• Quarter 1 Review (Feb 12, 2001)
• Quarter 2 Report (Jun 29, 2001)
• Quarter 3 Review (Aug 24, 2001)
• Quarter 4 Project web site (Feb 2002)
• Quarter 4 Report (Feb 18, 2002)
• Quarter 5 Report (April 2002)
• Quarter 6 Report (July 2002)
• Final report on OAI CCRP 2000-5
• Conference Presentation on IEEE ICIT 02

*[PDF format, Click Here to download Acrobat Reader from www.adobe.com]

[Back to Top]

Results:

The following results have been obtained within the project:

[Back to Top]

Software Tool:

• QMesh3.exe

Snapshots:

The main user interface

Fine meshes with GridPro

References:

Journal papers

Hard Copy

1. “Automatic structured Grid generation using GRIDGEN (Some restrictions apply)” John R. Chawner and John P. Steinbrenner. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.
2. “Automatic Multi-block grid generation for High-lift configuration wings” B. Kim and S. Eberhardt. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.
3. “The National Grid Project: A system overview” A. Gaither, K. Gaither, B. Jean, M. Remotigue, J. Whitmire, B. Soni, J. Thomson, J. Dannenhoffer and N. Weatherill. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.
4. “A technique for optimizing grid blocks” John F. Dannenhoffer. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.
5. “Algorithms for the automatic generation of 2-D structured multi-block grids” T. Schonfeld, P. Weinerfelt and C. B. Jenssen. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.
6. “Mesh control through boundary layers and face vertex types” FLUENT.
7. “Finite element mesh generation using self organizing neural networks” L. Manevitz and M. Yousef. Microcomputers in Civil Engineering, Vol. 12, pp 233-250, 1997. Blackwell publishers.
8. “Language for feature based design and Manufacturability Evaluation” David W. Rosen and John R. Dixon. International journal of System Automation: Research and Application (SARA), Vol. 2, pp. 353-373, 1992.
9. “A shape grammar for non-main fold modeling” Steven N. Longenecker and Patrick A. Fitzhorn. Research in Engineering Design, Vol. 2, pp. 159-170, 1991. Springer-Verlag New York Inc.
10. “Automatic blocking for complex three dimensional configuration” John F. Dannenhoffer, III. NASA CP-3291, Surface Modeling, Grid Generation, and Related Issues in CFD Solutions, NASA Lewis Research Center, Cleveland, OH. May 1995.

Soft Copy (can be accessed via OhioLink)

1. “Meshing by successive super element decomposition (MSD) – A new approach to quadrilateral mesh generation” C. S. Krishnamoorthy, B. Raphael and S. Mukherjee. Finite Elements in Analysis and Design, Vol. 20, pp.1-37, 1995. Elsevier Science Publisher.
2. “Box-skeletons of discrete solids“ Atul Sudhalkar, Levent Gursoz and Friedrich Prinz. Computer-Aided Design, Vol. 28, No. 6/7, pp. 507-517, 1996. Elsevier Science Publishers.
3. “A generalized length strategy for direct optimization in planar grid generation” Jose E. Castillo and James S. Otto. Mathematics and computers in Simulation, Vol. 44, pp. 441-456, 1997. Elsevier Science Publishers.
4. “Multi-block mesh extrusion driven by a globally elliptic system” John C. Vassberg. International journal for numerical methods in engineering, Vol. 49, pp. 3-15, 2000. John Willey & Sons, Ltd.
5. “Parallel quadrilateral sub-domain generation for finite element analysis” J. Sziveri, B. Cheng, A. Bahreininejad, J. Cai, G. Thierauf and B.H.V. Topping. Advances in Engineering Software, Vol. 30, pp. 809-823, 1999. Elsevier Science Publishers.
6. “A multi-block orthogonal grid generation using CAD system” Vladimir V. Chudanov, Anna E. Aksenova, Valerii A. Pervichko, Alexander G. Churbanov, Irina G. Plotnikova, Vladimir V. Varenkov and Petr N. Vabishchenich. Nuclear safety Institute, Moscow, Russia.
7. “A multi-level parallelization concept for high-fidelity multi-block solvers” Ferhat F. Hatay, Dennis C. Jespersen, Guru P. Guruswamy, Yehia M. Rizk, Chansup Byun and Ken Gee. MCAT Inc., NASA Ames Research Center, CA.
8. “Boundary-based corner detection using neural networks” Du-Ming Tsai. Pattern Recognition, Vol. 30, pp. 85-97, 1997. Elsevier Science Publishers.
9. “Automatic identification of non-intersecting machining features from 2D CAD input” Lee-Wen Tyan and Venkat Devarajan. Computer-Aided Design, Vol. 30, pp.357-366, 1996. Elsevier Science Publishers.
10. “Generation of multi-block topology for discretisation of three-dimensional domains” Amit Shirsat, Sandeep Gupta and Gopal R. Shevare. Computers and Graphics, Vol. 23, pp. 45-57, 1999. Elsevier Science Publishers.
11. “An automatic mesh generator for handling small features in open boundary power transmission line problems using artificial neural networks” D. G. Triantafyllidis and D. P. Labridis. Communications in Numerical Methods in Engineering, Vol. 16, pp. 177-190, 2000. John Willey & Sons, Ltd.
12. “Parallel training of Neural Networks for finite element mesh decomposition” B. H. V. Topping, A. I. Khan and A. Bahreininejad. Computers & Structures, Vol. 63, No. 4, pp. 693-707, 1997. Elsevier Science Publishers.
13. “A unified-grid finite volume formulation for computational fluid dynamics” Sukumar Chakravarthy. International Journal for Numerical Methods in Fluids, Vol. 31, pp. 309-323, 1999. John Willey & Sons, Ltd.
14. “Local mesh refinement within a multi-block structured-grid scheme for general flows” W. L. Chen, F. S. Lien and M. A. Leschziner. Computer Methods in Applied Mechanics and Engineering, Vol. 144, pp. 327-369, 1997. Elsevier Science Publishers.
15. “Using neural networks to predict bending angle of sheet metal formed by laser” P. J. Cheng and S. C. Lin. International Journal of Machine Tools & Manufacture, Vol. 40, pp. 1185-1197, 2000. Elsevier Science Publishers.
16. “Domain deformation mapping: Application to variational mesh generation” Valmor F. De Almeida. Society for Industrial and Applied Mathematics Journal, Vol. 20, No. 4, pp. 1252-1275, 1999.
17. “Optimization approaches in feature recognition” P. Gibson, H. S. Ismail and M. A. Sabin. International Journal of Machine Tools & Manufacture, Vol. 39, pp. 805-821, 1999. Elsevier Science Publishers.
18. “Computer interpretation of process and instrumentation drawings” C. Howie, J. Kunz, T. Binford, T. Chen and K. H. Law. Advances in Engineering Software, Vol. 29, No. 7-9, pp. 563-570, 1998. Elsevier Science Publishers.

Online References

1. Meshing Research Corner, http://www.andrew.cmu.edu/user/sowen/mesh.html
2. Mesh generation and Grid Generation on the Web, http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html
3. International Society of Grid generation, http://www.isgg.org
4. GRIDGEN tutorial: Multi-block on a swept ramp, http://www.arl.hpc.mil/docs/gridgen/16.sweep/sweep
5. Issues in grid generation and complex geometry, http://www.iitb.ernet.in/~aero/IITZeus/Document
6. Elsevier Science Publishers (Online Journals), http://www.elsevier.nl/
7. John Wiley & Sons Publication (Online Journals), http://www.interscience.wiley.com/

GridPro Software Materials

• GridPro Manual
• GridPro TIL Reference

[Back to Top]

This web page was developed by Mr. Wang and revised by Dr. Huang and Dr. Shi, February 2002.