Region Discretization

The discretization of a region consists in the fitting of templates into octants of an octal tree built in the region. Similarly as in the surface discretization, each template has to be topologically compatible and geometrically similar with the corresponding octant represented by a polyhedron, nodes and edges of which coincide with the tree nodes and edges bounding the octant. A very important feature of the tree-based techniques in 3D is the overall number of templates which have to be available to cope with all combinations of midside and midface nodes in an octant. Note that in the presented work, the octal tree is implemented in the generalized form, which further enlarges the overall number of templates. This can be demonstrated by the extended set of 2D templates bounding the faces of 3D templates. The additional 2D templates, depicted in Figure 3.7, can be derived from the basic set of templates (Fig. 3.6) by appropriate combining and scaling. Although the number of 3D templates is dramatically decreased by the application of the ``1:2 rule'', it remains still too large (over 5000) to implement the templates manually. Therefore, an automated approach for template creation during the runtime has been developed. Several classes of templates are recognized (Fig. 3.8). Simple templates are to be used in octants with only a few or no midside and midface nodes. These are the only templates which have been created manually. Symmetrical templates are designated for octants with midside and midface nodes arranged symmetrically with respect to a plane parallel with an octant face and passing through the centre of the octant (in the parametric space). Note that two types of symmetrical templates are distinguished depending on the occurrence of midside or midface nodes on the plane of symmetry. A combined template is based on splitting of an octant into two new ones (midside nodes on edges perpendicular to the plane of split have to be present) each of which is classified as a simple, symmetrical, or combined template. If no of these templates suits for a particular octant a default template is used. The default template has a node in the centre of the octant. The corner, midside, and midface nodes are then simply connected to this centre node with the only exception when a hexahedral element may be preserved in the corner of the octant. All the templates are designed in such a way that a face deplanation of individual elements is prevented (in the parametric space), which positively contributes to the element quality. Obviously, the above described templates do not provide an all-hexahedral mesh. The following types of elements, all treated as hexahedrons, are present in the mesh - hexahedrons, triangular prisms (wedges), pyramids, and tetrahedrons. The final mesh obtained as a collection of all applied templates is then smoothed using the following iterative relation

where is the smoothed node classified to the region, , , and are nodes which bound hexahedrons sharing node and which are connected to node directly by one, or indirectly by two or three edges, respectively, and , , , and are properly selected weights. Their current setting to , , , and , respectively, makes Eq. (3.27), in the case of an all-hexahedral mesh, equivalent to

where are nodes of hexahedrons connected to node . Note that the smoothing can be optionally extended by a weighting based on the required element size, nodal connectivity, or both. It should be also stated that the quality of the final mesh is slightly decreased by the irregular connectivity caused by the mixed nature of the region mesh.

The potential symmetry of a mesh may be (optionally) preserved if the use of values from the currently performed iteration is avoided during the smoothing process. This can be achieved either by duplication of the real coordinates of all the region nodes to store the two consequent iterations or by storing simultaneously the parametric and real space representations of each region node. Since the knowledge of parametric coordinates of region nodes has been considered more useful, the latter approach, using the parametric coordinates, has been adopted, although it results in somewhat higher computational costs. The use of the parametric space representation of a region node requires an actualization of its curvilinear coordinates whenever the node is moved. The evaluation of curvilinear coordinates of a point inside a region is accomplished iteratively in a similar fashion as the projection to a curve or surface. Firstly, any nearby point inside the region (typically the original position of the node being smoothed) is accepted as the first approximation of point . The increments , , and used to get a better approximation of point are obtained from the expression

where the gradients , , and are given by

(3.30) |

Note that this time, the whole set of three scalar equations represented by Eq. (3.29) is used to work out , , and . The increments , , and are then subjected to a normalization to prevent the individual parameters running out of the range of the parametric space and to avoid a diverging oscillation of the position of point around point in poorly parameterized regions. After that, the approximation of point is enhanced by incrementing its curvilinear coordinates by normalized , , and . The whole process is repeated until the point is close enough to point . The complete algorithm of the ``projection'' is summarized in Table 3.4.

*Daniel Rypl
2005-12-07*