In order to control the element size gradation and to implement the spatial localization, an octree is built around the surface to be discretized. The octree is a hierarchic data structure, at the top of which is the root octant represented by a cube surrounding the entire surface. This root octant is then recursively divided into eight octants until all terminal (not further divided) octants are at the desired level in the octree hierarchy (Fig. 20). Thus each octant, except the root, has just one parent and each non-terminal octant has exactly eight children. This parentage serves for the octree traversal in the vertical direction, from the root to the terminal octants (top-down) and vice versa (bottom-up). The desired level in the octree hierarchy is dictated by the prescribed element spacing and can be calculated as
The octree also stores the nodes introduced during the actual mesh generation. Generally, each new node is registered into the octree in order to enable its fast localization during subsequent mesh generation phases. The node registration consists in locating a terminal octant that contains the node and storing the node in that octant. The other mesh entities (edges and triangles) are not stored in the octree because they can be traced up from the nodes, using the mesh topology, and because their storage in the octree would considerably increase memory requirements.
The use of the octree data structure for the mesh density control suffers from some drawbacks. Firstly, from the geometrical point of view, the octree has a strictly orthogonal structure, usually aligned with the Cartesian coordinate system. This does not make the octree ideal for the description of a mesh density distribution that is not aligned with the Cartesian system. Also, the capability of the octree to capture a general (typically a polar or spherical) symmetry of the desired mesh density distribution is considerably reduced (see Fig. 22). Another deficiency of the octree resides in its global character. The element size on two independent parts of the model (possibly of the same surface) can be extracted from the same octant resulting virtually in the same or very similar mesh density. This phenomenon is further amplified by the enforcement of the one-level difference rule that decreases the maximal allowable gradient of the element spacing and increases therefore the distance of two locations which influence each other (in terms of the element size). This can be demonstrated by an example of a double bended curve in Figure 23 with an undesirable octree refinement (shaded octants) along flat parts of the curve induced by the one-level difference enforcement.
The actual octree building consists of two parts. In the first one, the maximum element size prescribed by the local specification is propagated from the surface to its boundary. Then the extent (bounding box) of the surface under consideration is determined and the octree is initialized by creation of the root octant enclosing the whole surface. In the second phase, the octree is refined with respect to the desired element size by introducing points into the octree. For each point, the terminal octant which comprises that point is located using the top-down traversal starting at the root octant. If this terminal octant is placed at a level lower than the desired one, the octant is refined by one level, preserving simultaneously the consistency of the octree. This process is then repeated, starting the top-down traversal at the octant located for the last time, until the terminal octant is at the desired level in the octree hierarchy. If the point is too close to the boundary of the terminal octant at the final level, the relevant neighbours of that octant are also refined to the desirable level (if necessary), which ensures a smooth distribution of the element spacing around that point. The points used to build the octree are gathered from the quadtree in the parametric space of the surface. The depth of the quadtree is driven by the size of the quadrants in the real space with respect to the element size specification (based on the desired element spacing and/or the radius of the curvature of the surface).