虚拟环境中物体碰撞检测算法研究.pdf

华中科技大学
博士学位论文
虚拟环境中物体碰撞检测算法研究
姓名:金汉均
申请学位级别:博士
专业:系统分析与集成
指导教师:李朝晖
20061111
华中科技大学博士学位论文

摘要
虚拟环境中物体间的碰撞检测是虚拟现实技术、计算机动画技术、机器人技术等
领域中一个极富挑战性的问题,其基本任务是确定虚拟空间中两个或多个物体彼此之
间是否发生接触或穿透。尽管针对碰撞检测问题国内外已有了大量的、有价值的、实
用的研究成果。但随着虚拟现实等新领域的涌现以及人们对虚拟环境真实性要求和用
户交互实时性要求的不断提高,如何有效地提高碰撞检测的速度以保持虚拟环境真实
性的问题也日益突出,它也一直是科技工作者研究的热点问题。
本文在对各类碰撞检测算法作出全面了解、深入分析的基础上,针对碰撞检测技
术目前存在的问题,分别从三个方面,设计、实现并验证了一组新的碰撞检测算法。
提出了一种检测两静态凸多面体间碰撞方法。该方法利用凸多面体上的任意一点
的值可以由凸多面体有限顶点的值表示的特点,将检测两凸多面体间是否发生碰撞问
题转化为求目标函数为两凸多面体间最短距离的非线性规划问题,通过计算最短距离
值来判断某时刻两凸多面体是否发生了碰撞。此方法不但可以判断两凸多面体间碰
撞,而且还可以计算穿透距离,实例证明所提的方法是有效的。将基本遗传算法应用
于求解这类问题。在对约束条件处理后,通过设置各种遗传算子,利用基本遗传算法
求解,并且与用传统方法计算的结果进行了比较。实例证明遗传算法计算速度快,计
算精度高,说明了遗传算法求解此类问题的有效性和快速性。
改进了AABB包围盒层次树的存贮结构。用优化的AABB包围盒层次树来检测变
形物体间碰撞。该方法利用包围盒中基本几何体间交互检测方法,将树中的包围盒存
贮结构进行了优化,去掉叶结点的存储信息,从算法的空间复杂度上进行了优化,模
拟效果证明该方法的快速性。
大部分碰撞检测的算法,都试图减少三角形与三角形之间交互检测数目。本文提
出的物体三角形与三角形之间交互检测是从两方面进行了优化。结合 DirectX 的特点,
通过判断一点到三角形平面距离以及是否从三角形内穿过来判断两三角形接触情况,
从而简化了三角形面片间交互判断步骤加快了检测速度,模拟效果证明该方法的有效
性;通过判断两三角形交线上重叠区域来判断物体三角形与三角形相交的情况,用
I
华中科技大学博士学位论文

JAVA 语言与 VRML 语言的结合来描述简化的区域交互判断方法,非常适应于网络环
境下物体间碰撞检测。
关键词:虚拟现实;碰撞检测;距离函数;遗传算法;层次包围盒;三角形交互;
算法优化























II
华中科技大学博士学位论文

Abstract
It is a challenge to detect collision in domains of virtual reality, animation, robotic, etc.
It has e the basic issue that whether a contact or ration has happened in virtual
environment or not. Many articles have given a mount of valuable and practicable study on
the problem. But while many novel e forth and the requirements for the reality
of scene and real-time of interactive e more and more critical, it is important to
improve the performance of collision detection to ensure the reality of virtual environment.
After giving prehensive understanding and intensive analysis for all kinds of
algorithms, the paper presents, implements and experiments a group of novel collision
detection algorithms in thr