Overview

Spatial decomposition methods were originally proposed as a way to represent approximations of geometric objects [Knuth-1975], [Samet-1984]. Quadtree- and octree-based mesh generation methods have been a topic of research for about three decades (see especially the surveys of the literature on spatial decomposition algorithms for mesh generation by [Thacker-1980] and [Shephard-1988]). In this context, decomposition approaches ^[1] have been designed to meet the needs of fully automatic mesh generation of arbitrary complex non-manifold objects and to reduce the extensive amount of time and effort required to generate meshes with semi-automatic methods [Yerry, Shephard-1983]. These approaches have proved to be robust and reliable and are commonly used in a wide range of engineering applications, see for instance, [Kela et al. 1986], [Perucchio et al. 1989], and [Shephard, Georges-1991].

In this type of approach applied to mesh generation, the object to be meshed is first approximated with a union of disjoint and variably sized cells representing a partition of the domain. These cells are obtained from a recursive refinement of a root cell enclosing the domain (i.e., a bounding box). Therefore, we obtain a covering up of a spatial region enclosing the object rather than of the object itself. In a second stage, each terminal cell is further decomposed into a set of elements whose union constitutes the final mesh of the domain (cf. Figure 5.1). The basic principle behind the method is that as the subdivision becomes finer, the geometry of the portion of the region...