Tetrahedral mesh generation using Delaunay refinement with non-standard quality measures.

*(English)*Zbl 1242.65257Summary: This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non-standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between \(18^{circ}\) and \(154^{\deg }\). Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between \(14^{\deg }\) and \(154^{\deg }\) can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius-to-shortest-edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above \(20^{\deg }\), regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth.

##### MSC:

65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |

65M50 | Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs |

##### Keywords:

Delaunay refinement; mesh generation; mesh quality; piecewise smooth boundaries; mesh improvement##### Software:

ANSLib
PDF
BibTeX
Cite

\textit{S. Gosselin} and \textit{C. Ollivier-Gooch}, Int. J. Numer. Methods Eng. 87, No. 8, 795--820 (2011; Zbl 1242.65257)

Full Text:
DOI

##### References:

[1] | Křížek, On the maximum angle condition for linear tetrahedral elements, SIAM Journal on Numerical Analysis 29 (2) pp 513– (1992) · Zbl 0755.41003 |

[2] | Shewchuk JR What is a good linear element? Interpolation, conditioning, anisotropy, and quality measures 115 126 |

[3] | Shewchuk JR Constrained Delaunay tetrahedralizations and provably good boundary recovery 193 204 |

[4] | Fried, Condition of finite element matrices generated from nonuniform meshes, AIAA Journal 10 pp 219– (1972) · Zbl 0242.65046 |

[5] | Babuška, On the angle condition in the finite element method, SIAM Journal on Numerical Analysis 13 (2) pp 214– (1976) · Zbl 0324.65046 |

[6] | Freitag, A cost/benefit analysis of simplicial mesh improvement techniques as measured by solution efficiency, International Journal of Computational Geometry and Applications 10 (4) pp 361– (2000) · Zbl 1074.68639 |

[7] | Mitchell, Proceedings of the Eight Annual Symposium on Computational Geometry pp 212– (1992) |

[8] | Mitchell, Quality mesh generation in higher dimensions, SIAM Journal on Computing 29 (4) pp 1334– (2000) · Zbl 0958.65126 |

[9] | Molino N Bridson R Teran J Fedkiw R A crystalline red green strategy for meshing highly deformable objects with tetrahedra 103 114 |

[10] | Labelle, Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Transactions on Graphics 26 (3) pp 57.1– (2007) · Zbl 05457725 |

[11] | Shewchuk JR Delaunay refinement mesh generation 1997 |

[12] | Chew, Proceedings of the Thirteenth Annual Symposium on Computational Geometry pp 391– (1997) |

[13] | Cheng, Sliver exudation, Journal of the ACM 47 pp 883– (2000) · Zbl 1320.68210 |

[14] | Cheng SW Dey TK Quality meshing with weighted Delaunay refinement 137 146 |

[15] | Cheng, Quality meshing for polyhedra with small angles, International Journal on Computational Geometry and Applications 15 pp 421– (2005) · Zbl 1104.68115 |

[16] | Oudot S Rineau L Yvinec M Meshing volumes bounded by smooth surfaces 2005 · Zbl 1134.65327 |

[17] | Cheng SW Dey TK Levine JA A practical Delaunay meshing algorithm for a large class of domains 477 494 |

[18] | Edelsbrunner, An experimental study of sliver exudation, Engineering with Computers 18 pp 229– (2002) · Zbl 01993869 |

[19] | Labelle F Sliver removal by lattice refinement 347 356 |

[20] | Si H On refinement of constrained Delaunay tetrahedralizations 509 528 |

[21] | Freitag, Tetrahedral mesh improvement using swapping and smoothing, International Journal for Numerical Methods in Engineering 40 (21) pp 3979– (1997) · Zbl 0897.65075 |

[22] | Olliver-Gooch, Guaranteed-quality simplicial mesh generation with cell size and grading control, Engineering with Computers 17 (3) pp 269– (2001) · Zbl 0983.68563 |

[23] | Alliez, Variational tetrahedral meshing, ACM Transactions on Graphics 24 (3) pp 617– (2005) · Zbl 05457178 |

[24] | Klingner BM Shewchuk JR Aggressive tetrahedral mesh improvement 3 23 |

[25] | Miller GL Talmor D Teng SH Walkington N Control volume meshes using sphere packing: generation, refinement and coarsening 47 61 |

[26] | Tautges TJ The common geometry module (CGM) 2004 |

[27] | Ruppert J A new and simple algorithm for quality 2-dimensional mesh generation 83 92 · Zbl 0801.68163 |

[28] | Ollivier-Gooch C http://tetra.mech.ubc.ca/GRUMMP/ |

[29] | Owen SJ White DR Tautges TJ Facet-based surfaces for 3D mesh generation 297 311 |

[30] | Bowyer, Computing Dirichlet tessellations, Computer Journal 24 (2) pp 162– (1981) |

[31] | Baker, Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation, Engineering with Computers 5 pp 161– (1989) |

[32] | Bern M Chew LP Eppstein D Ruppert J Dihedral bounds for mesh generation in high dimensions 189 196 · Zbl 0849.68116 |

[33] | Bern, Computing in Euclidean Geometry pp 23– (1992) |

[34] | Joe, On the shape of tetrahedra from bisection, Mathematics of Computation 63 pp 141– (1994) · Zbl 0815.51016 |

[35] | Field, Qualitative measures for initial meshes, International Journal for Numerical Methods in Engineering 47 pp 887– (2000) · Zbl 0944.65125 |

[36] | Li XY Teng SH Generating well-shaped Delaunay meshes in 3D 28 37 · Zbl 0988.65014 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.