# Overset Grid Assembler and Flow Solver with Adaptive Spatial Load Balancing
## 5 Core Algorithm
```
foreachMesh-block \(M_{i}\)do foreachTree \(T_{j}\) where \(j\
eq i\)do foreachMesh-cell \(c_{i}\) in \(M_{i}\)do  Query-point qp = centroid of \(c_{i}\);  array[ID],..., ID\({}_{n}\) = \(T_{j}\).search(qp); foreachID in arraydo if\(M_{j}\).cell(ID).polyhedron contains qpthen  Add \(M_{j}\).cell(ID) to the list of candidate donors of \(c_{i}\);
```  
**Algorithm 1** Donor search using ADT  
In the first time step, ADT is used for the donor search. In subsequent time steps, the donor search is performed with a stencil walk algorithm if the cell had a donor in the previous time step; otherwise, ADT is used as in the first time step. Referring to Figure 4, the stencil walk algorithm starts with choosing a starting or seed cell (shaded) and walking toward the query point (marked with a cross) by using cell-to-cell connectivity. First, a search line is drawn between the centroid of the seed cell and the query point. The search line is tested for intersection by the faces of the seed cell. The current cell (which was  
Figure 3: Insertion of points into a 2D ADT. Black and white filled circles indicate partitioning of domain in the \(x\)- and \(y\)-axis. initially the seed cell) is updated to be the neighbor cell which shares the intersected face. When the current cell is near a boundary and, therefore, has no neighbor which shares the intersected face, all other faces of that boundary are tested for intersection by the search line. If an intersected boundary face is found, the current cell is updated to be the interior cell of that boundary. If no other boundary face is found, then the algorithm stops indicating that no cell containing the query point is found. When none of the faces of the current cell intersects the search line, the current cell is added to the list of candidate donor cells. The reason for using the stencil walk algorithm in subsequent time steps is the absence of seed cells in the first time step. For receptors, the seeds are chosen to be the centroid of donor cells. For other cell types, seeds are not available and, therefore, as mentioned, ADT is used for the donor search. Since the stencil walk algorithm involves costly geometric intersections tests, a high number of walks is avoided by not picking random seed cells and using ADT whenever proper seed cells are not available. After the donor search, if no candidate donor cell is found for a mesh cell, the query point is either outside of \(M_{j}\) or inside a hole (if one exists) in \(M_{j}\). If \(M_{j}\) has a hole, and if the query point is inside any of the bins of hole map of \(M_{j}\), then the mesh cell is labeled as hole cell. Once a mesh cell is labeled as a hole cell, its type cannot be changed regardless of interaction of the mesh cell with other mesh blocks. Otherwise, if the mesh cell is not a hole cell, it is labeled as field cell. If a candidate donor cell is found and the volume of the query cell is larger than that of the candidate donor cell, then the mesh cell is labeled as receptor cell. A receptor cell may have multiple candidate donor cells. In this case, the candidate donor cell which has the smallest volume is assigned as the donor of the mesh cell. If the mesh cell has a smaller volume than a candidate donor cell, the mesh cell is labeled as a field cell. The reason for choosing the cell with smaller volume is to represent the domain with the highest resolution possible. Another option is to choose the cell closest to respective boundary. This kind of selection is beneficial in preserving boundary layer cells. The cells which have a hole neighbor or are located next to an intergrid boundary are labeled as mandatory receptor cells. These receptor cells serve as intergrid boundary conditions. The volume of intersection between mesh blocks can be reduced in order to save time by avoiding redundant interpolation of variables from donors to receptors. Minimization of the overlapped region is performed by excluding receptors having no field neighbor from the flow solution.