4.3 Cartesian and Octree Methods

A naive and intuitive approach is to generate a simple regular grid which entirely covers up the simulation domain. For example, an ortho-product point cloud can be used to fill the bounding box which is defined by the minimum and maximum of each coordinate with mesh points. The cells are then classified according to their location.

• The cells in the interior of the structure boundaries are used as mesh elements.
• The cells which completely lie outside of the simulation domain are suppressed.
• The cells which intersect the boundaries have to be split into mesh elements and exterior parts.

The selection of the stepsize or cell size is crucial to resolve features of the boundary and to limit the complexity of the split cells near the boundaries. Unfortunately, the resulting surface mesh cannot be controlled well. It is a matter of luck how the boundaries intersect the cells. Sharp intersections or cells which are cut off close to their corners result in very thin or degenerate elements. This situation becomes worse when the boundary is slightly tilted relative to the coordinate system (Fig. 4.6).

Figure 4.6: Intersection of the cartesian cells with the boundary, M. Berger et al. [2].

Depending on the type of solver and discretization the cell elements must be further processed. Interior cells can be split into tetrahedra according to a set of templates. For the cells near the boundary templates and distortion (warping, [141]) might not be sufficient and a more general subdivision into tetrahedra may become necessary. The evolving mesh is boundary consistent but not boundary-fitted, and its topology will generally be of an unstructured nature.

An important remedy to the evenly sized mesh across the entire simulation domain is to allow the local subdivision into smaller cells. This leads to octree decomposition techniques with tetrahedral and even hexahedral [148] mesh templates. Spatial tree data structures provide great efficiency in storing and locating geometrical information [142]. A set of rules is applied to each node of the tree until a state of subdivision is reached where the leafs of the tree contain single entities of the boundary. These rules must be designed carefully, especially under finite precision arithmetics, to avoid deadlocks and to guarantee a subdivision process which terminates. The order of irregularity of the tree is defined as the maximum difference between the levels of subdivision of neighboring leafs. For instance an order of one guarantees that a cell's edge cannot be smaller or greater than half or twice the length of the neighbor cell.

A tradeoff which is quite important to observe lies in the selection of the irregularity of the tree. A one irregular tree enables the use of less complex templates to further tessellate the cells. It will be easier to construct elements with non-obtuse angles [116]. For example an interior quad cell (not intersected by the boundary) with four edges of which any combination is split in half can be fitted with non-obtuse triangular templates. Note that this is valid only for square quads and not general rectangles. This advantage is inherited from ortho-product grids where non-obtuse triangular/tetrahedral templates are trivial due to the rectangular cells. However, a one irregular tree induces a very high number of mesh elements, because the refinement propagates through large portions of the mesh. In fact it is not unusual that the number of mesh points becomes unmanageable as experiments with point clouds generated from one irregular octrees have shown [192]. Higher irregular trees complicate the vocabulary of templates to fit all possible cell constellations and make the creation of good elements difficult.

Figure 4.7: Intersection based octree mesh of Flash EEPROM, ISE ETH [52].

The long history of octree methods has lead to quite elaborated schemes [152,22,159]. However, the difficulties to control the element quality near boundaries also with regard to the mesh requirements for surface triangles are inherent. Boundary-fitted meshes cannot be achieved. Anisotropy can only be implemented in a limited way by intersection based instead of bisection based splitting of the cells. Thereby, it is difficult to maintain the good properties of the original octree and some advantages like the possibility to define non-obtuse triangular/tetrahedral templates are lost. Thin layers can only be managed as long as they are planar, parallel, and have a normal vector of which two components are equal to zero (Fig. 4.7). Thin layers with a normal vector of which one component is zero can theoretically be managed similar to the layer-based method with needle elements. As long as these structural requirements are met, octree methods will be of practical relevance. Quite advanced methods which can handle such a limited kind of anisotropy are applied in practice. However, it is questionable how much further such methods can be developed and how significant the improvements can be.