Mesh Generation and Improvement
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.
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.
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.
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<=iV = 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.