Abstract. Creating a mesh is the first step in a wide range of applications, including scientific computing and computer graphics. An unstructured simplex mesh requires a choice of meshpoints (vertex nodes) and a triangulation. We want to offer a short and simple MATLAB code, described in more detail than usual, so the reader can experiment (and add to the code) knowing the underlying principles. We find the node locations by solving for equilibrium in a truss structure (using piecewise linear force-displacement relations) and we reset the topology by the Delaunay algorithm. The geometry is described implicitly by its distance function. In addition to being much shorter and simpler than other meshing techniques, our algorithm typically produces meshes of very high quality. We discuss ways to improve the robustness and the performance, but our aim here is simplicity. Readers can download (and edit) the codes from http://math.mit.edu/~persson/mesh. Key words. mesh generation, distance functions, Delaunay triangulation AMS subject classifications. 65M50, 65N50 1. Introduction. Mesh generators tend to be complex codes that are nearly inaccessible. They are often just used as "black boxes." The meshing software is difficult to integrate with other codes -so the user gives up control. We believe that the ability to understand and adapt a mesh generation code (as one might do with visualization, or a finite element or finite volume code, or geometry modeling in computer graphics) is too valuable an option to lose. Our goal is to develop a mesh generator that can be described in a few dozen lines of MATLAB. We could offer faster implementations, and refinements of the algorithm, but our chief hope is that users will take this code as a starting point for their own work. It is understood that the software cannot be fully state-of-the-art, but it can be simple and effective and public. An essential decision is how to represent the geometry (the shape of the region). Our code uses a signed distance function d(x, y), negative inside the region. We show in detail how to write the distance to the boundary for simple shapes, and how to combine those functions for more complex objects. We also show how to compute the distance to boundaries that are given implicitly by equations f (x, y) = 0, or by values of d(x, y) at a discrete set of meshpoints. For the actual mesh generation, our iterative technique is based on the physical analogy between a simplex mesh and a truss structure. Meshpoints are nodes of the truss. Assuming an appropriate force-displacement function for the bars in the truss at each iteration, we solve for equilibrium. The forces move the nodes, and (iteratively) the Delaunay triangulation algorithm adjusts the topology (it decides the edges). Those are the two essential steps. The resulting mesh is surprisingly well-shaped, and Fig. 5.1 The combination of distance function representation and node movements from forces turns out to be good. The distance function quickly determines if a node is
In the second stage of the algorithm, vertices of the mesh are dynamically moved to improve mesh quality, in part based on the ideas presented in the DistMesh algorithm REF .
A Simple Mesh Generator in MATLAB
SIAM Review
Mathematics Computer Science