Contents

• Motivation
• Domain of work
• Methodology
• Conclusions and Future work
• References

Motivation

• Definition with an Example
• Introduction
• Past work
• Importance of work
• Limitations

• 1. Definition with an Example :

This work is an important aspect of finite element analysis and this is called as finite element " mesh " generation.In this i am trying to devolope a valid mesh using " Quad Tree Decomposition " and this work is conformed to 2D objects of any geometry .Finite elenment analysis is perhaps the most popular numerical technique for solving engineering problem like structural analysis,Fluid mechanics,Mechanical engineering problems. Finite element meshing is defined as decomposition of geometry into simple Glued elements such as triangles,quadrilaterals etc,with no overlap betwwen elements and union of elements cover entire geometry. In this work i have been using quadrilateral elements(Squares).

Suppose take an example of a Semi Circle :
 

It has to be descritised using some mehing techniques to get valid finite element mesh.Using Quad Tree Decompositon this can be descritised as like this as per defined level of tree.

After decompostion it looks as
 

• 2. Introduction :

FINITE ELEMENT MDELLING :
 

A typical finite element model is comprised of nodes,degrees of freedom, boundary analysis,elememts.material properties,externally applied loads, and analysis type.Total process can be showed broadly as follows.
 

In practice,first must decide on the mesh layout,that is numbner of nodes and elements.Zones of expected abrupt changes in the field variable(such as stress concentration around holes)requirea denser number of nodes and elements than zones where gradual changes occur.This is known as medh gradation.

Another important aspects is section of shape of element,aspect ratio and number of nodes per elements. Triangular or quadrilateral elements are used in most of the times. triangular elements provide good aspect ratio and it results increased number of nodes causing computaionally expencive. On The other hand Quadrilateral elements provide sufficient flexibility and it results decreased number of nodes, But it is difficult generate mesh using quadrilateral elements foe a comlex objects.The following are general shapes which are used.Square elements are used in the Quad Tree decompositon(Varying size).The number of nodes per elements depends on nodal variables(degrees of freedom) and the continuity requirements between elements.

MESH GENERATION :
 

Mesh generation forms backbone of the FEA.Mesh generation refers to the generation of nodal coordinates and elements.It also includes the automatic numbering of nodes and elements based on minimal amount of user-suplied data. Automatic mesh generation reduces errors and saves a great deal of user time and reducing the FEA cost. Before existing of preprocessors,Finite element meshes were generated manualy. Manual meshing is inefficient,error-prone,and meshing data can grow rapidly and become confusing for complex objcts-especially three dimentional objects.Mainly Mesh generation is complex for comlicated solid objects and Mesh generation is very important and primary step of Finite Element Analysis.With the Widespread use of computer graphics and CAD technology,Mesh generation has been a target for automation.

Mesh Requirements :
-------------
1. Nodal Locations.Nodes must be lie inside or on the boundaries of the geometric model to be meshed.
2. Element type and shape.It could be decided depends on compatability and completeness requirements.
3. Mesh gradation.It refers to the density control of nodes and elements at various locations.
4. Mesh conversion.It may be desirable to convert a mesh of a given type of element to another mesh of different element type.Example any quadri laterl eement can be converted into triagular element.
5. Element aspect ratio.For geometric invariance,it is important to keep the aspect ratio of any emlement close to 1,all sides of element are equal in length.
6. Mesh geometry and topology.Mesh geometry refers to the coordinates of nodal points and the connectivity information of elements.Mesh topology refers to orientaion w.r.t to actual object.
7. Cost effectiveness.The it takes to generate the mesh and the time it takes to perform the FEA are crucial.

Various Methods :
-----------
1. Semi-Automatic Methods:
a.Wireframe or Surface based methods(Delaunay Triangulation).
b.Solid-Modelling-based Methods.
2. Fully-Automatic Methods.
a.Quadtree Method(For 2D objects).
b.Octree Method(For 3D objects).
 

• 3. Past work :

Most of people worked to devolpe triangular element mesh and hardly any work done on quadrilateral mesh generation.Triangular element has always been the easiest to formulate and understand for FEA.The triangular were available before the isoparametric formulation was discovered,which is centered around quadrilateral elements.And triangular elements provide good aspect ratio and it matches with boundary approaxmately than other elements.But it results more number of nodes and more elements in practical situations and it computaionally expensive.So,this motivated me to devolope quadrilateral mesh which overcome some of those limitations of triangular elements reasonably.
 

• 4. Importance of the work :

Quad Tree decomposition of 2d object devolopes a valid mesh for FEA.Using this Quad Tree decomposition we can model any complex 2d objects Ex:contour of cost of an ocean,ameaba etc. The Quad Tree representation has several advantages.

1. Any orbitary shaped objects, convex or concave with interior holes in case of solids ( Octree representation is used for 3D objects ) can be represented to the precision of smallest cell.
2. Geometrical properties such as surface area,volume,center of mass,and interference are easily calculated at different levels of precision.
3. Because of spacial sorting and the uniformity of representation operations on Quad trees,Octrees are efficient.
4. Quadrilateral elements offer greater flexibility than triangular elements.
5. This Qudtree gives varying density of elements.It generates very less elemen ts and at edges to generates highly denser elemets.
6. It provides good aspect raio,Because all sides of any element are equal.
7. It generates optimum number of elements and i reduces computational cost drastically.
 
 

• 5. Limitations :

The building of curve of an object is represented by the set of straight lines and is therefore an approxmation of the original curve by a straight lines which are parallel to sides of original universe space.For objects with complex details, quad tree requires a large number of cells to represent the object accurately. And only approximate properties of the object canbe calculated such as, curvature is lost in these representation.

Another major limitation of the Quad Tree or Octree data structure is the difficulty of incorporating it into existing graphics software systems.

Domain of work

1. This algorithm works any for complex 2D objects even with holes inside.
2. This works for polygons only and primarly any object is approximated as a closed polygon.It doesn't work for curved objects.
3. Union of all squares plotted doesn't represent actual abject practically (genarally slight more than actaul object).
4. It shouldn't match exactly with actual Boundary of an object and it can not retains curvarture property.
 

Methodology

Quad Tree data structure canbe represented as below

EXPLANATION OF EACH ALGORITHM STEP FOR THE EXAMPLE OF SEMI CIRCLE :
 

STEP 1 :
-----

Approxmation of given object into plygon. The semi circle is approximated with small lines as follows.
 

After 4th step the decomposed picture looks as :
 

After 5th step finally it looks as :

Explanation of the program :
I have used a recursively calling tree algorithm to devolope a data structrure. It means Root ( Universe square ) have four chailds and level of the increased by 1, First node is tested first if it is partially filled (means it has the intersection with actual object), Then it will be subdivided into four squares and the first node of the present four nodes is tested and continue till reaching defined level odf tree. if it reaches final level it should complate testing of four childs and comes to the level just above and comlete other childs at that level and it continously traverse to the root and then it goes to the second node of level '1' and continue to the right most last node.
 

INPUT :
----
Boundary information (B-rep)
1. Number of vertices
2. Nunber of vertices of any holes
3. Tree level.
4. Coordinates of vertices
5. Coordinates of hole
6. Four coordinates of universe square

OUTPUT : You may also see the README file in the source area for more details on how to compile and run this program.

VARIATION OF TIME OF EXECUTION OF PROGRAM WITH LEVEL OF QUAD TREE FOR DIFFERENT POLYGON EDGES AND TO SEE THAT CLICK HERE /k3/sraos/www/751/proj/a.gif
 

TEST CASES :
---------

CASE : 1
------
An Orbitory figuare looks as an Ameaba.

Input :

1. Number of vertices of polygon : 40
2. Number of vertices of hole : 4
3. Level of the tree : 6
4. Coordinates of all polygon vertices :

9.0 6.0 10.0 5.7 11.0 5.0 12.0 5.2 12.6 6.0 13.0 7.0 14.0 7.3 15.0 7.5 15.5 8.0 15.1 9.0 14.3 10.0 14.0 11.0 14.4 12.0 15.0 13.0 14.8 14.0 14.0 14.2 13.0 13.7 12.0 13.6 11.3 14.0 11.0 14.3 10.0 14.8 9.4 14.0 9.0 13.6 8.0 13.4 7.0 13.6 6.0 13.0 6.0 12.0 6.4 11.0 6.0 10.7 5.0 10.4 4.5 10.0 4.2 9.0 5.0 8.7 6.0 8.5 6.0 8.0 5.0 7.0 4.9 6.0 6.0 5.3 7.0 5.4 8.0 5.8

5. Coordinates of all hole vertices :

11 9 13 11 11 13 9 11

6. Coordinate of Universe Square :

4 16.2 16.2 16.2 16.2 4 4 4
 
 

Generated mesh is shown as like..
 

CASE : 2
------
Another Orbitary figuare ( Apple ).
 

CASE : 3
-----
Another Fiquare consisting a hole at middle.

CASE : 4
-----
Another Fiquare (plane in top view).

CASE : 5
-----
It is a simple case, but it indicate an important thing that The four squares which were gotten by subdivision of universe square are completly inside or out side due that it hasn't subdivided further and came out eventhough tree level has been given greater than 1.

It is an Inverted L-Shape

Conclusions and Future work

My work on a generalisation of the Quad Tree Datastructure has shown that decreased number of elements as compared with other decompositions.The main advantages over the other decomposition are reduced memory and computational work, it will be more compatable for any complex objects and it reduces the analysis time drastically.Any physical properties are easily estimated approxmately.It provides good aspect ratio also. Above results indicate that this approch offers increased versatality for any complex 2D objects.

There are many ways too extend the ideas presented here.

1. This can be extended for 3D objects(Octree).
2. This can be extended for curved apprxmation rather then polygon approxmation of actual object.
 

References

1.Sapadis, N,and R.perucchio; " Advanced techniques for Automatic finite element meshing from models,"computer aided desisn,Vol.21,no.4,pp-248_253,1989.
2.Bryant,c.f; " Two dimentional Automatic triangular mesh generation,"IEEE Trans magnetics, Vol.MAG-21,no.6, pp 2547_2550,1985.
3.Indranil chakravarthy,Ingrid Carlbom: " A hierarchical data structure for representing the spatia; decomposition of 3D objects,"IEEE, computer graphics and applicatios",vol.1,No.3,pp:24-31,1985.
/k3/sraos/www/751/proj/bib1

4.Yerry and Mark A Shephard: " A Modified Quadtree approch to finite element mesh generation","IEEE,Computeri Graphics and Applications,vol.3,no.1, pp"33-46,1983.
/k3/sraos/www/751/proj/bib2

5.CAD/CAM Theory And Practice
Author: Ibrahim Zeid
publication : Mc Graw-Hill international editions
Computer science series.
6.CAD theory and applications
Author: Roger and Adams.