Guaranteed-Quality Mesh Generation

Paul Chew

My work on mesh generation has been motivated by the finite element method, a widely used technique to obtain approximate solutions to partial differential equations. The first step of this method is to divide the given problem region into simply-shaped elements creating a mesh. A number of algorithms have been developed to automate this process, but most of these algorithms do not provide a guarantee about the quality of the resulting mesh (for instance, an element may cross a region boundary or there may be some flat triangles leading to poor error bounds). I have developed efficient techniques for producing meshes of guaranteed quality for problems in the plane and for curved surfaces: the elements produced are all triangles that are close to equilateral in shape, all region boundaries are respected, and the user can control the element density, producing small elements in ``interesting'' regions and large elements elsewhere. I am working to extend this technique to full three-dimensional problems, producing tetrahedral meshes.

Example 2D Mesh.

Example Surface Mesh.

The Mesher in Action. A postscript animation of the mesher at work. The colors represent grades for the various triangles: red implies bad shape, yellow implies too large, blue implies boundary is too long, and green implies all right.

An Interactive Meshing Demo. Mesh a polygonal shape of your own choosing. The input for this is currently very slow; the whole demo is still being modified.

Some References

L. Paul Chew, ``Guaranteed-Quality Mesh Generation for Curved Surfaces,'' Proceedings of the Ninth Symposium on Computational Geometry (1993), ACM Press, 274-280.

L. Paul Chew, Guaranteed-Quality Triangular Meshes, Department of Computer Science Tech Report 89-983, Cornell University (1989).