Hexahedra Meshing Schemes
The creation of a fully automatic all hexahedral meshing algorithm has been the goal and dream of many researcher for over the past 30 odd years. Incredibly large financial rewards await the one who cracks the problem. It seems at first such a simple task, pack some box shaped elements into a geometric space, however, this apparently simple problem has eluded many and still does for several reasons of which will be elaborated on here.
The main reason why a hexahedral mesh is difficult to create as opposed to a tetrahedral or other poly, hybrid mesh, is that it has a global connectivity constraint. In other words the region of influence (connectivity wise) for a tetrahedral mesh is one element wide, whereas the connectivity condition for a hexahedral mesh extends throughout the entire mesh. In order to automate a hexahedral meshing algorithm one must solve the entire problem at once or in an iterative manner where the global constraint is maintained.
In the world of meshing there are actually 3 schools of thought; the automatic unstructured group, the research groups that still think a fully automatic hex meshing algorithm is possible and those that produce hex meshes for a living.
The unstructured automatic school are for the most part primarily only interested in getting past the meshing hurdle and see it as a painful step that has been rudely placed in their path. If it were at all possible to get an accurate result from an unstructured mesh then there would be no need for hex meshes, unfortunately this is not the case. There is a slight dark side to unstructured meshes, most proponents promote unstructured meshes and solvers as being as good as a hex mesh, don't believe it, they just want you to think that so they can sell you their product. There is of course the other allure of an unstructured mesh; it's a fall back option, face it, if you can't build a hex mesh what are you going to do?
The research school of thought is another interesting case. There still exists a belief that a hex mesh can be fully automated. The idea of fully automatic is a big single button that one presses and out pops a mesh. This will never happen because its not possible to do that even on a tet mesh without a fair amount of manual fix-ups. The reasons for pursuing this are purely financial in nature and here's why. Research for research sake is a very lucrative business to be in, especially if it's government sponsored money. Trouble is once a workable solution has been found, the research stops and therefore, the goal or target point of the outcome changes in order to keep the research funds flowing. Another very important point should also be considered, pure researchers don't actually build real world meshes, they don't rely on meshing as a form of income.
The third school of thought is the one that actually gets the job done. This is where skill and experience are employed to solve the problem using what ever means, methods and software available. And as with all effort intensive tasks the skilled operator will find the quickest and most efficient way which brings us to the next point, how to...
If you think of a typical simulation scenario and break it down into its parts, operations that at first appear to be the norm take on a new relative form. For instance the procedure of CAD design, this can either take hours or months depending on the CAD operators skill and level of motivation, as in either self employed or working for a large corporation. There doesn't appear to be any research going on to automate CAD design, no big magic button one presses and out pops a complete design. Yet when you think about it creating a design of a part that will be subjected to stresses or perform an aerodynamic function starts off as an interpretation, a guess, an opinion about what would work best. The classical approach is to CAD the design then mesh it, and hopefully verify it's design before time runs out and the part needs to commit to the production tooling phase. In an ideal scenario the mesh and simulation should precede the CAD model and not the other way round.
Creating a hex mesh, and by this I mean a high quality mesh where the cell face angles are between 60 and 120 degrees is a very technically challenging and difficult task. Acknowledging this has to be the first order of business when deciding on how to tackle the problem. Then comes the realization that it actually is a very complex problem that requires a skilled and highly experienced operator to solve. For instance, take this scenario, you are scheduled in to have brain surgery, do you either have a kid who has just read a brochure or do you look for the best surgeon you can find?
The following are a list of attempts at automatic hex meshing and reasons for why they have failed.
Examples of Automatic Hex meshing research efforts:
This is a 2D quad meshing algorithm, but its importance plays a role in understanding the research direction of some 3D meshing methods. The paver starts at a surface boundary and just like a tri and tet element mesher inserts elements one at a time. It does a local look around at a distance equal to the length of one of the sides of the element for either another element edge or the boundary. As it progresses it produces non quad elements, where, it either collapses a set of elements back along a series of elements or expands a series. It all seems to work for many cases and as one would imagine has been the result of many countless hours of research and development. But it’s really not a very good method except for the fact that it works. Its main drawback is the higher than normal valence point count. This then brings us to the logical next step and transition to a 3D paving mesher.
This is an extension of the 2D surface paver. This algorithm takes the quad surface mesh and builds hexahedra (bricks) starting at the boundary surface and moving inwards. The obvious logical extension in the thought process is that it works for a surface mesh then why not for a volume. The problem that quickly arises are the formation of voids within the mesh, polyhedrals that can’t be segmented down to hexahedra. The real reason why the method doesn't work is because the paver itself is not a very good connectivity algorithm.
This algorithm was born out of a need for Sandia National Laboratories to integrate the STC into the Cubit code, a brick algorithm. The notion that this algorithm was possible and feasible came out of the Dual proof that any quad surface mesh would produce an internal hexahedral mesh. The idea was to start with a surface quad mesh and create a series of logical 2D sheets that would hold the logical chord connectivity information. So why didn't it work? The most obvious reason is the invalidity of the existence proof that any quad surface mesh emits a hexahedral mesh. There are an infinite number of cases where a surface quad mesh will not emit an internal hex mesh. The other reason is that the paver algorithm produces a surface mesh that is locally defined in 2D logical space, as soon as you extend it to 3D all of the other boundary faces must comply to it, instead they are all forced together and the STC from the opposing faces clash. A mesh should be created with the entire volume in consideration first and what happens at the boundary surface is a result of the connectivity that arises from within and not the other way around.
Trimmed Cell (Cartesian) algorithm
This method starts with a full Cartesian mesh, (all evenly shaped hexahedra) which is then intersected with the boundary. This creates several problems, firstly the trimmed elements at the boundary are no longer hexahedra and secondly the worst elements are right on the boundary. In order to capture a boundary flow one must have the highest possible quality elements on the boundary and have a layer of cells parallel to the surface. The main problem with this method is that it starts out by having no regard for boundary geometry, it’s a totally blind method. The idea that these types of meshes are considered as a hex mesh because they have ~90% hex elements by volume (which really accounts for <50% of the cells) and the rest of the cells are polyhedral. This leads to a poor quality solution since the small percentage of polyhedral cells account for 99% of the error. It really doesn't qualify as a hexahedral meshing algorithm since it doesn't actually produce an all-hex mesh.
The medial plane algorithm was one of the most logical attempts to define the mesh in terms of 3D space before the discovery of the STC. The medial plane is a surface that passes through an arbitrary domain in such a way that it passes through the logical centre of volume and divides the domain into 2 spaces. This method then aims to further subdivide the domain into geometric domains that have a known hexahedral meshed solution. Major problem with this method: the boundaries of the meshed sub-domains must match. Here in lies a rather typical disconnect between research and the real world. The amount of computational effort and research work that went into automatically determining the location of the medial planes could have been easily averted by allowing a skilled operator to just draw a medial plane in with the CAD program.
Tetrahedral to Hexahedral conversion
A novel approach that’s only one small step ahead of the Trimmed Cell method in terms of spatial dissemination. A tetrahedral mesh has a cyclic connectivity, any conversion method will simply inherit the same. It is also not possible to convert all the tets into hex elements using agglomeration so again it's not considered a hex mesh. This is like making a mess first then trying to clean it up later, why?
Examples of semi automatic Hex methods
These are the methods that actually work, they do require a level of skill and patience, but with time one can become very proficient.
This method as used very successfully within ICEM CFD starts with a single large block that covers the entire domain. The user then subdivides the block into sub blocks where those subdivided blocks that lie outside of the domain are deleted. As one then fits the edges of the blocks to the domain the edge angle of the blocks, in tubes for instance, becomes flat. The user then inserts “O grids” to alleviate this problem. This method tends to build cells with extremely high aspect ratios and has difficulties with complex geometries.
Software packages employing this method include GridGen, HyperMesh, StarCD (ProStar v3). The user creates blocks by manually building the edges of the blocks with a CAD program then logically selects the edges in a pattern order to create the same. This is an expert method that one can either do or not do, it’s very labor intensive and considered an art form. It’s entirely possible to create the very best possible quality meshes with this method with some forward planning and experience from doing similar model geometries.
Starting with a block mesh or existing hex mesh it’s possible to reuse a mesh by fitting it to another part of similar geometry. For instance exhaust manifolds generally are all the same, pipes joining in junctions. By saving the mesh from one manifold one can scale stretch and morph it to another manifold. The stretching operation will create some elongated cells that are simply refined by splitting later. The ability to morph a mesh is based solely on the quality of the base mesh. This method is the most economically feasible way if one is solving the same type of problem over and over again.
This is a block based method with an associated smoother algorithm. A hex mesh alone can be morphed and smoothed however it’s rather cumbersome to refine the mesh up and down. For instance changing the cell factors in a hexahedral mesh requires an operation that collapses cells on a layer to reduce the factors or adds layers by subdivision to increase the factors. The Cell3 method does not contain any cells but rather defines the cells via a mathematical subdivision of the individual cell3 volumes. The factors and weight functions then become part of the morphing and smoothing method. A Cell3 mesh greatly extends its range of morph-ability which translates directly to economic savings. It is also the fastest way to build a Hexahedral mesh many hundreds of times faster.
So where does CheetahSTC sit in the Meshing Scheme?
It's a multi level code, an automated code, where every part of the meshing process that can be automated has been. Its based on an expert system approach, we developed methods that worked in the manual sense, perfected, then automated them. Its a synergy between computer and human mind, a way of making things happen and happen very quickly with the highest possible quality. Many thousands of hours went into developing the individual steps, some of which would never of been obvious unless one had experienced all of the peculiar and complex cases that stop other methods. The focus is always to be moving forward, always being able to get a resulting hex mesh.
At the first level it has the block based method. The user constructs splines inside of CheetahSTC using the CAD functions of Rhino. Then the splines are selected all at once and the blocks are formed automatically in seconds, no need to select them in the logical order manually.This saves days of work on a large model.
The next level is the Cell3 method with the morphing and smoothing capability. Once you have a full block based mesh its utility can be extended and its value increased considerably by being able to reuse a mesh solution over and over again.
The final level is an automated STC based method for constructing the Cell3. This method uses a higher level definition above the STC that we call the Spatial Matrix Solver. In time we shall be releasing this program after patent protection. In the mean time we are offering a custom Cell3 service alone with the Cell3 functionality in CheetahSTC as a system for creating a revolution in meshing. Bringing real world automation to those who rely on quality hex meshes for a living.