Parametric Tree Construction

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

where , , and are the estimated numbers of elements on a curve, surface, and in a region, respectively, and subscripts and of parameters , , , , , and refers to the limits (previous and next) of the parametric extent of the cell. Whereas the gradients on a curve and and on a surface are provided in Section Mesh Size Control (Sequential Mesh Generation), the gradients , , and in a region are given by

(3.13) |

(3.14) |

(3.15) |

where the derivatives of the rational Bernstein polynomial are calculated according to the expressions

(3.16) | |||

(3.17) | |||

(3.18) | |||

The evaluation of integrals in Eqs (3.10), (3.11), and (3.12) to estimate the number of elements inside the cell is accomplished by a numerical integration over an auxiliary tree structure built in the examined cell. If the estimated number of elements exceeds some threshold value the cell is divided to the maximum allowable number of children. Each time the cell is to be divided, the appropriate neighbours of that cell are inspected in order to find existing nodes which will be part of the newly created cells (children) and in order to preserve the tree consistency in terms of the ``1:2 rule''. If the cell is located in the boundary layer of a tree structure (with respect to the model entity) then the corresponding boundary tree structure, created simultaneously with building of the tree structure of the model entity and stored at the corresponding boundary model entity, is examined to find the existing boundary nodes of newly created cells. This eliminates the duplication of nodes on an interface between the individual model entities, which is important if the tree structures of these model entities are built on the same processor. The non-existent nodes required to form any of the child cells are created and classified either directly to the model entity (an internal node) or to its boundary (a boundary node). In the latter case, the corresponding boundary tree structure is updated appropriately. In the third step, vertices fixed to model entities are considered. The terminal cell comprising the vertex is located using the vertical tree traversal. The cell size is then compared with the mesh size specification at the vertex and if the cell is too large it is appropriately divided. This process is then repeated, starting the vertical traversal at the cell located for the last time, until the size of the terminal cell is in agreement with the vertex mesh size specification. In the last step, tree compatibility on interfaces between non-boundary model entities is enforced using the technique described above. Note however, that instead of extracting the boundary tree structure from the tree structure of a non-boundary model entity, the tree structure stored on the corresponding boundary model entity can be used directly. Whereas the tree compatibility enforcement between two surfaces sharing a curve is fairly straightforward, the same process might be quite complicated when two adjacent regions sharing a surface are considered. The problem resides in the fact that the topological structures of the boundary quad trees extracted from two different octal trees along the common surface might be incompatible not only in terms of the arrangement of terminal cells (which is expected), but also in terms of the division ordering corresponding to the octree hierarchy. This makes the tree traversal during the octal tree updating very complex. An example of such a situation is shown in Figure 3.4 where two incompatible quad tree structures at the top of the figure should be exchanged between two adjacent regions, from which they have been extracted, in order to make the octal trees compatible along the common surface. The ordering of divisions is schematically indicated by the line continuity taking simultaneously into account the fact that a parent cell is always divided in the centre (in the parametric space). The final stage of compatible (in terms of distribution of terminal cells) quad tree structures is depicted at the bottom of Figure 3.4. In reality, the tree traversal, performed during the octal tree updating, has been successfully implemented only under the condition that the division of boundary cells of an octal tree structure is limited to a binary one (resulting just in two child cells). This limitation tends to spoil the tree isotropy along the region boundary which has to be recovered by a subsequent perpendicular division usually invoked by an excessive aspect ratio of the child cells.

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.

*Daniel Rypl
2005-12-07*