Data structures of AMR(Adaptive Mesh Refinement) with quadtree

Question

I am graduate student and recently tried to implement quad-tree based AMR. Well I have implemented simple Poisson Solver on node-based quadtree, but I am not sure that my data structure is right. To be honest, I am not sure about my coding skills. So I'll just post some of my structures.

class node
{
  double x,y;
  cell *NW,*NE,*SW,*SE;
}


class cell
{
  double x,y;
  cell *NW,*NE,*SW,*SE;
  node *nw,*ne,*sw,*se;
}

So I stored information of four cells(the smallest) that shares the node. Therefore I can easily access to neighboring nodes. However, I think this is inefficient in memory, since it stores too many things. So what I am curious about is that, is their more efficient way of making quadtree structure that stores both node and cell? Thanks in advance.

Answer 1

Your data structure is fine for a toy problem, but it's not general enough, not efficient, for real applications:

• You make the assumption that your mesh consists only of squares and that consequently only exactly four cells come together at each vertex. That's generally not the case for meshes on which you actually want to solve something -- these give rise to quad-forests: collections of quad-trees.

• You will be allocating a very large number of rather small objects using your data structures. This is unnecessary: The vertices can be stored in one long array; the cells can be stored in one array per level, so that the child pointers are simply indices in the next level's array; if you arrange the four children of one node consecutively in the array, then you actually only need one child pointer; for most cases, you really only need pointers from cells to vertices, but not the other way around; and finally, for most algorithms working on quad-trees, it turns out to be more efficient if you store structures of arrays than arrays of structures. All of these realizations lead to data structures that are much more complicated than what you have here, but that are fast and cache efficient on modern processors. They also require far less memory than having to deal with all of the pointers you have.

If you're curious about how others implement these things, you might want to look at the way some of the existing libraries implement their data structures. Here, for example, is the key data structured used in deal.II: https://github.com/dealii/dealii/blob/master/include/deal.II/grid/tria_levels.h (Disclaimer: deal.II is a project I'm associated with, and the contents of this file were largely written by myself back in ~1998.)

Answer 2

Since the quad-tree has logarithmic height, the overall space cost is small.

If your mesh were the same everywhere, you could do implicit packing, as in a heap. For a binary tree, that looks like this:

   a
 b   c
d e f g

a b c d e f g

The position of each node in the linear format can be calculated with simple mathematics. This can be easily extended to a quad-tree.

However, if the quad-tree does not all have the same resolution, then this trick does not apply.

It is probably best to stick with a simple data structure for now. This will aid in debugging and you can adjust later if profiling suggests that's a good idea.