EEE TRANSACTIONS ON MAGNETICS, VOL. 27, NO.

5, SEF'TEMBER 1991 4197

AUTOMATIC MESH GENERATION BASED ON EXPERT-SYSTEM-METHODS
K. Reichert, J. Skoczylas, T. Tarnhuvud
Department of Electrical MachineJ,
Swiss Federal Institute of Technology (ETH),
CH-8092 Zurich, Switzerland

A h s t r n r i - In this paper the mesh generation process for two-

dimensional problems is discussed. A new mesh generator based
o n expert-system methods i s presented. For every corner of a
closed polygon the corner-angle conditions are analysed and dif-
ferent types of mesh primitives are generated. In every step of the
mesh generation the conflict with the existing mesh is recognized
and an optimal action will be chosen. Thus, any area surrounded
by a polygon even w i t h a very sophisticated contour can be suc-
cessfuly covered with a basis mesh. This mesh is further improved
by side-swapping and node-shifting algorithms, b o t h optimizing
the shape of the elements and the location o f the nodes. Problem-
Figure 1: hlesli prirnitives
oriented adaptive mesh refinement algorithms provide further op-
timization according t o suitable criteria.
with roundings, long and straight edges and any sharp curvatures,
the distribution of nodes can be strongly nonuniform. The mesh
INTRODUCTION generator must therefore be flexible and robust enough t o handle
Any CAD-System produces a set of geometry primitives such as any sophisticated geometry and produce an optimal mesh. This
points, lines, arcs, circles, ... specifying the material interfaces mesh should have the following features:
and the boundaries of a device. The finite element mesh has
0 The number of elements should be as small as possible for
t o be fitted t o this geometry in an optimal sense. This requires
a desired accuracy of the solution.
a powerful mesh generator and also methods for optimizing and
for refining an existing mesh in order t o achieve higher accuracy. 0 The triangles should differ as little as possible from equilat-'
Thus, the full mesh generation process consists of the following erals. This provides the required high quality of the approx-
tasks: ima t ion.

Mesh generation A constant decay of the elements density should be provided

Mesh optimization t o bridge the gap between areas w i t h course density of node-
chains and areas with high density.
0 Adaptive mesh refinement
Basic_functions
~ _ _ _ ~ ~
Before going into detail in the following sections, some definitions
o f the mesh primitives must be given (see fig. 1): T h e meshing problem t o be solved within irregular polygons can
be formulated in general as follows:
Node - the common point of some mesh-elements or two
node-chains. 0 Gitwn: A polygon w i t h 77 edges o f lenght ~!(i). n nodes w i t h
coordinates r(z),y(z), and 17 corner angles ~ ( i (see
) Fig 2).
Node-chain - The line joining two nodes, both lying on the
interface boundary between two types of materials or o n a To bc d e t e r m i n e d : A n optimal sequence of single genera-
geometric boundary. tion actions f r o m all possible actions, satisfying the following
conditions:
Edge - The line joining two nodes of the actual polygon
considered for meshing. At the beginning of the mesh gen- the new polygon resulting f r o m the generation o f a sin-
eration the edges are identical with the node-chains. during gle element should be more uniform, i.e. approaching
the generation they are identical with the element sides. the shape o f a circle,

the number of edges should decrease,

Polygon - A closed contour of edges defining the actual area
t o be meshed, i.e. t o be covered with finite elements. the area o f the element being created should be as
small as possible,
Element - finite element: triangle or quadrangle, determined
elements growth should be uniform,
by nodes and edges.
elements should be as equilateral as possible.
Corner - an area between two edges with a common node
as a corner point. This problem IS being solved by means o f E r y c r t - S y . ~ / r n ~
Alrfhods.
The mesh generation process is controlled by a series o f " r d c s ' '
MESH GENERATION of the following type
T h e basis for the finite element mesh generation are node-chains
IF ("rondi/io7i" k ) THEN "mcsh gciiciulioti u c t ~ o t i "k
being often irregularly distributed on the geometry. As the shape
of the devices may be of great complexity, having many corners 0018-9464/91$01.00 0 1991 IEEE
I
I
 IEEE TRANSACTIONS ON MAGNETICS, VOL. 27, NO.5,SEPTEMBER 1991
4198

The general structure of such a "rii/c" k is as follows:

set initial conditions for the search o f an optimal triangle t o
be generated

DO for all the n corners of the actual polygon:

new edges
- IF "condition for rule I; at corner i" THEN
* create new triangles by means o f the lcfh action
Figure 3: N o n - i n t erferencc roridit ions.
a t the ith corner and at adjacent edges,
N o t - la.si a c i i r i t y conditions: In order t o avoid the
* write new node ( i f defined ) and new triangle
~

mesh generation activity expanding f r o m just one edge of

datas into the finite element data structure.
the actual polygon, every new edge is being inactivated as
1: modify the pointer vector z v ( i ) determining the
long as other actions at old active edges are possible. In case
new sequence o f edges,
there is n o solution action possible all edges o f the polygon
* set new conditions at the new edges.
are reactivated.
- END IF
From the experience w i t h the algorithms, the following actions
ENDDO of mesh generation are considered t o be necessary t o achieve an
n
optimal generation process (see Fig. 4):

Cut-off one corner by generating one triangle

Cut-off one corner by generating two triangles

Cut-off two corners by generating three triangles

Generating one equilateral triangle

Generating one right-angled triangle

Generating two triangles

F i g u r e 2: F E - m e s h geiierat i o n in ail irregular polygon.
Fig. 4 gives more details on these actions including their specific
if -conditions.
The following "cot~diiions"have to be implemented in the
mesh generation process: a) Cut-off one corner by generating one triangle

C o r n e r angle conditions: The angle a ( i ) of the ill1 "If-Condifions":

corner and all angles o f the triangles being generated in this 30" < a , < 115".
corner should satisfy specified angle conditions. The purpose 30" < P t , P > + i -
of this criteria is to avoid very slender triangles and t o select M i n i m u m area F,,
optimal ones in the process. 1, >~ l , or
, ~1 , + 1 > xl,
Alin.im.tim conditions: From all possible actions those b ) Cut-off one corner by generating two triangles
generating triangles w i t h minimum area and minimum length (y, "If-Coiiditions ":
of edges should be selected. Thus, the mesh grows uniformly -. I
70" < a,tl < 125"
from those parts of the polygon with the most dense seg- 150" < Q,, a , + z < 210".
mentation by node-chains.
"Dcsigtc ":
Afi77i7nt~rngrourth c o ~ t d c i i o n s :
Since many actions of
P, on diagonal o f
the type "cut-off element" are possible at the same time,
rhombus:
there exists the problem t o select the most favourable one.
c =0.7flz
The ratio of the areas of the new triangle being cutted-
off and the last triangle has t o be limited, thus ensuring a
smooth growth of the mesh. c) Cut-off two corners by generating three triangles

)Yoit - i t l l c r f r r c i t c c c o ~ t d i i i o i ~ ~A~ new

: triangle can not "11-( I O 7 L d l t 1 0 7 Z S "1
be created if:

- i t will cover any other existing triangle,

- it will cross any edge of existing triangles or the bound-

ary of the polygon,

- it's distance t o any edge of the actual polygon will be

below a certain limit (see Fig. 3).
I+1
 4199
EFE TRANSACTIONS ON MAGNETICS, VOL. 27, NO. 5, SEPTEMBER 1991
DO WHILE 71 > '{ and triangles may be generated without violat-
d) Generating one equilateral triangle
tng the interference conditions
"If- Cotid i / i o i i .S ": Cut-off all corners by generating three triangles
119- < n,. a,,, < 295", ( action c) )
Minimum of l,, Cut-off triangles ( action a) ) at the new corners
"Ursigii": Generate a new triangle ( action d). e) or f ) )
equilateral triangle Cut-off triangles ( action b) ) w i t h minimal area 1; as long
e) Generating one right-angled triangle as the condition F, < 1 81; i s true

"If-Colldlllolls " END DO

I,, , > 31",,,,
Final generation phase
and I , 5 I .
At the end of the main phase of the mesh generation there
a i-1 may be still more than three edges of the polygon left free due t o
the interference conditions. The meshing is continued by means
of the action "cut-off triangle" in an optimal sequence as long as
f ) Generating two triangles n is greater than three.

"If-Coiidafioizs " DO WHILE 71 >3

go" < a$+,< 140",
129" < a, < 295". Cut-off triangles ( action a) ) not violating interface con-
Minimum o f I,, ditions with minimal weighted area n , / , / , + l s i ~ ~ oand
, cl, <

0 111 " J
" D C S lqll'l
2 179''
Increase o , , , ~ , in steps of 10" from 110" until o,,,,,
equal-sided triangle o n I , .
cut-off-triangle I', - Pa if n o more actions of mesh generation are possible due t o
if - coiidifio~ls.

Figurr 4: The i ~ c l i o i i sof tircsli gencrn(ioii. END DO

The angles conditions for the above specified actions have been The remaining three edges determine the last triangle. The final
determined more or less heuristically. phase of mesh generation is always successful. A n optimization
phase as will be described in the next section ends the mesh gen-
T m for c mesh g e n e r a t i o n ill eration.
~h e _
a l g o_r i t h_ - a u t o m a t i-
u l a r polygons
i r r e g_-___
_. -_
All functions of the mesh generation shown above have t o be
integrated hierarchically in an expert decision process, consisting In case of very complex polygons with a highly non-uniform node-
of three phases chain distribution the mesh generation procedure will have diffi-
culties t o avoid slender elements, especially when cutting-off trian-
Preparation phase ~~ gles. The local decay of the mesh density must also be optimized.
The purpose of this phase is t o equalize the corners of the The mesh optimization will be achieved in two steps:
. ,.,
initial Dolveon and t o eliminate acute corners
z i d r -stiwppii)~/:Pairs of triangles sharing a common side and
Cut-off all triangles with ( I , i110" and I, .4 I , ,
; or I,, > having the same material properties are tested for swapping,
41, using the circle criterion 111 (see Fig. 5) due t o the "if-
(action a) Fig 4 ) condition" 11' < ]<$.

Cut-off all close t o right-angled corners by generating two n i i d a h i f / i i i y : Every node

ilmlt. iivi~y/i/ci)i?i,q I not being lo-
triangles cated on the material interface w ~ lbe
l moved into the centre
(action b) Fig 4 ) of ali neighbouring nodes according t o the relations:

Cut-off all triangles (action b) ) with minimal area 1; as

long as the following conditions are true I., < 1 8 1 ;
I,,,", ' I,,,,,,
where "',> !/,I a r e the coordinates Of
. the neighbouring
where I,,,,, and I,,,, a r e the minimal and the maximallenght of
the edges of the actual polygon, respectively. "If-condition": ,/(.r, - .i'r12 1 - ,vu,)?)i A with (,r,.!y,)
A a small value.
the coordinates of the node i and
Main mesh generation phase
-
A DA_PTIVE-ME S HAREFINEM EKT
The purpose of the main phase is t o generate the bulk of the
The primary mesh, generated from the geometry as above, will
triangles until the interference conditions are preventing any fur-
in general not provide an effrcient and accurate field-calculation
ther actions
Therefore it i s necessary t o generate new problem-oriented meshes,
 4200 EEE TRANSACTIONS ON MAGNETICS, VOL. 27, NO. 5, SEPTEMBER 1991

121 Pinchuk A.R., Silvester P.P.. Error estimation for automatic

adaptive finite element mesh generation, IEEE Trans. o n
Magnetics, Vol.MAG-21. pp. 2551-2554, 1985.

131 Tsrnhuvud T.. Reichert K.. Skoczylas J., Problem-oriented

adaptive mesh generation for accurate finite-element calcula-
tion, IEEE Trans. Magnetics, Vol.MAG-24, No. l . , pp. 779ff.
Jan. 1990

no swapping swap 141 Penman J.. Grieve M.D. Self-adaptive mesh generation
technique for the finite-element method, IEE Proceedings.
Figure 5: Sitlc-swapping conditions. vo1.134. pp. 634-649, 1987.
which are specific for each quantity t o be calculated.
Based o n a solution of the field quantities ( potential ...) at
the nodes of the initial mesh a-posteriori adaptive mesh refinement
is performed in two steps:

The mesh is first refined globally according t o an error cri-

teria which corresponds to the global error in the solution.
121, 131 141, The resulting mesh serves as / J ~ I . F I C 71rcsh for
the postprocessing calculations where new meshes are gen-
erated.

After having reached the accuracy of the global solution re-

quired the postsprocessing calculations follow. Here, the
problem-oriented local mesh refinement will be executed t o
determine specific field quantities with the accuracy required.
The basic idea of this approach i s t o refine the mesh adap-
tively but only locally, e.g. along the path of integration for
the force calculation. Thus, for different quantities differ-
ent / u i y < / ii)r.s/i(.s will result according t o the property of
the quantity and the error criteria used. W i t h this strategy
the number of elements and the computation time can be
reduced considerably without affecting the accuracy 13).

This process i s shown in the figure 6

Geometry
User
L=l Initial mesh

I Refinement

I Basic mesh I
Local
Refinements

Target meshes

EXAMPLES FOR T H E N E W M E S H
GENERAT1O.N PROCESS
The mesh generation procedure has been applied t o a large number
of field calculation problems A typical example is given in figure
7
REFEREN-CES

[I] Cendes Z.J., Shetiton D., Shahnasser H. Magnetic field com-

putation using Delunay triangulation and complementary fi-
nite element method, IEEE Trans. on Magnetics, Vol.l\nAG-
19. pp. 2551-2554, 1983.