The individual model entities are discretized using a tree based approach. For each relevant model entity, a tree of an appropriate dimension (a binary tree for curves, a quad tree for surfaces, and an octal tree for regions) is built separately. Thus no problems with the tree data distribution on the model level occur. To allow for parallelization on the model entity tree level the tree data structure is implemented as a parametric one. This means that it 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. In this approach, the number of children of a parent cell may be 2 for any tree, 4 for quad and octal tree, and 8 for octal tree. This 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 relevant model entities is based on templates, similarly as in the classical tree based algorithm. 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 quadrants or octants sharing an edge do not differ in the size (in the parametric space) in the direction of this edge by factor greater than two. As a consequence, there is no more than one midside node per edge. Note that there are no all-hexahedral templates available and that the final mesh is therefore of a mixed nature.

The compatibility of the mesh inside a subdomain is guaranteed by the use of appropriate templates. On the subdomain (processor) interface, the application of appropriate templates will ensure the compatibility only under the assumption that the tree structures are compatible along that interface. This is, however, not the case because each parametric tree is built independently. To resolve this incompatibility the following approach has been proposed. Once the tree structure has been built in a given subdomain, a boundary parametric tree is extracted from the basic tree of that subdomain for each boundary which also forms boundary of another subdomain. For example, assuming only the model decomposition level, 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. These extracted boundary trees are then sent to the subdomain, boundary of which corresponds to the extracted tree. In order to minimize the amount of this interprocessor communication, a compressed form of boundary tree structures is used. Each subdomain then updates its basic tree structure along the boundary according to the received boundary tree structure. This concept is applied iteratively to those subdomains which have recorded a change in their parametric tree in the previous run, until the basic parametric tree of all subdomains remains unchanged.

*Daniel Rypl
2005-12-03*