Next: Region Discretization Up: Mesh Generation Previous: Curve Discretization

Surface Discretization

In the presented implementation of surface discretization, the mesh generation is constrained directly to the surface. The parametric space of the surface is not explicitly used for the mesh generation but it is used to resolved some local checks. A widely known advancing front algorithm with some modifications (allowing for surface curvature) is employed. Firstly, the initial front consisting of edges constituting the boundary of the surface (including possible 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 triangle is assumed to be generated on the left side of it when viewing against the outer normal of the surface (Fig. 2).

  2. The position of ``ideal'' point (Fig. 2), forming the new triangle, is calculated as

    where

    The stands for the position vector, means the surface outer normal and denotes the element size (as extracted from the octree). Subscript refers to a particular point in 3D.

  3. The projection of point to the surface is accomplished using the normal , gradients and and parametric coordinates and of any nearby point (typically an already existing node). The projection is performed in an iterative manner. The point is firstly projected to the tangential plane given by the normal . The increments of parameters and , calculated using the surface gradients at point , are then used to get better approximation of point . Consequently surface normal and gradients are calculated at this point and the whole process is repeated until the desired accuracy in the approximation of point is achieved (Fig. 2). Note that only one iteration is used for projection on planar well parameterized surface.

  4. The new position of ``ideal'' point is evaluated (Fig. 3) taking into account local surface curvature (this point is now referred as )

    where

    The is reflecting the local mesh size variation (Fig. 4) and is given as

  5. Projection of point to the surface and the corresponding mesh size are calculated.

  6. The local neighbourhood of point in terms of a set of octants is established.

  7. The neighbourhood is searched for the most suitable candidate to form a new triangle . Two auxiliary geometrical loci are constructed around point to resolve the acceptance of tentative node . Firstly, a sphere with center in and radius of . And secondly an ellipsoid derived from sphere by extension of its half-axis parallel to the active edge by a half (Fig. 5). The selection of point is driven by the following rules. Point is

    1. identical with point if there is no point inside the sphere , no point inside the ellipsoid directly connected with the active edge and there is no point inside the sphere circumscribed to the triangle .
    2. an already existing node inside the sphere circumscribed to the triangle forming the largest angle if there is no point inside the sphere and no point inside the ellipsoid directly connected with the active edge .
    3. taken as node if it falls inside the sphere and there is no other node inside the sphere circumscribed to the triangle .
    4. an already existing node inside the sphere circumscribed to the triangle forming the largest angle . Point is an already existing node inside the sphere (case depicted in Fig. 5).
    5. taken as node if the already existing edge or forms sufficiently small angle with the active edge and no point is inside the sphere circumscribed to the triangle .
    6. an already existing node inside the sphere circumscribed to the triangle forming the largest angle , where point is the end point of already existing edge or being at sufficiently small angle to the active edge .
    7. taken as node if it falls inside the ellipsoid and there is no other node inside the sphere circumscribed to the triangle . Point is the end point of already existing edge or .
    8. an already existing node inside the sphere circumscribed to the triangle forming the largest angle , where node falls inside the ellipsoid and is directly connected with the active edge .
    In cases (ii), (iv), (vi) and (viii), the validity of point must be always verified. Similarly point has to be verified in cases (iii) and (iv). It may happen that although the point is satisfying all the criteria in terms of metric of the real space it is still very far from point in the parametric space. In other words, the distance between points and measured on the surface may be much larger than the distance in . However, having access to the parametric space of the surface the verification can be easily performed. Acceptance of node in cases (vii) and (viii) improves mesh quality in the mesh size transition zones and eliminates creation of chunks of edges when front closes up. To speed up the neighbourhood searching only the half-space given by point and vector is considered.

  8. The intersection check is carried out to avoid overlapping of the created triangle with existing edges and triangles in the neighbourhood. Using the parametric space the intersection check can be performed quite efficiently. Caution should be taken when relatively long edges on poorly parameterized surface are considered. In this case the mapping of the whole edge, not only its nodes, should be taken into account. If the edge or is the already existing one the check can be entirely omitted. This will reduce the number of intersection investigations to about a half. In the case an intersection is detected, the selected point is rejected and the search of the neighbourhood is repeated without taking this point into account.

  9. The front is updated to account for newly formed triangle . The node , if chosen according to the rule (i), is registered into the octree.

Although large effort is devoted to the creation of well shaped elements already in the phase of advancing front procedure some badly shaped triangles are comprised in the grid. Therefore, the Laplacian smoothing technique, optionally extended by weighting based on required element size, node connectivity or both, is used to optimize the shape of elements. Contradictory to the smoothing carried out in 2D, the repositioning of a node (to the weighted average of the positions of nodes connected to it) is likely to shift the node out of the surface. Therefore, the projection (the same one as used for ideal point to surface projection) is employed to satisfy the surface constraint. The optimized grid is usually obtained after only a few cycles of smoothing (typically up to five).



Next: Region Discretization Up: Mesh Generation Previous: Curve Discretization

Daniel Rypl
2005-12-03