- Note: see also the french version, presumably more subtle (due to my not so good english).
- Do not invent questions that are not posed (academic pbs),
- as a consequence, consider actual questions (industrial pbs),
- consider real-life cases by themselves and/or due to their size,
- no a priori dogmatic ideas,
- push the research up to software, validation, diffusion, …, and don’t be happy with just a publication (of course, this is a little bit longer and you don’t publish a paper every two weeks),
- be capable to say I dont know.
- 2009, 2010, 2011, … P2 meshes (planar or surface triangles and tets). A large topic with a shortage of available papers before turning to larger orders if needed.
- 2012, … Q2 and R2 meshes (planar quads (complete or Serendip) – hexa (complete or Serendip) – penta or prism (complete or Serendip) of degree 2. And also, construction of large tet meshes made up of a few billions of elements
Chronology and history of the researches since about 30 years at Inria as far as the meshing aspects are considered together with some remarks and comments. In some cases, it is somehow a little bit old but this allows us to understand what we are doing today in this area and why we consider or are capable to consider the cases we are currently looking at.
- 1980, … Automated mesh construction of a 3D complex domain is not currently available. Nevertheless, some Delaunay triangulation algorithms exist, but this is not suitable for non convex domains, apart in some specific cases . Delaunay, this is since 1934. Bowyer, Watson and Hermeline (Paris 6), this is 1980-1981.
- 1988, a very first automatic mesher in 3D (with F. Hecht and E. Saltel) including a “a la” Delaunay triangulation algorithm, a boundary recovery algorithm, a method to constructing the internal vertices, a constrained (also “a la” Delaunay) point insertion algorithm together with an optimisation algorithm (being Delaunay is not a guarantee of quality, as some seems to think). It is working (not so bad), it is robust, nevertheless it is a little bit slow, …
- 1990, you say it is robust, why? Apparently, this is due to a cavity correction algorithm when inserting the points. It was just needed to have this simple idea instead of visiting bad directions (such as specific arithmetic or other stupidities). Moreover, we know how to insert a point in a non Delaunay context, which will lead to funny applications (such as anisotropy).
- 1990, you say it is slow, why? Apparently, this is due to the optimisation step. If it is needed to optimize the mesh, this meansthat the points are bad located , despite Delaunay. Here this is the point location algorithm we have to revisit (1991 with F. Hecht and M.G. Vallet). Of course and in addition, the optimisation algorithm is combinatorial, but this can be overpassed, it is just needed to follow a more clever method (1993 with B. De l’Isle).
- Then, the triangulation method is seen as being slow. Go back to this point (with H. Borouchaki, 1995, 1997, 2003, …). The retained solutions are somehow in conflict with the currently admitted dogms , but, 2005, in some cases (cloud of points on a surface), one can complete as much as 1 million tets within a second, not so bad!
- a revisited Delaunay point insertion method allows us to insert points in a non Delaunay context. It was just enough to have this idea and, obvioulsy, we use this fact to constructing anisotropic triangulations (1991, F. Hecht and M.G. Vallet, and, after, H. Borouchaki, …). The notion of a metric emerges and anisotropic meshes (and non only triangulations or cases with just prescribed sizes) are here.
- 1991, a general purpose book, more or less funny few years after.
- 1998, a four-handed book about Delaunay (H. Borouchaki).
- 1999, a four-handed general purpose book (P.J. Frey).
- When you have in hand a reliable and fast mesher, it is used in cases which are more and more complex. In this way, we meet new questions and we face again older points.
- as an example, in 2003, with H. Borouchaki and E. Saltel, we returned to the boundary integrity problem. the original algorithm (1989, ..) makes use of edge and facet swaps and adds a few Steiner points if required. In an anisotropic context, this may fail. Then, we conceive anisotropic swaps that can be used even in the isotropic case and we designed a totally new approach. We introduce the intersection points of the current triangulation and the missing boundary edges, then we remove those points. Non removable points are pushed inside the domain (and are no longer on the boundary) and, therefore, are the true Steiner points. By the way, this proves the existence of a tetra mesh for any domain.
- 2003, … young people in the group do more and more complex computations in CFD and exhibit some cases not really well solved. Go back to metrics, field interpolation, internal point construction and insertion. Those bad guys are also quite demanding in terms of CPU requirements, then, go back to large size problems, background mesh management and look for more efficient data structures.
- 2003, a four-handed vulgarization book (P.J. Frey).
- 2004, … surface reconstruction from a cloud of points. A quite old topic already seen here or there in more or less specific cases. Up to me, this point is not well adressed. I look at this problem , and, …, it works reasonably (by the way, conception of a fast triangulation algorithm with a touch of Hilbert somewhere) but not always, I dropped but, in case of courage, I will return to this topic.
- 2008, a general purpose book again (with P.J. Frey).
- 2009, … computing with meshes of order greater than one is a recurrent demand (in terms of the geometry together with the solver side), I am currently on this subject for the simplicial meshes of degree 2 with, let me say, a series of surprising things.
- 2010, … computing with boundary layers (Navier-Stokes) requires to know how to complete those layers, we are currently starting a work on this subject.
- … october 2011, the story is still in progress, just wait a while, …