Hexahedral Meshing Analysis
for Complex Geometry
A. Yahalom , G.A. Pinhasi
Flow-sim LTD, Ariel 44837, Israel,
The college of Judea and Samaria - Faculty of Engineering
Ariel 44837, Israel
Abstract
The current work is related to numerical meshing technique of complex geometries. Computer algorithms were devoted to for the creation of a pure hexahedral meshing of a domain defined according to the STL data format.
The developed algorithm is capable of generating a modified Cartesian grid for simple or complex geometries. The modified Cartesian grid algorithm was shown to be robust, but it tends to generate poor quality elements at the volume boundary. Thus, an optimization algorithm was developed based on the modification of the boundary elements (displacement of the nodes near the boundary) to meet the grid-quality requirements.
1. Introduction
Most of the computer simulations and analysis techniques used require first converting the model into a finite element mesh. For many physical problems hexahedral meshing provides better solutions than the tetrahedral one. However, the generation of hexahedral meshes turns out to be much more complex than for tetrahedral meshes.
Automated hexahedral element meshing has been the objective of mesh generation research for years. The rigid connectivity and shape constraints of these meshes provide the challenge.
Considerable progress has been made on automatic hexahedral mesh generation in recent years. There are currently several distinct strategies proposed for unstructured all-hex mesh generation that are predominant in the literature (Sheffer and Bercovier, 2000; Sheffer at al., 1999). A few automated meshing algorithms (e.g. mapping, sub-mapping, sweeping) have proven to be very reliable on certain classes of geometry. Still there is a necessity for general algorithms viable on arbitrary complicated geometry.
The objective of the current research is to develop an algorithm in order to create a pure hexahedral meshing of a domain defined according to the STL data format. This algorithm will be able to generate a grid in (or around) relatively complex parts.
The current work, presents the work on shape recognition and volume decomposition to automatically decompose a STL model into hex meshable volumes. There are four phases in this approach: Creating a Cartesian grid, Modification of the boundary nodes, Modification of the boundary element and mesh-quality optimization.
The first version of the developed algorithm is capable to generate a modified Cartesian grid for complex parts. It was successfully applied to test cases, for both, simple and complex geometries.
2. Numerical method
The problem of hexahedral grid generation may be viewed as a series of smaller problems not uncommon in computational geometry. This section briefly discusses some of the key aspects involved in the process.
Automated hexahedral meshing presents a number of significant constraints:
1. Opposing Faces: For any face of the hex there must always be an opposing face.
2. Continuous Layers: Hex mesh is, in fact, a series of interlaced layers of elements.
3. Propagating Refinements: Any refinement added to the mesh must be accomplished by adding a continuous layer of elements.
4. Element Quality: The hex-elements maintain “a reasonable shape”.
5. Geometric Sensitivity: All surfaces have associated quad meshes (Sharp angle problems).
2.1. Description of the Domain to be Gridded
There are two possible ways of describing the surface of the computational domain: using analytic function and via discrete data. In the later, a cloud of points or an already existing surface triangulation describes the surface of the computational domain.
One of the surface triangulation data protocols is the ASCII STL format, which is a standard output of CAD-CAM software. In the STL format each surface element is defend by three points and a normal vector (Fig 1).
Fig 1. ASCII STL file protocol for surface triangulation
2.2. Cartesian Meshing
As a first step, a relatively simple algorithm was developed to perform the Cartesian hexahedral grid. Cartesian grids continue to be attractive because of their inherent simplicity. Also it is not necessary to communicate the actual topology of the configuration to the grid generator. The price of this simplicity is, however, a very large number of cells.
The intersection of the Cartesian cells with the boundary triangulation is made more efficient by the use of the STL data structure (as compared to solid or CAD representation), which makes it possible to identify the list of surface triangles intersecting a given Cartesian cell.
In the Cartesian meshing scheme the created mesh consists entirely of cubic hexahedral mesh elements. The elements size can vary according to user-specified and default settings.
2.3. Modified Cartesian grid: Boundaries Representation
For improvement of the simple Cartesian grid, algorithms were developed to perform the modified Cartesian hexahedral grid. The developed algorithm perform Cartesian hexahedral grid with boundaries representation. Grid adaptation is carried out by some combination of redistribution (moving the grid points), refinement (adding/deleting grid points), or modification of the solution representation on the grid. By using it, the points that are closed to the surface are placed on the correct boundary.
The most important ingredient of the modified grid generator is a fast algorithm for finding the correct target point on the boundary. The algorithm is based on finding the STL triangle element that is closed to the point and on the analytical equations representing the STL surface triangulation. The point is moved over the minimum possible distance. The developed algorithm tries to avoid (if possible) the necessity to smooth the edges and corners by placing the nodes on the edge line or on the corner point (Fig. 2.2 a,b)
Some nontrivial logic is used to avoid problems at the sharp corners or when the surface curvature is such that more then one face of any given element is cut by the boundary. It also arranges the boundary elements nodes so that all four nodes of the element facet would place on the STL boundary element.
This grid type has a major drawback: The worst quality elements generally appear on the boundary, which for many applications is where the highest-quality elements are required. For that reason further modifications are needed.
(a) / (б)
Fig. 2.2. Modified Cartesian Hexahedral element and STL face:
(a) Corner (b) edge
2.4. Improving Boundary Elements
The most serious problem of the embodied Cartesian grid approach is the poor quality of the mesh close to the surface (the boundary elements in the current grid model). To circumvent any possible problems these irregular grids may trigger for field solvers, the generated mesh is optimized further to improve the uniformity of the mesh.
The uniformity of the mesh is defined by the “quality” of each element in the grid. The parameters required evaluating the quality are the side distance parameters (the element lengths), and the angles between the edges and the faces of the element. Some commonly used quality definitions are: Aspect Ratio, Diagonal Ratio, Edge Ratio and Volume. Quality measures may include combinations of geometric ideas such as orthogonality of the grid elements, the uniformity of volumes in the grid and the relative amount of grid skewness. Grid quality depends on the measure used to quantify quality. These measures have been used to optimize 3D grids within a given grid topology.
In the developed algorithm use the elements average volume as the quality parameter by using coordinate transformation of the modified elements. Every hexahedral element is transformed to a square element by using interpolation functions and the proper Jacobian matrix. The volume and “quality of an element” can be found from its Jacobian matrix. The algorithm used this property in the grid optimization and in the removal of bad elements.
The boundary element adaptation is carried out by redistribution (moving the grid points). By using it, the internal nodes (not boundary nodes) of the boundary element are displaced according the Cartesian directions (x,y,z) (see Fig.2.3). For any displaced node the quality of the neighboring elements are calculated. The node displacement proceeds until a mash that satisfies a present measure of quality is achieved. The optimization procedure finds the minimum node displacement that would lead to the maximum quality for the surrounding elements. In the current algorithm the sum of surrounding-elements quality is used as objective function for the optimization procedure.
This technique remarkably improves the quality of the boundary elements (surface element layer) and by that the entire grid quality. The developed grid generator includes algorithm that have quality assessment. For that purpose the element-shape quality needs to be quantified.
(a) /
(b)
Fig.2.3. Improving Boundary Elements; (a) 2D view (b) 3D
3. Preliminary results
The current work was divided into three major stages: generation of modified Cartesian hexahedral grid, grid improvement and code evaluation. The developed algorithm is being applied to GM’s “engine head” test case. The results for Cartesian grid and for modified grid modified grid with grid improvement are presented.
3.1. Cartesian Hexahedral Grid
The first version of the developed algorithm for Cartesian grid was successfully tested on complex geometries. Fig.2.4 present the face view of Cartesian grid obtained by the developed algorithm for entire part of an engine head and in closed view. The grid density is 300900300. The resulting grid exhibits stair casing at the boundaries and does not fully represent the boundaries.
3.2. Modified Cartesian Hexahedral Grid
For improvement of the simple Cartesian grid, an algorithm was developed to generate the modified Cartesian hexahedral grid. The algorithm of the boundary representation was successfully applied to GM’s test case, for specific parts of the body, as well as for the entire body. The calculated grid was tested using grid visualization and quality calculations.
3.2.1. Boundary Texture-View
The preliminary grid tests were preformed using a “homemade” visualization tool. The visualization tool was developed to display the nodes and element in space, at the boundary and at any given cut. Fig.2.5 present face view of Modified Cartesian grid obtained by the developed algorithm for the GM test case. The grid density is 300900300.
From the boundary texture-view figures it appears that the developed algorithm is capable to represent the boundary of the body quite well. The obtained grid does not have any visually obvious problems such as unintended “holes” or element overlap. Furthermore the edges and corners are represented correctly.
3.2.2. Quality of the Boundary Elements
The developed grid generator includes simple algorithms for quality assessment. In order to test the accuracy and the quality of the calculated grid the following tests where made:
1. Testing the grid calculated volume (sum of the elements volume) against the actual body volume (known or calculated from the STL body representation).
2. Analyzing the statistics of the grid elements volume: mean and the standard deviation. This was done for the boundary elements only (in this stage the internal elements are with constant size and shape).
From the volume analysis for relatively simple bodies, the body volume calculated from the preformed grid was found to be similar to the actual body volume. Furthermore, the mean volume of the boundary-elements was found to be closed to the original cubic element. However the relatively large standard deviation indicates the existence of bad quality elements (having small or large volume). For the GM test case, the number of elements on the boundary was 704,575 with an average volume of 0.77 mm3.
Since the worst quality elements appear on the boundary a further grid modification is needed. This was done by a procedure for improving the quality of the boundary elements.
3.3. Improving Boundary Elements
The proposed algorithm for modification of the boundary elements was successfully tested on relatively simple parts. After analyzing the nodes coordinates the elements geometry and quality it seems that the algorithm displaces the appropriate nodes correctly while a "satisfactory" element aspect ratio is obtained. So far satisfactory results were obtained for the simple parts.
The optimization procedure is operating by using the element volume as the quality criterion. The grid modification procedure needs to be tested against other quality measures to find the best quality criterion for the optimization procedure. Element shape quality needs to be better quantified, but the various metrics currently in use are duplicative, insufficient and not yet adequately analyzed (Douglsss et al, 2001).
(a) /
(b)
Fig.2.4: Cartesian grid for engine head geometry: 300900300
(a) The entire part (b) closed view
(a) /
(b)
Fig.2.5: Modified Cartesian grid for engine head geometry: 300900300
(a) The entire part (b) closed view
4. Summary
The developed Hex grid generator starts with inserting into the STL model a mesh primitive such as Cartesian grid. The nodes of the elements are relaxed to the surface of the geometry, and operations are preformed to improve the quality of the mesh.
The developed technique is highly automated and applicable to most geometry. The proposed grid generation model is a stand-alone simple application running under PC. The algorithm is demonstrated on simple geometries as well as on complex real-life examples (GM test case).
Algorithms developed till this stage generates satisfactory results. Further algorithms for grid improvement are being developed. Grid optimization techniques developed will include: removal of bed elements, and element optimization. Further investigation is being made on a mesh quality objective function whose optimization automatically produces high-quality elements when possible. The grid modifications will improve the mesh quality in terms of smoothness and uniform element size.
Acknowledgments
This research was supported by Flow-sim LTD, ISRAEL the developer of the FLUIDEX package.
References
- Anderson, D.A., Tannehill, J.C. and Pletcher, R. H. (1984) Computational Fluid Mechanics and Heat Transfer, McGraw-Hill, New York.
- Lohner, R. (2001) Applied CFD Techniques, Wiley, New York.
- Thompson, J.F, Soni, B.K. and Weatherill, N.P. (1999) Handbook of Grid Generation, CRC press, New York.
- Reddy, J.N. and Gartling, D.K. (1994) The Finite Element Method in Heat Transfer and Fluid Dynamics, CRC Press.
- Knupp, P. M. (2001) “Hexahedral and Tetrahedral Mesh Untangling”, Engineering With Computers, 17 (3), 261-268.
- Blacker, T. (2001) “Automated Conformal Hexahedral Meshing Constraints, Challenges and Opportunities”, Engineering With Computers, 17 (3) 201-210.
- Sheffer, A. Bercovier, M. (2000) “Hexahedral meshing of non-linear volumes using Voronoi faces and edges“, International Journal for Numerical Methods in Engineering, 49 (1) 329-351.
- Sheffer, A., Etzion, M., Rappoport, A., Bercovier, M. (1999) “Hexahedral mesh generation using the embedded Voronoi graph”, Engineering with Computers., 15 (3), 248-262.
- Douglass, R.W., Carey, G. F., White, D.R., Hansen, G.A., Kallinderis, Y., Weatherill, N. P. (2002) “Current views on grid generation: Summaries of a panel discussion” Numerical Heat Transfer Part B-Fundamentals., 41 (3-4), 211-237.
- Lu, Y. Gadh, R. Tautges, T J. (2001) “Feature based hex meshing methodology: Feature recognition and volume decomposition”, Computer-Aided Design. 33(3), 221-232.
- Aftosmis, M.J., Berger, M.J. and Melton, J.E. (1997) “Robust and Efficient Cartesian Mesh Generation for Component-Based Geometry”
1