论文标题
硬核胶体立方体和球之间的快速重叠检测。 OCSI算法
Fast overlap detection between hard-core colloidal cuboids and spheres. The OCSI algorithm
论文作者
论文摘要
在包括计算机科学和物理在内的各种科学学科中，刚性三维对象之间的碰撞是一个非常普遍的建模问题。它涵盖了多面体形状的现实动画，以便计算机视觉转变为简单和复杂流体中热力学和动态特性的描述。例如，通常将特别外来形状的胶体颗粒建模为硬核对象，其碰撞测试是正确确定其相和聚集行为的关键。在这项工作中，我们提出了OpenMP Cuboid Sphere相交（OCSI）算法，以检测岩体或扁平的立方体和球形之间的碰撞。我们通过根据计算机图形和胶体科学中常用的多种算法进行基准标记来调查OCSI的性能：快速拒绝（QRI），快速拒绝交织（QRF）和SIMD流媒体扩展（SSE）。我们观察到QRI和QRF显着取决于特定的立方体各向异性和球体半径，而SSE和OCSI则独立于物体的几何形状保持其速度。尽管OCSI和SSE都基于SIMD并行化，并且表现出极好的性能，但前者提供了更容易访问的编码和用户友好的实现，因为它将OpenMP指令用于自动矢量化。
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 OpenMP Cuboid Sphere Intersection (OCSI) algorithm to detect collisions between prolate or oblate cuboids and spheres. We investigate OCSI's 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 SIMD Streaming Extensions (SSE). We observed that QRI and QRF significantly depend on the specific cuboid anisotropy and sphere radius, while SSE and OCSI maintain their speed independently of the objects' geometry. While OCSI and SSE, 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.
