# Fast Overlap Detection between Hard-Core Colloidal Cuboids and Spheres. The OCSI Algorithm
## 2 Algorithms
OCSI proved to be efficient for the most two common compilers, for two different programming languages and for two different instruction sets, SSE and AVX, highlighting its versatility with respect to SSE-intr. ## 5 Conclusions

In summary, we have benchmarked four different collision-detection algorithms that check the occurrence of overlaps between one cuboid and one sphere. Our analysis focused on a specific acceptance ratio, which is within the usual range applied to efficiently sample the configuration space of hard-core systems in Monte Carlo simulations [52]. We notice that SSE-intr has been previously tested for different acceptance ratios and did not show relevant changes in performance [7]. A similar tendency is also expected for OCSI, but should be confirmed by further tests. While QRI and QRF are observed to be geometry-dependent, SSE-intr and OCSI are basically insensible to the cuboid anisotropy and sphere radius and, thanks to automatic vectorization, they are also significantly faster. According to these results, we expect OCSI and SSE-intr run-times to be constant also for bigger spheres, while QRI and QRF run-times can show a different behaviour than the ones observed so far. To ascertain these tendencies, further tests should be performed. In particular, the OCSI algorithm proved to be especially valuable in terms of performance and simplicity of implementation in both C and F90. Intel (r)compilers and GNU Compilers were not able to automatically vectorize QRI and QRF. Anyway, there are ways to perform conditional statements like the ones used in the quick rejection test implementing SIMD parallelism [53]. Whether or not vectorized versions of QRF and QRI are possible and, if so, how efficient they would be as compared to the current versions requires further study. It should be stressed that the method applied to generate the sphere around the cuboid is crucial to provide a robust comparison between different algorithms. The choice of the spherocuboid as a sampling volume allows to precisely set the desired acceptance ratio and guarantees that the algorithms are tested for all the possible positions of the sphere around or inside the cuboid. This is especially relevant to fairly assess the performance of QRI and QRF, due to their use of quick rejection tests. In Monte Carlo simulations, where the generation of configurations follows a different procedure, the performance of collision-detection algorithms, most likely affected by the degree of system order and packing, should be tested. Finally, it is important to mention that the OCSI algorithm allows for the calculation of the cuboid-sphere minimum distance, hence suggesting a future study to determine a suitable interaction potential beyond mere hard-core interactions. The formal proof reported here can also be useful to test the intersection of cuboids with particles of different shape. As a final note, we stress that our algorithm has been only tested for specific pairs of geometries (cuboids and spheres), while it might be relevant, in computational colloid science as well as in computer graphics, to assess its performance with other geometries. We are currently working on extending our algorithm to detect collisions between cuboids and oblate or prolate spherocylinders. It would also be especially interesting to investigate to what extent our methodology could be applied to more complex geometries, whose collision is generally detected by more sophisticated decomposition techniques, such as e.g., Voronoi diagrams [54] or convex polygon triangulations [55; 56]. We hope that our contribution might stimulate further research in this direction. The source code of the program for the optimisation of the spherocuboid volume, the C/C++ and F90 benchmark programs and the raw data required to reproduce our findings can be downloaded at [[http://dx.doi.org/10.17632/w7g3](http://dx.doi.org/10.17632/w7g3) ynkcfn.2]([http://dx.doi.org/10.17632/w7g3](http://dx.doi.org/10.17632/w7g3) ynkcfn.2). Conceptualization, A.P. ; methodology, L.T. ; software, L.T.