基于矩形包围盒的多边形碰撞检测算法

• 作者: 吴介一 周之平 张飒兵 白伟冬
• 来源期刊: 中国图象图形学报
• 学科: 工学
• 关键词: 简单多边形 包围盒 预检测 碰撞检测
• 年，卷（期）: 2004,（11）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 1294-1303
• 页数: 10页
• 分类号: TP391.41|TP391.72
• 字数: 9580字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8961.2004.11.005

摘要

碰撞检测是计算机图形学领域中的一个普遍存在的问题.为了提高多边形碰撞检测的效率,针对简单形式刚性运动的多边形对象,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法.该算法基于坐标轴的单调性对多边形进行分割,并通过矩形包围盒之间的预检来减少无关边对的相交测试,以加速算法的终止.由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量,所以,经过少量的"边-边"相交判断就能求解到所有交点,同时能快速地获得两多边形干涉发生的第1位置.试验表明:(1)对于一般多边形,该算法的复杂度也远远低于O(NP×NQ);(2)对于凸多边形对象,该算法的复杂度为O(NP+NQ),其中NP,NQ为多边形P,Q的顶点数.由此可见,算法能够获得较好的运算效率.