Civil Engineering Reference
In-Depth Information
800.0
10M points
20M points
30M points
40M points
700.0
600.0
500.0
400.0
300.0
200.0
100.0
0.0
1
2
3
4
5
6
Partition into k × k × k zones
Figure 7.24
Partition into k × k × k zones.
subdivision, i.e. more zones in a zonal subdivision, in general, will take more CPU time for
the insertion of the same number of points. However, given a zonal subdivision, the CPU
time only increases linearly with the total number of points inserted, indicating that the
additional work for zonal division is linear. The linear complexity for point insertion by
zonal subdivision has an important implication that the parallel zonal insertion is almost
100% scalable for the number of processors available.
7.4.7 Memory requirement
Similar to the parallelisation in 2D, no extra memory is needed for the parallel zonal inser-
tion scheme compared to the classical sequential insertion process, except for a zonal label
for each point stored as a 2B integer in a linear array. To minimise the use of memory, the
circumcentre and the circumradius of each tetrahedron are not stored, which are recalcu-
lated whenever necessary. For each point insertion, about 7 × (4 + 4) × 4 + 3 × 8 = 248 ≈
250 B memory is required to store the vertices and the neighbours of the seven tetrahedra
(rounded up from an average of 6.75) generated and the x-, y- and z-co-ordinates of the
point. Thus, a PC with 16 GB, apart from the memory taken up by the operating system, can
generate quite comfortably 350 million tetrahedra for an insertion of more than 50 million
points without being appreciably slowed down due to lack of memory.
An inherent advantage with zonal insertion in 2D and 3D is that given the same amount
of memory, a larger point set can be handled by insertion with zonal subdivision, as infor-
mation of neighbouring tetrahedra is only needed for one zone at a time, rather than for the
entire population of all the tetrahedra as in the case of point insertion within a single zone
without subdivision. However, for parallel insertion, if the zones are not processed all at the
same time, some memory saving is possible for the reason stated above.
7.4.8 Treatment of degeneracy
Robustness is paramount in parallel point insertion, and all the points have to be kept intact
throughout the insertion process. For randomly generated points or natural data points,
the situation is not that bad, and there is a case of inconsistency about 1 in 1000 for the
generation of 50 million points using double-precision calculations. For artificial objects,
