Generation of triangular meshes for complex domains on the plane

Abstract

Many physical phenomena can be modeled by partial differential equations. The development of numerical methods based on the spatial subdivision of a domain into finite elements immediately extended interests to the tasks of generating a mesh. With the availability of versatile field solvers and powerful computers, the simulations of ever inereasing geometrical and physical complexity are attempted. At some point the main bottleneck becomes the mesh generation itself. The paper presents a detailed description of the triangular mesh generation scheme on the plane based upon the Delaunay triangulation. A mesh generator should be fully automatic and simplify input data as much as possible. It should offer rapid gradation from small to large sizes of elements. The generated mesh must be always valid and of good quality. All these requirements were taken into account during the selection and elaboration of utilized algorithms. Successive chapters describe procedures connected with the specification of a modeled domain, generation and triangulation of boundary vertices, introducing inner nodes, improving the quality of the created mesh, and renumbering of vertices.

Wiele zjawisk fizycznych może być modelowanych poprzez równania różniczkowe cząstkowe. Rozwój metod numerycznych, opartych na podziale fizycznego obszaru na elementy skończone, spowodował wzrost znaczenia zadania generowania odpowiednich siatek. Wraz z powstawaniem uniwersalnych algorytmów symulacji oraz wzrostem mocy obliczeniowej komputerów, badane są zjawiska o wzrastającej złożoności geometrycznej i fizycznej. W pewnym momencie głównym problemem stało się samo zagadnienie generowania siatek spełniających rosnące wymagania. Artykuł prezentuje dokładny opis schematu generowania trójkątnych siatek na płaszczyźnie, opartych na triangulacji Delaunaya. Generator siatek elementów skończonych powinien być w pełni automatyczny i wymagać możliwie ograniczonego zestawu danych wejściowych. Powinien też umożliwiać szybką gradację rozmiarów elementów siatki. Utworzona siatka musi być zawsze poprawna i musi charakteryzować się dobrą jakością. Wszystkie te wymaganie zostały uwzględnione podczas wyboru i opracowania wykorzystanych algorytmów. Kolejne rozdziały opisują procedury wykorzystywane podczas specyfikacji geometrii modelowanych obszarów, generowania i triangulacji wierzchołków brzegowych, wprowadzania wierzchołków wewnętrznych, poprawy jakości stworzonej siatki oraz renumeracji wierzchołków.