## 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. 