一种快速精确的连续碰撞检测算法.pdf

为了实现运动刚体间快速精确的碰撞检测,提出了一种新的连续碰撞检测算法.利用图形硬件的计算能力,该算法在每个时间区间上实时处理,把单个时间区间划分成若干个子时间区间,使用静态和连续的定向包围盒(OOB)相交性检测方法,计算出在子时间区间内的潜在碰撞集(PCS),并结合基于图形硬件的可靠碰撞剔除方法,三角面片之间的碰撞检测方法和回退方法,计算出刚体间的初始碰撞时刻和碰撞位置.并应用于一个三维建模系统中的装配模块.实验结果表明,与传统的碰撞检测方法相比,该算法可以缩短计算时间,具有更好的性能和精度. 浙江大学学报工学版第40卷第6期 黄通浪 唐敏 董金祥 随着计算机图形学和虚拟现实技术的发展，碰撞检测在游戏开发、机器人控制、物理仿真等领域变得尤为重要。碰撞检测算法能够有效地判断在虚拟环境中，运动物体之间是否存在交互。本文提出了一种新型的连续碰撞检测算法，该算法充分利用了图形硬件的计算能力，实现在多个时间区间的实时处理，并通过一系列优化方法，显著提升了碰撞检测的速度与精确度。 算法的核心思想是在每个时间区间上进行实时处理。为了提升效率，它将每个时间区间进一步划分为若干个子时间区间。在这些子区间内，算法使用了静态和连续的定向包围盒（OOB，Oriented Bounding Boxes）相交性检测方法。这种层次化的结构允许系统快速识别出可能发生碰撞的物体，然后生成所谓的潜在碰撞集（PCS，Potential Collision Set）。通过这种方式，算法能够有效地缩小需要进一步细致检测的物体数量。 针对这些潜在碰撞集，算法结合了基于图形硬件的可靠碰撞剔除方法。这种剔除方法利用图形处理单元（GPU）的并行计算优势，可以快速地计算三角面片之间的碰撞情况，并剔除不会发生碰撞的组合。这一步骤对于减少后续计算量至关重要，因为它保证了在有限的时间内只对可能发生碰撞的面片进行更细致的检测。 除此之外，算法还采用了三角面片之间的碰撞检测方法和回退方法。这些方法进一步细化了碰撞检测的精度，确保了算法即使在高速运动的刚体之间也能够准确判断碰撞发生的时间点和位置。回退方法则是在发生碰撞后，计算双方刚体的初始碰撞时刻和精确位置。 本文所提出的算法已经在三维建模系统中的装配模块上得到了实际应用。通过实验与传统碰撞检测方法的比较，该算法显著缩短了计算时间，并且在性能和精度上都有显著的提高。 在标签方面，文章主要涉及到了碰撞检测、刚体、硬件加速这三个核心概念。其中，硬件加速指的是通过使用图形硬件（如GPU）来进行计算加速的实践。这种加速方法特别适用于图形密集型的应用，如虚拟现实（VR）、增强现实（AR）以及需要大规模物理计算的场景。 在碰撞检测领域，高效准确的算法一直是研究的热点。传统的碰撞检测方法通常采用穷举所有可能的物体间碰撞对进行检测，这种方法在面对大规模物体或者高速运动物体时，会导致计算量剧增，影响系统的实时性和精确度。为了克服这些限制，研究人员不断地探索新的算法和技术，例如层次包围盒树（如BVH，Bounding Volume Hierarchy）、空间划分技术、时间膨胀技术和GPU加速等，本文的算法是这些研究方向中的一项重要贡献。 图形硬件加速在碰撞检测中的应用，允许利用图形处理器的强大并行处理能力，以实现同时处理成千上万个顶点和面片的数据。GPU加速技术不仅提高了碰撞检测的效率，还因为其可以处理的并行级别，使得算法在处理大量数据时变得更加高效。 通过将以上概念和方法整合进一个具体的算法框架中，研究者们能够为不同的应用场景提供定制化的碰撞检测解决方案，提高系统的响应速度，同时保证了碰撞检测的精确性。这对于那些对实时性和交互性要求极高的领域，如游戏、机器人模拟、自动装配线等领域，无疑是一个巨大的进步。