# Fast Overlap Detection between Hard-Core Colloidal Cuboids and Spheres. The OCSI Algorithm
## 1 Introduction  
Employing computer programs and algorithms to generate 2D or 3D images is referred to as rendering. Rendering is a topic of striking relevance in computer graphics with practical impact on many heterogeneous disciplines, spanning engineering, simulators, video games and movie special effects. Collision detection and collision determination are key elements of rendering as they determine the distance between two objects and their possible intersection [1]. Due to their widespread use in video representation of time-evolving systems, with tens of frames displayed per second, algorithms for rendering are expected to be very efficient [2, 3]. Generally, to assess whether two complex objects collide, the distance between their respective bounding volumes is evaluated first. Common bounding volumes are cuboidal boxes, whose axes might or might not be aligned, or spheres. Due to their simple geometry, the collision between cuboids and/or spheres is computationally easier [4, 5, 6, 7], thus enhancing the speed and efficiency of the overall rendering process [2]. Collision detection algorithms are of utmost relevance in many heterogeneous applications spanning computer graphics for shape modelling and video games [8, 9, 10, 11, 12], robotics to prevent potential collisions in man-robot interactions [13, 14, 15, 16, 17], risk assessment associated to vessel collision [18] or machining of sculptured surfaces [19], and simulations of molecular or particle systems to estimate their thermodynamic properties [20, 21]. Collision algorithms have also been key to address the thermodynamics of liquid and solid phases and their phase transition by early molecular simulation studies thatemployed the hard-sphere model [22; 23; 24]. More recently, and following the seminal theory by [PERSON] on the isotropic-to-nematic transition of hard rods [25], they were fundamental to confirm the crucial role of excluded volume effects in the formation of colloidal liquid crystal phases of anisotropic particles [20]. Realising the practical impact of the particle shape on the design of nanomaterials triggered the blooming of biosynthetic [26], chemical [27] and physical [28] experimental routes to manufacture precise building blocks with ad hoc properties, including lock-and-key particles [29], fused spheres [30], superballs [31] and cuboids [32; 33; 34; 35]. The appearance of these exotic shapes unveiled a realm of novel opportunities in nanomaterials science by offering an increasingly varied selection of morphologies for state-of-the-art applications spanning medicine (controlled drug delivery), smart materials (self-healing coatings) and photonics (light detection), among others. Often anticipating experimental evidence, computer simulations have significantly contributed to our comprehension of the effect of particle shape and interaction at the nanoscale on the material properties at the macroscale [36; 37; 38; 39]. Understanding the fundamentals of such a complex correlation, which develops over orders of magnitude in length and time scales, dramatically depends on the existence of reliable force fields mimicking the interactions between particles. This is not always the case for most exotic particle shapes, whose force field is assumed to be described by mere excluded volume effects and thus only incorporates a hard-core interaction potential. Consequently, efficient and robust algorithms able to detect collisions and intersections between objects become essential to extract structural, thermodynamic and dynamic properties of such systems from a molecular simulation. In colloid science, cuboids are especially intriguing building blocks that can form a rich variety of liquid crystal phases [40; 41; 42; 43; 44]. Incorporating guest spherical particles in these phases is relevant to understand phenomena of diffusion in crowded environments that display a significant degree of ordering.