Adaptive Quadtree Grid and Cartesian Cut-Cell Method

No matter which numerical technique, e.g. finite difference, finite volume, or finite element methods, is used to solve the flow field inside a problem domain, the first step is to replace the spatial domain of interest with a structured or unstructured discrete domain (a grid) to facilitate the solution process.  The quality of the grid plays a direct role on the accuracy of the flow solution.

Quadtree grids, which can be classified as a particular type of unstructured grid, consist of congruent but different size of square cells, which are constructed by recursive subdivision from an initial unit square according to prescribed yet flexible criteria.  Quadtree grids have gained increasing popularity in recent years due to many of their obvious advantages: they are cheap and automatic to generate; mesh information is stored in simple hierarchical data structures; and it is easy to obtain a locally high resolution, dynamically adaptive grid.  This is of course ideal when simulating free surface flows containing zones of locally high hydrodynamic gradient, such as fronts, transitions, bores, and localised eddies.  The quadtree grid is also well suited to providing a high resolution approximation to complicated boundary geometry.

The quadtree grid generation is fast, automatic, robust and straightforward in concept.  The procedure may be summarized as follows:

        1) Scale the physical flow domain so that it fits within a unit square.

        2) Divide the initial unit cell into four equal quadrant cells.

        3) Check each cell in turn, and subdivide if necessary according to specific subdivision criteria.

        4) Carry out further cell subdivision to ensure that no cell has a side length more than twice the size of its neighbours.

Herein, seeding points are used to define the boundary geometries.  And a cell is divided when it contains two or more seeding points and its subdivision level is less than the maximum specified.

However, one obvious drawback of quadtree grid is that the approximation of any curved boundary has the form of a staircase, no matter how fine the mesh is near the boundary.  This introduces additional numerical errors and even local spurious circulations into the flow solution.  Therefore the development of a high-resolution quadtree grid based shallow water equation solver with adequate boundary fitting would represent a significant advance.  Works have been done to provide boundary fitness for quadtree grids by using Cartesian cut-cell technique.  Cartesian cut cells cut the input geometries (solid bodies) out of the background grid and thus approximate the boundary with piece-wise linear segments, instead of staircases.

Back to Research