Reproduced below with the permission of SIAM Review is the review of two mesh generation texts co-authored by Tim Tautges and myself. This article originally appeared in SIAM Review, 59(3), 681-699, ISSN (print) 0036-1445, ISSN (online) 1095-7200. The permalink to the issue’s Book Reviews is https://doi.org/10.1137/17N974409. Any typographical or formatting errors in the article below are the result of my translation of the article from PDF to text to blog.
Delaunay Mesh Generation. By S. W. Cheng, T. Dey, and J. Shewchuk. CRC
Press, Boca Raton, FL, 2013. $80. xvi+394 pp., hardcover. ISBN
978-1-58488-730-0.
Finite Element Mesh Generation. By Daniel S. H. Lo. CRC Press, Boca
Raton, FL, 2015. $137.00. 672 pp., hardcover. ISBN 978-0-41569-048-5.
Introduction. Mesh generation is the discretization of space corresponding to a “continuous” definition such as a CAD model or analytic surface-based definitions. The resulting mesh is a collection of elements of prescribed dimension and topology with shape characteristics beneficial to their intended end use such as computational simulations of fluid flow or stress and strain in a solid. Mesh generation has been described as both a science and an art. The science of mesh generation involves technical aspects in mathematics, computer science, and engineering; where provable methods are not available or are unsatisfactory, art can be involved in creating heuristic methods to accomplish a given task. Effective work in mesh generation also requires skills in software design and implementation.
Two recent books on mesh generation give complementary views of the subject. Delaunay Mesh Generation is a very deep exploration of provably good Delaunay meshing algorithms for simplicial (triangle/tetrahedral) meshes, while Finite Element Mesh Generation gives a broad overview of mesh generation and related algorithms for both simplicial and quadrilateral/hexahedral meshes. The two books take almost opposite approaches to their respective subjects (deep and narrow vs. shallow and wide), while also treating many common themes (measurable mesh quality, planar versus curved domains, etc.). Beyond the technical material itself, the books also use very different styles of exposition. Below we review them individually, then compare and contrast them on their treatment of various subjects.
Delaunay Mesh Generation (Cheng, Dey, and Shewchuk). This book (referred to in what follows as CDS) deals exclusively with the generation of simplicial meshes, with particular emphasis on methods whose robustness, resulting mesh quality, or other aspects can be proven. The book begins with an introduction to the basic goals of mesh generation, some prerequisite background (definitions, topology), and a short history of the field and of the authors’ contributions to it. The remaining chapters are organized informally into three parts: two-and three-dimensional Delaunay mesh generation of “piecewise linear complexes” (i.e., straight lines and planar surfaces) (Chapters 2-5); high-quality Delaunay mesh generation (Chapters 6-11); and mesh generation of nonplanar curves, surfaces, and volumes.
A mesh has the so-called Delaunay property if, for all triangles or tetrahedra, a circumcircle/sphere containing all vertices of the element contains no other vertices of the mesh. The first part of the book begins by describing various properties of Delaunay meshes and proving some of them. For example, it is proven that if no four points in a planar point set lie on a common circle, the Delaunay triangulation (DT) of the set is unique and maximizes the minimum angle. A good understanding of these properties is essential to understanding the proofs later in the book, which themselves are critical for constructing effective meshing algorithms. This part of the book goes on to describe the two constituent functions or predicates (each in two or three dimensions, for a total of four) of almost all Delaunay-like meshing algorithms: ORIENT (is a point on one side or the other of a line/plane?) and INCIRCLE (does a point lie inside, on, or outside the circle/sphere intersecting three/four other points?). These predicates, along with data structures for representing points and elements, form the core of all Delaunay mesh generators. For example, the well-known Bowyer-Watson algorithm for constructing DTs can be implemented in an afternoon given these predicates. In addition to the basic triangulation algorithm and properties, this part also discusses items of practical importance, for example, runtime considerations and techniques for treating and resolving a specified mesh boundary, resulting in constrained DTs. This order of treatment, starting with a provably-robust algorithm then describing methods for making it faster and extending it to treat closely related problems, is in our opinion exactly right, and it is practiced in most other areas of computational simulation. This sequence appears in numerous other places in this book. One other critical element of this part is a discussion of why Delaunay meshes are significant (because DTs minimize the linear interpolation error for vertex-defined fields, and because DT has maximum angular quality compared to all other triangulations of the same point set). This concern for the purpose of the mesh, in quantitative terms, is both an excellent example of what practitioners in the field need to remember, and, in our opinion, the thing many most quickly forget.
The first part of the book culminates with a description of Ruppert’s algorithm for three-dimensional DT, first published in 1992. This algorithm was significant because it was “the first provably good meshing algorithm that was also satisfying in practice.” That is, it was robust, fast, and generated meshes with favorable topological and geometric characteristics (element size and grading, etc.). This is a critical consideration in the book and for mesh generation as a whole: that good meshing algorithms succeed on all three of those axes. The authors use Ruppert’s algorithm to establish a generic refinement template algorithm that is used throughout the remainder of the book. This description also demonstrates the careful analysis of meshing algorithms for both robustness and runtime, an analysis approach used in later chapters of the book. In our opinion, the development of the methodology described here, by the authors of this book and others, has been responsible for a good part of the success of DT algorithms over the last three decades.
The second part of the book starts with a description of weighted Voronoi diagrams, leading to the concepts of orthoballs and power distances. These seemingly esoteric concepts are central to the development of (and proof of the effectiveness of) methods for eliminating sliver elements that are the bane of all three-dimensional DT algorithms. Appearing just after the very practical discussion of Ruppert’s algorithm, this discussion at first seems misplaced and possibly even superfluous. A quick roadmap of where the discussion will be headed in later chapters would have been very helpful here. A description of the sliver exudation algorithm and a proof of its effectiveness follow shortly thereafter. This algorithm is interesting in that it degrades (or, alternately, redefines) the Delaunay property of a mesh in order to achieve a minimum quality guarantee, while preserving size or grading characteristics of the mesh. Although in our view this algorithm is not well understood in the meshing community, we feel that this also provides an example of a common axiom encountered in many other areas of mesh generation: one carefully designed, provably robust algorithm is worth more than several different ad hoc heuristics attempting the same task. An added bonus is that, while the guaranteed quality is less than desired, in practice the algorithm performs much better than those (low) quality bounds would indicate; this is also typical of other quality and speed guarantees in this book.
The last part of this book describes meshing of curved geometry, characterized by a local feature size, often derived from a medial axis description of the geometry. In contrast to the rest of the book, we feel that this description is less than satisfying. For example, only geometric aspects of the medial axis are described, whereas we feel that topological aspects of the medial axis can also be sometimes relevant (though admittedly not for DT). This part goes on to prove aspects of Delaunay algorithms and meshes on curved geometry. The book’s discussion uses the concepts of the mesh dual (or Voronoi diagram) and its primal (the Delaunay mesh) simultaneously, which we found quite difficult to follow. We feel the discussion would have been clearer if it were given first in terms of the Delaunay mesh, to establish the algorithm itself, followed by the introduction of the dual to assert things about the geometric quality. Finally, similar to the introduction of the orthoball and power distance discussion in the second part of the book, this last part would have benefited greatly from an overview of where the discussion was headed, to provide insight into why the concept of the Voronoi diagram is important.
Except for the two areas that could have used better foreshadowing of where the discussion was headed, overall we were greatly impressed with this book. The concept of provability in meshing is somewhat rare, especially outside the area of simplicial mesh generation; however, this book amply demonstrates the benefits of provable algorithms and provides insight into how to go about developing such proofs. The book takes a very systematic approach, starting with the simplest problem (triangles on planar surfaces) to introduce the specification of algorithms and proofs of their effectiveness, then extending these methods and proofs to ever more complex problems (three dimensions, curved geometry). Although the concept of provable algorithms is central to the entire book, the authors also devote much discussion to practical aspects such as runtime and implementation considerations. Although the three parts of the book align roughly with the three authors’ areas of expertise, this is no rehash of prior publications; the material flows from one concept to the next, building on previous descriptions, and has no redundancy in concept descriptions. The whole book is cohesive, and it even has portions not already published as research elsewhere.
One of the most pleasurable aspects of the book for us, and we expect for other practitioners in the mesh generation field, was the “Notes and Exercises” section at the end of each chapter, which provided information of a historical nature or otherwise tangent to the central discussion in each chapter. These sections, along with a few sections of the introductory chapter, provide one of the best historical reviews of the development of simplicial meshing that we have seen.
Those already familiar with mesh generation, and with existing books on the subject, will be surprised by a few aspects of this book. First, there is virtually no discussion of point placement strategies, which is a critical first step of simplicial mesh generation. One could call that either a glaring omission or a wise choice to limit the scope to provable algorithms. We feel that its omission in no way degrades the discussion of provable algorithms in the book. There is all of one sentence on the subject of exact arithmetic in the discussion of the INCIRCLE predicate; this is odd, not only given coauthor Shewchuk’s well-known work in this area, but also because of how common a pitfall this can be in the implementation of such algorithms. Another issue, regarding the lack of figures, is discussed later in this review. Finally, there is relatively little discussion of open problems in mesh generation. This would be a welcome addition to the “Notes and Exercises” sections, given the decades of accumulated experience in the field represented by the authors.
Finite Element Mesh Generation (Lo). Lo’s Finite Element Mesh Generation presents material on a broader range of mesh generation methods than CDS, and practitioners, rather than researchers, seem to be the target audience with its emphasis on implementation over theory.
The book begins with a general overview of the challenges posed by mesh generation (Chapter 1) including the lack of formal rules for mesh generation problem definition and the unanswered question of a priori prediction of expected mesh quality given the boundary constraints. The advocated approach for implementation – similar to CDS’s – is one that develops first robustness, then quality, then speed. As the book then illustrates, 90% of an implementation can come from the mathematics, while the other 10% represents the implementer’s imagination, another reference to the science/art duality of meshing noted above.
Chapter 2 is devoted entirely to terminology and data structures, computational geometry algorithms, mesh topology utilities, sorting, and tree algorithms, all of which are intended as foundational material for the subsequent chapters. Yet there are odd omissions for a book about mesh generation, such as only a passing reference to barycentric coordinates without the corresponding methods for computing them. We believe the reader would be better served by references to geometric and topological material from other books, and the material on trees could be rewritten with more emphasis on search time, generation time, and memory usage.
The core of the book consists of chapters on planar meshing (Chapter 3), curved surface meshing (Chapter 4), and volume meshing (Chapter 5), similar to the general sequence in CDS. The predominant content of Chapter 3 is the generation of unstructured triangular meshes using the Delaunay and the advancing front techniques (AFT), with a subsequent section on how the two techniques can be combined. DT is covered in detail; like CDS, the necessity of finite precision arithmetic is mentioned but not explained, while unlike CDS point placement algorithms are covered. The AFT is covered, including point placement schemes that allow the mesh to be adapted to finite element solutions. Quadrilateral generation methods cover both structured and unstructured algorithms. The bulk of the description of unstructured quad generation is devoted to indirect methods for converting an all-triangle mesh into all-quad or quad-dominant meshes, with emphasis on techniques that maximize the geometric quality (e.g., distortion relative to a rectangle). It is surprising that more space is not given to a detailed description of the well-known Qmorph algorithm, given its widespread use in practice; the subject of guaranteed-all-quad indirect algorithms, all of which rely on Edmonds’ original “blossom” algorithm [1], is also conspicuously missing. Coverage of structured quad generation is also quite uneven, given that the described interpolation and sweeping methods are not widely used in practice, while the widely used PDE-based methods are omitted from the discussion entirely. Chapter 3 exemplifies the varying depth of coverage in this book; while the quadrilateral methods appear in a form similar to a literature review, material on DT is microorganized into six levels of subsections. Unfortunately, methods and publications from Lo are also overrepresented in this chapter, in our judgment out of proportion to their use in general practice.
Chapter 4 addresses curved surface meshing. DT is extended to curved surfaces, by replacing the circle predicate in planar space with an ellipse predicate in the parametric space (whose mapping to real space turns the ellipse into a circle). Similar discussion is included for the AFT. Anisotropic mesh generation is also addressed via the ellipse packing method, where ellipse parameters are derived from the anisotropic size field rather than the parametric space mapping. The chapter ends with a brief discussion of direct meshing methods that operate in three dimensions with explicit projection of points onto the surface and Boolean operations on existing meshes. We were perplexed by another example of unevenness of topic coverage when an algorithm for closest point projection was described despite there being no prior introduction to the mathematics of CAD surfaces.
Volume mesh generation with tetrahedra and hexahedra in Chapter 5 completes the three main chapters on mesh generation algorithms. For simplicial meshing, it is made clear that the extension of DT and the AFT to three dimensions is not trivial, both because of the need to match existing boundary mesh (“boundary recovery”) and because three-dimensional DT produces sliver cells. Therefore, extensive coverage is given of methods for boundary mesh recovery and point insertion. Similar to the chapter on planar meshes, volume methods are described for both the AFT and a hybrid AFT-DT method. The chapter ends with a brief survey of hexahedral meshing techniques from extrusion and revolution to medial surface, plastering, whisker weaving, and H-morph. We find this chapter dissatisfying for various reasons. Coverage is very uneven, with too much detail on data structures and trivial algorithms like flood fill; misplaced coverage of element quality measurement and improvement; and not enough treatment of other areas such as sweeping of surface meshes into three dimensions (the workhorse of all-hex meshing in practice). Unfortunately, the author chose to document in great detail the performance of their meshing algorithm and that of two commercially available meshing tools, including when the latter either performed poorly or crashed. Given the pace of development of all meshing tools, overly specific examples of both positive and negative performance aspects are much less useful than a set of well-chosen examples representative of a tool’s general performance. On the positive side, this chapter’s coverage of boundary recovery in triangular meshes was appropriately detailed and justified in terms of that algorithm’s importance in practice.
The book closes with chapters dedicated to various types of mesh processing including mesh quality optimization (Chapter 6), parallel mesh generation (Chapter 7), and miscellaneous mesh processing techniques (Chapter 8). The information in Chapter 6 is very valuable in practice as methods for measuring and improving mesh quality have seen much recent research and development. Beginning with the attributes of a good shape measure (invariant under affine transformation, ranges from 0 for a degenerate element to 1 for a regular element), the author describes specific shape measures, all of which build on the definitive work of Knupp [2] while also acknowledging that true quality is what makes the mesh “apt for numerical computations.” A small but important omission is any discussion of element-to-element variation of shape measures and the influence of the boundary on these measures.
Chapter 7’s discussion of parallel meshing algorithm implementations focuses primarily on DT, since the AFT is deemed much more difficult to parallelize efficiently due the high degree of locality in the method’s computations. With the focus on DT, two options for parallelization are presented: partitioning of the overall domain into subsets for distribution across compute nodes and parallelization of the highly localized node insertion and retriangulation operations. Parallelization is at the leading edge of mesh generation, and good performance remains an open issue. This chapter would have been better spent on a more general discussion of different sources of and options for concurrency in mesh generation, rather than detailed anecdotal descriptions of specific approaches.
Chapter 8 closes the book with brief discussions of auxiliary techniques, beginning with surface verification and preparation. Given the challenges cited in the book for recovering the boundary mesh when applying DT, surface mesh preparation is an extremely important preprocessing step. A large portion of the chapter presents methods for two- and three-dimensional insertion of nonuniform points, which we found to be excessive given the methods’ relatively infrequent use in practice. Edge refinement and two long sections on merging tetrahedral and hexahedral meshes follow. We would have much preferred that space be used to expand the discussions of high order (i.e., nonlinear) meshes on curved geometry and mesh adaption, two important and actively researched topics in mesh generation not otherwise treated in this book.
Summary. The significance of mesh generation in computational sciences, computer graphics and animation, and related disciplines cannot be overstated. NASA’s CFD Vision 2030 Study [3] cites mesh generation as one of the top challenges that needs to be overcome if computational fluid dynamics is to meet NASA’s goals by the year 2030, and other studies have come to similar conclusions for other areas of application. Therefore, texts that provide strong back-ground and insight into the discipline are timely and valuable.
The two books reviewed take different approaches to the presentation of this important material. CDS provides a deep and narrow focus on Delaunay techniques, including provability of the algorithm’s properties, balancing the discussion between provability and practicality. Theirs is an integrated discussion of the authors’ and others’ work that flows from chapter to chapter, with a consistent level of detail and little if any redundancy. In contrast, Lo presents a much broader range of methodologies for a broader range of mesh types, with the depth of coverage varying considerably (and inconsistently) depending on the subject. Rather more discussion is given of the author’s previous work, out of proportion to its impact in practice. While this is to be expected to some extent from anybody brave enough to write a technical book, readers would be better served with a more balanced treatment of the general field of mesh generation.
Both texts exhibit a flaw in their use of mesh images that is likely more due to the limits of publication rather than intent. Few of the images of meshes in either text are of sufficient quality to support claims made about them (e.g., improved element quality, algorithm robustness). Attempts to illustrate an algorithm’s applicability to mesh complex or “real world” geometry suffer from the limited display space, making the figures unsuitable for this purpose. This relatively poor use of images highlights another weakness common to both texts: the lack of quantified comparisons and contrasts of different methods applied to the same problems. Common benchmarks would be useful for providing an “apples to apples” comparison of the various methods described.
REFERENCES
[1] J. Edmunds, Paths, trees, and flowers, Canad. J. Math., 17 (1965), pp. 449-467.
[2] P. M. Knupp, Algebraic mesh quality metrics, SIAM J. Sci. Comput.,
23 (2001), pp 193-218, https://doi.org/10.1137/ S1064827500371499.
[3] J. Slotnick et al., CFD Vision 2030 Study: A Path to Computational
Aerosciences, Tech. Report, NASA CR-2014-218178, NASA, Hampton, VA, 2014.
TIMOTHY J. TAUTGES
Siemens, Inc.
JOHN R. CHAWNER
Pointwise, Inc.
Challenges in mesh generation were aptly described in the NASA CFD Vision 2030 Study. A quote from the study’s executive summary is “Mesh generation and adaptivity continue to be significant bottlenecks in the CFD workflow, and very little government investment has been targeted in these areas.” This article discusses topics important to the mesh generation community that are relevant to addressing the goals of the NASA study from the perspective of a developer of commercial meshing software. (more)
