A Survey of Unstructured Mesh Generation Technology
Steve Owen
Department of Civil and
Environmental Engineering
and
Ansys Inc.
sjowen@sandia.gov
Abstract
A brief survey of some of the fundamental algorithms in unstructured mesh generation is presented. Included is a discussion and categorization of triangle, tetrahedral, quadrilateral and hexahedral mesh generation methods currently in use in academia and industry. Also included is a brief discussion of smoothing, cleanup and refinement algorithms. An informal survey of currently available mesh generation software is also provided comparing some of their main features.1. Introduction
Automatic unstructured mesh generation is a relatively new field. Within its short life span we have seen tremendous advances in many diverse fields. Once in a while, it is useful to step back from our own expertise and look at the entire picture of what is going on in the field. The purpose of this survey is to give some perspective to what the current trends are in mesh generation and outline some of the major technology areas, who is working in these fields and what software is available.Probably the simplest approach is to first break down the technology based on the shape of element generated. We will consider triangle and quad generation methods in 2D and tetrahedral and hexahedral methods in 3D. Straddled between 2D and 3D, we have surface meshing, which has it's own set of issues. In addition we have another set of issues dealing with post processing of the mesh including smoothing, cleanup and refinement. Within each of these issues, have emerged a few clear categories of algorithms, which tend to dominate much of the literature and software. Not included in this survey are a wide variety of equally important related topics such as adaptive, anisotropic and parallel mesh generation as well as data structure and geometry management issues. Because of the immense scope of the field of unstructured mesh generation, I have limited this survey to include what I consider the more fundamental aspects of the field. Since I do not purport to be an expert in all fields of mesh generation, this will be at best, a cursory look at the main issues in each category.
1.1 Software Survey
As part of this paper, I conducted an informal survey of software vendors, research labs and educational institutions that develop mesh and grid generation software. The purpose was to get a broad picture of who was currently involved in developing software and what common algorithms were employed. The results of the survey are included as an appendix to this paper. They are also posted on the World Wide Web [1]. From the over 100 surveys mailed, approximately 80 responded. While the emphasis of the survey was unstructured, many unstructured codes are also included.The survey is certainly not a complete list of all those developing software, but it does illustrate the wide range of mesh generation technology currently available. Included are simple research codes used by only a few people, to commercial codes integrated within complex analysis packages.
1.2 Structured vs. Unstructured
This survey paper focuses on unstructured meshing technology. There is a large group of literature[2] [3] and software[4] that deals with structured meshing commonly referred to as "grid generation". Strictly speaking, a structured mesh can be recognized by all interior nodes of the mesh having an equal number of adjacent elements. For our purposes, the mesh generated by a structured grid generator is typically all quad or hexahedral. Algorithms employed generally involve complex iterative smoothing techniques that attempt to align elements with boundaries or physical domains. Where non-trivial boundaries are required, "block-structured" techniques can be employed which allow the user to break the domain up into topological blocks. Structured grid generators are most commonly used within the CFD field, where strict alignment of elements can be required by the analysis code or necessary to capture physical phenomenon.Unstructured mesh generation, on the other hand, relaxes the node valence requirement, allowing any number of elements to meet at a single node. Triangle and Tetrahedral meshes are most commonly thought of when referring to unstructured meshing, although quadrilateral and hexahedral meshes can also be unstructured. While there is certainly some overlap between structured and unstructured mesh generation technologies, the main feature which distinguish the two fields are the unique iterative smoothing algorithms employed by structured grid generators.
Continue
to Tri/Tet methods.
