Quality local refinement of tetrahedral meshes based on 8-subtetrahedron subdivision

Liu, Anwei; Joe, Barry

doi:10.1090/S0025-5718-96-00748-X

Quality local refinement of tetrahedral meshes based on 8-subtetrahedron subdivision
HTML articles powered by AMS MathViewer

by Anwei Liu and Barry Joe PDF

Math. Comp. 65 (1996), 1183-1200 Request permission

Abstract:

Let $\mathcal {T}$ be a tetrahedral mesh. We present a 3-D local refinement algorithm for $\mathcal {T}$ which is mainly based on an 8-subtetrahedron subdivision procedure, and discuss the quality of refined meshes generated by the algorithm. It is proved that any tetrahedron $\mathbf {T} \in \mathcal {T}$ produces a finite number of classes of similar tetrahedra, independent of the number of refinement levels. Furthermore, $\eta (\mathbf {T}_i^{n}) \geq c \eta (\mathbf {T})$, where $\mathbf {T} \in \mathcal {T}$, $c$ is a positive constant independent of $\mathcal {T}$ and the number of refinement levels, $\mathbf {T}_i^{n}$ is any refined tetrahedron of $\mathbf {T}$, and $\eta$ is a tetrahedron shape measure. It is also proved that local refinements on tetrahedra can be smoothly extended to their neighbors to maintain a conforming mesh. Experimental results show that the ratio of the number of tetrahedra actually refined to the number of tetrahedra chosen for refinement is bounded above by a small constant.

References

R. E. Bank (1990), PLTMG: A Software Package for Solving Elliptic Partial Differential Equations: Users’ Guide 6.0, SIAM, Philadelphia.
R. E. Bank and A. H. Sherman, An adaptive, multilevel method for elliptic boundary value problems, Computing 26 (1981), no. 2, 91–105 (English, with German summary). MR 619932, DOI 10.1007/BF02241777
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Barry Joe, Three-dimensional triangulations from local transformations, SIAM J. Sci. Statist. Comput. 10 (1989), no. 4, 718–741. MR 1000742, DOI 10.1137/0910044
B. Joe (1991), Delaunay versus max-min solid angle triangulations for three-dimensional mesh generation, Intern. J. Num. Meth. Eng., 31, pp. 987-997.
B. Joe (1994), Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions, Intern. J. Num. Meth. Eng., 37, pp. 693-713.
B. Joe (1995), Construction of three-dimensional improved-quality triangulations using local transformations, SIAM J. Sci. Comput., 16, 1292–1307.
Baker Kearfott, A proof of convergence and an error bound for the method of bisection in $\textbf {R}^{n}$, Math. Comp. 32 (1978), no. 144, 1147–1153. MR 494897, DOI 10.1090/S0025-5718-1978-0494897-3
A. Liu (1994), Quality local refinement of tetrahedral meshes, Ph.D. Thesis, Department of Computing Science, University of Alberta.
Anwei Liu and Barry Joe, On the shape of tetrahedra from bisection, Math. Comp. 63 (1994), no. 207, 141–154. MR 1240660, DOI 10.1090/S0025-5718-1994-1240660-4
A. Liu and B. Joe (1994), Relationship between tetrahedron shape measures, BIT, 34, pp. 268-287.
A. Liu and B. Joe (1995), Quality local refinement of tetrahedral meshes based on bisection, SIAM J. Sci. Comput., 16, 1269–1291.
R. Löhner, K. Morgan, and O. C. Zienkiewicz (1986), Adaptive grid refinement for the compressible Euler equations, in I. Babuška et al., Accuracy Estimates and Adaptive Refinements in Finite Element Computations, Wiley, New York.
W. F. Mitchell (1989), A comparison of adaptive refinement techniques for elliptic problems, ACM Trans. on Mathematical Software, 15, pp. 326-347.
D. Moore and J. Warren (1990), Adaptive mesh generation I: packing space, Technical Report, Department of Computer Science, Rice University.
T. W. Nehl and D. A. Field (1991), Adaptive refinement of first order tetrahedral meshes for magnetostatics using local Delaunay subdivisions, IEEE Trans. on Magnetics, 27, pp. 4193-4196.
M.-Cecilia Rivara, Algorithms for refining triangular grids suitable for adaptive and multigrid techniques, Internat. J. Numer. Methods Engrg. 20 (1984), no. 4, 745–756. MR 739618, DOI 10.1002/nme.1620200412
M.-C. Rivara (1987), A grid generator based on 4-triangles conforming mesh-refinement algorithms, Intern. J. Num. Meth. Eng., 24, pp. 1343-1354.
María-Cecilia Rivara, Selective refinement/derefinement algorithms for sequences of nested triangulations, Internat. J. Numer. Methods Engrg. 28 (1989), no. 12, 2889–2906. MR 1030410, DOI 10.1002/nme.1620281212
M.-C. Rivara and C. Levin (1992), A 3-D refinement algorithm suitable for adaptive and multi-grid techniques, Comm. Appl. Num. Meth., 8, pp. 281-290.
S. Zhang (1988), Multi-level iterative techniques, Ph.D. Thesis, Department of Mathematics, Pennsylvania State University.