Quality meshing with weighted Delaunay refinement

ABSTRACT

Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra called slivers that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove silvers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including silvers. This success is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation. We show that an incremental weight pumping can be mixed seamlessly with vertex insertions in our weighted Delaunay refinement paradigm.

REFERENCES

• 1: Nina Amenta , Marshall Bern , David Eppstein, Optimal point placement for mesh smoothing, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.528-537, January 05-07, 1997, New Orleans, Louisiana, United States
• 2: M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry, 2nd Ed., World Scientific, 1995, 47-123.
• 3: Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
• 4: L. P. Chew. Guaranteed-quality triangular meshes. Report TR-98-983, Comput. Sci. Dept., Cornell Univ., Ithaca, New York, (1989).
• 5: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 6: L. Paul Chew, Guaranteed-quality Delaunay meshing in 3D (short version), Proceedings of the thirteenth annual symposium on Computational geometry, p.391-393, June 04-06, 1997, Nice, France [doi>10.1145/262839.263018]
• 7: Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Silver exudation, Journal of the ACM (JACM), v.47 n.5, p.883-904, Sept. 2000 [doi>10.1145/355483.355487]
• 8: T. K. Dey, C. Bajaj and K. Sugihara. On good triangulations in three dimensions. Internat. J. Comput. Geom.,2, (1992), 75-95.
• 9: Geometry and topology for mesh generation, Cambridge University Press, New York, NY, 2001
• 10: Herbert Edelsbrunner , Xiang-Yang Li , Gary Miller , Andreas Stathopoulos , Dafna Talmor , Shang-Hua Teng , Alper Üngör , Noel Walkington, Smoothing and cleaning up slivers, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.273-277, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335338]
• 11: H. Edelsbrunner and D. Guoy. An experimental study of sliver exudation. Proc. 10th Intl. Meshing Roundtable, (2001), 307-316.
• 12: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 13: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
• 14: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 15: Scott A. Mitchell , Stephen A. Vavasis, Quality Mesh Generation in Higher Dimensions, SIAM Journal on Computing, v.29 n.4, p.1334-1370, Feb. 2000 to March 2000 [doi>10.1137/S0097539796314124]
• 16: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 17: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 18: G. Strang and G. J. Fix. An Analysis of the Finite Element Method. Prentice Hall, 1973.