carrier image

Weighted Delaunay Refinement for Polyhedra with Small Angles

Cheng, S.-W., T. K. Dey, and T. Ray

Proceedings, 14th International Meshing Roundtable, Springer-Verlag, pp.325-342, September 11-14 2005


14th International Meshing Roundtable
San Diego, CA, USA
September 11-14, 2005

S.-W. Cheng,
Hong-Kong U. of Science and Technology, Hong Kong.

T. K. Dey and T. Ray
The Ohio State U., Columbus, OH, USA.

Recently, a provable Delaunay meshing algorithm called QMesh has been proposed for polyhedra that may have acute input angles. The algorithm guarantees bounded circumradius to shortest edge length ratio for all tetrahedra except the ones near small input angles. This guarantee eliminates or limits the occurrences of all types of poorly shaped tetrahedra except slivers. A separate technique called weight pumping is known for sliver elimination. But, allowable input for the technique so far have been periodic point sets and piecewise linear complex with non-acute input angles. In this paper, we incorporate the weight pumping method into QMesh thereby ensuring that all tetrahedra except the ones near small input angles have bounded aspect ratio. Theoretically, the algorithm has an abysmally small angle guarantee inherited from the weight pumping method. Nevertheless, our experiments show that it produces better angles in practice.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article