The problem of the construction of "good" grids for the numerical solution of multidimensional boundary value problems (BVPs) in complicated computational domains has a big history and extensive special literature.
There are two main conventional requirements for the discretization of BVPs. The first one consists in the approximation quality which lies in the adaptivity to boundary peculiarities (vertices, edges, surfaces) and to differential properties of a solution, with possibility of local refinements. The second requirement means a simple grid topology and data structure to provide an efficient finite element or a finite volume approaches. We also take into account that modern fast algorithms of the numerical solution are based on the domain decomposition and multigrid principles which require much more complicated grid objects.
Thus, our objective is to satisfy the above mentioned conditions by constructing quasiregular, hierarchical, locally modified grids, for sophisticated two-dimensional boundary value problems.
The latter means that a computational domain (CD) consists of various computational subdomains (CSDs) with different functional or "physical" properties (differential equations to be solved with a description of coefficients and functions), and their boundaries can be piece-wise smooth, multi-connected and consisting of different segments of computational boundaries segments (CBSs).
A local modification means that the grid nodes near boundary vertices and edges are shifted to the boundary with a possibility of saving the topology of a grid.
Quasiregularity means that a discretized computational domain, or grid domain, can consist of grid subdomains (GSDs), or subgrids, both regular and irregular. A regular grid, for example rectangular or triangular, is defined by its coordinate lines, and by simple uniform interconnections between the neighbouring nodes. Each GSD can include several embedded subgrids with refined meshsteps. We suppose three levels of grid refinement embeddings. This approach also includes the classical multigrid principle.
Formally, the problem of construction of a universal mesh consists in forming the grid data structure (GDS) which defines uniquely all the topological and geometric specifications of elementary grid objects, i.e., nodes, edges and finite volumes with necessary references to macro-objects from input data (CSDs, CBSs), which are the results of user graphic interface preprocessing. Thus, in what follows we present definitions and data structures for the macro- and the micro-level grid objects, algorithms a local of grid modification and data transformations which provide the full necessary information for the implementation of approximation of the BVP by finite volume or finite element methods.