The Story
Hexahedral meshes are notoriously difficult to construct yet they offer the greatest returns for both CFD and FEA simulations. Accuracy and speed of solution plus the ability to run LES, DNS, VOF, crack propagation, hyper elastics and complex combustion models makes it a necessity rather than a luxury.
The classical approaches to automating the construction of an all hexahedral mesh have all but failed, sure enough some codes can produce an all-Hex mesh but the quality is rather poor on complex geometric models. While at the same time other approaches have focused instead on mixed cells, commonly called Hex dominant meshes but these typically have the non Hex cells in the region of highest gradient, just where they shouldn't be.
So why is it so hard to build an all-Hex mesh?
Unlike an unstructured mesh a Hexahedral mesh has a global connectivity constraint called the Spatial Twist Continuum STC. This STC defines how the cell connectivity, as defined by Chords, propagate throughout the mesh, learn more...
So what is different about the Moceon approach to meshing?
Well it all began some 15 years ago on the 16th September 1993 with the discovery of the Spatial Twist Continuum. The original problem came from a research effort to find a closure solution for an automatic Hex-meshing algorithm. The method used then was to apply the cell-by-cell construction technique that worked successfully on a 2D Quad mesh method directly to the 3D Hex case. As the Hex cells were added starting from the boundary quad cells progressively in an inward fashion, pockets formed that were not sub-dividable with hexahedra. The STC showed that the construction of a Hex mesh had to be treated completely differently and that the old ways would no longer work. However efforts were still expended by others to proceed with the classical cell-by-cell method and use the STC as a guide to help steer the addition of these cells. Time has proven the original hypothesis correct; that the STC is not just a dual representation of a Hex mesh but is in fact a higher order definition of a Hex mesh.
The correct way to create a Hex mesh is to solve the STC first. This is the solution to the global connectivity constraint and logically it must be solved otherwise there is no practical way to fix it later. Attempts to do so only end up with a rather messy mesh that contains either collapsed cells or voids.
Any auto Hex meshing code that fails to address the STC will always fail, simply because it is always present in an all-Hex mesh and therefore cannot be avoided.
The problem however just doesn’t stop there. An automatic meshing algorithm has to start somewhere and it needs to operate with some information, building a mesh cell-by-cell means that the focal distance of the algorithm is limited to the relative size of a single cell. Meshes of this type tend to completely ignore the global shape of the geometry, meaning the points of transition; the “Folds” are determined by the local geometric variations and not by the global geometric flow of the mesh. The result of a local based approach is that there are far too many ‘Folds’ and they are usually in the wrong place, have the wrong propagation paths and lead inevitably to failed, void, collapsed or poor quality results.
Yet another problem is that the starting surface quad mesh may not produce a valid internal Hex-mesh. The fact that there are an infinite number of cases where a surface quad mesh will not yield a valid internal mesh, completely invalidates any method that tries to build a Hex mesh in such a way.
But the real reason for solving the STC first has to do with the very nature of the numerical methods. A Finite Volume and a Finite Element Method both solve a set of Partial Differential equations over discretized subdivisions of space. The values and gradients of each cell/element are compared with the values of each neighboring cell/element. A smooth (connectivity wise) STC represents a continuum of cell-based connections from one boundary surface across the mesh volume to an opposite boundary in a manner that has the shortest possible non-circular path, thereby reducing the intrinsic differencing error.
This is the true measure of cell quality, it’s not just the cells internal angles themselves it's the way the cells align with the physics and numerics of the solver and this shows in both the speed of the simulation and the accuracy/repeatability of the result.
Defining Hex cells also does not necessarily need to follow a classical approach either. A mesh that is defined by vertices’ and cells only is considered a static mesh. To make a change to a mesh of this definition type requires making changes to every vertex, on a 500 million-cell model this is a formidable task. The approach we use is a higher order definition, a Block form referred to as a Cell3, which is a set of volumes that completely define the mesh in a numerical volumetric sense.
This Cell3 definition contains a valid smooth STC solution. The mesh itself, is just a product of the cell factors (number of cells per Cell3 Volume) and the global nominal cell size. The local cell size is refined further by another variable called the weight value and this is used to control the local cell size. By using this Cell3 definition a 500 million-cell model can be fully captured in a 50 MB file. Changing the mesh from course to fine is just as simple as changing one value; the nominal cell size, and the entire mesh changes instantly.
The Cell3 definition is particularly suited to moving mesh problems; actually it was originally designed as a method for complex engine moving mesh models where the cell factors are dynamically changed throughout the simulation. For problems where the ideal mesh size is not known before hand it’s rather easy to start with a course mesh then instantly change it to a finer mesh whilst the simulation is running. This is very helpful when setting up massive multi million cell models and trying to quickly debug a solver.
But what about the STC, is that not difficult to solve?
Well yes it is, in some cases it's extremely difficult to solve. But here's the trick. Of all the types of problems and model geometries that are solved on a regular basis there exists a high degree of repetition. You could call it a geometric repetition or even a topological repetition, but it's actually an STC solution repetition.
Again: an all-Hex mesh has an STC definition and a block structure. This block structure can be extracted from an existing Hex mesh and used to represent the cells by a set of factors. For instance a block is nothing more than a big hex cell that is split into smaller cells. If you use StarCD’s block method you will be very familiar with this form.
Let's take the scenario where you have a perfectly good Hex mesh for a model and you build a new CAD model that is in many ways the same topologically speaking. One option would be to start from scratch and build another new mesh or you could extract the blocks, then scale, stretch and fit them into the new geometry. But the cells will become distorted, unless of course you change the factors on the blocks to produce nice cubic proportioned cells everywhere. Essentially what you have done is reused the same STC solution, in a very quick and efficient way.
This is the basis for the Cell3 structure; it contains all of the data of the cell-based mesh but in a reduced memory and compact dynamic form. It is an STC solution in a Cell3 form to a complex geometry that can be morphed to fit into a myriad of different but topologically similar models in a mere fraction of the time it takes to build a new Hex mesh or even run an automatic unstructured mesh.
Yes , the STC is the most difficult part to solve, once it's been solved for a particular class and type of problem, why solve it again, just recycle it. This also means that for any class of model geometry type there is an ideal or optimal STC solution. Once it’s found it has an intrinsic value, which gives value to a library of Cell3 solutions. And anything that has a value can be bought, sold and traded.
CheetahSTC is a Rhino3D plugin program. Meaning it has all the CAD functions required to build new Cell3 volumes (Blocks) from scratch, then scale, translate, mirror, copy, join, stitch…. Plus it has a very powerful Morphing capability. Morphing is actually a combination of methods and not just a single function. By combining a surface projection algorithm with a highly advanced smoother, morphing a Cell3 to the model geometry in seconds is not only a reality it has transformed the way meshes are built.
So where does one get these Cell3 from?
- If you already have a collection of Hex meshes you can extract them by tracing out the blocks starting from the cells that have 3 or 5 or 6 valance points.
- You can build them inside CheetahSTC by creating logical block edges. Select the edge curves and CheetahSTC will automatically convert them into Cell3.
- Assemble larger and more complex Cell3 by joining component Cell3 together.
- Or if you desire we can build a custom Cell3 for you. Learn more...
The process we used to create this method became with the revolutionary discovery of the STC, which was followed by a long evolutionary development path. This became by manually building a mesh using a very regimented method that would always yield a result, this took in some detailed cases a few months to build. It was more akin to an art form, in that, if you do something by hand you will always find the most efficient and effective way. The method and the art were solid and it always worked, so from this foundation we automated the individual steps one by one, in some cases reducing 6 days of manual work down to 0.6 seconds. This was followed by yet another radical discovery; the Spatial Matrix solver which is another level of mathematical abstraction which we now use to build complex Cell3. The latest crowning achievement, the new smoother, like all our code is STC based, it is the engine that makes the Cell3 come alive.
I guess you could say in a way that a complex problem requires an equally complex solution, unless of course you just change the way you view the problem then it all becomes quite simple. And that’s the way the STC method and the Cell3 evolved.