# Fast Overlap Detection between Hard-Core Colloidal Cuboids and Spheres. The OCSI Algorithm
## 2 Algorithms
```
1:functionQRF(\(\mathbf{r_{SC}},R,\hat{\mathbf{e_{T}}},\hat{\mathbf{e_{L}}},\hat{\mathbf{e_{W}}},c_{T},c_{L},c_{W}\))
2:\(d\gets 0\)\(\triangleright\) initialising minimum distance
3:for\(i\in\{T,L,W\}\)do
4:\(a_{i}\leftarrow\mathbf{r_{SC}}\cdot\hat{\mathbf{e_{i}}}\)
5:if(\(a_{i}<-c_{i}-R\)or\(a_{i}>c_{i}+R\))return\(false\)\(\triangleright\) quick rejection test
6:endfor
7:for\(i\in\{T,L,W\}\)do
8:if(\(a_{i}<-c_{i}\))then
9:\(l\gets a_{i}+c_{i}\)
10:\(d\gets d+l^{2}\)
11:elseif(\(a_{i}>c_{i}\))then
12:\(l\gets a_{i}-c_{i}\)
13:\(d\gets d+l^{2}\)
14:endif
15:endfor
16:if(\(d\leq R^{2}\))return\(true\)\(\triangleright\) checking overlap
17:return\(false\)
18:endfunction
```  
**Algorithm 3** QRF  
The different location of the quick rejection tests in QRI and QRF is expected to determine a difference in the efficiency of the two algorithms, which is analysed in detail in Section 4. Additionally, QRI and QRF quick rejection tests depend on both \(c_{i}\) and \(R\), so these algorithms' efficiency are expected to be influenced also by sphere and cuboid geometry. Finally, keeping in mind the potential application in computational colloid science, where crowded systems are usually simulated, the efficiency of QRI and QRF is also influenced by the system packing, which determines the probability for an attempted move to produce an overlap. [PERSON] et al. also proposed a parallel version of Algorithm 1, generalised for randomly oriented cuboids and using SSE intrinsic functions (SSE-intr) [7]. SSE is an instruction set available in x86 architectures; it uses 128-bit registers to process simple instructions on multiple data in parallel [45]. By substituting the _if_ statements in lines 8 and 11 of Algorithm 3 to compute the minimum distance, with the _max_ and _min_ functions available in SSE instruction set, the computation of the minimum distance can be vectorized. This algorithm, running in parallel and thus significantly faster than QRI and QRF, does not need quick rejection tests. A pseudocode for this algorithm, here named after the SSE instruction set, is presented in Algorithm 4 for the general case of randomly oriented cuboids. ```
1:function\(\text{SSE}(\mathbf{r_{\text{SC}}},R,\hat{\mathbf{e}}_{\text{T}},\hat{\mathbf{e}}_{\text{L}}, \hat{\mathbf{e}}_{\text{W}},c_{T},c_{L},c_{W})\)
2:for\(i\in\{T,L,W\}\)do
3:\(a_{i}\leftarrow\mathbf{r_{\text{SC}}}\cdot\hat{\mathbf{e}}_{\text{i}}\)\(\triangleright\) vectorising the dot product
4:endfor
5:for\(i\in\{T,L,W\}\)do\(\triangleright\) vectorising the cycle
6:\(l_{i}\leftarrow\min(a_{i}+c_{i},0)+\max(a_{i}-c_{i},0)\)
7:\(l_{i}\gets l_{i}^{2}\)
8:endfor
9:if\((l_{T}+l_{L}+l_{W}\leq R^{2})\)return\(true\)\(\triangleright\) checking overlap
10:return\(false\)
11:endfunction
```  
**Algorithm 4** SSE-intr  
Finally, we present our own algorithm, which incorporates a number of elements providing additional efficiency when compared to Algorithms 1, 2 and 3, and versatility when compared to Algorithm 4. A new element that significantly simplifies the algorithm is the use of the absolute value to estimate the minimum distance. In addition, we employed OpenMP directives for an SIMD parallelization of the two loops, one over the computation of the dot products of the distance of the centres of mass of the two particles with the orientation of the cuboid, and the other over the computation of the minimum distance, without using SSE intrinsic instructions. OpenMP is an application programming interface specification composed of compiler directives, library routines and environment variables for parallel programming in Fortran and C/C++. From version 4.0, it provides mechanisms to assist SIMD parallelization of loops [46]. The advantage of avoiding explicit SIMD vectorization is the possibility to vectorize the algorithm using different instruction set architectures, such as the more modern Advanced Vector Extensions (AVX) instruction set [47], by simply changing compiler settings during compilation.