Octree Data Structure

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

where stands for the size of the edge of the root octant, denotes the desired mesh size, and brackets represent the integer part of the enclosed quantity. The coefficient (currently set to ) is used to ensure that the octant is always greater than the desired mesh size (at least by ), which is later used during the actual surface and region discretization. As the tree level can only take integer values, the size of individual octants corresponds only approximately to the required element spacing. The exact values of the spacing are stored at each node of the octree and take into account the size of octants sharing the node. Since the mesh density is usually varying over the domain, the octree generally exhibits a very irregular structure, which seriously complicates octree management. Therefore a maximum one-level difference of octants sharing an edge is enforced (Fig. 2.10) followed by an appropriate modification of the octant nodal values of the mesh size. The process of octree one-level enforcement can be accomplished either as a postprocessing applied to an initially built octree or during the actual octree building. The advantage of the latter approach lies in the fact that a valid octree satisfying the one-level difference rule is maintained throughout the whole octree building process. This enables the use of all tools, developed to handle the final octree, in any phase of the octree data structure building. The enforcement of the one-level difference has two important aspects that affect the computational complexity of the presented algorithms. Firstly, it allows an efficient implementation of the octree traversal in the horizontal direction (on a constant octree level), which substitutes, in some cases, the computationally more demanding vertical traversal. And secondly, it ensures the gradual variation of the mesh density by restricting the maximum gradient of the element size to , which contributes to the creation of well-shaped elements. During the actual mesh generation, the required element size is extracted from the octree for a given location using the linear interpolation of octree nodal values of the mesh size according to the following formula

where the blending functions are defined as

The dimensionless coordinates , , and are given by

where , , and are coordinates of the point where the mesh size is being extracted, , , and are coordinates of the centre of the terminal octant containing that point, and is the size of that octant. A two-dimensional example of an octree (a quadtree) together with mesh size contours extracted from the octree built around a planar domain using the curvature-based mesh size control is depicted in Figure 2.11.

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.