Civil Engineering Reference
In-Depth Information
2.7.7 Octree
The Quadtree scheme for the partition of space by local refinement can be readily extended to
higher dimensions. In 3D, each cubic cell (zone) is subdivided into eight octants or eight child
cells symmetrically about the three axes; such a construction is known as Octree. Similar to
Quadtree, Octree subdivision is often applied to computer graphics, the generation of tetra-
hedral and hex meshes, surface construction from cloud points, detection of collision in space
(Vemuri et al. 1998a,b), etc. Based on Octree for node positioning, Krysl and Ortiz (2001)
proposed a variational Delaunay approach to the generation of tetrahedral FE meshes. In
conjunction with an Octree scheme, Rassineux (1998) presented the generation and optimisa-
tion of tetrahedral meshes by AFT. With an Octree partition of space, Vemuri et al. (1998a)
developed a fast collision detection scheme with applications to particle flows. Mesh size at
a point is determined and stored by means of Octree (Quadros et al. 2004). Data-parallel
Octrees for surface reconstruction was developed by Zhou et al. (2011). Automatic MG based
on the Octree for cardiac electro-physiology problems was presented by Prassl et al. (2009).
The point insertion algorithm for the construction of Quadtree can also be applied to
3D to construct an Octree partition for a given set of spatial points. The following is the
pseudo-code
of Octree construction for a set of N points {(Xi,
if
, Y
if
, Z
if
), i = 1,N} by inserting
one point after another until all the points are processed.
Algorithm Octree (N, X, Y, P, Q)
// N = Number of points, x
min
, x
max
, y
min
, y
max
, z
min
, z
max
= x, y, z
// limits of the points
// NP = Number of points allowed in a cell, NZ = Number of zones (cells)
// created
// P
k
= Number of points in cell k, or the first child of cell k if P
k
> NP
// Q = Array recording points allocated to the zones
{
Set pointer array P to zero, P
if
= 0, i = 1,N
NZ = 8; xm =(x
min
+ x
max
)/2; ym =(y
min
+ y
max
)/2; ; zm =(z
min
+ z
max
)/2
Loop: i = 1,N
z = 1; u = X
if
; v = Y
if
; w = Z
if
x1 = x
min
; x2 = x
max
; y1 = y
min
; y2 = y
max
; z1 = z
min
; z2 = z
max
if (u > xm) z = z + 1;
x1 = xm;
x2 = x
max
if (v > ym) z = z + 2;
y1 = ym;
y2 = y
max
if (w > zm) z = z + 4;
z1 = zm;
z2 = z
max
Zone (z, i, u, v, w, X, Y, Z, x1, x2, y1, y2, z1, z2, NZ, P, Q)
End loop i } // Note: if applies to the entire line
Procedure Zone (z, i, u, v, w, X, Y, Z, x1, x2, y1, y2, z1, z2, NZ, P, Q)
// Insert point i (u,v,w) to zone z (x1,x2,y1,y2,z1,z2)
{ 1: n = P
z
If (n < NP) then
k = NP(z-1) + n + 1; Q
k
= i; P
z
= n + 1; return
End if
If (n = NP) then
Split_Zone (z, i, u, v, w, X, Y, Z, x1, x2, y1, y2, z1, z2, NZ, P, Q)
Return
End if
ym = (x1 + x2)/2; ym = (y1 + y2)/2; zm =(z1 + z2)/2
