# Presentation: 143332

## Steve Owen

**An Introduction to Mesh Generation Algorithms**

- Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

**Notes:**
This course is designed to be an overview of some of the fundamental algorithms and processes used in finite element mesh generation

## Overview

**The Simulation Process**
**Geometry Basics**
**The Mesh Generation Process**
**Meshing Algorithms**
- Tri/Tet Methods
- Quad/Hex Methods
- Hybrid Methods
- Surface Meshing
**Algorithm Characteristics **

## Simulation Process

- 1. Build CAD Model

- 2. Mesh

- 3. Apply Loads and Boundary Conditions

- 4. Computational Analysis

- 5. Visualization

## Adaptive Simulation Process

- 1. Build CAD Model

- 2. Mesh

- 3. Apply Loads and Boundary Conditions

- 4. Computational Analysis

- 7. Visualization

- 5. Error Estimation

- Error?

- 6. Remesh/Refine/Improve

- Adaptivity Loop

- Error < 

- Error > 

## Geometry

- Mesh Generation

- Geometry Engine

## Geometry

**vertices:** *x,y,z location*

## Geometry

**vertices:** *x,y,z location*

**curves:** *bounded by two vertices*

## Geometry

**Geometry**

**vertices:** *x,y,z location*

**surfaces:** *closed set of curves*

**curves:** *bounded by two vertices*

## Geometry

**Geometry**

**vertices:** *x,y,z location*

**surfaces:** *closed set of curves*

**volumes**: *closed set of surfaces*

**curves:** *bounded by two vertices*

## Geometry

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**surfaces:** *closed set of curves*

**volumes**: *closed set of surfaces*

**curves:** *bounded by two vertices*

## Geometry

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**volumes**: *closed set of surfaces*

**surfaces:** *closed set of curves*

**loops**: *ordered set of curves on surface*

**curves:** *bounded by two vertices*

## Geometry

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**volumes**: *closed set of surfaces*

**loops**: *ordered set of curves on surface*

**surfaces:** *closed set of curves (loops)*

**coedges**: *orientation of curve w.r.t. loop*

**curves:** *bounded by two vertices*

## Geometry

**Geometry**

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**volumes**: *closed set of surfaces (shells)*

**surfaces:** *closed set of curves (loops)*

**loops**: *ordered set of curves on surface*

**coedges**: *orientation of curve w.r.t. loop*

**shell**: *oriented set of surfaces comprising a volume*

**curves:** *bounded by two vertices*

## Geometry

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**volumes**: *closed set of surfaces (shells)*

**surfaces:** *closed set of curves (loops)*

**loops**: *ordered set of curves on surface*

**coedges**: *orientation of curve w.r.t. loop*

**shell**: *oriented set of surfaces comprising a volume*

**curves:** *bounded by two vertices*

## Geometry

**Geometry**

**body**: *collection of volumes*

**vertices:** *x,y,z location*

**volumes**: *closed set of surfaces (shells)*

**surfaces:** *closed set of curves (loops)*

**loops**: *ordered set of curves on surface*

**coedges**: *orientation of curve w.r.t. loop*

**shell**: *oriented set of surfaces comprising a volume*

**coface**: *oriented surface w.r.t. shell*

**curves:** *bounded by two vertices*

## Geometry

- Volume 1

- Surface 1

- Surface 2

- Surface 3

- Surface 4

- Surface 5

- Surface 6

- Volume 2

- Surface 8

- Surface 9

- Surface 10

- Surface 11

- Surface 7

**Manifold Geometry**: *Each volume maintains its own set of unique surfaces*

## Geometry

**Geometry**

- Volume 1

- Surface 1

- Surface 2

- Surface 3

- Surface 4

- Surface 5

- Surface 6

- Volume 2

- Surface 8

- Surface 9

- Surface 10

- Surface 7

- Volume 1

- Volume 2

- Surface 7

**Non-Manifold Geometry**: *Volumes share matching surfaces*

## Mesh Generation Process

- Mesh Vertices

- Mesh Curves

- Verify/correct for sizing criteria on curves

- Set up sizing function for surface

- Mesh surface

- Set up sizing function for volume

- Mesh volume

- Smooth/Cleanup surface mesh

- Verify Quality

- Verify Quality

- Smooth/Cleanup volume mesh

- For each surface

- For each volume

- The Mesh Generation Process

- Apply Manual Sizing, Match Intervals

## Meshing Algorithms

## Octree

- http://www.simulog.fr/mesh/gener2.htm

- Advancing Front
- Delaunay

- http://www.ansys.com

## Octree/Quadtree

- Define intial bounding box (*root* of quadtree)
- Recursively break into 4 *leaves* per *root* to resolve geometry
- Find intersections of leaves with geometry boundary
- Mesh each *leaf* using corners, side nodes and intersections with geometry
- Delete Outside
- (Yerry and Shephard, 84), (Shepherd and Georges, 91)

## Octree/Quadtree

- QMG,
- Cornell University

## Octree/Quadtree

- QMG,
- Cornell University

## Advancing Front

- Begin with boundary mesh - define as initial *front*
- For each edge (face) on front, locate ideal node C based on front AB

## Advancing Front

**Advancing Front**

- A

- B

- Determine if any other nodes on current front are within search radius *r* of ideal location C (Choose D instead of C)

- D

## Advancing Front

**Advancing Front**

- Book-Keeping:  New *front edges* added and deleted from *front* as triangles are formed
- Continue until no *front edges* remain on *front*

- D

## Advancing Front

**Advancing Front**

- Book-Keeping:  New *front edges* added and deleted from *front* as triangles are formed
- Continue until no *front edges* remain on *front*

## Advancing Front

**Advancing Front**

- Book-Keeping:  New *front edges* added and deleted from *front* as triangles are formed
- Continue until no *front edges* remain on *front*

## Advancing Front

**Advancing Front**

- Book-Keeping:  New *front edges* added and deleted from *front* as triangles are formed
- Continue until no *front edges* remain on *front*

## Advancing Front

**Advancing Front**

- A

- B

- C

- Where multiple choices are available, use best quality (closest shape to equilateral)
- Reject any that would intersect existing front
- Reject any inverted triangles (|AB X AC| > 0)
- (Lohner,88;96)(Lo,91)

*r*

## Advancing Front

**Advancing Front**

- Ansys, Inc.
- www.ansys.com

## Delaunay

- Triangle
- Jonathon Shewchuk
- http://www-2.cs.cmu.edu/~quake/triangle.html

- Tetmesh-GHS3D
- INRIA, France
- http://www.simulog.fr/tetmesh/

## Delaunay

*Empty Circle (Sphere) Property*:
- No other vertex is contained within the circumcircle (circumsphere) of any triangle (tetrahedron)

## Delaunay

- Delaunay Triangulation:
- Obeys empty-circle (sphere) property

**Delaunay**

## Delaunay

- Non-Delaunay Triangulation

**Delaunay**

## Delaunay

**Lawson Algorithm**
- Locate triangle containing X
- Subdivide triangle
- Recursively check adjoining triangles to ensure empty-circle property.  Swap diagonal if needed
- (Lawson,77)

- X

**Delaunay**

## Delaunay

- X

**Lawson Algorithm**
- Locate triangle containing X
- Subdivide triangle
- Recursively check adjoining triangles to ensure empty-circle property.  Swap diagonal if needed
- (Lawson,77)

**Delaunay**

## Delaunay

**Bowyer-Watson Algorithm**
- Locate triangle that contains the point
- Search for all triangles whose circumcircle contain the point (*d<r*)
- Delete the triangles (creating a void in the mesh)
- Form new triangles from the new point and the void boundary
- (Watson,81)

- X

**Delaunay**

## Delaunay

- X

**Bowyer-Watson Algorithm**
- Locate triangle that contains the point
- Search for all triangles whose circumcircle contain the point (*d<r*)
- Delete the triangles (creating a void in the mesh)
- Form new triangles from the new point and the void boundary
- (Watson,81)

**Delaunay**

## Delaunay

- Begin with Bounding Triangles (or Tetrahedra)

**Delaunay**

## Delaunay

- Insert boundary nodes using Delaunay method (Lawson or Bowyer-Watson)

## Delaunay

- Insert boundary nodes using Delaunay method (Lawson or Bowyer-Watson)

## Delaunay

- Insert boundary nodes using Delaunay method (Lawson or Bowyer-Watson)

## Delaunay

- Insert boundary nodes using Delaunay method (Lawson or Bowyer-Watson)

## Delaunay

- Insert boundary nodes using Delaunay method (Lawson or Bowyer-Watson)

## Delaunay

- Recover boundary
- Delete outside triangles
- Insert internal nodes

## Delaunay

**Delaunay**

- Node Insertion

**Grid Based**
- Nodes introduced based on a regular lattice
- Lattice could be rectangular, triangular, quadtree, etc...
- Outside nodes ignored

*h*

## Delaunay

- Node Insertion

**Grid Based**
- Nodes introduced based on a regular lattice
- Lattice could be rectangular, triangular, quadtree, etc...
- Outside nodes ignored

## Delaunay

**Delaunay**

- Node Insertion

**Centroid**
- Nodes introduced at triangle centroids
- Continues until edge length,

## Delaunay

- Node Insertion

**Centroid**
- Nodes introduced at triangle centroids
- Continues until edge length,

*l*

## Delaunay

- Node Insertion

**Circumcenter (“Guaranteed Quality”)**
- Nodes introduced at triangle circumcenters
- Order of insertion based on minimum angle of any triangle
- Continues until minimum angle > predefined minimum

- (Chew,Ruppert,Shewchuk)

## Delaunay

**Circumcenter (“Guaranteed Quality”)**
- Nodes introduced at triangle circumcenters
- Order of insertion based on minimum angle of any triangle
- Continues until minimum angle > predefined minimum

- Node Insertion

- (Chew,Ruppert,Shewchuk)

## Delaunay

**Delaunay**

**Advancing Front**
- “Front” structure maintained throughout
- Nodes introduced at ideal location from current front edge

- Node Insertion

- A

- B

- C

- (Marcum,95)

## Delaunay

**Advancing Front**
- “Front” structure maintained throughout
- Nodes introduced at ideal location from current front edge

- Node Insertion

- (Marcum,95)

## Delaunay

**Delaunay**

**Voronoi-Segment**
- Nodes introduced at midpoint of segment connecting the circumcircle centers of two adjacent triangles

- Node Insertion

- (Rebay,93)

## Delaunay

**Delaunay**

**Voronoi-Segment**
- Nodes introduced at midpoint of segment connecting the circumcircle centers of two adjacent triangles

- Node Insertion

- (Rebay,93)

## Delaunay

**Delaunay**

**Edges**
- Nodes introduced at along existing edges at *l=h*
- Check to ensure nodes on nearby edges are not too close

- Node Insertion

*h*

*h*

*h*

- (George,91)

## Delaunay

**Delaunay**

**Edges**
- Nodes introduced at along existing edges at *l=h*
- Check to ensure nodes on nearby edges are not too close

- Node Insertion

- (George,91)

## Delaunay

- Boundary Constrained

**Boundary Intersection**
- Nodes and edges introduced where Delaunay edges intersect boundary

## Delaunay

- Boundary Constrained

**Boundary Intersection**
- Nodes and edges introduced where Delaunay edges intersect boundary

## Delaunay

- Boundary Constrained

**Local Swapping**
- Edges swapped between adjacent pairs of triangles until boundary is maintained

## Delaunay

- Boundary Constrained

**Local Swapping**
- Edges swapped between adjacent pairs of triangles until boundary is maintained

## Delaunay

- Boundary Constrained

**Local Swapping**
- Edges swapped between adjacent pairs of triangles until boundary is maintained

## Delaunay

- Boundary Constrained

**Local Swapping**
- Edges swapped between adjacent pairs of triangles until boundary is maintained

## Delaunay

- Boundary Constrained

**Local Swapping**
- Edges swapped between adjacent pairs of triangles until boundary is maintained

- (George,91)(Owen,99)

## Boundary Constrained

- D

- C

- Delaunay

**Local Swapping Example**
- Recover edge CD at vector **V**s

## Boundary Constrained

- D

- C

- E1

- E2

- E3

**Local Swapping Example**
- Make a list (queue) of all edges Ei, that intersect **V**s

- Delaunay

## Boundary Constrained

- D

- C

- E2

- E3

- Delaunay

**Local Swapping Example**
- Swap the diagonal of adjacent triangle pairs for each edge in the list

## D

- C

- E3

- Delaunay

**Local Swapping Example**
- Check that resulting swaps do not cause overlapping triangles.  I they do, then place edge at the back of the queue and try again later

## D

- C

- Delaunay

**Local Swapping Example**
- Check that resulting swaps do not cause overlapping triangles.  If they do, then place edge at the back of the queue and try again later

## D

- C

- Delaunay

**Local Swapping Example**
- Final swap will recover the desired edge.
- Resulting triangle quality may be poor if multiple swaps were necessary
- Does not maintain Delaunay criterion!

## Delaunay

**Delaunay**

- A

- C

- D

- E

- B

- Boundary Constrained

**3D Local Swapping**
- Requires both boundary *edge* recovery and boundary *face* recovery

**Edge Recovery**
- Force edges into triangulation by performing 2-3 swap transformation

*ABC = non-conforming face*

*DE = edge to be recovered*

- (George,91;99)(Owen,00)

## Delaunay

**Delaunay**

- A

- B

- C

- D

- E

- Boundary Constrained

**3D Local Swapping**
- Requires both boundary *edge* recovery and boundary *face* recovery

**Edge Recovery**
- Force edges into triangulation by performing 2-3 swap transformation

*ABC = non-conforming face*

*DE = edge to be recovered*

*ABCE*
*ACBD*

***2-3 Swap***

- (George,91;99)(Owen,00)

## Delaunay

**Delaunay**

- A

- B

- C

- D

- E

- Boundary Constrained

**3D Local Swapping**
- Requires both boundary *edge* recovery and boundary *face* recovery

**Edge Recovery**
- Force edges into triangulation by performing 2-3 swap transformation

*ABCE*
*ACBD*

***2-3 Swap***

*BAED*
*CBED*
*ACED*

*DE = edge recovered*

- (George,91;99)(Owen,00)

## Delaunay

**Delaunay**

- A

- C

- D

- E

- B

- Boundary Constrained

**3D Local Swapping**
- Requires both boundary *edge* recovery and boundary *face* recovery

**Edge Recovery**
- Force edges into triangulation by performing 2-3 swap transformation

*DE = edge recovered*

*ABCE*
*ACBD*

***2-3 Swap***

*BAED*
*CBED*
*ECED*

- (George,91;99)(Owen,00)

## Delaunay

**3D Edge Recovery**
- Form queue of faces through which edge AB will pass
- Perform 2-3 swap transformations on all faces in the list
- If overlapping tets result, place back on queue and try again later
- If still cannot recover edge, then insert “steiner” point

- Edge AB to be recovered

- Exploded view of tets intersected by AB

## Delaunay

**Delaunay**

***2-3 Swap***

***2-2 Swap***

***Face Split***

***Edge Split***

***Edge Suppress***

- abce, acbd

- abde, bcde, cade

- aceb, adcb

- adeb, edcb

- abce, acbd

- abfe, bcfe, cafe
- bafd, cbfd, acfd

- abnini+1 {i=1...N}

- abnini+1,
- cbnini+1 {i=1...N}

- abnini+1 {i=1...N}

- nm,knm.jnm.ia,
- nm,knm.jnm.ib {m=1...M}

- N = no. adj. tets at edge ab

- M = no. unique trias in polygon P={n1,n2,n3}

## Structured

**Structured**

- Requires geometry to conform to specific characteristics
- Regular patterns of quads/hexes formed based on characteristics of geometry

**Unstructured**

- No specific requirements for geometry
- quads/hexes placed to conform to geometry.
- No connectivity requirement (although optimization of connectivity is beneficial)

- Internal nodes always attached to same number of elements

## Structured

- Mapped Meshing

- 4 topological sides
- opposite sides must have similar intervals

**Geometry Requirements**

**Algorithm**

- Trans-finite Interpolation (TFI)
- maps a regular lattice of quads onto polygon

- (Thompson,88;99)

- (Cook,82)

## Structured

- 3D Mapped Meshing

- 6 topological surfaces
- opposite surfaces must have similar mapped meshes

**Geometry Requirements**

## Structured

- http://www.gridpro.com/gridgallery/tmachinery.html

- http://www.pointwise.com/case/747.htm

- Mapped Meshing

- Block-Structured

## Structured

- i

- j

- Sub-Mapping

- Blocky-type surfaces (principally 90 degree angles)

**Geometry Requirements**

- (White,95)

## Structured

- Sub-Mapping

- Automatically decomposes surface into mappable regions based on assigned intervals

- (White,95)

## Structured

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- source

- target

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

- linking surfaces

## Structured

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

**Structured**

- Sweeping

**Geometry Requirements**
- source and target surfaces topologicaly similar
- linking surfaces *mapable* or *submapable*

## Structured

- Cubit, Sandia National Labs

- Gambit, Fluent Inc.

- Sweeping

## Sweeping

**Sweeping**

- Sweep Direction

- 1-to-1 sweepable

## Sweeping

- n-to-1 sweepable

- Sweep Direction

## Sweeping

- n-to-m sweepable
- Multi-Sweep

- Sweep Direction

## Sweeping

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Sweeping

**Sweeping**

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

##      Sweeping

- Sweep Direction

**The fundamental strategy of multi-sweep is to convert an n-to-m sweepable volume into a number of n-to-1 sweepable volumes.**

## Decomp Sweep Overview

**Decomp Sweep Overview**

- Sweep Direction

## Decomp Sweep Overview

- Sweep Direction

## Sweeping

**Sweeping**

- (White, 2004)

- CCSweep

## Medial Axis

- (Price, 95;97)(Tam,91)

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

## Medial Axis

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

**Medial Axis**

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

- Medial Object - Roll a Maximal circle or sphere through the model.  The center traces the medial object
- Medial Object used as a tool to automatically decompose model into simpler mapable or sweepable parts

- (Price, 95;97)(Tam,91)

## Medial Axis

- Medial Axis + Midpoint Subdivision
- (Price, 95)

- (Sheffer, 98)

- Embedded Voronoi Graph

## Meshing Algorithms

## Indirect Quad

**Triangle splitting**
- Each triangle split into 3 quads
- Typically results in poor angles

## Indirect Hex

**Indirect Hex**

**Tetrahedra splitting**
- Each tetrahedtra split into 4 hexahedra
- Typically results in poor angles

## Indirect Hex

**Tetrahedra splitting**
- Each tetrahedtra split into 4 hexahedra
- Typically results in poor angles

## Indirect Hex

**Tetrahedra splitting**
- Each tetrahedtra split into 4 hexahedra
- Typically results in poor angles

- (Taniguchi, 96)

## Indirect Hex

**Example of geometry meshed by tetrahedra splitting**

## Indirect

**Triangle Merge**
- Two adjacent triangles combined into a single quad
- Test for best local choice for combination
- Triangles can remain if attention is not paid to order of combination

## Indirect

**Triangle Merge**
- Two adjacent triangles combined into a single quad
- Test for best local choice for combination
- Triangles can remain if attention is not paid to order of combination

## Indirect

**Triangle Merge**
- Two adjacent triangles combined into a single quad
- Test for best local choice for combination
- Triangles can remain if attention is not paid to order of combination

## Indirect

**Directed Triangle Merge**
- Merging begins at a boundary
- Advances from one set of triangles to the next
- Attempts to maintain even number of intervals on any loop
- Can produce all-quad mesh
- Can also incorporate triangle splitting
- (Lee and Lo, 94)

## Indirect

- A

- B

**Triangle Merge w/ local transformations (“Q-Morph)**
- Uses an advancing front approach
- Local swaps applied to improve resulting quad
- Any number of triangles merged to create a quad
- Attempts to maintain even number of intervals on any loop
- Produces all-quad mesh from even intervals
- (Owen*,* 99)

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Unstructured-Quad

- Q-Morph

**Unstructured-Quad**

## Indirect

**Q-Morph**

**Lee,Lo Method**

## Indirect

**  **

**  **

**Tetrahedral Merge w/ local transformations (“H-Morph”)**

## Unstructured-Hex

- H-Morph

- “Hex-Dominant Meshing”

- (Owen and Saigal, 00)

## Unstructured-Hex

- (Owen and Saigal, 00)

- H-Morph

- “Hex-Dominant Meshing”

## Unstructured-Hex

## Meshing Algorithms

## Unstructured-Hex

- Grid-Based

- Generate regular grid of quads/hexes on the interior of model
- Fit elements to the boundary by projecting interior faces towards the surfaces
- Lower quality elements near boundary
- Non-boundary conforming

## Unstructured-Hex

- Grid-Based

- Generate regular grid of quads/hexes on the interior of model
- Fit elements to the boundary by projecting interior faces towards the surfaces
- Lower quality elements near boundary
- Non-boundary conforming

## Unstructured-Hex

- Grid-Based

- Generate regular grid of quads/hexes on the interior of model
- Fit elements to the boundary by projecting interior faces towards the surfaces
- Lower quality elements near boundary
- Non-boundary conforming

## Unstructured-Hex

- Grid-Based

- Generate regular grid of quads/hexes on the interior of model
- Fit elements to the boundary by projecting interior faces towards the surfaces
- Lower quality elements near boundary
- Non-boundary conforming

## Unstructured-Hex

- Grid-Based

- (Schneiders,96)

## Unstructured-Hex

- http://www.numeca.be/hexpress_home.html

- Grid-Based

- Gambit, Fluent, Inc.

## Direct Quad

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- (Blacker,92)(Cass,96)

## Unstructured-Quad

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- (Blacker,92)(Cass,96)

## Unstructured-Quad

**Unstructured-Quad**

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- (Blacker,92)(Cass,96)

## Unstructured-Quad

**Unstructured-Quad**

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- Form new row and check for overlap

- (Blacker,92)(Cass,96)

## Unstructured-Quad

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- Insert “*Wedge*”

- (Blacker,92)(Cass,96)

## Unstructured-Quad

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- Seams

- (Blacker,92)(Cass,96)

## Unstructured-Quad

**Unstructured-Quad**

- Paving

- Advancing Front: Begins with front at boundary
- Forms rows of elements based on front angles
- Must have even number of intervals for all-quad mesh

- Close Loops and smooth

- (Blacker,92)(Cass,96)

## Unstructured-Hex

- Plastering

- (Blacker, 93)

- 3D extension of “paving”
- Row-by row or element-by-element

## Unstructured-Hex

**Unstructured-Hex**

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

- Plastering

- 3D extension of “paving”
- Row-by row or element-by-element

- (Blacker, 93)

## Unstructured-Hex

**Exterior Hex mesh**

**Remaining** **Void**

**Ford Crankshaft**

- Plastering+Tet Meshing

- “Hex-Dominant Meshing”

## Direct

- Whisker Weaving

- First constructs *dual* of the quad/hex mesh
- Inserts quad/hex at the intersections of the dual chords

## Direct

- Whisker Weaving

*Spatial Twist Continuum* - Dual of a 3D hex mesh (Murdoch, 96)
- Hexes formed at intersection of twist planes

## Direct

**Direct**

- Whisker Weaving

*Spatial Twist Continuum* - Dual of a 3D hex mesh (Murdoch, 96)
- Hexes formed at intersection of twist planes

*Twist Plane*

## Direct

**Direct**

- Whisker Weaving

*Spatial Twist Continuum* - Dual of a 3D hex mesh (Murdoch, 96)
- Hexes formed at intersection of twist planes

*Twist Plane*

## Direct

**Direct**

- Whisker Weaving

*Spatial Twist Continuum* - Dual of a 3D hex mesh (Murdoch, 96)
- Hexes formed at intersection of twist planes

*Twist Planes*

## Direct

- Whisker Weaving

- Define the topology of the twist planes using whisker diagrams
- Each whisker diagram represents a closed loop of the surface dual
- Each boundary vertex on the diagram represents a quad face on the surface
- Objective is to resolve internal connectivity by “weaving” the chords following a set of basic rules

- (Tautges,95;96)

- Whisker diagrams used to resolve hex mesh above

## Hex Meshing Research

- Unconstrained Paving

- Remove constraint that we must define number of quad when row is advanced.  This constrains only 1 DOF.

- Remove constraint of pre-meshed boundary.

## Hex Meshing Research

- Unconstrained Paving

- Each Row Advancement Constrains Only 1 DOF

- Quads are only completely defined when 2 unconstrained rows cross

- Quad Elements

## Hex Meshing Research

- Unconstrained Paving

- Each Row Advancement Constrains Only 1 DOF

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

- (DOF = 2)

## Hex Meshing Research

- Unconstrained Plastering

- (DOF = 1)

## Hex Meshing Research

- Unconstrained Plastering

- (DOF = 0)

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

## Hex Meshing Research

- Unconstrained Plastering

## Hybrid Methods

**CFD Meshing**

- Image courtesy of acelab, University of Texas, Austin, http://acelab.ae.utexas.edu

- Image courtesy of Roy P. Koomullil, Engineering Research Center, Mississippi State University, http://www.erc.msstate.edu/~roy/

## Hybrid Methods

**Hybrid Methods**

- Advancing Layers Method

## Hybrid Methods

**Hybrid Methods**

- Advancing Layers Method

- Discretize Boundary

## Hybrid Methods

- Advancing Layers Method

- Define Normals at boundary nodes

- (Pirzadeh, 1994)

## Hybrid Methods

**Hybrid Methods**

- Advancing Layers Method

- Generate nodes along normals according to distribution function
- Form layer

- Distance from wall

- Element size

- distribution function

## Hybrid Methods

- Advancing Layers Method

- Generate nodes along normals according to distribution function
- Form layer

- Distance from wall

- Element size

- distribution function

## Hybrid Methods

- Advancing Layers Method

- Generate nodes along normals according to distribution function
- Form layer

- Distance from wall

- Element size

- distribution function

## Hybrid Methods

- Advancing Layers Method

- Define new boundary for triangle mesher

## Hybrid Methods

- Mesh with triangles

## Hybrid Methods

**Hybrid Methods**

- Convex Corner

- Concave Corner

## Hybrid Methods

**Hybrid Methods**

- Convex Corner

- Concave Corner

## Hybrid Methods

- Convex Corner

- Concave Corner

## Hybrid Methods

- Convex Corner

- Concave Corner

- Blend Regions

## Hybrid Meshes

- Convex Corner

- Concave Corner

- Blend Regions

## Hybrid Methods

- Convex Corner

- Concave Corner

- Blend Regions

## Hybrid Methods

- Convex Corner

- Concave Corner

- Smoothed Normals

## Hybrid Methods

- Convex Corner

- Concave Corner

- Smoothed Normals

## Hybrid Methods

**Hybrid Methods**

- Convex Corner

- Concave Corner

- Smoothed Normals

## Hybrid Methods

- Multiple Normals

- 

- Define Normals every  degrees

## Hybrid Methods

**Hybrid Methods**

- Multiple Normals

## Hybrid Methods

- Intersecting Boundary Layers

## Hybrid Methods

- Intersecting Boundary Layers

## Hybrid Methods

**Hybrid Methods**

- Intersecting Boundary Layers

- Delete overalppaing elements

## Hybrid Methods

- Intersecting Boundary Layers

## Hybrid Methods

- Image courtesy of SCOREC, Rensselaer Polytechnic Institute, http://www.scorec.rpi.edu/

- (Garimella, Shephard, 2000)

## Hex-Tet Interface

- Conforming quad-triangle

- Conforming hex-tet?

## Hex-Tet Interface

**Hex-Tet Interface**

- Solutions
- Free Edge (Non-conforming)
- Multi-point Constraint
- Pyramid

## Hex-Tet Interface

- Heat sink meshed with hexes, tets and pyramids

## Hex-Tet Interface

- Pyramid Elements for maintaining compatibility between hex and tet elements (Owen,00)

## Hex-Tet Interface

**Tetrahedral transformations to form Pyramids**
- Use 2-3 swaps to obtain 2 tets at diagonal
- combine 2 tets to form pyramid

- A

- B

- N5

- N1

- N

- 4

- N

- 3

- N

- 2

- (d)

## Hex-Tet Interface

**Tetrahedral transformations to form Pyramids**
- Use 2-3 swaps to obtain 2 tets at diagonal
- combine 2 tets to form pyramid

- A

- B

- N5

- N1

- N

- 4

- N

- 3

- N

- 2

- (d)

## Hex-Tet Interface

**Tetrahedral transformations to form Pyramids**
- Use 2-3 swaps to obtain 2 tets at diagonal
- combine 2 tets to form pyramid

- A

- B

- N5

- N1

- N

- 4

- N

- 3

- (d)

## Hex-Tet Interface

- (d)

**Tetrahedral transformations to form Pyramids**
- Use 2-3 swaps to obtain 2 tets at diagonal
- combine 2 tets to form pyramid

- A

- B

- N5

- N

- 3

- N1

## Hex-Tet Interface

**Hex-Tet Interface**

- (d)

**Tetrahedral transformations to form Pyramids**
- Use 2-3 swaps to obtain 2 tets at diagonal
- combine 2 tets to form pyramid

- A

- B

- N5

- N

- 3

- N1

## Hex-Tet Interface

- N

- 1

- N

- 4

- B

- A

- N

- 2

- N

- 3

- Non-Conforming Condition:
- Tets at quad diagonal A-B

**Pyramid Open Method**

## Surface Meshing

- Direct 3D Meshing

- Parametric Space Meshing

- u

- v

- Elements formed in 3D using actual x-y-z representation of surface

- Elements formed in 2D using parametric representation of surface
- Node locations later mapped to 3D

## Surface Meshing

**A**

**B**

**3D Surface Advancing Front**
- form triangle from front edge AB

## Surface Meshing

**A**

**B**

**Surface Meshing**

**C**

**N**C

**3D Surface Advancing Front**
- Define tangent plane at front by averaging normals at A and B

*Tangent plane*

## Surface Meshing

**A**

**B**

**C**

**N**C

**D**

**3D Surface Advancing Front**
- define D to create ideal triangle on tangent plane

## Surface Meshing

**A**

**B**

**C**

**N**C

**D**

**3D Surface Advancing Front**
- project D to surface (find closest point on surface)

**Surface Meshing**

## Surface Meshing

**3D Surface Advancing Front**
- Must determine overlapping or intersecting triangles in 3D.  (Floating point robustness issues)
- Extensive use of geometry evaluators (for normals and projections)
- Typically slower than parametric implementations
- Generally higher quality elements
- Avoids problems with poor parametric representations (typical in many CAD environments)
- (Lo,96;97); (Cass,96)

## Surface Meshing

- Parametric Space Mesh Generation

- Parameterization of the NURBS provided by the CAD model can be used to reduce the mesh generation to 2D

*u*

*v*

*u*

*v*

## Surface Meshing

- Parametric Space Mesh Generation

- Isotropic: Target element shapes are equilateral triangles
- Equilateral elements in parametric space may be distorted when mapped to 3D space.
- If parametric space resembles 3D space without too much distortion from *u-v* space to *x-y-z* space, then isotropic methods can be used.

*u*

*v*

## Surface Meshing

- Parametric space can be “customized” or *warped* so that isotropic methods can be used.
- Works well for many cases.
- In general, isotropic mesh generation does not work well for parametric meshing

*u*

*v*

- Parametric Space Mesh Generation

- Warped parametric space

## Surface Meshing

*u*

*v*

- Anisotropic: Triangles are stretched based on a specified vector field
- Triangles appear stretched in 2d (parametric space), but are near equilateral in 3D

- Parametric Space Mesh Generation

## Surface Meshing

- Stretching is based on field of surface derivatives

- Parametric Space Mesh Generation

- Metric, **M** can be defined at every location on surface.  Metric at location **X** is:

## Surface Meshing

- Distances in parametric space can now be measured as a function of direction and location on the surface.  Distance from point X to Q is defined as:

- Parametric Space Mesh Generation

- X

- Q

- X

- Q

**M**(X)

## Surface Meshing

- Parametric Space Mesh Generation

- Use essentially the same isotropic methods for 2D mesh generation, except distances and angles are now measured with respect to the local metric tensor **M**(X).
- Can use Delaunay (George, 99) or Advancing Front Methods (Tristano,98)

## Surface Meshing

- Parametric Space Mesh Generation

- Is generally faster than 3D methods
- Is generally more robust (No 3D intersection calculations)
- Poor parameterization can cause problems
- Not possible if no parameterization is provided
- Can generate your own parametric space (Flatten 3D surface into 2D) (Marcum, 99) (Sheffer,00)

## Algorithm Characteristics

## Algorithm Characteristics

- Sub-map
- Tri Split
- Tri Merge
- Q-Morph
- Grid-Based
- Medial Axis
- Paving
- Mapped
- Sub-map
- Sweeping
- Tet Split
- Tet Merge
- H-Morph
- Grid-Based
- Medial Surf.
- Plastering
- Whisker W.

**Algorithm Characteristics**

- Tris

- Hexes

- Quadtree
- Delaunay
- Adv. Front

- Octree
- Delaunay
- Adv. Front

- Quads

- Tets

- Conforming Mesh

- Boundary Sensitive

- Orientation Insensitive

- Commercially Viability

- Regular Node Valence

- Arbitrary Geometry

- 1

- 2

- 3

- 4

- 5

- 6

## More Info

- http://www.andrew.cmu.edu/~sowen/mesh.html

- Meshing Research Corner

## References

## References

## References

## References

## References