A hierarchic tree of appropriate dimension (a binary tree for curves, a quad tree for surfaces, and an octal tree for regions) is built for each model entity which does not form boundary of another model entity of a higher dimension (these entities are called non-boundary model entities thereafter). To allow for the parallelization on the model entity tree level (see Section Domain Decomposition (Parallel Mesh Generation)), the tree data structure is implemented as a parametric one. This means that the tree is built in parametric coordinates of corresponding model entity. Since the mapping between the parametric and real spaces of the model entity is generally not affine (stretching and distortion occur), the tree data structure is implemented as a generalized one (Fig. 3.2). In this approach, the number of children of a parent cell may be 2 for any tree, 4 for a quad or octal tree and 8 for an octal tree. Note that the same effect could be achieved if the quad and octal trees would be implemented as freely alternating binary trees. Also note that the same generalized tree may be described by several different hierarchical structures. The use of the generalized tree structure enables to build a relatively isotropic tree (in the real space) even when a significant stretching induced by the mapping exists. The distortion of the mapping, on the other hand, is entirely inherited by the tree and may result in a poor quality grid on ``skew'' model entities.
The actual discretization of model entities is based on templates (predefined sets of elements filling in entirely the cells of the tree) similarly as in the standard tree-based algorithm. The complexity of a template depends on the number and arrangement of nodes in a particular cell. In order to limit the total number of templates to a reasonable number, a ``1:2 rule'' is applied. This rule guarantees that each two cells sharing an edge do not differ in the size (in the parametric space) in the direction of this edge by a factor greater than two or, in other words, that there will be no more than one midside node on an edge of any cell. Note that the ``1:2 rule'' is analogous to the one-level difference rule applied to the conventional octree (Section Octree Data Structure (Sequential Mesh Generation)). Since the level of a cell in a generalized tree structure is ambiguous, the use of the ``1:2 rule'' is more convenient. The enforcement of the ``1:2 rule'' can be accomplished during the actual discretization or as a postprocessing applied to an initially built tree. The former approach has been adopted because it maintains a valid tree structure satisfying the ``1:2 rule'' throughout the whole tree building process. This is an important aspect as it enables to avoid the duplication of nodes of the tree structure. Since these nodes will later become the nodes of a finite element mesh, it is highly desirable to prevent the duplication in order to comply with the topological compatibility requirements. The compatibility of the mesh on interfaces between individual model entities is ensured by the use of appropriate templates under the assumption that the tree structures are compatible along each interface. This is, however, not the case because the parametric tree structures are built independently. To resolve this problem the following approach has been proposed. Once the tree structures have been built in all non-boundary model entities, a boundary parametric tree is extracted from the basic tree for each boundary which also forms the boundary of another non-boundary model entity. For example, a quad tree is extracted from the basic octal tree of a model region for those of its boundary surfaces which form the boundary of another region. This extracted boundary tree is then sent to model entities, boundary of which corresponds to the extracted tree. In order to minimize the amount of interprocessor communication if the adjacent non-boundary model entities are discretized on different processors, a compressed form of the boundary tree structures is used for the communication. Each model entity then updates its basic tree structure along the boundary according to the received boundary tree structure. This concept is applied iteratively to those model entities which have recorded a change in their parametric tree in the previous iteration, until the basic parametric tree of all non-boundary model entities remains unchanged. Note that the compatibility of the tree structures on the topological level ensures simultaneously the compatibility on the geometrical level. The process of the parametric tree construction is schematically depicted in Figure 3.3.
The actual tree building is done in four steps. In the first one, each vertex is associated with a special tree node, classified to that vertex and corresponding to a tree structure of zero dimension. These vertex tree nodes will later become parts of cells of tree structures of a higher dimension. In the second step, the root cell corresponding to the parametric space of a particular non-boundary model entity is recursively divided in the parametric space until the size of the terminal cells in the real space does not exceed the desired value given by the mesh size specification (local or adaptive) extracted from that entity. The actual type of the division of a cell is evaluated according to the number and arrangement of edges which are too long with respect to the desired element size. If the aspect ratio of a cell in a direction exceeds a threshold value then the division in this direction is preferred even if a division in other direction would be also acceptable. This enables to achieve the isotropy of the tree structure (in the real space) already in the initial phase of the tree building. If the further division of a cell is not required, the mesh density is integrated over the cell in order to identify potential mesh refinement inside the cell. This integration is accomplished according to the relations
The construction of the parametric tree structure suffers also from some drawbacks. Firstly, it is generally impossible to guarantee creation of a symmetrical tree structure even in the case that the model geometry and mesh size specification are ideally symmetrical and round off errors of the floating point arithmetics are disregarded. This phenomenon is caused by the generalized nature of the tree structure, partial predetermination of the cell division along boundary (due to the restriction to the binary division), and, finally, by the predetermination of the tree traversal and application of the ``1:2 rule'' during the tree building. Secondly, an infinite recursion of the cell division may occur under certain circumstances during the tree building or during the tree compatibility enforcement. Fortunately, this effect happens only very rarely when severely degenerated and poorly parameterized domains are involved. And finally, the gradation of the mesh size can be unpredictably influenced by the application of the ``1:2 rule'', the effect of which might be magnified by the mapping between the parametric space, where the rule is actually applied, and the real space, where the mesh size gradation can be evaluated. On the other hand, the most apparent advantage of the parametric tree structure consists in its relation to the underlying model resulting in lost of the global character and in a possibility of parallel processing.