QUALITY MESHING OF POLYHEDRA WITH SMALL ANGLES

Abstract

We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio of most output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Furthermore, the mesh is not unnecessarily dense in the sense that the edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. This algorithm is simple to implement as it eliminates most of the computation of local feature sizes and explicit protective zones. Our experimental results validate that few skinny tetrahedra remain and they lie close to small acute input angles.