International conference OFEA-2001 "Optimization of finite-element approximations & splines and wavelets"
June 25-29, 2001 St.-Petersburg, Russia

Update: Information about next grid generation event can be found at

Update: Proceedings of minisymposium are published in English in the series



edited by S.A. Ivanenko, V.A. Garanzha


ISBN 5-201-09766-9, 160 PAGES

The goal of the minisymposium is to bring together mathematicians, physicians, engineers and numericists, who are concerned with numerical grid generation methods in a wide context.

The main issue is a critical look at the subject and informal exchange of ideas. New approaches and insights may be presented, even if they did not yet show full success. The demonstration of bottlenecks and limits of applications is explicitly welcome.

Minisymposium topics:
  • local and global optimality criteria in grid generation and optimization
  • Delaunay-Voronoi methods
  • nondegenerate grids and barrier methods
  • grid quality measures with particular emphasis on hexahedral and surface grids
  • error analysis, stability, sensitivity and nonuniqueness in grid generation
  • robustness of adaptive moving grid methods for complex applications
  • numerical methods for controlling spatial mappings with application to grid generation, surface projections, morphing, construction of surfaces from wireframes and other computational geometry and CAD problems
  • automated multiblock decomposition, creation and transformation of grid connectivity
  • quasi-isometric grids
  • quasi-orthogonal grid generation
  • grid visualization and animation
  • technical presentations from industrial researchers

  • contributed presentations
  • special panel discussion session "Challenge of universal grid generation criteria: limitations of methods, stability, sensitivity and nonuniqueness in grid generation", providing a discussion forum for researchers working in grid generation and applications
  • software demonstration

Minisymposium organizers:

Dr. Sergey A. Ivanenko
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia
tel. 7 (095)1354498
fax. 7 (095)1356159

Dr. Vladimir Garanzha
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia
tel. 7 (095)1357378
fax. 7 (095)1371333
mailto:garan at


1. Abstract , full paper (pdf) Alboul L., van Damme R.
Optimality criteria and optimisation procedure for 2.5D triangulations.

2. Abstract , full paper (pdf) Azarenok B.N.
Adaptive moving grids in problems of gas dynamics.

3. Belikov V.V.
Application of hybrid grids to numerical simulation of natural flows in GIS environment.

4. Abstract , full paper (pdf) Branets L.V, Garanzha V.A.
Global condition number of trilinear mapping. Application to 3-D grid generation.

5. Abstract Burago N.G.
Utilization of moving grids for nonstationary nonlinear problems in solid and fluid dynamics. Application to simulation of natural phenomena and technological processes.

6. Abstract Galyukov A.O, Serkov A.M.
An Object Oriented Approach to Unstructured Grid Generation.

7. Abstract , full paper (pdf) Garanzha V.A.
Max-norm optimization of spatial mappings with application to grid generation, construction of surfaces and shape design.

8. Abstract , full paper (pdf) Godunov S.K., Zhukov V.T., Feodoritova O.B.
About one approach to generation of quasi-isometric grids.

9. Abstract , full paper (pdf) Ivanenko S.A.
Optimality principle for nondegenerate grids.

10. Abstract , full paper (MS Word) Mikhalin V.A.
Parabolic grid generator for numerical simulations of external aerodynamics problems.

11. Abstract and paper Semenov A.Yu.
Marching noniterative generation of orthogonal grids.

12. Abstract Sorokin A.M., Vladimirova N.A.
Adaptive refinement of constrained directions applied to Euler and Navier-Stokes problems.

13. Abstract Tishkin V.F., Bogomolov K.L.
High-aspect ratio adaptation of unstructured meshes.

14. Abstract , full paper (pdf) Ushakova O.V.
Nondegeneracy criteria for 3-D grid cells. Formulas for cell volume.

15. Abstract , full paper (pdf) Volkov-Bogorodsky D.B.
On construction of spatial harmonic maps by the block analytical-numerical method.


In a new millennium, grid generation technologies are undergoing an important transition. They are playing an integral role in many interdisciplinary applications. In addition, techniques are increasingly being used in nontraditional areas such as medicine, material sciences, manufacturing technologies, and others. At this time, it is particularly important to take an inward look and catalog the challenges that face the field and identify the barriers to be overcome. Numerical uncertainties need to be categorized and quantified so that they are not carried over to the new fields where we do not have years of experience to help us separate numerical uncertainties from physical uncertainties in simulation process. In addition, techniques deemed inappropriate may well be the methods of choice when previously developed approaches are not able to produce satisfactory results. Detailed account of new promising techniques is presented.

Utilization of moving grids for nonstationary nonlinear problems in solid and fluid dynamics.
Application to simulation of natural phenomena and technological processes.

Nicolai G. Bourago

Institute for Problems in Mechanics RAS, Vernadskogo prospect 101,
Moscow, 117126, Russia

Processes in question are: high rate impact of solids, forging and forming, damage and compaction, motion of fluid with free surfaces, motion of free stream jets (like fountains) and their interaction with walls and fluid, melt-dopant convection-diffusion flow during crystal growth, environmental problems of smoke propagation in air and contaminant filtration in ground.

Based on general equations [1] the mathematical models for these phenomena are built by using moving structured/unstructured grids with dot and continuous markers. Series of numerical algorithms developed on the basis of finite element and finite volume techniques and incorporated into integrated code "ASTRA" [2-4].

Major impact of the research is directed onto practical implementation and comparison of variety existing different treatments of moving boundaries. It is demonstrated that similar results can be obtained by many different ways.

In addition numerical experiments with moving adaptive grids have been made and quite useful experience obtained.

All the results are presented as the collection of computed animations of the typical processes.

[1] Bourago N.G., Glushko A.I., Kovshov A.N. Thermodynamical method of deriving constitutive equations for continuous medii, Izvestia RAS, Mechanics of Solids, N.6, 2000, pp. 4-15.
[2] Bourago N.G., Computer code ASTRA for nonlinear problems in continuum mechanics, Abstracts of NORDIC-7 Seminar on computational mechanics, Trondheim, pp.141-142, 1994.
[3] Bourago N.G., Fedyushkin A.I., Polezhaev V.I. "Dopant distribution in Crystals grown by Submerged Heater method under steady and oscillatory rotation", J. Advances in Space Research, vol.24, N.10, 1999.
[4] Bourago N.G., Kukudzhanov V.N. "Numerical solution of elastic plastic problems by FEM", in Book "Computer mechanics of Solids", "Nauka", 1991, vol.2, pp. 78-122.

About one approach to generation of quasi-isometric grids.

S.K. Godunov, O.B. Feodoritova, V.T. Zhukov

Sobolev Institute of Mathematics, 4, Universitetskii pr.,
Novosibirsk, RUSSIA, 630090
Keldysh Institute of Applied Mathematics, Miusskaya sq., 4, Moscow,
RUSSIA, 125047

full paper (pdf)

An approach for generation of the block-structured quadrangular grid on a plane is presented. The approach is based on the theory of quasi-isometric mapping [1], [2]. This mapping is conformal with respect to the special metric, representing the natural metric on the constant curvature surface or plane. The grid is constructed by minimization of the variational functional. The basic variational principle, the feature of the numerical method as well some problems concerning the generalization of this approach for a multiblock domain are given.

The multiblock technique plays an important role in applications. We have been developing such technique as a step to automatic multiblok grid generation. The block interfaces, as well as block-structured grid itself, are to be constructed by grid generation process using some topological and geometrical information about considered physical domain. This information is not usually sufficient to construct the block structure (included the interfaces) by a simple method. We investigate the possibility of quasi- isometric mapping technique for construction both of the grid and the interfaces by means of discretization of the mapping of the union of the unit squares into physical domain.

[1]. S.K.Godunov, V.M.Gordienko and G.A.Chumakov, Quasi-isometric Parameterization of a Curvilinear Quadrangle and a Metric of Constant Curvature, Siberian Advances in Mathematics, 1995, v.5, N 2, 1-20.
[2]. S.K.Godunov, V.T.Zhukov, O.B.Feodoritova, An algorithm for construction of quasi-isometric grids in curvilinear quadrangular regions, Proc. 16th Internat. Conf. on Numer. Meth. Fluid Dynamics. Arcachon, France, 49-54 (1998).

Optimality principle for nondegenerate grids.

Sergey A. Ivanenko
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia

full paper (pdf)

Boundary-conforming invertible map of a unit square onto a physical domain generates unfolded grid. If a map is not invertible, it produces a folded grid, which cannot be used in computations. A variational principle is formulated for the set of all invertible maps, being the extensions of a given boundary map. The principle allows to separate this set from all other maps.

The functional, called the energy density of a map is considered. It depends on first derivatives of coordinates and variable coefficients. These coefficients form a symmetric positive-definite matrix. The variational principle states that a map will be invertible if and only if it is a minimum of the energy density functional. From this it follows that the Euler equations of the functional describe all possible invertible (smooth and one-to-one) maps.

A discrete analog of the variational principle, based on the energy density of grid deformation is formulated. Complete proof of the principle is presented.

The energy density of grid deformation is a discrete functional with an infinite barrier at the boundary of the set of unfolded grids. The barrier property is very important in problems with moving boundaries and in moving adaptive grid technology because such methods ensure generation of unfolded grids at every time step. Direct control of cell shapes is used to provide grid orthogonality with prescribed width of cells near the boundary. Adaptation to the solution of host equations is realized as in the adaptive-harmonic grid generator.

Variational principle is implemented in simulation of water flow around the waterfall dam with high free surface gradients. Moving grid, capturing the free boundary as a grid line is used in computations. Grid orthogonality near the free surface provides much more accurate resolution of free surface movement. The computer time compared with computations without boundary orthogonality is reduced considerably.

In the second study the application of adaptive grids to the numerical solution of shallow water equations is considered. Simulation of wind-induced currents in the Mojaiskii reservoir has been performed and results are presented. Adaptation to the numerical solution with boundary orthogonality allows to increase the accuracy of computations, which is consistent with experimental data.


Nondegeneracy Criteria for 3-D Grid Cells. Formulas for Cell Volume.

Olga V. Ushakova
Institute of Mathematics and Mechanics
Ural Branch of the Russian Academy of Sciences
S.Kovalevskaya st. 16, Ekatherinburg, 620219 Russia

full paper (pdf)

Numerical solution of partial differential equations in three dimensions often makes use of hexahedral cells having eight corners, twelve edges and six faces. In constructing the hexahedral cell for given eight corner points the most popular choice [1] is based on a trilinear map from a unit cube to a space defined by these points. Since a nondegeneracy of a grid is a major objective of grid generation algorithms and a common requirement to be satisfied for a computational grid, both a mathematician developing a grid generation method, in particular [2], and a practicing engineer must care about this. Such test is very important, especially, in three dimensions when a visualization of a grid is complicated.

In a number of works (see [3],[4]) attempts to find nondegeneracy criteria for 3-D cells have been undertaken.

In the present work nondegeneracy criteria have been found. They include nondegeneracy conditions of three-dimensional cells [5] and a special numerical algorithm for testing the Jacobian of a trilinear map on its positivity when sufficient nondegeneracy conditions are not satisfied. To check the obtained criteria a computational code has been written. The results of computation for hexahedrons randomly selected by the computer show the success rate of above criteria and give examples of hexahedral cells the nondegeneracy of which is verified by these criteria.

New formulas for cell volume are obtained.


[1] J.Killeen, Controlled Fusion, Academic Press, New York, San Francisco, London, (1976).
[2] O.B. Khairullina, A.F. Sidorov, O.V. Ushakova, Variational Methods of Construction of Optimal Grids, Handbook of Grid Generation, Ed. by J.F. Thompson, B.K. Soni, N.P. Weatherill; Boca Raton etc.: CRC Press, pp. 36-1--36-25,(1998).
[3]S.A. Ivanenko, Harmonic mappings, Handbook of Grid Generation. Ed. by J.F. Thompson, B.K. Soni, N.P. Weatherill; Boca Raton etc.: CRC Press, pp. 8-1-- 8-43, (1998).
[4] P.M. Knupp and S. Steinberg, Fundamentals of Grid Generation, CRC Press, (1994).
[5]O.V. Ushakova, Conditions of Nondegeneracy of Three-dimensional Cells. A Formula of a Volume of Cells, Numerical Grid Generation in Computational Field Simulations, Proceedings of the 7th International Conference, September 25-28, 2000, Whistler, British Columbia. Edited by B.K. Soni, J. Haeuser, J.F. Thompson, P. Eiseman, pp.659--668, (2000).

Global condition number of trilinear mapping. Application to 3-D grid generation.

L.V. Branets, V.A. Garanzha
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia
mailto:garan at

full paper (pdf)

Algebraic properties of certain distortion measures for trilinear cells are investigated. It is shown that if the distortion measure based on the combination of dimensionless conformal ratio and dimensionless volumetric change measure [1] is positive and has uniform upper bound then the trilinear mapping is nondegenerate and its metric tensor has global lower and upper spectral bounds which become tighter when upper bound on distortion measure is decreased.

This distortion measure as a continual characteristics of the trilinear mapping is shown to be bounded from above by a convex sum of discrete distortion measures computed at the set of cell ``quadrature points''. The consequence of the above result is that the upper bound on distortion measure of local mappings in each grid cell can only decrease with uniform grid refinement when maximum-norm minimization technique from [1] is applied to obtain each grid. Hence the global condition number of local mappings remains bounded in the limit of infinite grid refinement which is a key property in grid generation [2] and is generally violated by the discrete methods based on harmonic mappings and other methods based on the local quality criteria.

The implementation issues related to the minimization of distortion measures for hexahedral grids in the maximum norm along with robust untangling methods are discussed. The easily reproducible hard 3-D test cases for hexahedral grid untangling, optimization and sensitivity analysis are presented. It is shown that application of the technique from [1] to the 3-D problems allows to achieve the same level of robustness and grid quality as in the 2-D case.

1. V.A. Garanzha. Barrier method for quasi-isometric grid generation.- Com. Math. Math. Phys. V.40, N.11, 2000, pp. 1617-1637.
2. S.K. Godunov, V.M. Gordienko and G.A. Chumakov. Quasi-isometric parametrization of a curvilinear quadrangle and a metric of constant curvature. //Siberian Advances in Mathematics. 1995, V.5, N.2, P.1-20.

Max-norm optimization of spatial mappings with application to grid generation, construction of surfaces and shape design.

V.A. Garanzha
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia
mailto:garan at

full paper (pdf)

The optimality principle for spatial mappings based on the minimal deviation from isometry conditions [1] plays the key role in many practical application. The metric-based control over properties of local mappings in the finite element method allows to minimize the deviation of size, shape and orientation of grid cells from the prescribed values.

The applications include grid adaptation to flow features, grid orthogonality near boundary, surface grid generation, quasi-isometric projections of complicated surfaces, shape optimization and various structural optimization problems with most advantages in the case of large deformations.

There is also a separate class of 2.5-D applications where this principle plays a crucial role: construction of surfaces from wireframes, morphing, repair of CAD data such as elimination of wrinkles, etc.

This optimality principle is implemented via the minimization of the functional which is elliptic and in the discrete case has an infinite barrier on the boundary of the feasible set consisting of grids with quasi-isometric local mappings [2]. This feasible set is contracted using the continuation technique which forces the global lower and upper spectral bounds of metric tensors of local mappings in the finite element grid to increase and to decrease, respectively.

The main issue related to construction of quasi-isometric projections of surfaces is that initial guesses are generally infeasible, hence in order to build the semidiscrete mappings the method should handle the following problems: 1) creation of nondegenerate local mappings or in other words grid untangling; 2) stabilization and untangling of free boundaries in the small; usual pattern when creating the nondegenerate mapping from infeasible initial guess is the creation of knots and spiral-like structures on the free boundaries such that the resulting mapping is nondegenerate but multivalued; such behaviour must be prohibited; 3) global nonoverlapping of free boundaries; The solution of the above problems presented in this work was found to be quite reliable and survived extensive testing on hard industrial problems.

Another important problem of construction of globally optimal adaptive grids also can be reformulated as a shape optimization problem. Here computational domain with prescribed control metrics inside is mapped onto an a-priori unknown domain such that in new coordinates the control metrics is as close to the unit one as possible. Quasi-uniform structured or unstructured grid in new domain can be generated by any well known method and mapped back to initial domain thus creating very good guess to globally optimal grid. Numerical experiments show that this approach greatly reduce sensitivity of grids to sharp metric variations since ``residual'' metrics in transformed space tends to be quite smooth.

Numerical results related to surface grid generation, construction of surface projections, morphing and shape optimization are presented.

1. S.K. Godunov, V.M. Gordienko and G.A. Chumakov. Quasi-isometric parametrization of a curvilinear quadrangle and a metric of constant curvature. //Siberian Advances in Mathematics. 1995, V.5, N.2, P.1-20.
2. V.A. Garanzha. Barrier method for quasi-isometric grid generation.- Com. Math. Math. Phys. V.40, N.11, 2000, pp. 1617-1637.


Boris N. Azarenok
Computing Center of the Russian Academy of Sciences,
Vavilov Str.40, Moscow, 117967, Russia

full paper (pdf)

It will be presented applications of adaptive moving grids for hyperbolic problems of gas dynamics. This method is based upon a theory of the harmonic mapping using a variational approach, specifically, by minimizing the Dirichlet functional written on the surface of the graph of a control function. In such an approach there is an infinite barrier that prevents the grid cells from folding, that is particularly important in the vicinity of shock waves. In the domains of high gradients of the control function the grid lines are strongly compressed that allows to decrease the thickness of shocks by several factors of ten and thus to increase significantly the accuracy of calculations.

1-D test has shown the accuracy, obtained on the adaptive mesh, is higher than on nonadapted by 100 times. For the test of 2-D steady flow in a channel adaptation increases accuracy by 5 times that is equivalent to saving the computer memory by 25 times and running time by 50 times.

In the present study the moving adaptive meshes are used in modeling the unsteady supersonic flow in the wind tunnel containing a step. First, as a control function it is used a vector-function of all flow parameters: velocity components, pressure and density. Such a choice allows the mesh "to feel" singularities in the solution, i.e., shock waves and contact discontinuities, throughout the flow. Further, in order to achieve a better resolution in particular domains, some one parameter is used as a control function. For example, for better capturing the contact discontinuity by the grid lines it is used the modulus of velocity.

The next computations include 1) transonic gas flow over an airfoil at a small angle of attack, and 2) supersonic flow over the same airfoil. In the both cases due to adaptation the thickness of the shocks is reduced by 40-50 times in comparison with the nonadapted mesh that provides with capturing the shocks very accurately.


Adaptive refinement of constrained directions applied to Euler and
Navier-Stokes problems

A.M. Sorokin
N.A. Vladimirova

Central Aerohydrodynamics Institute, 140180,
Zhukovsky-3, Moscow reg., Russia

The Euler and Navier-Stokes calculations of aerodynamic problems should be based on adaptive gridding. The quality of numerical solutions essentially depends on the grid resolution of shocks and viscous dominated flow regions. The adaptive technique presented in this work employs the sorting of edges into three classes: the edges aligned with the gradient vector of monitor function, the edges aligned with contour levels of monitor function and the rest, called unaligned. The adaptive procedure refines only aligned edges if the value of error estimator at them exceeds the fixed threshold . The interpolation error based estimator was used at an edge as the weighted sum of the first and second order derivatives of monitor function along the edge direction. The Mach number was chosen as the monitor function in Euler and Navier-Stokes calculations. All the edges except the gradient aligned ones are subjected to edge swapping to align them with contour levels of monitor function. The adaptive technique maintains the grid structure in which any node has the gradient aligned edges entering and leaving it. The performance of adaptive technique is illustrated with Euler and Navier-Stokes 2D problems.



The Central Research Institute of Machine Building
Korolev, Moscow Region, Russia

full paper (MS Word)

The planar grid parabolic generator was suggested by Nakamura [1]. The major advantages, namely, the operating speed due to the lack of iterations and the possibility of hands-off operation when generating grids in regions of complex geometry, allow this generator to be incorporated in gasdynamic equations integrating codes based on marching methods.

The parabolic generator is built upon finite difference approximation of the Laplace equations which represent one-to-one mapping of physical space onto reference domain in curvilinear coordinates. Mesh point coordinates are supposed to be specified at the computational region boundary. The solution represents level-to-level transfer from inner boundary to outer one. The transfer goes in two stages. The first one is an algebraic predictor whereby the mesh point coordinates are calculated approximately with the use of algebraic relationships; the second one is a parabolic corrector which provides the coordinates refinement.

The predictor stage allows the algorithm to be varied depending on a computational region features which makes the parabolic generator a very flexible tool for solving gasdynamic problems.

In order to exclude the probability of grid degeneracy in hand-off operation, the modified algorithm was suggested [2], wherein the mesh point coordinates can travel along the outer boundary at the predictor stage of grid generation, which improves significantly the grid quality and the generator operational reliability.

Variants of parabolic grid generator have been developed for grid generation in regions of complex geometry and different topology, including those with curvilinear boundaries, as well as for adaptive grid generation.

The parabolic generator requires no iterations, however, it can serve as the base for building iterative algorithms providing high-quality grids generation starting from a quite arbitrarily initial guess.

Applying different parabolic generator versions made it possible to solve numerically a number of external aerodynamics problems, specifically, steady supersonic flow along spacecraft of complex geometry, e.g. spaceplanes of different types, aerodynamically controlled and stabilized rockets (including those with curvilinear aerodynamic means for stabilization and control), as well as supersonic aerodynamic interference.

1. Nakamura S., Noniterative Grid Generation Using Parabolic Difference Equations for Fuselage-Wing Flow Calculations, Eighth International Conference on Numerical Methods in Fluid Dynamics, Aachen, Germany, June 1982.
2. V.A.Mikhalin, Modification of Parabolic Grid Generator, In: Atomic Science and Technology Issues // Mathematical Modelling of Physical Processes, vol.1-2, pp.91-94, 1995.

Application of hybrid grids to numerical simulation of natural flows
in GIS environment.

Vitaliy V. Belikov

Reseach Institute of Energy-Output Constructions
Stroitelnii pr.7a,
Moscow, Russia

Automated method for meshing arbitrary two-dimensional domains based on a variational approach is presented. Mesh cells can be triangles or quadrilaterals. The sum of two weighted functionals is used. The first one is an energy density functional. The second one controls the size of cells. A special control papameter is introduced to switch the shape of the cells (triangular or quadrilateral) depending on mesh requirements and location of a cell. It means that the algorithm can produce not only mixed, but also all-triangular and all-quadrilateral meshes. Extension to the three-dimensional case is discussed.

It is well known that in general case of complicated domain or adaption to a boundary layer any structured grid generator will produce grids with strongly skewed quadrilateral cells. At the same time many solvers need "nearly orthogonal" (with the cell shape close to rectangular) grids for successful applications. Unstructured grids can overcome this drawback. Mixed triangular/quadrilateral meshes can be constructed for arbitrary domain with such a property that all cells will be of "good shape",i.e. close to squares or equilaterals.

Algorithm contains three stages: 1. Advancing front method is used to construct initial mesh. At each step the minimal angle of the current boundary is obtained and then one or two triangles or quadrilaterals are constructed minimizing the fuctional which is the weighted sum of energy density functional and the functional, controlling cell size. If a new mesh point is inserted at this step, its location is defined minimizing the total functional. 2. Smoothing stage. 3. This stage contains insertion and/or deletion of mesh nodes and swapping to produce better shaped cells.

The algorithm is extended to the case of adaptation. Unstructured mesh is constructed on the surface of control function. The mesh is then projected onto a physical domain and resulting adaptive mesh will be clustered in regions of high gradients of control function.

The algorithm is implemented in GIS environment for meshing the arbitrary domains and is used for simulation of dam break water flow. Results of computations for real-world objects are presented.


On construction of spatial harmonic maps by the block
analytical-numerical method

Dmitrij B.Volkov-Bogorodsky

Institute of Applied Mechanics of Russian Academy Sciences,
Leninskij prospect, 32-A, Moscow, 117334 Russia

full paper (pdf)

The work is devoted to construction of harmonic mappings of spatial domains onto canonical ones in parametric space: onto unit box, onto unit ball or onto spherical layer (for double- connected domains). This problem has great practical interest, because it provides reliable method for mesh generation in spatial domains.

Construction of harmonic maps is realized by block analytical- numerical method, which has been developed during long time [1-3] and can be called a meshless method in modern classification. This method is based on decomposition of initial complex-shaped region onto simple sub-domains (blocks) and on approximation of solution in every block by a series of special functions having good approximative properties and exactly satisfying the problem operator. Every block can contain its own system of special functions which best reproduce the analytical properties of solution. Singular functions can be used near boundary edges, which allows to describe harmonic mapping behavior near boundary corners accurately.

The block analytical-numerical method represents solution in analytical form, which is convenient for analysis of harmonic map features and for fast reconstruction of the corresponding harmonic meshes. Numerical evidences suggest that the presented technique is highly competitive practical method for constructing harmonic maps and meshes.

[1] Vlasov, V.I., Volkov, D.B.: The multipole method for Poisson equation in regions with rounded corners // Comp. Maths Math. Phys. Vol. 35, No. 6 (1995). P. 687-707.
[2] Vlasov, V.I., Volkov-Bogorodsky, D.B.: Block multipole method for boundary value problems in complex-shaped domains // ZAMM. Vol. 78, Suppl. 3 (1998). P. 1111-1112.
[3] Volkov-Bogorodsky, D.B.: Development of block analytical- numerical method for problems in mechanics and acoustics // Proceedings of the conference "Composite materials". M.: IAM RAN, 2000. P. 44-56 (In Russian).

An Object Oriented Approach to Unstructured Grid Generation

Alexander O. Galyukov and Alexander M. Serkov
Soft-Impact Ltd, P.O.Box 33, 194156 Saint-Petersburg, Russia

Unstructured grid generation procedures are typically based on either a Delaunay or an advancing-front approach. The Delaunay approach offers the advantages of efficiency and a sound mathematical basis while the advancing-front technique offers the advantages of high- quality point placement strategy.

In this paper we present an object-oriented implementation of the algorithm that is a combination of the above methods. Such approach was initially developed for two-dimensional case [1] and then the procedure was considerably enhanced and extended to construct high-quality two- and three-dimensional unstructured grids of triangular or tetrahedral elements [2]. These methods are similar to a typical Delaunay approach in that they start with a valid boundary point triangulation. New points are inserted incrementally using an advancing-front type placement, but added from the boundary towards the interior. Each facet is examined to determine the ideal location for a new node on the interior of the existing triangulation. The node is then inserted and local reconnection is performed utilizing either a Delaunay in-sphere criterion or a min-max (minimize maximum angle) criterion. The overall procedure is applied repetitively until a complete field grid is obtained with a desired point distribution.

For two-dimensional case, automated multi-block geometry recognition algorithm is incorporated into the code simplifying the geometry input. An interface to CAD data is provided through DXF and IGES file converters including simple geometry repair procedures.

We make it a special point of the code development to utilize as much the advantages of object- oriented programming as possible to enhance the code efficiency and algorithm robustness. Main features of the code implementation, underlying data structures, and an overall algorithm are described in the present paper. Several examples are presented which demonstrate that high- quality unstructured grids can be efficiently generated for complex configurations.

[1] D.J. Mavriplis, An advancing Front Delaunay Triangulation Algorithm Designed for Robustness. AIAA Paper 93-0671, Jan. 1993.
[2] D.L. Marcum and N.P. Weatherill, Unstructured Grid Generation Using Iterative Point Insertion and Local Reconnection. AIAA J. 33(9), 1995, pp. 1619-1625.

High-aspect ratio adaptation of unstructured meshes

Vladimir Tishkin
Institute for Mathematical Modelling of RAS
125047, Miusskaya Sq., 4, Moscow, Russia

Konstantin Bogomolov
Moscow State University

An algorithm for adaptation of unstructured triangular mesh to a control function is presented. The goal is to construct a mesh that resolves areas of strong gradient of the control function with highly stretched thin triangles oriented perpendicularly to the gradient. Such anisotropic mesh allows achieving good adaptation in the direction where it is required without unnecessarily increasing the number of elements by adapting in the conjugate direction.

The mesh is adapted by optimizing a discrete mesh quality functional. The optimization is achieved via movement of mesh nodes and local topology reconstruction. The reconstruction is performed by swapping diagonal of a quadrilateral consisting of two neighboring triangles when such swapping will result in a correct mesh with a smaller value of the functional. This way adaptation preserves the number of elements present in the original triangulation.

The quality functional used is a combination of grid regularity and adaptivity functionals. The regularity component is the sum of reciprocals of squared sines of mesh triangles' angles. This functional is analogous to an orthogonality functional sometimes used with structured quadrilateral grids: it imposes an infinite barrier at the boundary of the set of correct meshes with a given topology. However, it may also prevent construction of highly stretched triangles with small and/or large angles. In order to prevent this effect, we calculate the angle in space with the metric used by the adaptivity component of the functional.

The adaptivity functional is based on lengths of all mesh edges in a special metric. The functional is constructed so that its minimum is achieved on a mesh with the lengths of all edges in this metric equal to a given value. This value is selected automatically based on the metric area of the domain and the number of triangles in the grid. The metric is constructed so that length of a segment evaluated in it will depend both on the normal length of the segment, its orientation relative to the control function's gradient, and the local magnitude of the gradient. Metric lengths of segments oriented perpendicularly to the gradient will evaluate to their normal lengths, while lengths of those oriented along the gradient will be magnified in proportion to the squared magnitude of the gradient. Metric coefficients are calculated and smoothed in a preprocessing step before the adaptation.

Several examples of grids adapted to test control functions with thin layer zones of strong gradients are presented.

Optimality criteria and optimisation procedure for 2.5D triangulations.

L. Alboul, R. van Damme
University of Twente, Faculty of Mathematical Sciences,
P.O.Box 217, 7500 AE Enschede, the Netherlands

full paper (pdf)

Triangulating a set of points (a data set) is a key technique in solving problems in Surface Reconstruction, for example, in scattered data interpolation and approximation, or in applications where one deals with reconstructing or modelling the surface of a three-dimensional object from an initial data set. The first step in evaluating a surface is to obtain a triangulation of the data sites. The data can be either a set of irregularly distributed points, or a se of straight-line segments, or a set of polygonal cross sections.

We discuss possible approaches to solve the problem of finding an optimal triangulation. The problem of finding a suitable triangulation of the given data consists, in general, in two steps: first, in constructing some initial triangulation, and second, in its optimisation with respect to a chosen criterion. We discuss the procedure of optimisation for triangulations of closed surfaces in 3D. Such triangulations can be defined as 2.5D triangulations. Optimisation usually consists in transforming the initial triangulation via a sequence of transformations to some final triangulation, which is better with respect to the given criterion. The operation of transformation should preferably be simple as well as general enough in order to be able to reach th optimal triangulation from any initial one.

We compare several optimality criteria; among them the Tight criterion and the criterion based on minimisation of the total Mean curvature, both introduced b L. Alboul and R. van Damme (see, for example, [1]). Then we discuss a possible operation of local transformation, suitable for 2.5D triangulations. In the case of triangulations of points in the plane a simple operation of transformation exists, known as Lawson's procedure [3]. The operation consists of swapping a diagonal of the convex quadrilateral formed by two adjacent triangles to the other diagonal, thus replacing one edge by a new one and obtaining another triangulation of the given data. Recently Alboul and van Damme have introduced a generalisation of Lawson's procedure for triangulation of surfaces in 3D, by allowing self-intersections of a triangulation and defining a local swapping procedure for a non-flat quadrilateral [2]. We discuss this procedure in the case the data are taken from the surface of an object of the simplest topological type, i.e. the boundary of the object is topologically equivalent to the 2D sphere. We show, for example, that we are able to recover the optimal triangulation of convex data, i.e. a convex triangulation, startin from almost any initial triangulation of the data.

1. L. Alboul, G. Kloosterman, C.Traas, and R. van Damme. Best data-dependent triangulations. Journal of Comp. and Applied Math, 119 (2000) 1-12.
2. L. Alboul and R. van Damme. A generalisation of diagonal flip operation for triangulations of discrete data in 3D. (Submitted).
3. C.L. Lawson. Transforming triangulations. Discrete mathematics, 3:365-372, 1972.

Web page design by V.A. Garanzha, L.V. Branets