首页 | 本学科首页   官方微博 | 高级检索  
     

基于矩形包围盒的多边形碰撞检测算法
引用本文:周之平,张飒兵,吴介一,白伟冬. 基于矩形包围盒的多边形碰撞检测算法[J]. 中国图象图形学报, 2004, 9(11): 1294-1303
作者姓名:周之平  张飒兵  吴介一  白伟冬
作者单位:东南大学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

A Polygon Collision Detection Algorithm Based on Rectangular Bounding Volume
ZHOU Zhi-ping,ZHANG Sa-bing,WU Jie-yi,BAI Wei-dong,ZHOU Zhi-ping,ZHANG Sa-bing,WU Jie-yi,BAI Wei-dong,ZHOU Zhi-ping,ZHANG Sa-bing,WU Jie-yi,BAI Wei-dong and ZHOU Zhi-ping,ZHANG Sa-bing,WU Jie-yi,BAI Wei-dong. A Polygon Collision Detection Algorithm Based on Rectangular Bounding Volume[J]. Journal of Image and Graphics, 2004, 9(11): 1294-1303
Authors:ZHOU Zhi-ping  ZHANG Sa-bing  WU Jie-yi  BAI Wei-dong  ZHOU Zhi-ping  ZHANG Sa-bing  WU Jie-yi  BAI Wei-dong  ZHOU Zhi-ping  ZHANG Sa-bing  WU Jie-yi  BAI Wei-dong  ZHOU Zhi-ping  ZHANG Sa-bing  WU Jie-yi  BAI Wei-dong
Abstract:Collision detection is a prevalent problem in computer graphics. A fast, accurate and feasible collision detection algorithm is important for an application. In this paper, a new planar simple polygon intersection algorithm, based on 2D axis-aligned bounding rectangle data structure, is presented for the polygons subjected to simple and unreformed movement. A new partition strategy for geometrical graphics according to the axial monotony, and the pre-checking process between 2D axis-aligned bounding rectangles reduce the number of unnecessary edge-pairs to be checked efficiently,so the algorithm can terminate promptly. After the partition along with coordinate axis, the interference checking between monotone chains proceeds. A novel search method based on sweep-line theory is adopted to eliminate the number of collision test for both segment-pairs and bounding volume-pairs drastically. So it can prompt the execution of algorithm. The accurate intersections, as well as the first occurrence of intersection between two objects subjected to a dynamic environment, are acquired by lessarithmetical operation. The experimental results indicate that the complexity is far less than O(NP×NQ)for generic polygons,even asymptoticallyO(NP+NQ) for two convex polygons, where in NP,NQ denote the vertex number of two polygonsP,Qrespectively. So, it is a fast and efficient algorithm.
Keywords:simple polygons   bounding volume   pre-check   collision detection
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《中国图象图形学报》浏览原始摘要信息
点击此处可从《中国图象图形学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号