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.

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.

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.

2000-01-20