The forest workflow

An overview of the forest of octrees creation and manipulation.

Introduction

The forest data structure (cf. p4est_t (2D), p8est_t (3D)) encodes the mesh topology as a forest of quadtrees (2D) or octrees (3D). The forest can be created given a connectivity (cf. the connectivity page). In contrast to the connectivity data structure, the forest data structure is distributed in memory when MPI is activated, i.e. the forest data structure only stores leaves that are processor-local according to the parallel mesh partition. This page provides an overview of the typical workflow in p4est to create and manipulate such a forest to represent the desired mesh topology.

Forest creation

A fundamental step in a typical workflow with p4est is to create a forest of quadtrees or octrees. The p4est library offers the functions p4est_new (2D), p8est_new (3D) and p4est_new_ext (2D), p8est_new_ext (3D) (versions with additional parameters) to create such a forest.

Creating a forest that encodes a partition-independent 2D mesh:

/* user data structure for the data inside each forest leaf */
typedef struct my_user_data {
 int foo;
}
my_user_data_t;
 
/* callback function to initialize the data in each forest leaf */
static void
my_quadrant_init (p4est, which_tree, quadrant) {
 ((my_user_data_t *) quadrant->p.user_data)->foo = *(int *) p4est->user_pointer;
}
 
static int foo = 17489;
void *user_pointer = &foo;
 
forest = p4est_new_ext (mpicomm, connectivity, 0, level, 1,
                        sizeof (my_user_data_t), my_quadrant_init, user_pointer);

mpicomm is an MPI communicator (cf. simple/simple2.c for a usage example).

The highest occurring level of refinement is specified by the level parameter. If it is zero or negative, there will be no refinement beyond the coarse mesh connectivity at this point.

We provide an optional callback mechanism (cf. my_quadrant_init above) to initialize the user data that we allocate inside each forest leaf.

The user_pointer is assigned to the member of the same name in the created forest (before the init callback function is called the first time). This is a way to keep the application state referenced in a forest object.

The resulting forest object in the above example represents a uniform mesh (with the coarse mesh topolgy as encoded in the passed connectivity) refined to the specified level. It is also possible to create a partition-dependent mesh by changing the two parameters set to 0 and 1 in the example above. However, for maximal reproducibility, we recommend to create a partition-independent mesh.

For more details on the function parameters see p4est.h and p4est_extended.h – as always, the 3D equivalents are prefixed with p8est.

Manipulate the forest's refinement structure and partition

There are two types of forest manipulation. The first is to manipulate the mesh that the forest represents and the second is to the manipulate the parallel partition of the forest, i.e. the parallel distribution of the leaves. All forest manipulation functions in p4est manipulate either the mesh or the partition but not both. This means that the functions for changing the refinement structure do not involve MPI communication.

All forest manipulation functions are collective over the MPI communicator passed during the forest creation.

Functions to manipulate forest's refinement structure

• p4est_refine Refinement of specific hypercubes given a refinement criterion, i.e. a user-defined callback function. While it is possible to enable recursive refinement, in practice we set it to non-recursive and loop around the function. This has the advantage that we can repartition in parallel after every iteration.
• p4est_coarsen Coarsen a family of hypercubes given a coarsening criterion, i.e. a user-defined callback function. This function is partition-dependent if families of leaves are split across processes. Partition-independent forests created using p4est_new or p4est_new_ext as described above do not split families among proccesses. In the case that the forest's partition is adjusted, the last call of p4est_partition or p4est_partition_ext must be with allow_for_coarsening activated (cf. the next section) to ensure partition-independent coarsening results.
• p4est_balance Ensure a 2:1 balance of the size differences of neighboring elements in a forest by refining mesh elements. This is accomplished by adding some more refinement where needed.

For all three ways of manipulating the forest's refinement structure the user may pass a callback to initialize the user data of the newly created leaves.

Except of the mentioned special requirements for p4est_coarsen all refinement structure manipulating functions are independent of the forest's partition.

All of the listed functions have a version with extended options declared in p4est_extended.h (2D) and p8est_extended.h (3D).

Function to manipulate the forest's partition

The forest's partition is a parallel, disjoint and linear subdivision of the forest's leaves among the MPI processes. The partition is computed using the Morton curve as space-filling curve.

The functions p4est_new and p4est_new_ext create a uniformly partitioned forest with respect to the leaf count. However, after manipulating the forest's refinement structure, the partition may no longer be uniform. Another reason for manipulating the partition is that the application may desire to partition the leaves according to the work associated with them instead of the leaf count. Manipulating the partition incurs MPI communication since the leaves and their data are shipped.

• p4est_partition Partition the forest in parallel, equally with respect to the leaf count or according to a given user-defined weight per leaf. The parameter allow_for_coarsening can be used to ensure that families of leaves are assigned to the same process – cf. p4est_coarsen.

Examples of forest workflows

Simple examples of typical forest workflows can be found in simple/simple2.c (2D) and simple/simple3.c (3D). A more application-oriented example can be found in steps/p4est_step3.c (2D) and steps/p8est_step3.c (3D). This example shows in particular the handling of leaf data for a simple advection solver.