Bubble Mesh ... Physically-based triangulation

Abstract A repeating hexagonal pattern is a common one, observed in soap bubbles floating in liquied, compound eyes of insects, and many other natural phenomena. For example, bubbles of real soap floating in liquid are closely packed and they form a virtually regular hexagonal pattern. By connecting the bubbles' center points, a mesh of basically equilateral triangles is produced. Bubble meshing is proposed by simulating such natural phenomena. Background High density meshes are required, for example, to obtain accurate results of FEM analysis and to enhance the quality of computer graphics. An easy method to obtain the accurate results is to subdivide uniformly the given entire domain into fine elements (See the left side of the above figure). However, it is obvious that the method causes the increase of the computation time. The generally employed method is to generate finner elements at the subdomain where higher accuracy is required. Such a mesh generated by a conventional method is shown in the right side of the above figure. The conventional method, however, generates ill-shaped elements at the boundaries between the subdomains of different element sizes. The basic requirements for a mesh generation are summarized as Element shape regularity, Element size control. The appearance of a capable mesh generator which can generate meshes satisfying the two basic requirements is desired. Principle Bubble meshing is summarized as a sequence of two steps: (1) packing circles or spheres, called bubbles, closely in a domain, and (2) connecting their centers by Delaunay triangulation, which selects the best topological connection for a set of nodes by avoiding small angles. The key element of bubble meshing lies in the first step, that is, the optimization of mesh node locations by close packing bubbles. A repulsive or attractive force much like an intermolecular van der Waals force is assumed to exist between two adjacent bubbles. A globally stable configuration of tightly packed bubbles is determined by solving the equation of motion. The above figure shows the initial configuration of packed bubbles and the triangular mesh obtained by connecting the center points of neighboring bubbles. The above figure shows the bubble configuration and the triangular mesh finally obtained by solving the equation of motion. This figure shows that irregularity of triangles is reduced. Click here to see the animation of converging bubble configurations. (The size of the image is 109KB.)

Bubble meshing generates a two-dimensional triangular mesh by the following two steps: Solving the equation of motion on vertices, edges, and faces in that order, Generation of a triangular mesh by connecting the center points of bubbles by Delaunay Triangulation. Similar steps are also applied to the generation of three-dimensional tetrahedral meshes. Implementation of bubble meshing Before solving the equation of motion, the initial bubble configurations must be determined. As shown in the above figure, to detemine the initial bubble configurations, a large bubble covering entire domain is subdivided into sub-bubbles by using a divide-and-conqure algorithm until the sizes of bubbles correspond to the value defineed by a node spacing function. A force function f(r) between two adjacent bubbles is shown in the above figure. If f(r) = r0, where r0 is defined to be the two bubbles are defined to be in a stable distance. The function f(r) satisfies If f(r) > 0, a repulsive force is assumed to exist between two bubbles, and if f(r) < 0, a attractive force is assumed to exist between them. The kinetic equation is written in where, By solving this kinetic equation by Runge-Kutta method, the optimized bubble configuration is obtained. In the process of the optimization, population of bubbles is adaptively controlled. That is, excess bubbles which significantly overlap their neighbors are removed, and new bubbles are added around open bubbles which lack the appropriate number of neighboring bubbles. After the optimization of the bubule configuration, a triangular mesh is generated by using Delaunay triangulation. To the top page of meshing project

Last modified 30 June 1998