Keywords: 3D surface, quadrilateral mesh, advancing front, topological cleanup, one-level refinement.

Most of the research on the development of fully automatic unstructured mesh generators has been concentrated on various triangulation schemes. Their advantage lies in the fact that simplicial elements (triangles and tetrahedrons) are most suitable to discretize domains of arbitrary complexity, particularly when locally graded meshes are needed. Currently, the dominating activity is focused on the development of methods for generation of quadrilateral and hexahedral meshes. This effort is driven, first of all, by the fact that quadrilateral and hexahedral elements are much more popular in the engineering analysis community because of their favourable features from the computational point of view.

This paper deals with discretization of 3D surfaces into all-quadrilateral meshes. The focus is laid on using an existing triangular mesh generator based on the Advancing Front Technique subjected to some minor modifications instead of developing a complex strategy for a new quadrilateral mesh generator. The actual discretization is split into three phases. In the first phase, a mixed mesh is created using the augmented triangular mesh generator. This initial mesh could generally contain a large percentage of triangular elements. In the second phase, the initial mesh is subjected to optimization in terms of Laplacian smoothing and topological cleanup. After the second phase, only very low percentage of the triangular elements is present in the mesh. In the third phase, the remaining triangles are eliminated by a one-level refinement applied to the optimized initial mesh. The final mesh is then once more optimized using the Laplacian smoothing. The proposed strategy is capable to produce uniform and graded all-quadrilateral meshes of high quality. The performance of the adopted approach is demonstrated on several examples.

The adopted mesh generation strategy belongs to the family of direct techniques in terms of working directly on the 3D surface. The triangular kernel, used to generate triangular meshes, is based on a widely known advancing front algorithm with some modifications allowing for surface curvature and special front management. The basic idea of producing a quadrilateral is based on generating consecutively two adjacent triangles that will be merged to form a valid quadrilateral element. This implies the following modifications to the standard triangular kernel: (i) ideal point creation, (ii) front processing, and (iii) convexity check. Since it is not guaranteed that the boundary of the surface (domain) is discretized into an even number of edges, an isolated triangle may remain in the mesh. Moreover, in the present algorithm, the formation of a quadrilateral is relaxed whenever it is too difficult or impossible to generate immediately the second triangle that could be merged with the first one into a valid quadrilateral. The resulting mesh is therefore of mixed nature containing potentially a large percentage of triangular elements.

The mesh is then subjected to several cycles of smoothing and topological cleanup. While the smoothing improves the shape and consequently the quality of individual elements, the cleanup removes the triangular elements from the mesh whenever possible and optimizes the mesh connectivity, resulting again in the improvement of the mesh quality. In each cycle, the smoothing is followed by the cleanup. However in the last cycle, only smoothing is performed followed by the convexity check. Typically, only a few cycles (around 6) are sufficient to obtain a reasonably optimized mesh. Since the standard Laplacian smoothing behaves not fully satisfactorily for mixed meshes, a weighted Laplacian smoothing is adopted. The weights are determined using a "do not harm" concept, the idea of which is to not move the node shared by elements of ideal shape. The topological cleanup consists of several sets of topological operations that are performed in an appropriate order. The following sets of operations have been implemented: (i) merge operations, (ii) swap operations, (iii) refine operations, (iv) coarse operations, (v) split operations, and (vi) transform operations. While the merge and transform operations attempt to remove as many triangles as possible, the swap, refine, and coarse operations try to optimize the valence of individual nodes by decreasing the difference between the actual and the "ideal" valence. A particular topological transformation is accomplished only if violation of selected geometrical criteria does not occur. Theoretically, all triangles could be removed, if the domain is bounded by an even number of edges. In practice, however, individual triangles are topologically so far from each other that the adopted transformation schemes are not capable to remove them.

The one-level refinement eliminates the remaining triangles by splitting each triangle, quadrilateral, and pentagon (optionally formed by a remaining triangle and a neighbouring quadrilateral) to three, four, and five quadrilaterals, respectively. Since this procedure actually halves the size of all elements, it is important to generate the initial mixed mesh with doubled target element size. However, this might not be always possible, especially if the element size is controlled by the surface curvature. The final mesh is then optimized by the standard Laplacian smoothing.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £122 +P&P)