Mesh Generation for High Performance Computing: Current Trends and Applications

Advanced Algorithms - Hexahedral Meshing

Instructor: Scott A. Mitchell, Ph.D.

Audience: Contains mostly intermediate/advanced material. Some background in mesh generation will be assumed.

This talk will focus on the advanced hexahedral mesh generation algorithms for assemblies of volumes found in the CUBIT Mesh Generation Toolkit, and related algorithms found in other software packages. We will also discuss hexahedral mesh generation research ideas.

Sweeping is a "two and a half dimensional" meshing algorithm, meaning that one 2-dimensional cross-section can have an unstructured quadrilateral mesh, which is then replicated in a structured way into a third dimension called the "sweep direction". CUBIT's sweeping capability allows any number of meshed "source surfaces" to define the cross-section. Basic sweeping allows a single unmeshed (or isomorphically meshed) "target surface". If there is a linear transformation from the source to target, then CUBIT takes advantage of that when positioning interior nodes. Otherwise, CUBIT's advanced smoothing capabilities allow the sweep direction to vary wildly and the source to target transformation to be arbitrary. Multiple-source, multiple target sweeping, similiar to Fluent's Cooper Tool, allows there to be any number of unmeshed source and target surfaces. The geometric curves bounding the target surfaces are first projected onto the various source surfaces. The partitioned source surfaces are then meshed, and sweeping proceeds largely as in the multiple source, single target case. Additional steps are necessary for assemblies of volumes; these steps are handled automatically in CUBIT.

Grafting is a way to sweep assemblies of volumes when the sweep directions collide with one another. Consider a volume that by itself would be sweepable, such as a hexagonal prism, but with adjoining volumes that prevent a structured mesh on the side surfaces, such as a cylinder with axis perpendicular to the prism axis. The prism is called the "trunk", and the cylinder a "branch". First the branches are pruned so that the trunk may be swept. Then the (structured) meshes on the bark of the trunk are moved and refined to match the geometry of the branches. Finally, the branches may be swept away from the trunk.

Sweep forging is another algorithm, like grafting, for extending the class of geometries that may be swept. Instead of pruning the branches, the bark of the branches is left in place, but is topologically modified by splitting and combining curves. Also, we sometimes pretend that the geometry of the branches is different, for example two curves meeting at a tangency may be treated as if they meet at a right angle, so that the trunk may be swept. As in grafting, mesh moving and refining algorithms improve the quality of the swept trunk before the branches are swept. Sweep forging holds the promise of handling real features such as holes and fillets, in addition to the trunk imprints. Grafting and sweep forging are in progress.

The CUBIT team has researched and developed Plastering for many years. Plastering is an advancing front hexahedral mesh generation algorithm for general geometries. Several useful tools have emerged. First, although the algorithm cannot completely fill most volumes with hexes, we are able to stop short of filling the entire volume, and fill the remaining part with a tetrahedral mesh that node-wise conforms to the hex mesh. This "HexTet" algorithm reliably produces a reasonably quality, hex-dominant mesh. We may also transition between the hex and tet mesh using square-base pyramids. Another option is to get an all-hex mesh by splitting each tet into 4 hexes, and each plastered hex into 8 smaller hexes, and transitioning between the two regions with the all-hex geode template. Geode-template quality is acceptable in some limited regimes.

The CUBIT team has researched and developed Whisker Weaving and the Spatial Twist Continuum (STC) for many years. The STC, described in Pete Murdoch's PhD thesis, is the observation that the dual of a hexahedral mesh can be viewed as an arrangement of surfaces, each surface representing the layer of hexes it passes through. In addition to Whisker Weaving, the STC has been used to create the geode-template, some mesh connectivity improvement algorithms, and aids the understanding of mesh refinement. Whisker weaving is an advancing front algorithm based on the STC. We have developed both a state-list algorithm that advances the front, building the STC arrangment, one hex at a time, and a curve contraction algorithm that builds the STC arrangment one surface at a time. Local rules guide the advancing front away from poor quality degeneracies. After the arrangment is build, the STC is moved and refined in an effort to improve quality. Although a topologically well-defined mesh is always created, acceptable quality meshes remain rare. Similar to the curve contraction algorithm, we have a proof that, given mild conditions on a quadrilateral mesh bounding a volume, there always exists a topologically well-defined.hexahedral mesh filling the volume. Even so, no good-quality hexahedral mesh has been found by the research community, by any means, for some surprisingly small and simple examples.