Introduction

Triangulations and, more precisely, meshes, with the subtle difference that separates these two entities, lie at the heart of any number of problems that arise from varied scientific disciplines. A triangulation or a mesh is a discrete representation, using simple geometric elements (triangle, quadrilateral, tetrahedron, etc., any arbitrary polygon or polyhedron), of a domain that may be an object or a region of which we want a discrete, spatial description. There are, thus, many applications, including numerical simulations of any kind of physical problem, though not restricted to these. In particular, a discrete representation of a (volume) object or a surface may simply be seen as a geometric modeling problem as is. This book adopts a double point of view, as indicated by its title, and we will look both at the use of meshes in numerical simulations (the finite element method, especially) with, of course, the underlying constraints, as well as the use of these meshes for the (discrete) modeling of geometry.

The literature on triangulations and meshes may be classified in two chief categories: one more purely mathematical and geometric, the other more oriented toward industrial applications (numerical simulations) with, of course, though not always, relations between these categories.

The first point of view is covered by the computation geometry community, which studies (among others) Delaunay triangulations in all cuts, definitions, properties, construction algorithms and the complexity of these algorithms. They also study some applications of these triangulations. Nonetheless, relatively recently, mesh generation problems are also being studied, but under a more theoretical angle, generally relating to situations that allow for the use of Delaunay triangulations for which robust construction methods as well as interesting geometric properties have been known for a long time. This (somewhat monotheistic) philosophy necessarily imposes limits on the nature of the problems worked (workable). The first reference book on these subjects is that of Preparata and Shamos [Preparata, Shamos-1985] published in 1985. This was followed by several others, among which we cite two by Edelsbrunner [Edelsbrunner-1987] and [Edelsbrunner-2001], that of Yvinnec and Boissonnat [Boissonnat, Yvinec-1997], by Dey [Dey-2007] and winding up the list with the book by Cheng et al. [Cheng et al. 2012], which was published in 2012. With a few exceptions, the orientation chosen by these references is not always guided by the preoccupations of mathematicians, engineers and the world of numerical simulation in general.

It is this very need for numerical simulations, in particular (and historically) in solid or fluid mechanics, that has led to the emergence of a "meshing" community among mathematicians and engineers. Without fear of contradiction, we can state that the very first book on meshes that was seen from this point of view is that of Thompson et al. [Thompson et al. 1985], which was also published in 1985. This book essentially discusses structured meshes or grids1 while the first truly generalist book, discussing all types of meshes, structured or not, is that by George [George-1991], which dates back to 1991. Over the years and with the evolution of computers and methods as well as the increasingly complex nature of the meshes to consider, other books have been published. Let us mention books by George and Borouchaki [George, Borouchaki-1998], published in 1997, which revisits meshing methods based on Delaunay algorithms; by Carey [Carey-1997], also in 1997, which gives a very pedagogic presentation of methods; by Topping and co-authors [Topping et al. 2004], in 2004, cited in order to be exhaustive; by Frey and George [Frey, George-2008], in 2000, with a second edition in 2008, which returns to the general view and incorporates newly appeared techniques; by Löhner [Löhner-2008], in 2002, with a second edition that came out in 2008, which abounds in innovative details; up to the recent book by Lo [Lo-2015], published in 2015, which, among others, sheds new light on some problems. In this context, we may wonder what motivated the writing of this book. We will attempt to answer this question (and also try, by doing so, to arouse the reader's curiosity).

The first observation is that the few books on this subject are already either a little old or rather classic in the way they discuss the approaches and the methods concerning the many questions linked to meshes. The second remark is that, evidently, new questions have appeared relatively recently, e.g. everything related to (finite) elements or patches of higher degrees, metrics and their links to interpolation errors, geometric modeling by meshes, numerical simulation via advanced methods (adaptation of meshes) and so on. This remark immediately calls forth another: we will resolutely adopt a double point of view by considering finite elements (or the constitutive elements of a mesh) as geometric patches and vice versa, thus establishing a link between the Lagrange world of finite elements and the Bézier world of CAD. This choice, as we will see, noticeably changes the manner in which we perceive the problems and, consequently, the manner in which we try to find solutions. In this spirit, this book in two volumes, beyond a set of subjects that we may qualify as classic (and, thus, essential), approaches many subjects that are very recent or even completely novel. Moreover, and this may be more surprising (and certainly rare), some methods (which we find in the literature) have been deliberately left out as they were deemed to not be of great interest and, a contrario, some methods are described in a manner that is, at the very least, nuanced and even critical. Indeed, it seemed pertinent to share our perception, even though this is subjective, up to a point, of these methods, perhaps to prevent the reader from going down paths that we think are dead ends. Having specified this, this book provides the necessary basis for a course on meshes and related problems at the masters level and it may serve as a technical reference for engineering students in science and, more generally, engineers using numerical simulations. We will give a brief description of the content of the chapters in both volumes.

? Volume 1:

We first give a chapter-wise overview of the first volume of this book. In the first three chapters, this volume introduces the basic concepts related to finite elements seen through their shape functions either as finite elements or as patches. In addition to the classic expression via Lagrange polynomials (complete, reduced or rational) (Chapter 1), we give the equivalent formulation based on Bézier forms (Chapter 2), which makes it possible to easily find the conditions for the geometric validity of these finite elements (or patches) whether they are straight or curved and whatever their degree (Chapter 3). Triangulation problems are the subject of the next three chapters, where we specify vocabulary and the basic concepts that make it possible to describe the different construction methods for any triangulation (Chapter 4), Delaunay triangulation (Chapter 5) as well as the triangulation (of a domain) with constraints (Chapter 6). In the next two chapters, we use the concepts introduced earlier to discuss the vast problem of geometric modeling of a domain in its various aspects. Geometric modeling, from our point of views (meshes and numerical simulations), consists of construction of a discrete representation from a continuous representation and vice versa. Different methods are described in Chapters 7, while Chapter 8 gives several significant examples for the application of these methods. Chapter 9 brings together some basic algorithms and formulas related to finite elements (patches) and triangulations, to persuade the reader to go beyond a theoretical viewpoint, to a practical viewpoint, which we believe is essential.

? Volume 2:

We share the contents of Volume 2 of this book, for which four new authors have joined us. This volume (finally) approaches mesh problems and begins with a detailed description of the concept of metric, a concept which will be seen to be fundamental in all that follows. The first two chapters, Chapters 1 and 2, thus focus on metrics. We introduce the concept of metric, we demonstrate their properties and their relations with the geometry of elements of a mesh and how to control interpolation errors during the resolution of a problem (by finite elements). The construction methods of meshes and their optimization are the focus of the following five chapters: Chapter 3 (mesh for a curve), Chapter 4 (simplicial meshes), Chapter 5 (non-simplicial meshes), Chapter 6 (meshes of higher degree) and Chapter 7 (optimizing meshes). We will then discuss the large subject of the adaptation of meshes, controlling the solutions via error estimates and corresponding interpolation metrics in Chapter 8. The use of a dose or a certain dose of parallelism (based on its multiple forms) is seen through Chapter 9. Chapter 10 illustrates, using concrete examples, a series of applications of the methods and methodologies introduced and described through the different chapters of both volumes of this book. As in Volume 1, the final chapter, Chapter 11, gives practical observations on some of the algorithms from Volume 2, especially how to use and manipulate metrics.

? Finally, at the end of this second volume, we sketch out future...