Category Archives: grid generating

Delaunay Triangulation

it’s official for Wikipedia : divide and conquer algorithms are the faster for Delaunay triangulation ,so to celebrate let’s talk about this specific algorithm for the triangulation of a set of points (2D or 3D) which is called grid and is used in many aspects of scientific computing.

DELAUNΑY TRIANGULATION

DT combines several quality measures : maxmin angle condition,minmax constrained circumcenter etc .DT of a point set is the planar dual of the Voronoi diagram.The Voronoi Diagram is a partition of the plane into polygonal cells, each of one assinged to an initial point., so that the cell for input point P consists of a region fo the plane closer to P than any other input point.Any point (nodal-point of the grid) lies outside the circumcentre and hence any vertex of the Voronoi diagram has degree 3 and the DT will be a triangulation.

There are many algorythms for DT.Some of them have to do with the Convex hull of the set points.The main idea goes like this : Lift each point of the input to a paraboloid in one dimension up (for 2D it will be 3D) ,by mapping the point (x,y) ,to the point (x,y,x^2+y^2).The convex hull of the lifted points can be divided  into lower and upper parts: a face belongs tho the lower convex hull if it is supported by a plane that separates the point set from (0,0,-\infty).It can be shown that the DT of the input points is the projection of the lower convex hull onto the xy-plane:

Image

Many algorythms of O(nlog n ) run-time are developed for DT.One nice one and pretty understanding is devide_and_conquer .For the generall overview of the most famous algorythms for DT and their run-time comparison is triangulation_algorythms_sigkrisi.

SOURCE CODE

you can try to compute the delauney triangulation from source code for your input data points from here (Fortran 90,C,C++)

Leave a comment

what is CFD ?

well a friend asked me what exactly is CFD or more formally Computational Fluid Mechanics and how does this field of engineering  contributes in real life .

what is CFD ?

Computational Fluid Dynamics or CFD as it is popularly known, is used to generate flow simulations with the help of computers. CFD involves the solution of the governing laws of fluid dynamics numerically. The complex set of partial differential equations are solved on in geometrical domain divided into small volumes, commonly known as a mesh (or grid).

what is about ?

  • CFD allows numerical simulation of fluid flows, results for which are available for study even after the anaylsis is over. This is a big advantage over, say, wind tunnel testing where analysts have a shorter duration to perform flow measurements.
  • CFD allows observation of flow properties without disturbing the flow itself, which is not always possible with conventional measuring instruments.
  • CFD allows observation of flow properties at locations which may not be accessible to (or harmful for) measuring instruments. For example, inside a combustion chamber, or between turbine blades.
  • CFD can be used as a qualitative tool for discarding (or narrowing down the choices between), various designs. Designers and analysts can study prototypes numerically, and then test by experimentation only those which show promise.

CFD uses numerical methods to solve the fundamental nonlinear differential equations that describe fluid flow (the Navier-Stokes and allied equations) for predefined geometries and boundary conditions. The result is a wealth of predictions for flow velocity, temperature, density, and chemical concentrations for any region where flow occurs through virtual modeling techniques.

In the last decades computers improved CFD capabilities giving huge boost to Aeronautics , wind turbines modelling , aircraft design and more .
Remember one key-word above : mesh . The quality of the mesh plays huge role for solving NS-equations .

 

Large-Scale Numerical Simulations and Applications in CFD

 

Leave a comment

Adaptive meshes #1

Mesh generation has been an important procedure in computational fluid dynamics (CFD) modeling. A good mesh should be able to :

  • capture as many details as possible in the flow
  • not overly resolved in the regions with mostly uniform flow.As a result one can achieve optimal accuracy in the solution with minimal computational cost. In order to generate such a mesh, a lot of prior knowledge about the pvv hysics of the modeled problem as well as the assumptions and limitations of the computational scheme is needed. Sometimes the time and cost invested in mesh generation can take up a large percentage of the total modeling effort. Even so, when we encount er complex structural geometries or flows with a wide range of length scales, it is very hard to produce a mesh that is ‘optimal’.vv

For these reasons, adaptive methods in CFD have receivved much attention over the past thirty years due to their flexibility in resolving complex geometries and other problems such as unsteadyvv flow calculations. The goal of these methods is to evenly distribute error over the whole flow domain in order to minimize global inaccuracvy.

The adaptation is usually based on some error indicav tors calculated from solutions given in the past iterations, so that regions with larger errors are refined (and in some cases, those with l ess errors coarsened). So using either h-,p-,hp-refinement we can achieve the optimal grid .For example  for a cylinder , considering the  error , upwind and downwind , we apply there finement at the area which is required , which is  past the cylinder where vortices exist  .

Below appear : on the left the error distribution  and on the right the refined grid after 3 h-refinements (STRUCTURED GRID)

      

this could be applied for  an UNSTRUCTRED GRID like the following ( note that this is not refined, it’s a “coarse grid”)

or apply a refinement at HYBRID grid

                                                              

Leave a comment

Automatic triangulation of planar domain # cavendish algorithm

Let’s assume we want to construct a grid over an arbitrary planar domain filling it with triangles .We can use Cavendish’s semi automatic triangulation algorithm  . This algorithm  which will be described generates meshes with triangular elements for the decomposition of a region giving a special advantage to the user to specify the density of the elements , giving that way a mesh , appropriate to the physical and boundary conditions . The algorithm uses a modified algorithm  from the Suhara-Fukuda algorithm and goes like this :

DEFINING THE AREA (interior , boundary nodes and density of elements)

For instance , let’s assume we want to generate a triangular mesh over a circular domain with circle in it ( hole) .We call the domain R. The user is first required to make an arcwise (multiply) .

The domain R with counter-clockwise ordering of boundary nodes

The domain R with counter-clockwise ordering of boundary nodes

connected polygonal approximation R to the planar structure to be triangulated.The boundary {\partial}R must be composed of a disjoint union of simple, closed, piecewise linear arcs.

In order to provide the facility for triangulations of varying node density, the user is required to cover the region R with a disjoint set of simply connected polygonal zones Z_{i}   ,R \in\cup Z_{i} In particular, for each zone Z_{i} user is required to specify (in counter-clockwise order) the x-y co-ordinates which serve to define the boundary \partial{Z_{i}}
For each zone  there must be an accompanying density factor  r_{i} > 0.

Zonal decomposition of R

In order to get triangles with very avute angles , we demand all the nodes to lie in the interior area that is defined by the boundary elements .

NODES GENERATING

Starting from node 1 and moving counter clockwise , the algorithm circumscribes the smallest rectangle in the zone Z which belongs .To make things clearer we superimpose a rectangular grid with unit equal to the density .Our purpose is to to randomly generate one interior node in each sub-square of the grid .

Generation of interior node points

Thus applying this to all the other sub-domains Zi we get the interior nodes . As many as five consecutive attempts are made to generate a retainable random point in any one sub-square. If no point is successfully generated after five consecutive attempts, then no node is designated in that sub-square and the next sub-square is considered. This process is repeated until all sub-squares have been tested .The flow chart of the method is the following :

But we are not done . there must be an algorithm that will precises the interconnections of the nodes by checking the neighborhood of each edge such that the choice of the 3rd node , will give as acute interior angels . But this will be discussed latter …

Leave a comment