Next: Projection Up: Direct Triangulation of 3D Surfaces Previous: Mesh Density Control


Octree Control Space

In order to control the element size gradation and to implement the spatial localization, an octree is built around the surface to be discretized. The octree is a hierarchic data structure, at the top of which is the root octant represented by a cube surrounding the entire surface. This root octant is then recursively divided into eight octants until all terminal (not further divided) octants are at the desired level in the octree hierarchy (Fig. 20). Thus each octant, except the root, has just one parent and each non-terminal octant has exactly eight children. This parentage serves for the octree traversal in the vertical direction, from the root to the terminal octants (top-down) and vice versa (bottom-up). The desired level in the octree hierarchy is dictated by the prescribed element spacing and can be calculated as

(51)


where stands for the size of the edge of the root octant, denotes the desired element size, and brackets represent the integer part of the enclosed quantity. The coefficient (currently set to ) is used to ensure that the octant is always greater than the desired element size (at least by ), which is later used during the actual surface discretization. As the tree level can only take integer values, the size of individual octants corresponds only approximately to the required element spacing. The exact values of the spacing are stored at each node of the octree and take into account the size of octants sharing the node. Since the mesh density is usually varying over the surface, the octree generally exhibits a very irregular structure, which seriously complicates octree management. Therefore a maximum one-level difference of octants sharing an edge is enforced (Fig. 21) followed by an appropriate modification of the octant nodal values of the element size. The process of the octree one-level enforcement can be accomplished either as a postprocessing applied to an initially built octree or during the actual octree building. The advantage of the latter approach lies in the fact that a valid octree satisfying the one-level difference rule is maintained throughout the whole octree building process. This enables to use all tools, developed to handle the final octree, in any phase of the octree data structure building. The enforcement of the one-level difference has two important aspects that affect the computational complexity of the presented algorithms. Firstly, it allows an efficient implementation of the octree traversal in the horizontal direction (on a constant octree level), which substitutes, in some cases, the computationally more demanding vertical traversal. And secondly, it ensures the gradual variation of the mesh density by restricting the maximum gradient of the element size to , which contributes to the creation of well-shaped elements. During the actual mesh generation, the required element size is extracted from the octree for a given location using the linear interpolation of octree nodal values of the element size according to the following formula

(52)


where the blending functions are defined as

(53)


(54)


(55)


(56)


The dimensionless coordinates , , and are given by

(57)


where , , and are the coordinates of the point where the element size is being extracted, , , and are the coordinates of the centre of the terminal octant containing that point, and is the edge size of that octant. A two-dimensional example of an octree (a quadtree) together with element size contours extracted from the octree built around a planar domain using the curvature-based mesh density control is depicted in Figure 22.

The octree also stores the nodes introduced during the actual mesh generation. Generally, each new node is registered into the octree in order to enable its fast localization during subsequent mesh generation phases. The node registration consists in locating a terminal octant that contains the node and storing the node in that octant. The other mesh entities (edges and triangles) are not stored in the octree because they can be traced up from the nodes, using the mesh topology, and because their storage in the octree would considerably increase memory requirements.

The use of the octree data structure for the mesh density control suffers from some drawbacks. Firstly, from the geometrical point of view, the octree has a strictly orthogonal structure, usually aligned with the Cartesian coordinate system. This does not make the octree ideal for the description of a mesh density distribution that is not aligned with the Cartesian system. Also, the capability of the octree to capture a general (typically a polar or spherical) symmetry of the desired mesh density distribution is considerably reduced (see Fig. 22). Another deficiency of the octree resides in its global character. The element size on two independent parts of the model (possibly of the same surface) can be extracted from the same octant resulting virtually in the same or very similar mesh density. This phenomenon is further amplified by the enforcement of the one-level difference rule that decreases the maximal allowable gradient of the element spacing and increases therefore the distance of two locations which influence each other (in terms of the element size). This can be demonstrated by an example of a double bended curve in Figure 23 with an undesirable octree refinement (shaded octants) along flat parts of the curve induced by the one-level difference enforcement.

The actual octree building consists of two parts. In the first one, the maximum element size prescribed by the local specification is propagated from the surface to its boundary. Then the extent (bounding box) of the surface under consideration is determined and the octree is initialized by creation of the root octant enclosing the whole surface. In the second phase, the octree is refined with respect to the desired element size by introducing points into the octree. For each point, the terminal octant which comprises that point is located using the top-down traversal starting at the root octant. If this terminal octant is placed at a level lower than the desired one, the octant is refined by one level, preserving simultaneously the consistency of the octree. This process is then repeated, starting the top-down traversal at the octant located for the last time, until the terminal octant is at the desired level in the octree hierarchy. If the point is too close to the boundary of the terminal octant at the final level, the relevant neighbours of that octant are also refined to the desirable level (if necessary), which ensures a smooth distribution of the element spacing around that point. The points used to build the octree are gathered from the quadtree in the parametric space of the surface. The depth of the quadtree is driven by the size of the quadrants in the real space with respect to the element size specification (based on the desired element spacing and/or the radius of the curvature of the surface).



Next: Projection Up: Direct Triangulation of 3D Surfaces Previous: Mesh Density Control

Daniel Rypl
2005-12-07