| 基于矩形包围盒的多边形碰撞检测算法 |
| |
| 作者姓名： | 周之平 张飒兵 吴介一 白伟冬 |
| |
| 作者单位： | 东南大学CIMS中心 南京210096
(周之平,张飒兵,吴介一),东南大学CIMS中心 南京210096(白伟冬) |
| |
| 基金项目： | 江苏省自然科学基金重点项目 ( BK2 0 0 12 0 4) |
| |
| 摘 要： | 碰撞检测是计算机图形学领域中的一个普遍存在的问题。为了提高多边形碰撞检测的效率 ,针对简单形式刚性运动的多边形对象 ,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法。该算法基于坐标轴的单调性对多边形进行分割 ,并通过矩形包围盒之间的预检来减少无关边对的相交测试 ,以加速算法的终止。由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量 ,所以 ,经过少量的“边 -边”相交判断就能求解到所有交点 ,同时能快速地获得两多边形干涉发生的第 1位置。试验表明 :(1)对于一般多边形 ,该算法的复杂度也远远低于 O(NP× NQ) ;(2 )对于凸多边形对象 ,该算法的复杂度为 O(NP NQ) ,其中 NP,NQ 为多边形 P,Q的顶点数。由此可见 ,算法能够获得较好的运算效率
|
| 关 键 词： | 包围盒 碰撞检测算法 简单多边形 计算机图形学 对象 复杂度 加速算法 相交 单形 运算效率 |
| 文章编号： | 1006-8961(2004)11-1294-10 |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
