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:

- 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 .
- The positions of the ``ideal'' points and forming
the tentative quadrilateral (Fig. 61) are calculated as
(122)

where the ideal edge- is perpendicular to the active edge if
,
(123)

- halves angle if
(124)

- coincides with the neighbour edge if
(125)

- is perpendicular to the active edge if
,
(126)

- halves angle if
(127)

- coincides with the neighbour edge if
(128)

- is perpendicular to the active edge if
,
- 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. - 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.
- 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. - 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.
- 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.

*Daniel Rypl
2005-12-07*