Biting: Advancing Front Meets Sphere Packing

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Department of Computer Science, University of Illinois at Urbana- Champaign, Urbana, IL 61801
[xli2 | steng | ungor] @cs.uiuc.edu

Abstract
A key step in the finite element method is to generate a high quality mesh that is as small as possible for an input domain. Several meshing methods and heuristics have been developed and implemented. Methods based on advancing front, Delaunay triangulations, and quadtrees/octrees are among the most popular ones. Advancing front uses simple data structures and is efficient. Unfortunately, in general, it does not provide any guarantee on the size and quality of the mesh it produces. On the other hand, the sphere-packing based Delaunay methods generate a well-shaped mesh whose size is within a constant factor of the optimal. In this paper, we present a new meshing algorithm, the biting method, which combines the strengths of advancing front and sphere packing.

In this paper, we show that the advancing front method can be used to efficiently construct a quality sphere-packing. At a high level, this new advancing front based packing algorithm first finds a sphere packing of the boundary of the domain and then grows the packing towards the interior of the domain. Each time when a new sphere is added to the interior, a larger protection sphere is removed (bitten away) from the domain so that no future sphere will overlap with this one. By doing this, it builds the sphere packing by adding spheres one at a time, or a layer at a time, in the same spirit as the standard advancing method; our new method uses advancing front to construct a sphere packing instead of the mesh elements themselves. We show that this advancing front based method does generate a well-spaced point set, whose Delaunay triangulation is well-shaped. We will refer this new method as the biting method and show that it can be made as practical as the standard advancing front meshing methods. Biting sphere at a point x is B(x, c*h(x)), where c is a constant less than 1. At this point, we should note that biting spheres are different from the packing spheres due to technical reasons that will be discussed in full paper.

Usually advancing front is represented as a circular list of already placed points. In our method, it is represented as a set of arcs and boundary segments. We always choose the next Steiner point on the front itself. In other words, the front itself is a subset of the feasible region for the selection of new mesh vertices, making it easier to choose the next point. This makes the placement step easier. The intersection of two arcs or an arc and a boundary segment provides a good candidate for a new Steiner point, whose biting sphere will reduce the interior. Isn't this the way we take a bite on a biscuit or an apple? We center our bite more or less around a sharpest nose. Then bite after bite, we eat away the boundary of the food and move to its interior.

The basic idea of the biting method is to first compute the control spacing function of the mesh. We then try to find a point set by constructing a sphere packing with respect to the spacing function. For making sure that the biting process results in a sphere packing, we use the following simple idea: at every step, we choose a center on the advancing front and remove its biting sphere. The removal of its biting sphere ensures that the future packing spheres will not intersect with the packing sphere of this center. The Delaunay triangulation is then used to generate the mesh from the resulting sphere packing. Noting that, for protecting the boundary of the input domain, we use the vertex protection and edge protection to ensure that the boundary element is well-shaped. For more detail, please see the full paper.

We show that biting method generates a well-shaped mesh. Moreover, the size of this mesh is within a constant factor of the optimal. For the first claim we prove that the points placed by the biting method is well-spaced. In other words, there exists a b-sphere-packing (based on this point set) with respect to a 1-Lipschitz spacing function f. Second claim follows from the maximality of the spacing function and a volume argument.

Although biting method uses the advancing front technique to bite the spheres from the domain, it is not necessary to always bite from the boundary of the remaining domain. A biting strategy that picks a sphere centered at any point in the remaining domain still results a sphere-packing and hence a well-shaped mesh. However the biting method proposed in this paper is an easy way to place the biting spheres and, to our intuition, practically promises better-shaped meshes. The effectiveness of our method will be supplemented by the experimental results.

References

[1] M.Bern, S.Mitchell and J.Ruppert, Linear-size non-obtuse triangulation of polygons. Proc. of 10th Symp. on Computational Geometry, New York, 221-230, 1994.

[2] T.D.Blacker, Paving: a new approach to automated quadrilateral mesh generation. Int. Jour. for Numerical Methods in Eng., 32:811-847, 1991.

[3] X.-Y.Li, S.-H.Teng and A.Ungor, Simultaneous refinement and coarsening:adaptive meshing with moving boundaries, Proc. 7th Int. Meshing Roundtable, Dearborn, Mich., 201-210, 1998.