Guaranteed-Quality Mesh Generation
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).