【作者】 霍滨焱；

【导师】 张菁；

【作者基本信息】 哈尔滨工程大学 ， 计算机软件及理论， 2005， 硕士

【摘要】 碰撞检测是机器人、动画仿真与虚拟现实等领域中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测已有了大量有价值的研究成果,但随着诸如虚拟现实等新兴领域的涌现及随之而来的人们对交互实时性、场景真实性要求的不断提高,碰撞检测技术所面临的问题也日益突出,其中最核心的问题是如何有效地提高碰撞检测的速度。 在对各类碰撞检测算法做出全面了解、透彻分析的基础上,针对碰撞检测技术目前存在的问题,本文详细分析、扩展并验证了一种基于图像空间的实时碰撞检测算法。该算法对如何利用图形硬件的高计算性能,加速碰撞检测过程进行了有益的探索性研究。 算法通过将图形硬件的计算优势和简化的几何模型表示相结合,以实现复杂物体间的实时碰撞检测。算法在继承一般基于图像空间的碰撞检测算法优点的同时,突破了它们的局限性,能够在保证效率的前提下处理任意形状多面体之间的碰撞检测问题。算法首先自动将物体表面分解为凸面片,构建与凸面片相对应的凸包围体,并将凸分解结果合理地组织成层次二叉树结构以有效利用物体的空间连贯性,同时采用三角形带压缩这一绘制加速技术加快碰撞检测阶段的绘制速度。算法在具体绘制操作之前,采用了包围球和OBB包围盒树技术以尽可能早地排除彼此不发生碰撞的凸包围体,并有效利用了OBB包围盒重叠检测的结果以设置视域参数,进一步提高了碰撞检测的效率。该算法还利用基于时空相关性的加速方法改进算法效率。更多还原

【Abstract】 Real time collision detection is one of the most important problems in the fields of robotics, computer animation, and virtual reality, etc. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects. Indeed, there have been many research achievements on solving the problem of collision detection, this problem, however, is yet to be solved with the emergence of such burgeoning techniques as virtual reality, and the demands of real time interactivity and realistic simulation of motions of virtual objects thereafter.Based on the intensive survey and comprehensive analyses of various approaches to collision detection, several algorithms have been analyzed, expanded and implemented and verified to explore the possibility of speeding up the process of collision detection from, respectively, the perspectives of using the high computing power of graphics hardware, exploring the programmability of graphics processing units (GPUs).From the perspective of using the high computing power of graphics hardware, a collision detection algorithm based on image space is analyzed, which combines graphics hardware capabilities with a simplified geometric representation to facilitate the process of collision detection between complex geometric objects. The method can process arbitrarily shaped mesh objects, while preserving the merits of image-based collision detection algorithms. This is achieved by decomposing the surfaces of an object into a list of convex pieces. High efficiency of the algorithm is obtained by organizing the convex pieces into a binary tree with nodes composed of convex pieces, and by adopting triangle strip compression, which is a kind of real time rendering techniques. Furthermore, the sphere tree and the oriented bounding box (OBB) tree, are used to exclude those convex pieces that don’t interfere with each other as early as possible, and the result of OBB overlapping test is used to facilitate the viewing parameter setting for real time rendering. And the time-space relativity is also used to improve the efficiency of the algorithm.更多还原