The individual model entities are discretized using the tree based approach. For each relevant model entity a tree of appropriate dimension (binary tree for curves, quad tree for surfaces and octal tree for regions) is built separately. Thus no problems with 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 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 not affine (stretching and distortion occur) the tree data structure is implemented as 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 relatively isotropic tree (in real space) even when 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 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 reasonable number the ``1:2 rule'' is applied. This rule guarantees that each two quadrants or octants sharing an edge do not differ in size (in parametric space) in direction of this edge by factor greater than two. The compatibility of the mesh on the interprocessor boundary is ensured by the use of appropriate templates on the assumption that the tree structures are compatible along that boundary. 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 domain, a boundary parametric tree is extracted from the basic tree of that domain for each boundary which also forms boundary of another domain. 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 domain 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 domain then updates its basic tree structure along the boundary according to the received boundary tree structure. This concept is applied iteratively to those domains which have recorded a change in their parametric tree in previous run, until the basic parametric tree of all domains remains unchanged.

*Daniel Rypl
2005-12-03*