{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:30:34Z","timestamp":1770820234749,"version":"3.50.1"},"reference-count":56,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T00:00:00Z","timestamp":1614211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2018-415"],"award-info":[{"award-number":["RPG-2018-415"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Collision between rigid three-dimensional objects is a very common modelling problem in a wide spectrum of scientific disciplines, including Computer Science and Physics. It spans from realistic animation of polyhedral shapes for computer vision to the description of thermodynamic and dynamic properties in simple and complex fluids. For instance, colloidal particles of especially exotic shapes are commonly modelled as hard-core objects, whose collision test is key to correctly determine their phase and aggregation behaviour. In this work, we propose the Oriented Cuboid Sphere Intersection (OCSI) algorithm to detect collisions between prolate or oblate cuboids and spheres. We investigate OCSI\u2019s performance by bench-marking it against a number of algorithms commonly employed in computer graphics and colloidal science: Quick Rejection First (QRI), Quick Rejection Intertwined (QRF) and a vectorized version of the OBB-sphere collision detection algorithm that explicitly uses SIMD Streaming Extension (SSE) intrinsics, here referred to as SSE-intr. We observed that QRI and QRF significantly depend on the specific cuboid anisotropy and sphere radius, while SSE-intr and OCSI maintain their speed independently of the objects\u2019 geometry. While OCSI and SSE-intr, both based on SIMD parallelization, show excellent and very similar performance, the former provides a more accessible coding and user-friendly implementation as it exploits OpenMP directives for automatic vectorization.<\/jats:p>","DOI":"10.3390\/a14030072","type":"journal-article","created":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T21:16:53Z","timestamp":1614287813000},"page":"72","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Fast Overlap Detection between Hard-Core Colloidal Cuboids and Spheres. The OCSI Algorithm"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1570-0512","authenticated-orcid":false,"given":"Luca","family":"Tonti","sequence":"first","affiliation":[{"name":"Department of Chemical Engineering and Analytical Science, The University of Manchester, Manchester M13 9PL, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7535-0000","authenticated-orcid":false,"given":"Alessandro","family":"Patti","sequence":"additional","affiliation":[{"name":"Department of Chemical Engineering and Analytical Science, The University of Manchester, Manchester M13 9PL, UK"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ericson, C. (2004). Real-Time Collision Detection, Taylor and Francis.","DOI":"10.1201\/b14581"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Akenine-M\u00f6ller, T., Haines, E., Hoffman, N., and Pesce, A. (2018). Real-Time Rendering, Chapman and Hall\/CRC. [4th ed.].","DOI":"10.1201\/b22086"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.cad.2009.04.010","article-title":"Efficient collision detection using a dual OBB-sphere bounding volume hierarchy","volume":"42","author":"Chang","year":"2010","journal-title":"Comput.-Aided Des."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gottschalk, S., Lin, M.C., and Manocha, D. (1996, January 4\u20139). OBBTree: A Hierarchical Structure for Rapid Interference Detection. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, New Orleans, LA, USA.","DOI":"10.1145\/237170.237244"},{"key":"ref_5","unstructured":"Glassner, A.S. (1990). A simple method for box-sphere intersection testing. Graphic Gems, Academic Press."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/0010-4485(94)90089-2","article-title":"Box-sphere intersection tests","volume":"26","author":"Ratschek","year":"1994","journal-title":"Comput.-Aided Des."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/2151237X.2007.10129232","article-title":"On faster sphere-box overlap testing","volume":"12","author":"Larsson","year":"2007","journal-title":"J. Graph. Tools"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Moore, M., and Wilhelms, J. (1988, January 1\u20135). Collision Detection and Response for Computer Animation. Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, Atlanta, GA, USA.","DOI":"10.1145\/54852.378528"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1016\/j.cad.2008.09.006","article-title":"Efficient algorithm to detect collision between deformable B-spline surfaces for virtual sculpting","volume":"40","author":"Pungotra","year":"2008","journal-title":"Comput.-Aided Des."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1177\/0278364911429335","article-title":"GPU-based parallel collision detection for fast motion planning","volume":"31","author":"Pan","year":"2012","journal-title":"Int. J. Robot. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.amc.2014.10.013","article-title":"Collision detection of convex polyhedra on the NVIDIA GPU architecture for the discrete element method","volume":"267","author":"Govender","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"042079","DOI":"10.1088\/1742-6596\/1213\/4\/042079","article-title":"Collision detection Based on OBB Simplified modeling","volume":"1213","author":"Zhang","year":"2019","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3148","DOI":"10.1109\/TCYB.2016.2573837","article-title":"Neural-learning-based telerobot control with guaranteed performance","volume":"47","author":"Yang","year":"2017","journal-title":"IEEE Trans. Cybern."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1007\/s10586-017-0815-6","article-title":"Collision detection for virtual environment using particle swarm optimization with adaptive cauchy mutation","volume":"20","author":"Zou","year":"2017","journal-title":"Cluster. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1109\/TRO.2017.2750703","article-title":"External Wrench Estimation, Collision Detection, and Reflex Reaction for Flying Robots","volume":"33","author":"Ott","year":"2017","journal-title":"IEEE Trans. Robot."},{"key":"ref_16","first-page":"1","article-title":"Collision detection algorithm for collaborative robots considering joint friction","volume":"15","author":"Xiao","year":"2018","journal-title":"IJARS"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.conengprac.2018.07.004","article-title":"Collision detection and identification for robot manipulators based on extended state observer","volume":"79","author":"Ren","year":"2018","journal-title":"Control Eng. Pract."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Nguyen, M., Zhang, S., and Wang, X.A. (2018). A Novel Method for Risk Assessment and Simulation of Collision Avoidance for Vessels based on AIS. Algorithms, 11.","DOI":"10.3390\/a11120204"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cad.2014.02.001","article-title":"Algorithms for collision detection and avoidance for five-axis NC machining: A state of the art review","volume":"51","author":"Tang","year":"2014","journal-title":"Comput.-Aided Des."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1038\/332822a0","article-title":"Thermodynamic stability of a smectic phase in a system of hard rods","volume":"332","author":"Frenkel","year":"1988","journal-title":"Nature"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"109363","DOI":"10.1016\/j.commatsci.2019.109363","article-title":"HOOMD-blue: A Python package for high-performance molecular dynamics and hard particle Monte Carlo simulations","volume":"173","author":"Anderson","year":"2020","journal-title":"Comput. Mater. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1063\/1.1740207","article-title":"Further results on Monte Carlo Equations of State","volume":"22","author":"Rosenbluth","year":"1954","journal-title":"J. Chem. Phys."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1063\/1.1743956","article-title":"Preliminary Results from a Recalculation of the Monte Carlo Equation of State of Hard Spheres","volume":"27","author":"Wood","year":"1957","journal-title":"J. Chem. Phys."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1208","DOI":"10.1063\/1.1743957","article-title":"Phase Transition for a Hard Sphere System","volume":"27","author":"Alder","year":"1957","journal-title":"J. Chem. Phys."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1111\/j.1749-6632.1949.tb27296.x","article-title":"The effects of shape on the interaction of colloidal particles","volume":"51","author":"Onsager","year":"1949","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1038\/nmat1152","article-title":"Biological synthesis of triangular gold nanoprisms","volume":"3","author":"Shankar","year":"2004","journal-title":"Nat. Mat."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2176","DOI":"10.1126\/science.1077229","article-title":"Shape-Controlled Synthesis of Gold and Silver Nanoparticles","volume":"298","author":"Sun","year":"2002","journal-title":"Science"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1126\/science.1086189","article-title":"Dense Packing and Symmetry in Small Clusters of Microspheres","volume":"301","author":"Manoharan","year":"2003","journal-title":"Science"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1038\/nature08906","article-title":"Lock and key colloids","volume":"464","author":"Sacanna","year":"2010","journal-title":"Nature"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1688","DOI":"10.1038\/ncomms2694","article-title":"Shaping colloids for self-assembly","volume":"4","author":"Sacanna","year":"2013","journal-title":"Nat. Comm."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"5286","DOI":"10.1073\/pnas.1415467112","article-title":"Shape-sensitive crystallization in colloidal superball fluids","volume":"112","author":"Rossi","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2290","DOI":"10.1021\/nl061722c","article-title":"Formation of Rectangularly Shaped Pd\/Au Bimetallic Nanorods: Evidence for Competing Growth of the Pd Shell between the 110 and 100 Side Facets of Au Nanorods","volume":"6","author":"Xiang","year":"2006","journal-title":"Nano Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1489","DOI":"10.1039\/c0nr00130a","article-title":"Uniform and controllable preparation of Au\u2013Ag core\u2013shell nanorods using anisotropic silver shell formation on gold nanorods","volume":"2","author":"Okuno","year":"2010","journal-title":"Nanoscale"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"9103","DOI":"10.1021\/la300407u","article-title":"Multimode Resonances in Silver Nanocuboids","volume":"28","author":"Cortie","year":"2012","journal-title":"Langmuir"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.jqsrt.2015.07.024","article-title":"Au@Ag core\/shell cuboids and dumbbells: Optical properties and SERS response","volume":"167","author":"Khlebtsov","year":"2015","journal-title":"J. Quant. Spectrosc Radiat. Transf."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1038\/nmat1949","article-title":"Anisotropy of building blocks and their assembly into complex structures","volume":"6","author":"Glotzer","year":"2007","journal-title":"Nat. Mat."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1021\/nn204012y","article-title":"Crystalline Assemblies and Densest Packings of a Family of Truncated Tetrahedra and the Role of Directional Entropic Forces","volume":"6","author":"Damasceno","year":"2012","journal-title":"ACS Nano"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1021\/nn4057353","article-title":"Entropically Patchy Particles: Engineering Valence through Shape Entropy","volume":"8","author":"Ahmed","year":"2014","journal-title":"ACS Nano"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nmat4072","article-title":"Entropy-driven formation of large icosahedral colloidal clusters by spherical confinement","volume":"14","author":"Dussi","year":"2015","journal-title":"Nat. Mat."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"4720","DOI":"10.1039\/C7SM00726D","article-title":"Phase behaviour of hard board-like particles","volume":"13","author":"Cuetos","year":"2017","journal-title":"Soft Matter"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1080\/08927022.2017.1402307","article-title":"Monte Carlo simulation of binary mixtures of hard colloidal cuboids","volume":"44","author":"Cuetos","year":"2018","journal-title":"Mol. Sim."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1922","DOI":"10.1039\/C8SM02283F","article-title":"Biaxial nematics of hard cuboids in an external field","volume":"15","author":"Cuetos","year":"2019","journal-title":"Soft Matter"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"052702","DOI":"10.1103\/PhysRevE.101.052702","article-title":"Dynamics of hard colloidal cuboids in nematic liquid crystals","volume":"101","author":"Cuetos","year":"2020","journal-title":"Phys. Rev. E"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"5565","DOI":"10.1039\/D0SM00484G","article-title":"Self-assembly of Freely-rotating Polydisperse Cuboids: Unveiling the Boundaries of the Biaxial Nematic Phase","volume":"16","author":"Corbett","year":"2020","journal-title":"Soft Matter"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/2.809248","article-title":"Internet Streaming SIMD Extensions","volume":"32","author":"Thakkar","year":"1999","journal-title":"Computer"},{"key":"ref_46","unstructured":"Van der Pas, R., Stotzer, E., and Terboven, C. (2017). Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD, MIT Press."},{"key":"ref_47","unstructured":"(2021, February 25). Intel Advanced Vector Extensions Programming Reference, Ref # 319433-011. Available online: www.intel.com."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Schneider, R. (1993). Minkowski addition. Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press. Chapter 3.","DOI":"10.1017\/CBO9780511526282"},{"key":"ref_49","unstructured":"Intel\u00ae Corporation (2021, February 25). Intel\u00ae C++ Compiler Classic Developer Guide and Reference. Available online: https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/documentation\/cpp-compiler-developer-guide-and-reference\/top.html2020."},{"key":"ref_50","unstructured":"Stallman, R.M., and the GCC Developer Community (2021, February 25). Using the GNU Compiler Collection, for gcc version 10.2.0. Available online: https:\/\/gcc.gnu.org\/onlinedocs\/gcc-10.2.0\/gcc\/."},{"key":"ref_51","unstructured":"OpenMP Architecture Review Board (2021, February 25). OpenMP Application Programming Interface Version 4.5. Available online: https:\/\/www.openmp.org\/wp-content\/uploads\/openmp-4.5.pdf."},{"key":"ref_52","unstructured":"Frenkel, D., and Smit, B. (1996). Monte Carlo Simulations. Understanding Molecular Simulation-From Algorithms to Applications, Academic Press. Chapter 3."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"4731","DOI":"10.1007\/s11227-019-03057-4","article-title":"Vectorizing programs with IF-statements for processors with SIMD extensions","volume":"76","author":"Sun","year":"2020","journal-title":"J. Supercomput."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi Diagrams\u2014A Survey of a Fundamental Geometric Data Structure","volume":"23","author":"Aurenhammer","year":"1991","journal-title":"ACM Comput. Surv."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"346","DOI":"10.3906\/elk-1805-143","article-title":"Convex polygon triangulation based on planted trivalent binary tree and ballot problem","volume":"27","author":"Selimi","year":"2019","journal-title":"Turk. J. Elec. Eng. Comp. Sci."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1315","DOI":"10.1080\/00207160.2013.837894","article-title":"Decomposition of Catalan numbers and convex polygon triangulations","volume":"91","author":"Krtolica","year":"2014","journal-title":"Int. J. Comput. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/72\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:28:34Z","timestamp":1760160514000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,25]]},"references-count":56,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030072"],"URL":"https:\/\/doi.org\/10.3390\/a14030072","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,25]]}}}