# OGSM: A Parallel Implicit Assembly Algorithm and Library for Overlapping Grids
## 3 Parallel Implicit Assembly Method
### Parallel Hole-Cutting Based on Two-Step Nodes Classification Scheme
#### 3.3.1 Preliminary Screening Step: Wall Distance Calculation  
Figure 6 illustrates the wall distance parameters \(ds\) and \(dt\) for an arbitrary node \(p\in N^{i}\) of source grid \(SG\). \(ds\) and \(dt\) are defined as  
\[ \begin{cases}ds(p)=d(p,N^{i}_{w})\\ dt(p)=\min\{d(p,N^{1}_{w}),d(p,N^{2}_{w}),\cdots,d(p,N^{L}_{w})\}\end{cases}  \tag{7}\]  
Figure 5: Schematic diagram of spatial separation plane algorithm. where \(ds\) denotes the distance from \(p\) to the wall boundaries of \(SG\), and \(dt\) denotes the distance from \(p\) to the wall boundaries of the \(L\) target grids that may overlap with \(SG\). The two preliminary screening conditions are as follows:  
* _Distance screening condition SC1_. If the distance of a grid node \(p\in N^{i}\) to its own component is less than that to any other components (i.e., \(ds<dt\)), then node \(p\) is an active node. * _Coverage screening condition SC2_. If grid node \(p\) is not surrounded by the minimal external box of any other component grid, it can neither be covered by the corresponding donor cells nor be surrounded by the solid wall boundaries. We utilize the box-splitting technique to efficiently calculate the crucial parameters \(ds\) and \(dt\) relevant to \(SC1\). **(a) Construction of box sequence. **  
The boxes surrounding all the nodes on the solid-wall boundaries can be constructed with the following four steps. 1. For the \(\kappa\) solid-wall nodes \(N^{i}_{w}\), the upper and lower bounds can be calculated as \[ \begin{cases}x_{max}=\max\{x_{0},x_{1},\cdots,x_{\kappa-1}\}\\ x_{min}=\min\{x_{0},x_{1},\cdots,x_{\kappa-1}\}\\ y_{max}=\max\{y_{0},y_{1},\cdots,y_{\kappa-1}\}\\ y_{min}=\min\{y_{0},y_{1},\cdots,y_{\kappa-1}\}\\ z_{max}=\max\{z_{0},z_{1},\cdots,z_{\kappa-1}\}\\ z_{min}=\min\{z_{0},z_{1},\cdots,z_{\kappa-1}\}\\ \end{cases} \] (8) These six spatial planes determine the root box \(B^{0}\), which is also treated as the current candidate box \(B^{c}\). 2. The ranges of the current candidate box \(B^{c}\) in the \(x\), \(y\) and \(z\) directions are calculated as \[ \begin{cases}\delta x=x_{max}-x_{min}\\ \delta y=y_{max}-y_{min}\\ \delta z=z_{max}-z_{min}\\ \end{cases} \] (9) Without loss of generality, we assume \(\delta z<\delta y<\delta x\) and sort the solid-wall nodes in \(B^{c}\) according to the \(x\)-coordinate. Along the direction with the largest range, we adopt  
Figure 6: Illustration of distance from a given node to solid wall boundaries. the bisection method to split \(B^{c}\) into two subsets. The nodes \(N_{w}^{c}\) relevant to \(B^{c}\) are correspondingly split into two subsets, i.e., \(N_{w}^{i_{0}}\) and \(N_{w}^{i_{1}}\). 3. To minimize the number of solid wall nodes bounded by the box \(B^{c}\), the operation of step (2) is recursively performed until the the number of elements in \(N_{w}^{i_{s}}\) is greater than \(\sqrt{\kappa}\). 4. When all the candidate boxes cannot be further split, the bottom leaves of the box-tree are collected and form cuboid capsules \(S^{i_{m}}(0<m<floor(\sqrt{\kappa}))\), which can be constructed using the spatial planes of \[ \begin{cases}x=x_{max}^{m},&x=x_{min}^{m}\\ y=y_{max}^{m},&y=y_{min}^{m}\\ z=z_{max}^{m},&z=z_{min}^{m}\end{cases} \] (10)  
**(b) Obtaining the closest wall distance**  
For an arbitrary node \(p\in N^{i}\), the closest wall distance can be quickly obtained with the following four steps. 1. Calculate the distance from \(p\) to each cuboid capsule \(S^{i_{m}}\). Figure 7 shows a schematic of \(d(p,S^{i_{m}})\), where the coordinates of \(p\) are \((x,y,z)\) and the center of \(S^{i_{m}}\) is located at \((x_{c},y_{c},z_{c})\). The distance \(d(p,S^{i_{m}})\) can be calculated as \[d(p,S^{i_{m}})=\sqrt{f^{2}(x,x_{c},\delta x)+f^{2}(y,y_{c},\delta y)+f^{2}(z, z_{c},\delta z)}\] (11) where \[f(\xi,\eta,\zeta)= \begin{cases}\xi-\eta-\dfrac{\zeta}{2},&if(\xi-\eta\geq \dfrac{\zeta}{2})\\ 0,&if(-\dfrac{\zeta}{2}<\xi-\eta<\dfrac{\zeta}{2})\\ \eta-\xi-\dfrac{\zeta}{2},&if(\xi-\eta\leq-\dfrac{\zeta}{2})\end{cases}