### The big picture

#### What is mesh?

- Look up in dictionary.com
- or look at the screenshots below. (hint: the one on the left side of first screenshot is called mesh)

#### Why generate mesh? (several examples below)

- Computer graphics
- Use: decompose polygons into triangles.
- Benefits:
- An algorithm only needs to take care of triangles.
- Triangle always stay on the same plane after any sequences of transformation.

- Interpolation of terrain database.
- Input: A set of locations and their heights, and a location to estimate.
- Output: Estimation of height at any location.
- Use:
- Form a mesh with the input locations.
- Find the triangle that contain the location to estimate.
- Interpolate the heights of each vertices of the triangle to estimate.

- Simulations that involve complicated differential equations. I.e. Heat transfer, Earthquake simulation
- Use: decompose a complicated model into tetrahedrons.
- Benfits: Simplify calculations in...
- Partial differential equations
- Numerical methods, such as finite element method or finite volume method.

- Computer graphics
#### What are the difficulties?

- The required mesh varies vastly depending on its application. Here are some of the possibilities,
- Composed of triangles or tetrahedrons of appropriate size, possibly varying throughout the mesh.
- Triangles or tetrahedrons must be "nicely" shaped for result to be accurate.

- Historically, the automation of mesh generation has porven to be the most challenge part of many simulation process.

- The required mesh varies vastly depending on its application. Here are some of the possibilities,

### My work

- Design data structures for mesh improvement algorithm.
- Implement algorithms to improve qualities of existing mesh.
- Scheme various different strategies targeted for specific mesh and quality measure.
- Design and implement a graphical tool for displaying mesh.

### Results - Graphical Tool

#### Basic Layout (Very similar to my 3d plotter)

- Left side shows the mesh.
- Upper right side shows the histogram of the quality of each tetrahedron in the mesh.
- X = quality of the mesh, ranging from 0 to 1
- Y = percentage, ranging from 0% to 100%
- For instance, in the following screenshot, about 10% of the mesh has a quality between 0.9 to 1

- Lower right side shows the current setting.
- Specify filename, the quality measure used, and several other parameters.

#### Color map each tetrahedron to its quality

- Lower right side shows the mapping, and it can be adjust at real time.

#### Filter by each tetrahedron's quality

- Display only those tetrahedron whose quality is below the cutoff. (The cutoff is 0.50 in the following screenshot)

### Results - Before & After mesh improvement algorithm

*(Technical)*#### Before #1

- Model: The same model is used for all the demonstrations here.
- Specifically, it's a cube that is cut by 3 identical retangular bars perpendicular to each other.
- 104 verticies (8 + 8 * 2 * 6)

- Mesh Generation: Delaunay Triangulations and refinement by inserting additional verticies.
- 6873 verticies, 32913 tetrahedrons.

- Quality Measure: C*V/(A_rms)^1.5 where
- C = (3^1.75)/(2*sqrt(2)
- V = volume of tetrahedron
- A_rms = Area Root Mean Square = sqrt(sum((Area of each side)^2)/4)
- Note: This measurement is approximately implicated in the condition number of the stiffness matrix for Poisson's equation.

- Cutoff: 0.30. I.e. only those tetrahedrons with quality less than 0.30 will be display below.

- Model: The same model is used for all the demonstrations here.
#### After Mesh Improvement Algorithm

- The algorithm attempts to move each vertex into a location that optimize the objective function for the vertex.
- Algorithm #1 - Objective function is the
*harmonic mean*of the element qualities that incident on the vertex.

- Algorithm #2 - Objective function is the
*minimun*of the element qualities that incident on the vertex.

#### Before #2

- Model: Same as above.
- Mesh Generation: Same as above.
- Quality Measure: C*(sin_min)
- C = 3 * sqrt(2) / 4
- sin_min = minimun sine of the dihedral angles = (3V / 2) * min(1<=i
V = volume - A_i = the unsigned areas of the faces of a tetrahedron

*l_ij = The length of the edge where face i (having area A_i) meets face j (having area A_j)*- Cutoff: Same as above.

#### After Mesh Improvement Algorithm

- The algorithm attempts to move each vertex into a location that optimize the objective function for the vertex.
- Objective function is the
*minimun*of the element qualities that incident on the vertex.

### Download all the original high quality screenshots. (559k)