Civil Engineering Reference
In-Depth Information
Table 5.5
CPU time of sphere packing
Nodes
Elements
CPU time(s)
10,000
59,725
62.438
20,000
119,801
146.922
30,000
178,997
237.470
40,000
239,038
328.891
50,000
299,286
426.984
500
450
New scheme
Old scheme
400
350
300
250
200
150
100
50
0
10,000
20,000
30,000
40,000
50,000
Number of spheres (nodes)
Figure 5.89
Graph of CPU time vs packing spheres.
site starting from a suitable close point on the front without a need for intensive searching
for the absolute minimum.
The Delaunay point insertion without searching for the BASE is a process of linear time
complexity. In the earlier implementation, we searched for the nearest sphere on the front,
and a quasi-linear time complexity was observed for the worked examples. Combining the
packing sphere and Delaunay point insertion, we would expect a linear time complexity
for MG if the insertion site can be located based on descent by rotation without searching
for the nearest sphere on the front. Table 5.5 shows the CPU times of a series of examples of
sphere packing and MG. The meshes were generated on an old PC more than 10 years ago with
CPU speed 1.7 GHz and 512-MB RAM running on VC++ 6.0 program. From Figure 5.89, the
CPU time increased slowly with the number of spheres packed, and a quasi-linear relation-
ship can be observed. It is remarked that computer codes for many parts in the early devel-
opment had not been optimised, and the purpose of the plot is to show the CPU time trend.
A new version had been worked out later, in which only a few adjacent tetrahedra on the
front from the current insertion site were checked for the next insertion point. Compared
with the initial scheme, for which all the surface tetrahedra are examined, the new scheme is
a much improved version. As all the processes are now localised in the new packing scheme,
a linear time complexity relationship is observed as shown in Figure 5.89.
5.7.4 Examples of sphere packing
Four examples of sphere packing and MG over a 3D unbounded domain have been worked
out for discussion. The statistics of the examples are listed in Table 5.6. N and M are, respec-
tively, the number of spheres (nodes) and the number of elements in the mesh. Max1 and Avg1
are, respectively, the maximum and the average number of rotations to locate the insertion
site in the sphere packing process. Max2 and Avg2 are, respectively, the maximum and the
