Next: Computational Complexity Up: Mesh Generation Previous: Surface Discretization

Region Discretization

The discretization of regions is also based on advancing front technique. Faces bounding the region under consideration and created during surface discretization are collected to form the initial front. The mesh generation then continues on the basis of the face removal using similar steps as in the case of surface discretization until there are no remaining faces in the front:

  1. The first available face in the front is made active. The nodes , and are oriented in anticlockwise sense with respect to normal pointing inside (not yet discretized part of) the region (Fig. 6).

  2. The position of ``ideal'' point , forming the new tetrahedron, is calculated as

    where

    The position of points , and on the sides of active face and associated mesh size is calculated according to the following formulas (analogous to those used in surface discretization)

  3. The new position of ``ideal'' point is evaluated taking into account local mesh size gradation in the same way as in the case of surface discretization (this point is now referred as )

    where

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

  5. The neighbourhood is searched for the most suitable candidate to form a new tetrahedron . Again, 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 face by a half. The similar set of rules as in the case of surface discretization (Fig. 5) is used to select point . Point is

    1. identical with point if there is no point inside the sphere , no point inside the ellipsoid forming a face directly connected with the active face and there is no point inside the sphere circumscribed to the tetrahedron .
    2. an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron , no point inside the sphere and no point inside the ellipsoid forming a face directly connected with the active face .
    3. taken as node if it falls inside the sphere and there is no other node inside the sphere circumscribed to the tetrahedron .
    4. an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Point is an already existing node inside the sphere .
    5. taken as node if the already existing face , or forms sufficiently small angle with the active face and no point is inside the sphere circumscribed to the tetrahedron .
    6. an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Point is the point of already existing face , or being at sufficiently small angle to the active face .
    7. taken as node if it falls inside the ellipsoid and there is no other node inside the sphere circumscribed to the tetrahedron . Point is the point of already existing face , or .
    8. an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Node falls inside the ellipsoid and forms a face directly connected with the active face .
    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. When searching for the most suitable candidate in the neighbourhood, the local Delaunay property is used as a criterion. This reduces the probability of consequent occurrence of an intersection. To speed up the neighbourhood searching only the half-space given by point and vector is considered. If no point has been selected the following actions are taken to resolve the problem. Firstly, new ``ideal'' point is established using reduced element size and the search of the neighbourhood is repeated. Secondly, the existing tetrahedrons in the local neighbourhood are deleted, updating simultaneously the front, and the created cavity is remeshed.

  6. To avoid overlapping of the created tetrahedron with existing edges, faces and tetrahedrons in the neighbourhood the intersection check is performed. In this case, however, the intersection check is computationally much more demanding due to the following reasons. Firstly, it is done fully in 3D and secondly, considerably larger number of mesh entities must be considered as the neighbourhood becomes truly three dimensional. Also the number of cases in which the intersection check may be entirely omitted is significantly reduced. In the presented implementation, the new edges and faces of created tetrahedron are tested against intersection with edges and faces in neighbourhood. The intersection check is further limited only to those edges and faces from the neighbourhood which have at least one point in common with the sphere circumscribed to the new tetrahedron. This criterion effectively replaces the reduction of the number of mesh entities involved in the intersection check based on the investigation of their bounding box. 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.

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

Contradictory to 2D (or surface) triangulation 3D discretization suffers from higher percentage of poor quality elements. This is, first of all, typical for 3D Delaunay triangulation in which high quality triangles may form degenerated tetrahedral elements with volume close (or even equal) to zero. Unfortunately, these elements, called slivers, are likely to be created also in advancing front technique. Since the Delaunay property is used as the governing criterion for neighbourhood search in the presented approach the probability of sliver occurrence is even higher. Therefore some postprocessing has to be employed to improve the quality of the mesh. In this case, however, the smoothing process alone is not effective enough. The application of Laplacian smoothing technique improves the mesh in average but quality of sliver elements is usually spoiled even more. It is therefore essential to combine the smoothing with some topologically based technique. In the presented approach, two different topological transformations (Fig. 7) are employed. The actual transformation is accomplished only if its application improves the overall mesh quality. The postprocessing then consists of several cycles of Laplacian smoothing (optionally with weighting) alternating with topological transformation process. This technique proves to be effective and yields relatively high quality meshes in only a few cycles (typically about five).



Next: Computational Complexity Up: Mesh Generation Previous: Surface Discretization

Daniel Rypl
2005-12-03