Fundamentals - Finite Element Mesh Generation - page 68

Figure 2.50 An Octree of 100 points.
subdivision for a given point is log(N). The insertion algorithm was tested with 10 3 to 10 7
randomly generated points (slightly biased towards a corner), and the results are shown in
Table 2.8. A quasi-straight line is produced in a plot of the CPU time against Nlog(N), as
shown in Figure 2.49. It is surprising to note that the construction of Octree takes slightly
less CPU time compared to the construction of Quadtree for the same number of points.
Although the number of regions is similar, the number of subdivisions might be quite dif-
ferent for each inserted point as Octree cells (NP = 8) are allowed to hold more points than
Quadtree cells (NP = 4).
Not only is the point insertion algorithm for the construction of Quadtree and Octree
simple and efficient but also the memory requirement is quite low. What we need are two
vectors of size NZ and NP*NZ. {P k , k = 1,NZ} represents the number of points in cell k
or the reference of the first child cell if P k > NP. The points allocated to cell k are given by
{Q m+j : j = 1,P k ; m = NP(k − 1)}, k = 1,NZ. To further save memory by reducing the size of
vector Q , the insertion algorithm can be run for the first time to establish the pointer vector
P without recording points allocated to the cells. In the second run, points are recorded in
vector Q in a compact manner without leaving any gap according to the number of points in
each cell already computed and stored in vector P . This is a trade-off between the CPU time
and the memory used; basically the program has to be run twice, but the memory reduced
could be more than half especially for the Octree construction where there are quite a lot
of empty cells.
In the construction of Quadtree or Octree, the cells are divided symmetrically along the
co-ordinate axes without referencing to the given point set. As a result, the level of subdivi-
sion (depth of a tree) depends on the distribution of the points. The most favourable condi-
tion is that the points are evenly distributed. On the contrary, in the worst scenario, all the
points but one are clustered within a tiny region, and it will take many subdivisions of cells
to separate the points. The capacity of a zone (cell), NP, can only be set between 1 and 4 in
Algorithm Quadtree and 1 and 8 in Algorithm Octree ; this restriction could be removed