Control Volume Meshes using Sphere Packing: Generation, Refinement and Co arsening

G. L. Miller, D. Talmor, S. H. Teng, N. Walkington
5th International Meshing Roundtable, Pittsburgh PA, October 1996.

144k compressed postscript

Abstract: In this paper we present a sphere-packing technique for Delaunay-based mesh generation, refinement and coarsening. We have previously established [MTTW95] that a bounded radius of ratio of circumscribed sphere to smallest tetrahedra edge is sufficient to get optimal rates of convergence for approximate solutions of Poisson's equation constructed using control volume (CVM) techniques. This translates to Delaunay meshes whose dual, the Voronoi cells diagram, is well-shaped. These meshes are easier to generate in 3D than finite element meshes, as they allow for an element called a sliver . We first support our previous results by providing experimental evidence of the robustness of the CVM over a mesh with slivers. We then outline a simple and efficient sphere packing technique to generate a 3D boundary conforming Delaunay-based mesh. We also apply our sphere-packing technique to the problem of automatic mesh coarsening. As an added benefit, we obtain a simple 2D mesh coarsening algorithm that is optimal for finite element meshes as well.