   Next: Mesh Optimization Up: Mixed Mesh Generation Previous: Triangular Kernel

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:

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 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 .

2. The positions of the ideal'' points and forming the tentative quadrilateral, are calculated as (Fig. 5) (7)

where the ideal edge • is perpendicular to active edge if , (8)

• halves the angle if  (9)

• coincides with the neighbour edge if  (10)

and the ideal edge • is perpendicular to active edge if , (11)

• halves the angle if  (12)

• coincides with the neighbour edge if  (13)

3. 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.

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. 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.

5. 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.

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 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.   Next: Mesh Optimization Up: Mixed Mesh Generation Previous: Triangular Kernel

Daniel Rypl
2005-12-03