|
p4est
2.8.7
p4est is a software library for parallel adaptive mesh refinement.
|
An overview of the local and remote search routines in p4est.
During mesh-based simulations it may be desired to match multiple user-defined queries with leaves of the forest. Next to a volume iteration over all leaves using p4est_iterate, p4est also offers several functions for depth-first, top-down tree traversal of multiple query points at once in p4est_search.h (2D) and p8est_search.h (3D), which allow to efficiently prune large regions from the search early on. p4est_search_local (resp. p8est_search_local in 3D) searches a set of user-defined query points in the local part of the forest. p4est_search_partition (not mentioning the 3D equivalents from here on for brevity) searches query points in the forest's partition and assigns them to intersecting processes. It can be used to organize a parallel search of distributed sets of queries unrelated to the partition of the mesh elements.
This feature is immensely powerful when a distributed point cloud, or the contents of a massive parallel input file, are to be matched efficiently with the elements of a parallel mesh. This functionality can be used to send the points to their matching processes in a decentralized point-to-point, scalable manner. Please see the associated paper for details.
We abstract the search functionality by intersecting points with quadrants. The quadrant is an inner node or a leaf of the refinement tree, and a point can be anything: an actual point in space, a search region, a geometric object, or any other concept that may intersect a quadrant. The user passes an array of points, formulated as anonymous pointers, to the toplevel search routines, which make them available to user-defined callback functions (cf. p4est_search_local_t).
A single point may match with multiple quadrants (in fact it must when considering the ancestors of a leaf quadrant that it resides in). A point may have non-zero volume, extent or shape which overlaps more than one, and even a large number, of mesh quadrants.
It is up to the user to define the point-quadrant intersection function. The p4est library does not perform any interpretation and does not require any explicit information about a point.
To search the local part of the forest, p4est_search_local can be called on an array of user-defined query points. Additionally, it receives user-defined quadrant and point callbacks of type p4est_search_local_t.
The search traverses all local quadrants by proceeding recursively top-down. For each tree, it may start at the root of that tree, or further down at the root of the subtree that contains all of the tree's local quadrants. The quadrant callback is executed whenever a quadrant is entered and once when it is left. If the callback returns false, the current quadrant and its descendants are excluded from further recursion. If the quadrant callback returns true, the point callback is executed for every potentially matching point and shall return true for any matching point. If it returns false, the point is discarded for the current branch. The set of points that potentially match a given quadrant diminishes from the root down to the leaves. If no points remain, the recursion stops. The point callback is allowed to return true for the same point and more than one quadrant; in this case more than one matching quadrants may be identified. The callback may use an efficient, over-inclusive test for ancestor quadrants, see, for example, spheres/spheres2.c. Only on leaves it must return exact results.
There are several variants of the local search, which allow to customize it to one's needs, e.g. by reordering or subsetting the child quadrants before entering the recursion using p4est_search_reorder.
To search points in the global partition of a parallel distributed forest, p4est_search_partition can be called on an array of user-defined query points. Similar to the local search, it receives user-defined quadrant and point callbacks of type p4est_search_partition_t.
The search traverses the global partition top-down, for multiple points at once if so desired, calling the quadrant and point callbacks on a quadrant as described for the local search. The recursion only goes down branches that are split between multiple processors. The partition search operates completely without communication. It can be used to map parallel distributed sets of query points to the processes whose local mesh they intersect. Based on the actions performed in the intersection callback, the user may proceed for example to communicate with the matching process for any point. The reciever of a point can then continue with a local search to identify one (or more) mesh elements that the point intersects. An example of this parallel search workflow using non-blocking point-to-point communication on the user side can be found in spheres/spheres2.c.
If the forest to be searched is not available locally at all, e.g. because it resides on an entirely different communicator, the partition search can be performed on an array of global first positions, which encodes the partition boundaries, by calling the variant p4est_search_partition_gfp.
There are several examples in 2D and 3D using the search. In particles/particles2.c and particles/particles3.c the query points are proper points, which move through the domain and are tracked through parallel distributed searches. In spheres/spheres2.c and spheres/spheres3.c the query points are spheres that match any quadrant intersecting their surface (but not their interior).