Quadtree/Octree Data Structures

Adaptive refinement of an initial element (element 0) into three levels (left) and the corresponding quadtree data structure (right).

The octree (quadtree in 2D) is the basic data structure in Sandia's adaptive mesh refinement applications. In the octree data structure, coarse-mesh elements are divided into some number of finer elements. These fine elements are stored as "children" of the coarse-mesh "parent" element in a hierarchical data structures.

Advantages

  • Coarsening is easily done by removing child elements from the octree.
  • Multi-level solvers and preconditioners can be implemented in a straight-forward manner.
  • Meshes of differing resolutions can be used to solve different aspects of a problem.
  • Load-balancing schemes can take advantage of the mesh hierarchy to obtain more global information about the current mesh and decomposition.

    • Disadvantages

  • High bookkeeping and storage overhead complications data migration.
  • Optimal ways of distributing octrees among parallel processors must be found.



    • Last Updated: October 15, 1997
    WWW Administration (www-admin@www.cs.sandia.gov)
    Karen Devine (kddevin@cs.sandia.gov)


    Back