Patrick M. Knupp Principal Member Technical Staff Applied Mathematics & Applications Dept.

MICS Research

TITLE: Mesh Generation Algorithms

STAFF: Scott A. Mitchell, Patrick M. Knupp, Jason Shepherd

This work has two components, Whisker Weaving and Mesh Optimization. Whisker Weaving (WW) is an algorithm for generating 3D unstructured hexahedral meshes. Most hexahedral meshing algorithms work on only a small class of geometries, restrict the surface mesh, and require extensive user input. WW is a unique technology designed to eliminate these shortcomings. If successful, it will significantly reduce the user-time needed to generate hexahedral meshes for complex geometries. As time to mesh is currently the most serious impediment to developing the automated design capability necessary for ASCI and other major programs, the potential impact of both WW and Mesh Optimization is great.

WW is unique in taking a topology-first approach to meshing. Other algorithms approach the problem geometrically and attempt to deal with topological problems as they arise. WW first generates the dual of a hexahedral mesh, an arrangement of surfaces, in an advancing front manner. Then certain connectivity degeneracies are removed. This determines the connectivity of the mesh. In order to get the nodal positions, we fix the nodes on the surfaces, and smooth the nodes in the interior of the volume.

Node smoothing is best done within the context of mesh optimization to improve mesh quality. Meshes of poor quality are often generated for computer simulations of complex physical processes, significantly affecting accuracy. Poor quality includes lack of smoothness, negative volume elements, skewed elements, lack of orthogonality, and poor spacing on the boundary. To improve such meshes CUBIT users presently call a "smoothing" algorithm. However, if the region is non-convex, smoothing may trade one aspect of quality for another; e.g., positive volume elements for smoothness.

How, then, to generate quality meshes? Currently, mesh "quality measures" are computed to flag problems after a mesh is generated. By using optimization one can directly incorporate quality measures into the mesh generation process. While not a panacea, mesh optimization will enable the user to rectify glaring defects in a mesh.

For Mesh Optimization we will investigate new functionals for quality measures, smoothing functionals, and functionals to control mesh quality on the boundary (this includes proofs of convexity of functionals and existence of optimized meshes). We will extend methodologies devised for structured meshes to unstructured, hybrid hex/tet grids on both surfaces and 3D volumes. The algorithms will be Implemented as CUBIT tools. The 3D smoothing functionals will be applied to meshes generated via Whisker Weaving to significantly improve quality. We will investigate optimization across multiple interconnected surfaces and volumes that occur in realistic, complex geometries. Optimization will be automated by run-time building of objective functions based on measures of existing mesh quality. We will explore direct minimization vs. indirect methods to determine relative performance and identify fast methods. Finally, we will investigate schemes that iterate between nodal-connectivity and mesh optimization.

FY98 Progress/accomplishments:

The "Winslow" elliptic smoother was extended to unstructured quadrilateral meshes. Winslow became CUBIT's default smoother. The mathematical method devised to extend Winslow is general and can be applied to other PDEs used in structured mesh generation.

The Jacobian-based mesh optimizer substantially improved WW mesh quality. This optimizer will be extended this summer to include weight and boundary correction terms, working towards guaranteed positive Jacobians.

FY99 Goals

Devise a 3D optimizer that produces a unique mesh with guaranteed positive Jacobians given any hex, tet, or mixed-element mesh with arbitrary connectivity.

Other goals: (i) extend Winslow to 3D and compare to Tipton smoother, (ii) perform mathematical analyses comparing continuum variational to discrete mesh optimization methods, (iii) investigate FV and FEM approaches to solving PDEs for unstructured meshes, and (iv) integrate optimization methods with WW and other mesh-generation algorithms.

FY00-FY01 Goals

Investigate optimization methods to control mesh skew and mesh quality on region boundaries. Study large-scale optimization on assemblies of volumes with fixed surfaces.

Leveraging

We will target improving the quality of WW, T-HEX, HexTet plastering, and Tet meshes. These highly unstructured meshes provide strong challenges to mesh optimization methods and will spur major improvements. Fast solvers and advanced optimization techniques will be added to CUBIT for ASCI-scale meshing. Integrating optimization with mesh generation will leverage WW research in Part II, and also T-HEX, Tet meshing, and Plastering. Additional leveraging will be gained via our collaboration on mesh optimization techniques with Lori Feitag, Argonne National Laboratory.

MICS-Funded meshing papers:

1. P. Knupp, "Hexahedral Mesh Untangling & Algebraic Mesh Quality Metrics," p173-183, Proceedings of the 9th Intl. Meshing Roundtable, New Orleans, 2000.
2. P. Knupp, "Achieving Finite Element Mesh Quality via Optimization of the Jacobian Matrix Norm and Associated Quantities. Part II - A Framework for Volume Mesh Optimization and the condition number of the Jacobian matrix," Int'l. J. Numer. Meth. Engr., Vol 48, pp1165-1185, July 2000.
3. P. Knupp, "Matrix Norms and the Condition Number: A general framework to improve mesh quality via node-movement," 8th International Meshing RoundTable, Lake Tahoe, pp13-22, 1999.
4. L. Freitag and P. Knupp, "Tetrahedral Element Shape Optimization via the Jacobian Determinant and Condition Number," 8th International Meshing RoundTable, Lake Tahoe, pp247-258, 1999.
5. P. Knupp, "Winslow Smoothing on Two-Dimensional Unstructured Meshes," Engineering with Computers, {\bf 15}, pp263-268, 1999.
6. P. Knupp, "Achieving Finite Element Mesh Quality via Optimization of the Jacobian Matrix Norm and Associated Quantities. Part I - A Framework for Surface Mesh Optimization," Int'l. J. Numer. Meth. Engr., Vol 48, Issue 3, pp401-420, May 30, 2000.
7. P.Knupp, "Algebraic Mesh Quality Metrics," SAND2000 1033-J, Sandia National Laboratories, 2000, submitted for publication.
8. P.Knupp, "Untangling Non-Simplicial Meshes," in progress.

Mesh Optimized Using one of our MICS research methods:

SAND No. 98-2049
Return to the Sandia Home Page.