Mesh Validity

The verification of the validity of a mesh is an important issue in terms of the reliability of a mesh generator. A detailed description of the definition of a geometric triangulation representing a valid finite element mesh is provided in [80]. In the context of the presented work, the mesh validity is considered only in terms of the topological compatibility and geometrical similarity (similarly as defined in [80]).

The mesh is topologically compatible with the model entity of dimension ( ) if each mesh entity classified to or to the model entity fixed to is shared exactly by two mesh entities classified to and if each mesh entity classified to the model entity forming times boundary of the model entity is used exactly by mesh entities classified to . A mesh is topologically compatible if it is compatible with all model entities. Examples of topologically compatible and incompatible meshes of a model curve and model surface are depicted in Figures 2.27 and 2.28, respectively. Mesh entities that are used too many times are termed topologically redundant, whereas those that are used too few times form topological holes.

A topologically compatible mesh is geometrically similar to a model entity ( ) if for any two different mesh entities and () classified to holds

A parametric intersection, denoted by symbol , is employed in Eq. (2.101) because of the fact that mesh entities (classified to a curve or surface) intersecting each other in the parametric space do not necessarily intersect each other in the real space (see Fig. 2.21). The concept of geometrical similarity is demonstrated by an example of a curve mesh in Figure 2.29. Note that there is no relationship between the geometrical similarity and geometrical accuracy in the above concept.

The hierarchical approach adopted for the mesh generation proved to be very beneficial because it enables a reliable classification of mesh entities to model entities during the actual discretization. Therefore the verification of the topological compatibility and geometrical similarity can be accomplished during the discretization and/or immediately after its completion.

In the case of a curve, the geometrical similarity is simply ensured by the specific discretization technique (Section Curve Discretization (Sequential Mesh Generation)) which eliminates intersection of edges in the parametric space of the curve under the assumption that the separately discretized parts of the curve do not overlap. The topological compatibility inside the individual parts is guaranteed through the use of the binary tree structure which exhibits compatibility features that are similar to the desired topological compatibility. To avoid an occurrence of topological redundancies and holes it is necessary to prevent the separately discretized parts of a curve to overlap and to be detached. Thus the overall topological compatibility and geometrical similarity of a curve mesh consists only in the verification of the topological compatibility at nodes corresponding to vertices fixed to the curve (but not bounding the curve) which have to be shared exactly by two edges classified to the curve.

When discretizing a surface, the topological compatibility is controlled by introducing a front flag. Initially, the flag of each node and edge on the front is set to (an on-front mesh entity). During the discretization the flag of an edge is set to (switch to an off-front mesh entity) if no more triangles classified to the surface can be connected to this edge, with respect to the topological compatibility requirements. Similarly, the flag of a node is set to unless it is shared at least by one on-front edge or unless it is not shared by any triangle classified to the surface. Note that only the on-front mesh entities are considered for eventual switching to off-front. The verification of the topological compatibility then consists simply in accepting only on-front mesh entities when forming new triangles and in the check that there are no remaining on-front mesh entities in the completed surface mesh. The geometrical similarity is ensured by the intersection check accomplished either in the parametric or in the real space (contradictory to Eq. (2.101)). In the latter case, however, the intersection check is implemented in such a way that it is equivalent (from the qualitative point of view) to the check in the parametric space. Exactly the same approach is employed in the case of a patch or shell discretization.

The front flag is also introduced during the discretization of regions, which enables an efficient verification of the topological compatibility. A similar approach to the one used in the surface discretization is employed. Initially, the flag of each node, edge, and triangle on the front is set to . The flag of an on-front triangle is then set to if no more tetrahedrons classified to the region can be connected to this triangle, with respect to the topological compatibility requirements. Similarly, an on-front node or an on-front edge is switched to off-front unless the node or edge is shared at least by one on-front triangle or unless the node or edge is not shared by any tetrahedron classified to the region. The topological compatibility is then again ensured by using only on-front mesh entities when forming new tetrahedrons and by verification that there are no remaining on-front mesh entities in the completed region mesh. The geometrical similarity is guaranteed by the reliable intersection check (in the real space) during the region discretization.

Note that the above described implementation of the topological compatibility check is more general than its definition at the beginning of this section because it takes into account mesh entities of dimension ( ) classified to model entity fixed to but not shared by any model entity fixed to (e.g. a node at an isolated vertex fixed to a surface).

*Daniel Rypl
2005-12-07*