Next: Mesh Optimization Up: Generation of Quad-dominant Meshes Previous: Mixed Mesh Generation


Quadrilateral Generation

The AFT for the generation of quadrilateral elements is accomplished according to the following scheme. Initially, the front consisting of edges constituting the boundary of the surface (including inner loops, if any) is established. Once the initial front has been set up, the mesh generation continues on the basis of a triangle removal algorithm, according to the following 7 steps, until the front becomes empty:

  1. The first available edge in the front is made active. The edge is oriented from to and the quadrilateral is assumed to be generated on its left side when viewing against the outer normal of the surface (Fig. 61). The active edge forms angle with the neighbour edge and angle with the neighbour edge .

  2. The positions of the ``ideal'' points and forming the tentative quadrilateral (Fig. 61) are calculated as

    (122)


    where the ideal edge and the ideal edge

  3. The first triangle is created from the active edge using the steps 3 - 10 of the triangular kernel presented in Subsection Surface Triangulation of Section Direct Triangulation of 3D Surfaces. The tentative triangle is formed by the more appropriate from points and . Assuming that the active edge forms angle with the ideal edge and angle with the ideal edge , the tentative triangle is formed by point , if , otherwise point is used. This criterion generally increases the angle at the ideal point of the tentative triangle and therefore reduces the possibility that a different point will be selected (step 7 of the triangular kernel) disturbing the shape of the ideal quadrilateral.

  4. In this step, the possibility of the creation of the second triangle is investigated. The second triangle can be created only if at least one of the edges and completing the first triangle was not existing in the mesh. Edge can be used to create the adjacent triangle if and edge can be used to create the adjacent triangle if , where and are the angles that the active edge forms with edges and , respectively. If both edges and could be used to create the second triangle, edge is selected if , otherwise edge is used (Fig. 62). This criterion should improve the quality of the resulting quadrilateral. If the second triangle cannot be created, the first triangle is stored as a triangular element and control returns to step 1.

  5. The second triangle ( or ) is created from the edge selected in the previous step using the steps 3 - 10 of the triangular kernel (Subsection Surface Triangulation of Section Direct Triangulation of 3D Surfaces). The tentative triangle is formed by the ideal point if edge was selected, otherwise the ideal point is used.

  6. If the two adjacent triangles, created in steps 3 and 5, form a convex quadrilateral, they are merged into a quadrilateral element (by deleting the diagonal edge or ). Otherwise the second triangle ( or ) is stored as the next triangular element and control returns to step 1.

  7. If the top edge of the quadrilateral is a new edge and it is too long with respect to the locally prescribed mesh density, the quadrilateral is split into a quadrilateral element and a triangular element by inserting a new node on edge . Note that node must be projected to the surface (to comply with surface constraint), classified to the surface, and registered into the octree.



Next: Mesh Optimization Up: Generation of Quad-dominant Meshes Previous: Mixed Mesh Generation

Daniel Rypl
2005-12-07