In order to control the element size gradation and to implement the spatial localization an octree is built around the domain to be discretized. The octree is a hierarchic data structure, at the top of which is a root octant represented by a cube surrounding the entire domain. 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. 2.9). Thus each octant, except the root one, 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 mesh size specification and can be calculated as
The use of the octree data structure for the mesh size 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 size distribution that is not aligned with the octree. Also, the capability of the octree to capture a general (typically a polar or spherical) symmetry of the desired mesh size distribution is considerably reduced (Fig. 2.11). The second deficiency of the octree resides in its global character. The mesh size on two independent parts of the model (possibly of the same model entity) 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 mesh size). This can be demonstrated by an example of a double bended curve in Figure 2.12 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 mesh size control is propagated from the individual model entities (starting with the ones of the highest dimension - typically regions) to their boundaries. Then the extent (bounding box) of the domain under consideration is determined and the octree is initialized by creation of the root octant enclosing the whole domain. In the second phase, the octree is refined with respect to the desired mesh 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 mesh size around the point. The points used to build the octree are gathered from the model description and/or from a background mesh. In the former case, the octree is successively built around individual model entities in a hierarchical manner starting with vertices. While the model vertices can be used directly in the octree construction, processing of curves, surfaces, patches, and shells is not as straightforward. In this case, the points to be introduced into the octree are retrieved from the appropriate model entity using either the parameterization of that entity itself (curves and surfaces) or the parameterization of a background entity (background surface of patches and shells). A binary tree or quadtree is built in the parametric space of the curve or (background) surface, respectively. The depth of the tree is driven by the size of the tree cells in the real space with respect to the mesh size specification (based on the desired element spacing and/or radius of curvature of the underlying model entity (see Section Mesh Size Control (Sequential Mesh Generation))). In order to avoid duplication of octree building on the boundary of a processed model entity, centres of individual tree cells (in the parametric space) are used as points introduced into the octree. Since there is no parametric entity covering the region, octree building in the region is problematic. Fortunately, only the maximum element size specification (propagated to bounding surfaces, patches, and shells during the octree initiation phase) is used as the mesh size control of the region. The octree building in the region therefore consists only in the refinement of all octants entirely inside the region to the level corresponding to that maximum element size. This can be done in two ways - during the actual octree building or during the mesh generation. The first approach requires the classification of octants as either ``inside'', ``outside'', or ``boundary'' with respect to a given region, which may be computationally demanding. Therefore the second approach is adopted, which refines the octant in the mesh generation phase, when the octant is touched for the first time, and which eliminates the explicit octant classification. The boundary octants (with respect to a given region) are guaranteed to be on the desired octree level due to the previous octree building around the bounding surfaces, patches, and shells.
When building the octree around a background mesh, the individual mesh entities of the background mesh are used to define the points to be introduced into the octree. Firstly, the nodes of the background mesh are directly inserted into the octree. Then the points are generated over individual elements of the background mesh (edges, triangles, and tetrahedrons) in such a way that the desired linear interpolation of the nodal mesh size specification is ensured.