Francois Labelle

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-104

August 17, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-104.pdf

Three-dimensional meshes are frequently used to perform physical simulations in science and engineering. This involves decomposing a domain into a mesh of small elements, usually tetrahedra or hexahedra. The elements must be of good quality; in particular there should be no plane or dihedral angle close to 0 or 180 degrees. Automatically creating such meshes for complicated domains is a challenging problem, especially guaranteeing good dihedral angles, a goal that has eluded researchers for nearly two decades. By using point lattices, notably the body centered cubic lattice, we develop two tetrahedral mesh generation algorithms that, for the first time, come with meaningful guarantees on the quality of the elements.

For domains bounded by an isosurface, we generate a tetrahedral mesh whose dihedral angles are bounded between 10.7 and 164.8 degrees, or (with a change in parameters) between 8.9 and 158.8 degrees. The algorithm is numerically robust and easy to implement because it generates tetrahedra from a small set of precomputed stencils. The algorithm is so fast that it can be invoked at each time step of a simulation, possibly in real time for small meshes. The tetrahedra are uniformly sized on the boundary, but in the interior it is possible to make them progressively larger. This combination of features makes the algorithm well suited for dynamic fluid simulation. If the isosurface is a smooth 2-manifold with bounded curvature, and the tetrahedra are sufficiently small, then the boundary of the mesh is guaranteed to be a geometrically and topologically accurate approximation of the isosurface.

For polyhedral domains, Delaunay refinement is a common mesh generation technique that produces guaranteed-quality tetrahedra with one exception: sliver-shaped tetrahedra that can have dihedral angles arbitrarily close to 0 and 180 degrees. We show how slivers away from the boundary can be avoided by inserting lattice points while maintaining the Delaunay property of the mesh. It is possible to control the size of tetrahedra, this time both in the interior and on the boundary, and a user may input a set of points which must be vertices of the output mesh. The resulting dihedral angles are guaranteed to be between 30 and 135 degrees, except near the boundary.

Most angle bounds are obtained by recursive bisection of the space of possible tetrahedron configurations together with interval arithmetic. They are guaranteed by computer-assisted proofs.

Advisors: Jonathan Shewchuk

---

BibTeX citation:

@phdthesis{Labelle:EECS-2007-104,
    Author= {Labelle, Francois},
    Title= {Tetrahedral Mesh Generation with Good Dihedral Angles Using Point Lattices},
    School= {EECS Department, University of California, Berkeley},
    Year= {2007},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-104.html},
    Number= {UCB/EECS-2007-104},
    Abstract= {Three-dimensional meshes are frequently used to perform physical simulations in science and engineering. This involves decomposing a domain into a mesh of small elements, usually tetrahedra or hexahedra. The elements must be of good quality; in particular there should be no plane or dihedral angle close to 0 or 180 degrees. Automatically creating such meshes for complicated domains is a challenging problem, especially guaranteeing good dihedral angles, a goal that has eluded researchers for nearly two decades. By using point lattices, notably the body centered cubic lattice, we develop two tetrahedral mesh generation algorithms that, for the first time, come with meaningful guarantees on the quality of the elements.

For domains bounded by an isosurface, we generate a tetrahedral mesh whose dihedral angles are bounded between 10.7 and 164.8 degrees, or (with a change in parameters) between 8.9 and 158.8 degrees. The algorithm is numerically robust and easy to implement because it generates tetrahedra from a small set of precomputed stencils. The algorithm is so fast that it can be invoked at each time step of a simulation, possibly in real time for small meshes. The tetrahedra are uniformly sized on the boundary, but in the interior it is possible to make them progressively larger. This combination of features makes the algorithm well suited for dynamic fluid simulation. If the isosurface is a smooth 2-manifold with bounded curvature, and the tetrahedra are sufficiently small, then the boundary of the mesh is guaranteed to be a geometrically and topologically accurate approximation of the isosurface.

For polyhedral domains, Delaunay refinement is a common mesh generation technique that produces guaranteed-quality tetrahedra with one exception: sliver-shaped tetrahedra that can have dihedral angles arbitrarily close to 0 and 180 degrees. We show how slivers away from the boundary can be avoided by inserting lattice points while maintaining the Delaunay property of the mesh. It is possible to control the size of tetrahedra, this time both in the interior and on the boundary, and a user may input a set of points which must be vertices of the output mesh. The resulting dihedral angles are guaranteed to be between 30 and 135 degrees, except near the boundary.

Most angle bounds are obtained by recursive bisection of the space of possible tetrahedron configurations together with interval arithmetic. They are guaranteed by computer-assisted proofs.},
}

EndNote citation:

%0 Thesis
%A Labelle, Francois 
%T Tetrahedral Mesh Generation with Good Dihedral Angles Using Point Lattices
%I EECS Department, University of California, Berkeley
%D 2007
%8 August 17
%@ UCB/EECS-2007-104
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-104.html
%F Labelle:EECS-2007-104