Introduction

Many problems in CFD, Computational Physics etc., involve the numerical solution of a set of equations in a complicated shape domain. The solution of such problems requires the domain to be discretized to produce a set of points on which the numerical algorithm can be based. For some problems, the generation of a suitable grid/mesh can be as demanding as the effort required to perform the computations for which the grid was intended. In recent times, considerable attention has been focused on the discretization process, which is commonly called mesh generation.

Numerical mesh generation has now become a fairly common tool for use in the numerical solution of PDEs on arbitrarily shaped regions. This is especially true in CFD, from which came much of the driving force for the development of this technique, but the procedures are equally applicable to all physical problems that involve field solutions. The basic techniques involved in numerical mesh generation are -

1.

a means of distributing points over the field in an orderly fashion, so that neighbors may be easily identified and data can be stored and handled efficiently.

2.

a means of communication between points, so that a smooth distribution is maintained as points shift their positions.

3.

a means of representing continuous functions by discrete values on a collection of points with sufficient accuracy, and a means for evaluation of the error in this representation.

4.

a means for communicating the need for a redistribution of points in the light of the error evaluation, and a means of controlling this redistribution.

This technique frees the computational simulation from restriction to certain boundary shapes, and allows general codes to be written in which the boundary shapes is specified simply by input.

Thus, mesh generation or grid generation is the process of decomposition of the domain. With the advent of Finite Element Methods (FEM) and Finite Volume Methods (FVM) which can be applied to grid cells of any arbitrary shape and connectivity, unstructured meshes are now being widely used. Triangulation is the most widely used form of unstructured mesh generation as any given arbitrary complex geometry can be more flexibly filled by triangular elements than by quadrilateral elements. Triangulation plays an important role in FEMs, numerical analysis, computer-aided geometric design (CAGD), approximation theory, and elsewhere. The applicability and accuracy of the finite element analysis is dependent upto a large extent on the validity and quality of the meshes generated. Thus it is important to have an acceptable and efficient process of mesh generation for all types of domains.

In some cases, the type and quality of triangulation is much more important than the time taken to generate the triangulation. For example, in case of boundary layer calculations, like in a flow past an airfoil, more points are required around the boundary than away from it. Here, conventional triangulation methods like Delaunay and Advancing Front often fail posing a need for another method which can give gradual variation or gradation in the triangulation generated. This is where Graded Triangulation comes into focus, which uses an appropriate combination of Delaunay and Advancing Front methods to generate the required mesh for this purpose.

The aim of this project is to develop a fully automatic unstructured triangular mesh generator. Work done in this project also forms an integral part of IITZeus, a surface modeling and mesh generation package being developed by the Department of Aerospace Engineering at IIT, Bombay. The package can generate curves like B-spline curves (BSC) and piecewise linear curves (PLC), and surfaces like B-spline surfaces (BSS), piecewise bi-linear surfaces (PBLS), surfaces of revolution (RS) and Coon's patches. These form the basis for generating the various inputs for the triangulation routines.