Auxiliary meshing techniques - Finite Element Mesh Generation - page 501

process as the LE of a tetrahedron may not be the LE in the ring of tetrahedra connected
to this edge. To ensure that elements are generated by the generalised bisection, an edge
should not be divided unless it is also the longest in the ring of tetrahedra. Working on
an element-by-element basis is not as efficient as the checking for the LE in a ring of tet-
rahedra could be time consuming. Indeed, much of the checking work is repeated when
we pass from one tetrahedron to its neighbours.
An alternative for mesh refinement by the generalised bisection is to proceed on a line-
by-line basis. A scheme ensuring that each subdivision is a generalised bisection of a ring
of tetrahedra is to cut always the LE of the mesh. This implies that all the edges satisfying
refinement criterion 8.4 have to be sorted in order of their length. A thorough sorting could
be time-consuming and runs at a time complexity of nlog(n) for a system of n objects.
Assuming that the generalised bisection is not very sensitive to a slight variation in length
and minor misplacement of edges in the order list, the first-level address sort ( bin sort ),
which has a linear time characteristic, is the most suitable to provide the priority sequence
for the bisection of edges.
Let L = {L i , i = 1,n} be the set of edges to be refined. Let ri i be the length of edge L i ; compute
r min = min i=1,n r i and r max = max i=1,n r i . A new order, k, for line Li i is given by

rr −

1 min

kNINTn = ( − 1 ) + 1

r − r

max in

Effectively, the edges are sorted in the ascending order of magnitude, i.e. shorter lines will
be placed in the front part of the list, and longer lines are placed towards the end of the list.
To assess the error of this sorting process, suppose that two edges Li i and L j are evaluated to
occupy the same position k:

rr −

rr −

j min

i min

NINT ( n − 1 ) += 1 NINT ( n − 1 ) += 1 k

r − r r − r

max in max in

rr r

r
n1

−
−

−< x

ma in

i j

Hence, if there are 1000 edges that need subdivision, then the error would be at most
r max /1000. In a coarse mesh where there are not many edges that need subdivision, more
space than necessary can be allowed for sorting (say, 1000 irrespective of the number
of edges) to ensure that the error between two consecutive edges can be limited to 0.1%
of r max .

8.4.3.1.4 Bisection of a ring of tetrahedra
Bisection of an edge IJ results in the refinement of the ring of tetrahedra connected to this
edge. The ring of tetrahedra associated to an edge can be obtained by a simple algorithm 2.5.9
without searching. As the four neighbours of each tetrahedron are known, starting from any
element that has edge IJ as one of its edges, the algorithm identifies successively all the elements
around line segment IJ when it comes back to the first element where the journey started. The
bisection of a ring of n tetrahedra associated with edge IJ, {IJP 1 P 2 , …, IJP n-1 P n , IJP n P 1 }, will
produce 2n tetrahedra {IKP 1 P 2 , …, IKP n-1 P n , IKP n P 1 , KJP 1 P 2 , …, KJP n-1 P n , KJP n P 1 } in which
K is a new node added to the mid-point of edge IJ, as shown in Figure 8.78. The new edges