Tutorial: Search

Search

In this tutorial we discuss t8code's search algorithm. You will find the code to this example in example/tutorials/t8_tutorial_search.cxx and it creates the executable example/tutorials/t8_tutorial_search.

We assume that you know how to generate a coarse mesh and an adapted forest on it. If not, please read Step 1, Step 2 and Step 3.

The purpose of search is to efficiently identify a subset of elements that match given conditions and to execute callback functions for these elements.

Examples of this feature include:

• Identifying the elements at the domain boundary.
• Finding elements that contain particles.
• In a weather simulation identify all elements that contain a hurricane.

In this tutorial we will create random particles inside our mesh, then use search to find those elements that contain particles and count for each element how many particles it contains.

Due to the tree-based structure of t8codes meshes, the search is performed hierarchically from the coarsest level down to the elements, checking on each level whether or not to continue the search. This way, we can exclude whole portions of the mesh from the search early on and thus have a significant performance advantage compared to linearly searching through all elements as would be necessary with unstructured meshes. You can see in the output of the executable that the number of searched elements is significantly smaller than the actual number of elements.

Callback functions and queries

In each (process local) tree of the forest, search will create the level 0 element that coincides with the tree and call the search-callback function on it. In the callback we decide whether to continue the search or not. If we continue the search, the children of this level 0 element are created and the search callback will be called for them -- again deciding whether to continue or not. This process repeats recursively and stops at those fine elements that are actually contained in the forest (leaf elements).

Additionally, the search algorithm can be given an array of 'queries' and a query-callback. These queries can be arbitrarily defined data. In our case this will be the array of particles. If queries and a query-callback are provided, then for each element first the search-callback is called to decide whether or not to continue searching. If it returns true, the query-callback will be called once for each active query object. If the query object returns 0, this query object will get deactivated for this element and its recursive children. The recursion stops when no queries are active anymore (independently of the return value of the per element callback).

Particles

We want to create random particles in the mesh and search for the elements containing them. A particle is just a point in 3D.

typedef struct
{
  double              coordinates[3];   /* The coordinates of our particle. */
} t8_tutorial_search_particle_t;

In t8_tutorial_search_build_particles we build an sc_array of num_particles many particles with random coordinates in a certain subregion of our mesh.

This array will be passed to search as our queries and for each element the active queries are those particles that are contained inside the element.

We also want to count for each element how many particles it contains and how many elements we searched in total. Thus, we build a user data struct

typedef struct
{
  sc_array           *particles_per_element;    /* For each element the number of particles inside it. */
  t8_locidx_t         num_elements_searched;    /* The total number of elements created. */
} t8_tutorial_search_user_data_t;

that we will pass onto our search callback. The particles_per_element array will be allocated to hold as many integers as we have (process local) elements.

The callbacks

Our two callbacks are now as follows:

The element callback

The per element callback that is called once for every searched element and returns true if the recursion should continue with the element's children. In our case, we want to continue as long as we have particles left that may be contained in the element. Since the recursion will stop automatically when we have no active queries, we can always return true in the element callback.

We use our user data to count the searched elements.

static int
t8_tutorial_search_callback (t8_forest_t forest,
                             t8_locidx_t ltreeid,         // The current tree
                             const t8_element_t *element, // The element to be searched
                             const int is_leaf,           // True if the element is a leaf (an actual element in our forest)
                             t8_element_array_t *leaf_elements, // The leafs in the forest that are descendants (arise from recursive refining) of element
                             t8_locidx_t tree_leaf_index, // The tree local index of the first leaf in leaf_elements
                             void *query,                 // The current query (NULL in element callback mode)
                             size_t query_index)          // The index of the current query in the query array (invalid in element callback mode)
{
  T8_ASSERT (query == NULL);

  /* Get a pointer to our user data and increase the counter of searched elements. */
  t8_tutorial_search_user_data_t *user_data =
    (t8_tutorial_search_user_data_t *) t8_forest_get_user_data (forest);
  T8_ASSERT (user_data != NULL);
  /* Count this element */
  user_data->num_elements_searched++;
  /* Continue the search */
  return 1;
}

should be se