Quadtree and Octree Grid Generation

Abstract

Engineering analysis often involves the accurate numerical solution of boundary value problems in discrete form. Hierarchical quadtree (or octree) grid generation offers an efficient method for the spatial discretisation of arbitrary-shaped two- (or three-) dimensional domains. It consists of recursive algebraic splitting of sub-domains into quadrants (or cubes), leading to an ordered hierarchical data structure with regard to the storage of mesh information. This paper describes quadtree Cartesian grid generation in detail and gives examples of its application to a circular geometry. The method is simple, rapid and does not experience difficulties with convergence (unlike curvilinear boundary-fitted mapping). Furthermore, the mesh may easily be adapted while preserving a well-ordered integer data structure. Extension to three-dimensions using octrees is straightforward.