Efektywne algorytmy automatycznej dyskretyzacji nietrywialnych trójwymiarowych form geometrycznych oraz ich obiektowa implementacja

Abstract

The task of the mesh generator is partitioning of the given geometric domain into a finite number of simple elements, conforming to requirements specified by user (e.g. type of elements, size, stretching or quality). The main contribution of this thesis is the development and optimization of an automated generator of unstructured anisotropic surface and volume meshes. The triangular meshes are created on parametric surfaces using a modified technique of incremental Delaunay triangulation. The anisotropic characteristic of mesh elements was obtained using non-Euclidean metric via the developed system of coordinate transformation. For three-dimensional problems, tetrahedral meshes can be generated using similar technique. The proposed improvements allow increasing the efficiency of discretization and enhancing the procedure of boundary constraining, which is one of the main problem of 3D Delaunay triangulation. Generation of meshes (both two- and three-dimensional) is realized using a special control space structure, responsible for delivery of a desired size and shape of mesh elements in any point of the discretized domain. There is presented an automated schema of discrete control space creation, taking into account a number of metric sources gathered automatically or obtained from the user. There are also presented numerous examples and experimental analysis of the computational and memory complexity of the subsequent phases of mesh generation and transformation. Zadaniem generatora siatek jest podzielenie zadanego obszaru geometrycznego na skończoną liczbę prostych elementów, spełniających określone przez użytkownika wymagania (np. typ elementów, rozmiar, wydłużenie lub jakość). Celem pracy jest implementacja i optymalizacja automatycznego generatora niestrukturalnych, anizotropowych siatek powierzchniowych oraz objętościowych. Siatki trójkątne tworzone są na powierzchniach parametrycznych z wykorzystaniem zmodyfikowanej techniki inkrementacyjnej triangulacji Delaunay'a. Anizotropowy charakter siatki został uzyskany dzięki wprowadzeniu nieeuklidesowej metryki poprzez opracowany system transformacji współrzędnych. Dla problemów trójwymiarowych tworzone są siatki czworościenne, także z wykorzystaniem podobnej techniki. Zaproponowane ulepszenia pozwalają zwiększyć efektywność dyskretyzacji i usprawnić procedurę odzyskiwania brzegu, stanowiącą jeden z głównych problemów tej techniki. Generowanie siatek (zarówno dwu- jak i trójwymiarowych) odbywa się w oparciu o specjalną strukturę przestrzeni kontrolnej, wskazującej pożądany rozmiar i kształt elementów w dowolnym punkcie dyskretyzowanej przestrzeni. Przedstawiony został schemat automatycznego tworzenia dyskretnej struktury przestrzeni kontrolnej, uwzględniającej szereg informacji o rozmiarze elementów pozyskanych automatycznie, jak również zadanych bezpośrednio przez użytkownika. Uzyskane wyniki poparte są licznymi przykładami i eksperymentalną analizą złożoności obliczeniowej i pamięciowej poszczególnych etapów tworzenia i transformacji siatki.