Mesh Generation Using Triangular Quadtrees

Abstract

In this work we present a methodology to generate triangular meshes for planar domains with curved boundary using triangular quadtrees. A triangular quadtree is similar to a conventional quadtree but uses equilateral triangles as cells instead of square cells. In a conventional approach the square cells of the quadtree are successively refined until an adequate resolution for the boundary is reached. Then vertexs of the tree are moved to match the boundary and the square cells are divided by its diagonal to form a mesh of triangles. The resulting triangles are mostly rectangular triangles. In the present approach there is no need to subdivide cells, since cells are triangles and the resulting triangles are almost equilateral and well shaped. Also the resulting mesh can be organized by levels, a desirable property for use of multilevel methods, and in each level the resulting meshes are structured, i.e. all vertexs are attached to the same number of adjacent elements.