摘要
为了进一步提高碰撞检测的实时性,提出一种基于Minkowski和的多面体快速碰撞检测算法.该算法以Minkowski和为工具,无需精确计算两个多面体之间的最短距离,首先通过构造两个多面体的Minkowski和,将多面体碰撞检测问题转化为判断原点是否在该Minkowski和内,然后运用射线和求交计算将三维空间问题转化为二维平面问题,再通过判断原点是否在平面多边形内来检测多面体是否发生碰撞,进而提高了碰撞检测的实时性和可靠性.在Visual C#环境下,利用OpenGL图形库搭建一个路径规划仿真系统.实验结果表明,该算法平均检测效率明显高于传统算法,并且有效降低了存储空间和时间复杂度.
In order to further improve the immediacy of collision detection,a fast collision detection algorithm of polyhedra is proposed based on the Minkowski sum.The algorithm does not need to accurately measured the shortest distance between two polyhedra.Firstly,the collision detection problem is converted to inspecting whether the origin is in the Minkowski sum by structuring the Minkowski sum of two polyhedra.Secondly,the three-dimensional problem is converted to the two-dimensional problem by ray and the intersection calculation.Then,the polyhedra collision is detected by estimating whether the origin is in the planar polygon,and the real-time and reliability of collision detection are improved.To test the presented algorithm,a motion planning control system is studied with OpenGL graphics library in Visual C# environment.Experimental results indicate that its average detection efficiency is markedly superior to traditional algorithms and it reduces the storage space and time complexity effectively.
出处
《小型微型计算机系统》
CSCD
北大核心
2012年第11期2543-2547,共5页
Journal of Chinese Computer Systems
基金
河北省科学技术研究与发展计划项目(11277108D)资助
