# Presentation: 219018

## Why Is Hex Meshing So Hard?What is the Cubit Team Doing About it?

**Cubit User’s Meeting**
**June 27, 2007**

## Tet Meshing Vs. Hex Meshing

- Tet Meshing
- Fully Automated
- Generate millions of elements in minutes/seconds
- Adequate for some analysis
- Inaccurate for other Analysis
- “The only people that use tets are those that don’t care about their answers.” – Sandia Analyst

- Hex Meshing
- Partially Automated, some Manual
- Generate millions of elements in days/weeks/months
- Preferred by most analysts for solution quality

## Design Through AnalysisAnalysts Man-Hours Spent (Not CPU Time)

- 10 Step Design through Analysis Process
- Iteration loops not shown for clarity

- 73% of time is spent in either meshing or geometry manipulation for meshing.

**Notes:**
Sandia has performed extensive timing studies of the Design Through Analysis process that our Analysts use.  This slide shows the 10 key steps that analysts go through during this analysis process.

The red and blue bars represent the percentage of man-hours that are spent in each step.  The red bars show the steps representing finite element mesh generation or geometry manipulation required in order to generate a mesh.  Total, these steps account for 70-80% of the total time spent in the design through analysis process.

As a result, research in the automation of finite element mesh generation has a greater potential to improve the efficiency of analysts than any other area of research in this process.  Successful mesh generation research therefore holds the prospect of shortening the overall design through analysis process which would allow analysts and engineers to perform more design iterations, resulting in more reliable designs at a lower cost.

## Why is Hex Meshing HarderThan Tet Meshing?

**More complex element connectivity**
**Must consider warp**
**Larger minimum angles required**
**Propagation**

## More Complex Element Shape

- Hex Element
- 8 nodes
- 12 edges
- 6 faces

- Tet Element
- 4 nodes
- 6 edges
- 4 faces

## More Complex Element Shape

**Most Meshing performed with a bottoms-up approach**
- 1st mesh all vertices with nodes
- 2nd mesh all curves with mesh edges
- 3rd mesh all surfaces with surface elements
- 4th mesh volumes

## Advancing Front Element Creation

**Advancing Front Element Creation**

- Only a single node is required to finish the tet element

## Advancing Front Element Creation

- To Complete the hex, 4 well positioned nodes are required,
- which may not be readily available.

## Advancing Front Element Creation

**Advancing Front Element Creation**

- To Complete the hex, 4 well positioned nodes are required,
- which may not be readily available.

## Hex Elements Must Consider Warp

## Hexahedra Require LargerMinimum Angles

- Small angles can be filled with high quality tets much easier than high quality hexahedra.

- Shape: 0.28
- Cond#: 5.5

- Shape: 0.41
- Cond#: 3.13

## Hex Mesh Propagation

**Local Changes to tri/tet meshes can easily be performed:**
- Insertion of a single node
- Removal of a single node
- Swap a single face

## Hex Mesh Propagation

**Hex Mesh Propagation**

**Changes Propagate in order to maintain all/quad hex mesh.**

**Local Changes to quad/hex meshes are difficult to keep local without introducing a hybrid mesh**

## Hex Mesh Propagation

**Hex Mesh Propagation**

**Changes Propagate in order to maintain all/quad hex mesh.**

**Local Changes to quad/hex meshes are difficult to keep local without introducing a hybrid mesh**

## Quad/Hex Mesh Dual

## Quad/Hex Mesh Dual

- Chords define continual chain of connected quadrilaterals which force propagation

## Quad/Hex Mesh Dual

- Chords define continual chain of connected quadrilaterals which force propagation

## Quad/Hex Mesh Dual

- Chords define continual chain of connected quadrilaterals which force propagation

## Quad/Hex Mesh Dual

- In 3D, hexahedra combine to form Dual Sheets, the 3D analog of Quad Chords.  A local change to a hex mesh must be propagated through the sheets in order to avoid introducing hybrid element types.

## Current Hex-Meshing State of the ArtPave-and-Sweep

**Current Hex-Meshing State of the Art****Pave-and-Sweep**

- Sweeping a source quad mesh along a topologically constant cross section

- Also handles multiple sources and targets.  No restriction on planar/perpendicular
- source/targets or linear sweep path.  Limited to 21⁄2D Topologies

- Decomposing general geometries into sweepable partitions is time and expertise intensive ... an “art” form, requiring tedium, creativity and experience.

**Notes:**
Unlike tetrahedral mesh generation, there is currently no general solution to Hexahedral mesh generation.  Rather, hex meshes are generated by both manual and semi-automatic methods.
The current state of the art in hexahedral mesh generation is the Pave-and-Sweep method.  The Pave-and-Sweep method generates all-hexahedral finite element meshes on 3D dimensional solids.  However, there are strict requirements on the topology of the solids it can mesh.  Solids must have Source and Target surfaces which are topologically opposite each other based on a sweep path with a topologically constant cross section.  Solids which meet these topological requirements are often described as 21⁄2 dimensional.  A hexahedral mesh is generate by creating a quadrilateral mesh on the source, which is then swept along the sweep path until it reaches the source and target.
Only a very small percentage of real-world 3D solids meet this restrictive 21⁄2 dimensional requirement.  However, with enough time and creativity, any 3D solid can be decomposed into 21⁄2 dimensional partitions, each of which can be swept individually.  The final mesh on the part is then the collection of the meshes on each of the partitions.  THIS GEOMETRY DECOMPOSITION IS VERY TIME CONSUMING AND TEDIOUS.  We want to eliminate the need for this geometry decomposition by developing a new algorithm which does not have the 21⁄2 dimensional topology restrictions.

## What is Cubit Doing about it?

**Two-Approaches being pursued:**
- Improved Geometry tools to make Pave-And-Sweep Easier
**Virtual operators**
**ITEM wizard**
**Power Tools**
**Continued research on completely automated Unstructured Hex Mesh Generation**
- CSRF funded projects
- DSP participants research
- Graduate Student Research

## CSRF Funded Projects

**CSRF has funded research in the Cubit team for the past decade.**
**Unconstrained Plastering is current research focus.  Some simple to medium complex models can be meshed automatically.**

## CSRF – Unconstrained Plastering Research

**Paving - 2D (1990)**
- Initial boundary intervals defined
- Advancing front by discrete elements
- Element-by-element placement
- Interior voids easily resolved
- Robustly quad meshes nearly any surface
- Creates skewed elements in thin surfaces

**Unconstrained Paving – 2D (2005)**
- No initial boundary intervals
- Advancing front by discrete geometric layers
- Layer-by-layer placement
- Under active research and development

- Slide 4 of 11 – Matt Staten

**Notes:**
A large part of this research has been to revisit the 2D realm, and the Paving algorithm which has provided a robust solution to general surface meshing. 
As shown in this animation, Paving starts from a pre-meshed boundary, followed by sequential discrete element by element advancement until the unmeshed void becomes small enough to be fit with a simple patterned mesh.
In the early 1990’s, Paving was extended into 3D with the Plastering algorithm.  Like Paving, Plastering begins by pre-meshing the boundary surfaces with quadrilaterals, followed by discrete element by element advancements.  However, the extra constraint of the 3rd dimension prevented the unmeshed void from becoming simple enough to be resolved with a simple pattern.  This slide shows a simple tapered block which I attempted to mesh with Plastering and the unmeshed void after it had been simplified as much as possible.  These unmeshed voids are often called “Ribbons” since they wind their way throughout the entire volume in a random manner.
At the onset of the current research effort, I re-examined Paving, to see if there were any constraints that we could eliminate, while still keeping it successful.  The result of this was an algorithm called Unconstrained Paving.  Unlike Paving, Unconstrained Paving does not pre-mesh the boundary curves.  Advancements are done with a row by row curve offset approach as opposed to a discrete element-by-element approach.  This allows us to keep closer control of the degrees of freedom on the surface, making the resolution of the voids much easier.  Our current research efforts involve extending this new Unconstrained Paving approach into 3D as Unconstrained Plastering.

## DSP Participant Research

**Jason Shepherd – University of Utah (2004-2007)**
- Theory of Sheet Based Hex mesh generation
**Primary Sheets**
**Secondary Sheets**
- Manual tools allowing for unstructured hex mesh generation on non-sweepable models with little (if any) geometry modification
- Automation of methods into Cubit currently being considered

## DSP Participant Research

**Jason Shepherd – University of Utah (2004-2007)**
- Example meshes

## DSP Participant Research

**Matt Staten – Carnegie Mellon University (2007-2010)**
- Theory and Application of Sheet Based Hex mesh generation
**Continued Unconstrained Plastering**
**Advanced Pillowing Techniques**
**Mesh Matching Techniques**
**Mike Borden – University of Texas at Austin (2007-2010)**
- IsoGeometric Analysis as an alternative to traditional Hex-based FEA analysis.

## Graduate Student Research

**Brigham Young University (1994-Present)**
- Recent Successes
**Improved Local Hexahedral Refinement**
**Localized Hexahedral Coarsening**
**Improved node placement in Pave-and-Sweep**
**Carnegie Mellon University (2002-Present)**
- Recent Successes
**Geometry based sizing functions for tet meshing**