Computational Complexity

As the number of the generated mesh entities increases, the time required for the mesh generation grows as well. From this point of view, it is desirable to prevent the computational time to grow faster than the number of mesh entities, which would make the mesh generator useless in most practical cases. In order to achieve a favourable computational complexity, the adopted algorithms should be investigated and the sources of the computational complexity identified. In the case of the advancing front procedure, the spatial localization, intersection checking, mesh size control, and front management (in terms of the active edge or triangle selection and searching) are considered to be general aspects influencing the overall performance. All the above sources of the computational complexity correspond to distinct algorithmic steps which have to be repeated for each element to be generated and it is therefore desirable to reduce the computational complexity of these steps to a constant one in order to obtain a linear overall computational complexity (with being the number of generated elements) which is an ideal one for mesh generation algorithms.

All the crucial aspects are addressed in the present approach. The spatial localization and mesh size control are implemented using the octree data structure. The management of the octree data structure generally exhibits the computational complexity which becomes nearly constant for a reasonable octree depth. This is due to the fact that only a negligible percentage of the total generation time is consumed by the vertical octree traversal which represents the logarithmic contribution in the octree computational complexity. In the conventional advancing front technique, the front is implemented as a priority queue where the smallest edge or triangle is always used to generate a new element. While this strategy avoids creation of too large elements, preventing possible loss of the desired mesh gradation, it typically results, on the other hand, in the overall computational complexity, which is generally unacceptable. In the present approach, the gradual size variation is ensured by the use of the octree data structure subjected to the one-level difference rule. Therefore, no special algorithm for the active edge or triangle selection strategy is required and the simplest approach, that uses always the first available edge or triangle in the front, was chosen. Moreover, since there is no need for a special data structure representing the front, the same data structure (namely a generalized linked list) used to store the individual mesh entities of the actual model discretization is simultaneously used as the front. This eliminates the searching for a particular mesh entity in the front because the algorithm always operates with the original of a given mesh entity. Each mesh entity (except tetrahedrons) is only provided with a flag specifying whether the entity is on the front or not. Thus the front is implemented as a consistent non-priority queue which obviously leads to the constant computational complexity of the front management. The number of mesh entities involved in the forming of a new element and in the consequent intersection check is driven by the size of the neighbourhood and by the shape of the front in that neighbourhood. Since the neighbourhood is specified in terms of octants, the size of which is directly related to the desired mesh size, the number of mesh entities which can be comprised in the neighbourhood is roughly the same. On the other hand, the shape of the front inside the neighbourhood can vary during the mesh generation resulting in a different number of on-front mesh entities considered during the element creation. Since the front is implemented as the consistent non-priority queue, the front is propagating from the domain boundary inside the domain quite regularly. Therefore, the shape of the front with respect to the neighbourhood remains approximately the same (in the idealized interpretation a line or plane separating the empty space from the already generated mesh) during almost the whole process of the mesh generation. The only exception takes place when the front closes up, in which case the number of mesh entities to be considered for the new element creation and intersection check may be significantly higher. However, the total percentage of the occurrence of this case is quickly decreasing with the increasing density of the mesh and therefore this effect can be neglected. Thus the intersection check also exhibits the constant computational complexity in average. The remaining procedures are similar to the conventional advancing front method and the overall computational complexity therefore approaches , which makes the proposed methodology very competitive in practical applications.

*Daniel Rypl
2005-12-07*