Quadrilateral Generation

Firstly the initial front consisting of edges constituting the boundary of the surface (including inner loops) is established. Once the initial front has been set up the mesh generation continues on the basis of the edge removal algorithm according to the following 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 the left side of it when viewing against the outer normal of
the surface (Fig. 5). 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, are calculated as (Fig. 5)
(6)

where the ideal edge

- is perpendicular to active edge if
,
(7)

- halves the angle if
(8)

- coincides with the neighbour edge if
(9)

and the ideal edge

- is perpendicular to active edge if
,
(10)

- halves the angle if
(11)

- coincides with the neighbour edge if
(12)

- is perpendicular to active edge if
,
- The first triangle is created from the active edge using
the steps 3 - 9 of the triangular kernel (Section 4.1). Assuming that the active
edge forms angle with the ideal edge and angle
with the ideal edge , the tentative triangle is
formed by the ideal point , if
, otherwise
the ideal
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. 6). 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
- 9 of the triangular kernel. The tentative triangle is formed by
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 is too long with respect to the local mesh size, 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, and registered into the octree.

*Daniel Rypl
2005-12-03*