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.
Therefore 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 (Fig. 10). 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 (predefined sets of elements filling in entirely
the quadrant or octant) 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, analogous to
the one level difference applied to the octree used in sequential mesh generator,
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. The process of parametric tree construction is
schematically depicted in Figure 11.

*Daniel Rypl
2005-12-03*