基于Minkowski差构造技术的凸体碰撞检测算法

摘要

碰撞检测是自然环境计算机模拟的基础,在计算机图形、CAD/CAM、机器人等领域有着广泛的应用。笔者提出了一个用于具有曲面边界凸体的碰撞检测的算法,通过构造两个凸体的Minkowski差来快速的检测两个凸体是否碰撞。当两个凸体碰撞时,算法可以快速地报告物体碰撞,并可以给出在给定方向上的穿透距离;当两个物体分离时,算法报告物体的分离,同时可以给出在给定方向上的移动距离。与已有的算法相比,这个算法可以更平衡地处理碰撞、分离的情况,该算法给出了稳定的碰撞检测条件。