Efficient generation of structured finite element meshes

The nonconforming voxel finite element method (NVFEM) greatly reduces the problem of geometric accuracy in traditional structured mesh generation by allowing deeper refinement of the elements that are cut by boundaries. The main cost of generating the NVFEM mesh lies in deciding whether an element is cut or not, which involves performing queries on the problem geometry.In this thesis, a generalized form of an efficient point location algorithm is used to perform the geometric queries in a time efficient way. The problem geometry is represented as a set of polygons and the assumption is made that the number of polygon edges might be very large for complex geometries. The algorithm uses a decomposition of the geometry into horizontal and vertical slabs to reduce the geometric query to binary searches. This makes it possible to accomplish the query, and the whole mesh generation, in a time that grows only logarithmically with the number of polygon edges.The meshing algorithm is implemented in MATLAB and tested on a variety of problems in 2D. Results obtained from timing the algorithm confirm that it has a logarithmic time complexity.La méthode des éléments finis de voxel non-conforme (NVFEM) permet d'éviter un grand nombre des difficultés du maillage traditionnel en permettant un raffinement plus profond des éléments qui sont coupés par des limites. Le coût principal de maillage traditionnel consiste en l'action de déterminer si l'on coupe un élément ou non, ce qui nécessite la mise en question du géométrie du problème. Dans la présente thèse, on se sert d'un algorithme de repérage efficace d'un point pour poser les questions géométriques en utilisant le temps de façon efficace. La géométrie du problème se présente sous forme d'un ensemble de polygones, et il est à présumer que dans le cas des géométries complexes le nombre de bords des polygones pourrait être considérable. L'algorithme se sert d'une décomposition de la géométrie en blocs horizontaux et verticaux pour réduire l'interrogation géométrique à des recherches binaires. Cela rend possible le fonctionnement de la mise en question et l'ensemble du maillage, dans un délai qui s'augmente de façon logarithmique plus il y a de bords de polygones. On applique l'algorithme de maillage à MATLAB et le met à l'essai dans une variété de problèmes dans 2D. Les résultats obtenus du chronométrage de l'algorithme confirment sa complexité de temps logarithmique