Automatic mesh generation for multiply connected planar regions based on mesh grading propagation

Computer-Aided Design, Elsevier, Vol 28, Num 9, pp.671-681, 1996

MESHING
RESEARCH
CORNER

Weidong Min
Department of Computing Science, 615 General Services Building, University of Alberta, Edmonton, Alberta, Canada, T6G 2H1
Zesheng Tang
CAD Center, Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, People's Republic of China
Zhengming Zhang, Yu Zhou and Minzhi Wang
CAD Center, Institute of Nuclear Energy Technology, Tsinghua University, Beijing, 100084, People's Republic of China

Abstract
Automatic mesh generation is one of the most important parts in CIMS (Computer Integrated Manufacturing System). A method based on mesh grading propagation which automatically produces a triangular mesh in a multiply connected planar region is presented in this paper. Its core part is an algorithm for triangulating convex polygons. Making use of the shrinking polygons of a convex polygon and the mesh grading propagation rules, the algorithm automatically propagates boundary gradings into the interior of the region and generates meshes whose elements are close to the equilateral triangle in linear time, meanwhile sizes of elements between dense meshes and sparse meshes vary smoothly. The algorithm is incorporated with domain decomposition techniques to generate satisfactory quasi-uniform meshes for 2D arbitrary domains. Experiment results show that its running time is linear with both the number of nodes and the number of elements when generating meshes of different mesh densities for the same arbitrary domain.