Civil Engineering Reference
In-Depth Information
T
32
, 7291 were actually carried out, which brought the initial minimum γ-value (γ
οmin
) of
0.000194 to 0.0005428 and the initial mean γ-value (γ
οmean
) of 0.42503 to 0.49232. As for
the T
44
transformation, out of the average of 39,642 scans for swap T44, only 1841 were
actually performed, which improved the initial mean γ-value (γ
οmean
) by a very small margin
from 0.42482 to 0.42852, and there was hardly any change for the initial minimum γ-value
(γ
οmin
) of 0.0001703.
In the second test, tetrahedral meshes generated by Delaunay insertion of 10,000 ran-
domly generated points are each optimised by two cycles of all the local topological trans-
formations developed, T
23
, T
32
, T
44
and T
56
, and the results are listed in Table 6.17. We can
see from Table 6.17 that, on average, T
23
was only carried out once out of 279,129 scans,
and similarly, only 33 T
56
were performed for 75,669 scans; this indicates that if we are not
aiming for the minute improvement of the mesh quality, a great deal on CPU time can be
saved by omitting the swaps T
23
and T
56
. Although T
44
is not as effective as T
32
, we can still
keep it as it will also slightly improve the mesh quality; however, we can consider applying it
less frequently relative to swap T
32
. From the optimisation of the Delaunay meshes, we also
observed that local topological operations converge very rapidly in general, and much fewer
operations are done in the second iteration (mesh k.2, k = 1,5 of Tables 6.16 and 6.17), and
virtually there is not much improvement even for the second iteration.
As for the CPU time required for the transformations T
32
and T
44
, Delaunay meshes of
100,000 points are generated for which the number of tetrahedral elements varies from
657,947 to 659,327. The average CPU times for two cycles of iterations are calculated by
dropping the largest and smallest values and taking the average of the remaining three
values, as shown in Table 6.18. In the two cycles of iterations, the number of tetrahedral
elements processed roughly equals to 657,947 + 659,327 = 1,317,274, from which we can
calculate that T
32
and T
44
can process about 400,000 and 500,000 tetrahedra, respectively,
per second on PC i7 CPU 870 at 2.93 GHz running on XP mode, which is about five times
slower than running on the same machine with Windows 7, Visual Studio 2010 on 64 bits.
However, the actual number of swaps is much fewer for T
44
compared to T
32
within a
second (hence, the efficiency of the two transformations), as a large amount of CPU time
is spent on scanning for T
44
, which includes the evaluation for any possible gain due to the
swap. As the swapping operations are local processes, the time complexity for optimisation
is linear provided that relevant topological relationships are prepared beforehand, which
can be done also in linear time. In summing up, an efficient topological optimisation scheme
Table 6.17
Optimisation of Delaunay triangulation by swaps T
23
, T
32
, T
44
and T
56
Mesh
Scan
23
T
23
Scan
32
T
32
Scan
44
T
44
Scan
56
T
56
γ
min
γ
mean
1.1
166,127
2
7501
7208
31,481
3413
41,804
22
0.00602
0.49449
1.2
114,142
0
500
231
21,558
267
34,216
5
0.00602
0.49693
2.1
164,575
2
7448
7130
31,056
3219
41,392
24
0.01584
0.49386
2.2
114,354
0
571
250
21,611
281
34,200
7
0.01813
0.49650
3.1
163,403
0
7194
6912
30,731
3234
41,123
32
0.01996
0.49681
3.2
114,310
0
518
253
21,355
275
34,321
6
0.01996
0.49955
4.1
165,216
0
7517
7193
31,205
3326
41,460
28
0.01257
0.49284
4.2
114,226
0
542
241
21,600
278
34,136
9
0.01257
0.49542
5.1
165,125
1
7524
7209
31,204
3286
41,456
29
0.00914
0.49375
5.2
114,168
0
506
220
21,602
277
34,236
5
0.00914
0.49619
Aver
279,129
1
7964
7369
52,681
3571
75,669
33
0.01316
0.49692
