大基于AABB包围盒的碰撞检测算法的研究

基于AABB包围盒的碰撞检测算法的研究

姓名：王晓荣申请学位级别：硕士专业：计算机软件与理论指导教师：金汉均

20070609

⑥硕士学位论文ＭＡＳＴＥＲ‘ＳＴＨＥＳＩ￥摘要碰撞检测是计算机动画、计算机图形学、机器人路径规划等领域的重要课题。近几年来，随着虚拟现实技术和分布式仿真技术的兴起，碰撞检测问题成为一个研究热点。快速的碰撞检钡４对提高虚拟环境的真实性、增强虚拟环境的交互性有着至关重要的作用。层次包围盒方法是解决碰撞检测问题时间复杂性的一种有效的方法，它是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层次结构来逼近对象的几何模型。本文首先分析了不同类型的包围盒及其相关算法，由于ＡＡＢＢ包围盒平行于空间坐标，很多方面都表现为线性，因此选择ＡＡＢＢ包围盒来近似描述对象。本文进一步分析了基于ＡＡＢＢ包围盒的相关算法，发现算法的执行速度主要受三个方面的影响：ＡＡＢＢ包围盒间的相交测试、ＡＡＢＢ树的遍历和基本几何元素的相交测试。本文总结了基于ＡＡＢＢ包围盒的碰撞检测算法关于这三个方面采用的算法，然后从时空相关性和存储空闻的角度提出了改进。ＡＡＢＢ相交测试的速度直接影响着碰撞检测算法的整体速度，包围盒排序法是进行ＡＡＢＢ间相交测试的有效方法。本文采用一维空问排序法将ＡＡＢＢ的端点值投影到三个坐标轴上，基于对象运动的时空相关性，选用希尔排序法对投影值序列进行排序。由于碰撞行为的局部性，算法在排序之前对坐标轴进行适当的划分，避免了不必要的相交测试，提高了全局搜索阶段算法的速度。在算法的局部检测阶段，本文从存储空间角度来加快对从ＢＢ树的遍历。由于构造的ＡＡＢＢ树是一棵二叉树，树中每个内部节点只有两个孩子节点，结合孩子节点的包围盒信息可以得到其父结点的包围盒，因此可以压缩存储ＡＡＢＢ树。算法首先简化树中每个节点存储结构的包围盒信息，减少父结点和孩子节点间冗余数据的存储，然后将树中所有叶节点的存储信息放置到其父节点里，从ＡＡＢＢ树的存储结构里删除叶结点。实验表明，结合包围盒和叶结点的存储优化，既节省了算法所需的存储空间，又加快了算法的执行速度。关键词：碰撞检测；ＡＡＢＢ包围盒；排序；重叠测试；存储优化③硕士擘位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳＡｂｓｔｒａｃｔＣｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｈａｓｂｅｅｎｒｅｓｅａｒｃｈｅｄｍｍａｎｙｆｉｅｌｄｓ，ｓｕｃｈａｓｃｏｍｐｕｔａｔｉｏｎａｌｙｅａｒｓ，ｃｏｌｌｉｓｉｏｎｓｉｍｕｌａｔｉｏｎｇｅｏｍｅｔｒｙ，ｃｏｍｐｕｔｅｒｄｅｔｅｃｔｉｏｎｈａｓｂｅｅｎｔｅｃｈｎｏｌｏｇｙ．Ｆａｓｔａｇｒａｐｈｉｃｓａｎｄｒｏｂｏｔｍｏｔｉｏｎｐｌａｎｎｉｎｇ．Ｉｎｈｏｔｔｏｐｉｃｗｉｔｈｔｈｅｂｏｏｍｏｆｖｉｒｔｕａｌｒｅａｌｉｔｙｅｘａｃｔｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｉｓｖｅｒｙｒｅｃｅｎｔａｎｄｄｉｓｔｒｉｂｕｔｅｄｔｏａｎｄｉｍｐｏｒｔａｎｔｉｍｐｒｏｖｅｒｅａｌｉｔｙａｎｄｅｎｈａｎｃｅｉｍｍｅｒｓｉｏｎｆｏｒｖｉｒｔｕａｌｅｎｖｉｒｏｎｍｅｎｔ．ａｌｌＢｏｕｎｄｉｎｇｖｏｌｕｍｅｈｉｅｒａｒｃｈｙｐｒｏｖｉｄｅｓｃｏｍｐｌｅｘｉｔｙｉｎｅｆｆｅｃｔｉｖｅｍｅｔｈｏｄｔｏｒｅｓｏｌｖｅｔｈｅｔｉｍｅｗｉｔｈａｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎ．Ｔｈｅｉｄｅａｂｅｈｉｎｄｉｔｉｓｔｏａｐｐｒｏｘｉｍａｔｅｔｈｅａｏｂｊｅｃｔｓｉｍｐｌｅｒｂｏｕｎｄｉｎｇｖｏｌｕｍｅｔｈａｔｉｓｌｉｔｔｌｅｂｉｇｇｅｒｔｈａｎｔｈｅｏｂｊｅｃｔ．Ｉｎｂｕｉｌｄｉｎｇｈｉｅｒａｒｃｈｉｅｓｏｎｏｂｊｅｃｔ，ｏｎｅｃａｎｏｂｔａｉｎｉｎｃｒｅａｓｉｎｇｌｙｍｏｒｅａｃｃｕｒａｔｅａｐｐｒｏｘｉｍａｔｉｏｎｓｏｆｔｈｅｏｂｊｅｃｔｓ．Ｓｏｄｕｒｉｎｇｔｒａｖｅｒｓｉｎｇｂｏｕｎｄｉｎｇｖｏｌｕｍｅｈｉｅｒａｒｃｈｙ，ｉｔｓｐｅｅｄｓｕｐｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｂｙｐｒｕｎｅｉｎｔｅｒｓｅｃｔｃｌｅａｒｌｙｔｈｏｕｇｈｒａｐｉｄｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔａｗａｙｐｒｉｍｉｔｉｖｅｓｐａｉｒｓ，ｗｈｉｃｈｗｉｌｌｎｏｔｂｅｔｗｅｅｎｂｏｕｎｄｉｎｇｃｈｏｉｃｅｏｆｖｏｌｕｍｅｓａｎｄｊｕｓｔｄｅａｌｖｏｌｕｍｅｉｓｔｈｅｂａｓｉｃｗｉｔｈｔｈｏｓｅｂｏｕｎｄｉｎｇｖｏｌｕｍｅｉｓｉｎｔｅｒｓｅｃｔｅｄ．Ｔｈｅｂｏｕｎｄｉｎｇａｎｄｋｅｙｐｒｏｂｌｅｍｏｆｔｈｉｓａｐｐｒｏａｃｈ．Ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｓｄｉｆｆｅｒｅｎｔｂｏｕｎｄｉｎｇｖｏｌｕｍｅｓａｎｄｃｏｒｒｅｌａｔｉｖｅａｌｇｏｒｉｔｈｍｓ．ＢｅｃａｕｓｅＡＡＢＢｐａｒａｌｌｅｌｓｃｏｏｒｄｉｎａｔｅ，ｗｅｃｈｏｏｓｅｉｔｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｏａｐｐｒｏｘｉｍａｔｅｔｈｅｏｂｊｅｃｔ．ＡｎａｌｙｚｉｎｇｔｈｅｃｏｌｌｉｓｉｏｎｂｅｏｆＡＡＢＢ，ｗｅｆｏｕｎｄｔｈａｔｔｈｅｓｐｅｅｄｏｆａｌｇｏｒｉｔｈｍｃａｎａｆｆｅｃｔｅｄｂｙｔｈｒｅｅｆａｃｔｏｒｓ：ｉｎｔｅｒｓｅｃｔｉｏｎＡＡＢＢｔｅｓｔｂｅｔｗｅｅｎｂｏｕｎｄｉｎｇｖｏｌｕｍｅｓ，ｔｒａｖｅｒｓｉｎｇｔｒｅｅａｎｄｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔｂｅｔｗｅｅｎｐｒｉｍｉｔｉｖｅｓ．Ｔｈｉｓｐａｐｅｒｓｕｍｍａｒｉｚｅｓｔｈｅｍｅｔｈｏｄｓａｂｏｕｔｔｈｒｅｅｆａｃｔｏｒｓａｎｄｐｒｏｖｉｄｅｓｉｍｐｒｏｖｅｍｅｎｔｍｅｔｈｏｄｓｆｒｏｍｔｅｍｐｏｒａｌ—ｓｐａｃｉａｌｃｏｈｅｒｅｎｃｅａｎｄｍｅｍｏｒｙａｐａｃｅ．ＴｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｍｅｔｈｏｄｔｏｓｐｅｅｄｏｆｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｉｓａｆｆｅｃｔｅｄｂｙｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔｂｅｔｗｅｅｎＡＡＢＢｂｏｕｎｄｉｎｇｖｏｌｕｍｅｓｄｉｒｅｃｔｌｙ．ＢｏｕｎｄｉｎｇｖｏｌｕｍｅｉｎｃｒｅｍｅｎｔｓｏｒｔｓｏｒｔｉｎｇｉｓａｎｅｆｆｅｃｔｉｖｅｅｓｔｉｍａｔｅｔｈｅｉｎｔｅｒｓｅｃｔｉｏｎｂｅｔｗｅｅｎＡＡＢＢ．Ｗｅｄｏｎ’ｔａｄｏｐｔｏｆｉｎｓｅｒｔｉｏｎｓｏｒｔａｌｇｏｒｉｔｈｍｂｕｔｔｈｅｄｉｍｉｎｉｓｈｉｎｇａｌｇｏｒｉｔｈｍｔｏｓｏｒｔＡＡＢＢｓ’ｏｒｔｈｏｇｏｎａｌｐｒｏｊｅｃｔｉｏｎｓｏｎｔｏｔｈｅａｘｅｓｏｆｔｈｅｃｏｏｒｄｉｎａｔｅｓｙｓｔｅｍ．Ｃｏｌｌｉｓｉｏｎｉｓａｌｏｃａｌｂｅｈａｖｉｏｒ，ｉ．ｅ。ａｌｌｏｂｊｅｃｔｃａｎｏｎｌｙｃｏｌｌｉｄｅｗｉｔｈｏｂｊｅｃｔｓｉｎｉｔｓｐｒｏｘｉｍｉｔｙａｎｄｉｓｈａｒｄｌｙａｆｆｅｃｔｅｄｂｙｏｂｊｅｃｔｓｆａｒａｗａｙｆｒｏｍｗｈｅｒｅｔｈｅｏｂｊｅｃｔａｉｓ．Ｂｕｔｔｈｅｏｒｔｈｏｇｏｎａｌｐｒｏｊｅｃｔｉｏｎｓｏｆｔｗｏｒｅｍｏｖｅｄｏｂｊｅｃｔｓｃａｎｏｖｅｒｌａｐｏｎｏｎｅａｘｉｓｐｏｓｓｉｂｌｙ，ｉｎｏｒｄｅｒｔｏｏｖｅｒｃｏｍｅｔｈｉｓ，ｄｕｒｉｎｇｔｈｅｓｏｒｔｉｎｇｐｒｏｃｅｄｕｒｅｅａｃｈａｘｉｓｉｓｃｕｔｉｎｔｏｓｅｒｉｅｓｏｆｓｅｇｍｅｎｔｓｃｏｎｔａｉｎｉｎｇｔｈｅ（ｎｅａｒｌｙ）ｆｌａｍｅｎｕｍｂｅｒｏｆｐｒｏｊｅｃｔｉｏｎｉｎｔｅｒｖａｌｓ．Ｔｈｉｓｗｉｌｌｒｅｄｕｃｅｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｔｉｍｅｏｆｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｔｈｅｇｌｏｂａｌｓｅａｒｃｈｐｒｏｃｅｄｕｒｅ．ａｌｇｏｒｉｔｈｍ，ａｎｄｓｐｅｅｄｓｕｐ⑨ｉｎｔｅｒｓｅｃｔｉｏｎＡＡＢＢｓａｖｅａ硕士擘住论文ＭＡＳＴＥＲ‘ＳＴＨＥＳＩＳＣｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＡＡＢＢｔｒｅｅｉＳｉｍｐｒｏｖｅｄｉＳａｆｒｏｍａｓｐａｃｅｐｅｒｓｐｅｃｔｉｖｅｉｎｌｏｃａｌｓｅａｒｃｈｐｒｏｃｅｄｕｒｅ．ＦｒｏｍｔｈｅｃｏｎｓｔｒｕｃｔｉｎｇｐｒｏｃｅｓｓｏｆＡＡＢＢｔｒｅｅ，ｔｈｅａｍｏｕｎｔｏｆｂｙｔｅｏｆＡＡＢＢｂｏｕｎｄｉｎｇ－ｖｏｌｕｒｎｅｔｅｓｔｏｕｔｂｏｕｎｄｉｎｇ－ｖｏｌｕｍｅｆｏｒｉｎｔｅｒｎａｌｎｏｄｅｆｒｏｍｌｅａｔ＂ｎｏｄｅｓｓｔｒｕｃｔｕｒｅｂａｓｅｄｏｎａｎｄｌｅａｆｒｅｄｕｃｅｄ．ＷｅｆａｓｔｗｉＤｅｔｈｅｔｒｉａｎｇｌｅ－ｔｒｉａｎｇｌｅａｌｇｏｒｉｔｈｍ．ａｎｄｔｈｅｎＷｉｐｅｔｈｅｌｅａｆｎｏｄｅｓｏｕｔ．Ｗｅｏｐｔｉｍｉｚｅｔｈｅｓｔｏｒａｇｅｏｆｂｏｕｎｄｉｎｇ－ｖｏｌｕｍｅｌａｒｇｅｎｏｄｅａｔｔｈｅｓａｍｅｔｉｍｅ．ｎ坞ｄｉｒｅｃｔｒｅｓｕＲｉｓｔｈａｔｉｔｃａｎａｍｏｕｎｔｏｆｓｐａｃｅａｎｄｓｐｅｅｄｕｐｔｈｅａｌｇｏｒｉｔｈｍ．Ｋｅｙｗｏｒｄｓ：ｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎ；ＡＡＢＢｂｏｕｄｉｎｇｖｏｌｕｍｅ；ｓｏｒｔｉｎｇ；ｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔ；ｍｅｍｏｒｙ－ｏｐｔｉｍｉｚｅｄ华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。作者签名：王魄莱日期：扣７年Ｚ月是日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。作者签名：五魂彖导师日期日期：棚年６月＆日本人已经认真阅读“ＣＡＬＩＳ高校学位论文全文数据库发布章程”，同意将本人的学位论文提交“ＣＡＬＩＳ高校学位论文全文数据库”中全文发布，并可按“章程”中的规定享受相关权益。囤壶论塞握銮后澄唇；旦圭生；旦＝生ｉ旦三生筮查！作者签名：互碗策日期．扣７年６月６日导师始念哟嘲。少６月７日⑨硕士擘住论文ＭＡＳＴＥＲ’ＳＴＨＥＳＪＳ第一章绪论１．１研究背景和意义随着计算机硬件技术的不断发展，虚拟环境已成为计算机科学的一个重要研究领域，可广泛地应用于教育、国防、医学、艺术、娱乐等多个方面【ｌｌ。在虚拟环境中，由于用户的交互和对象的运动，对象间经常可能发生碰撞。为了保持环境的真实性，真实地表现对象的运动，系统需要及时检测到这些碰撞，并计算相应的碰撞反应，更新绘制结果，否则对象间会发生穿透现象等不真实的现象，破坏虚拟环境的真实感和用户的沉浸感。例如在一个虚拟手术系统中，为了给训练者提供精确地力反馈以及沉浸感，碰撞检测模块必须能够把手术器械和人体组织碰撞的结构准确而又实时地传递给力反馈设备。近几年来，随着虚拟现实技术和分布式仿真技术的兴起，碰撞检测问题成为一个研究的热点。碰撞检测在很多领域是非常重要的，例如计算机图形学、机器人学、计算几何、计算机械学等。在计算机图形学和计算几何里，碰撞检测在很多应用里出现，比如视频游戏、仿真计算机辅助设计；在机器人学里，碰撞检测是机器人路径规划和控制的一个必要的组成部分，它帮助驾驶机器离开周围的障碍物。但是，一个虚拟环境通常包含若干个静止的环境对象和运动着的活动对象，每一个虚拟对象的几何模型都是由成千上万个基本几何元素（如四面体或三角形）组成的，虚拟环境的几何复杂度使得碰撞检测的计算复杂度大大提高，而参与者与虚拟环境的交互又要求实时完成，因此碰撞检测模块需要占用大量的存储空间和处理时间，往往导致系统处理的瓶颈。例如在一个虚拟手术系统中，为了提供给用户真实的沉浸感以及精确的交互能力，碰撞检测模块必须能够实时的计算手术刀和人体组织的碰撞并给出精确的碰撞结果。这就要求碰撞检测算法必须具有良好的时间复杂度以及空间复杂度。国内外学者在碰撞检测领域做了大量的工作，大部分研究都集中于解决虚拟场景中刚体对象之间的碰撞检测。相对于刚体对象而言，软体对象（又称变形体）有其特殊的物理特性，它们会在外力的作用下变形，即组成软体对象的基本几何元素的几何形状的改变和数量上的增减，例如人体的器官软组织或布料。因此，对变形体对象进行碰撞检测的算法就要求有更好的效率，才能满足虚拟环境的实时性。近几年的研究热点集中于处理变形体对象的碰撞检测，从各个方面来加速变形体对象的碰撞检测过程以及解决变形体对象的自碰撞问题。⑨硕士学住论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ１．２问题描述碰撞问题牵涉到碰撞检测和碰撞响应两部分内容。碰撞检测的目标是发现碰撞并报告；碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象作出正确的动作，以反应真实的动态效果。碰撞响应问题属于力学的研究领域【”鼬嗣。本文研究的主要是碰撞检测问题。通常碰撞检测可以分为静态碰撞检测、伪动态碰撞检测和动态碰撞检测三类。其中静态碰撞检测是判断一个活动对象在某一特定的位置和方向是否与环境对象相交；伪动态碰撞检测是根据活动对象的运动路径检测它是否在某一离散的采样位置方向上与环境对象相交；动态碰撞检测则是检测活动对象扫过的空间区域是否与环境对象相交。静态碰撞检测一般没有实时性的要求，其算法是动态碰撞检测算法的基础；动态碰撞检测的研究一般都考虑到四维时空问题或结构空间精确的建模；伪动态碰撞检测有关于时间点和运动参数之间的信息，可以通过开发时空相关性获得较好的性能。虚拟环境中的碰撞检测一般属于伪动态碰撞检测的范围。虚拟环境中的碰撞检测问题可以简化描述如下：碰撞检测系统的输入模型为一个静态的环境对象和一个动态的活动对象的几何模型，它们均为基本几何元素的集合。其中环境对象可以包括刚体对象，也可以包括软体对象，它们的位置和方向不会发生变化，但软体对象可能会在外力的作用下发生变形。活动对象可以在虚拟环境中自由运动，方向和大小完全取决于仿真过程或者用户控制的输入设备，无法用关于时间的运动方程来表示，只能褥到某一时闻采样点相对于前一时闻采样点或一固定参照物的运动信息（旋转角度和平移量）。其任务是确定在某一时刻两个几何模型是否发生干涉，即它们的交集是否不为空，如发生了碰撞，还需确定碰撞点（参与碰撞的基本几何元素）。虚拟环境中对象所用的几何模型可分为面模型和体模型两类【７Ｊ。面模型用对象的边界来表现对象，而不包括对象内部信息，其基本几何元素多为三角形；体模型采用体元来描述对象，可描述对象的内部信息，其基本几何元素多为四面体。面模型相对简单一些，而且绘制技术成熟，处理方便，但难以进行整体形式上的体操作（如拉伸、压缩等），多用于刚体对象的几何建模。体模型拥有对象的内部信息，可以很好地表达模型在外力作用下的体特征（变形、等），但体模型所耗存储量大，计算量也大，一般用于软体对象的几何建模。最原始最简单的碰撞检测方法是一种蛮力计算的方法，即对两个几何模型中的所有基本几何元素进行两两相交测试，尽管这种方法可以得到正确的结果，但当模⑥硕士擘位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩ￥型的复杂度增高时，这种Ｏ（ｎ２）次的相交测试也是无法容忍的。例如，对一个包含１００，０００个三角形的三维环境和一个由１０，０００个三角形构成的活动对象，如果使用这种蛮力计算法，那么在活动对象的每一个位置，需要执行ｌ亿次三角形与三角形相交测试以确定在当前时间活动对象是否与环境发生碰撞。以当前的软硬件能力，这大约需要ｌ～２个小时的时间，这与实时交互所需要的每秒３００次（触觉反馈宽带）以上的碰撞检测的要求相差甚远，因此，速度是虚拟环境中的碰撞检测的核心问题【”。１．３国内外研究动态１．３．１碰撞检测算法碰撞检测问题的相关研究源于１９７０年代。近三十年来，研究人员已经在碰撞检测领域做了相当多有意义的工作，形成了二些较为成熟的技术。碰撞检测算法使用在很多不同的研究领域，在两个几何模型间的碰撞检测算法大致可分为三类：几何方法、空间分解法和层次包围盒方法【９１．几何方法主要是分析每个单独模型的拓扑结构，跟踪并且计算两个或多个模型问的最近特征（点、边、面）。几何方法比较典型的是Ｌｉｎ－Ｃａｎｎｙ算法（加Ｊ和ＥｎｈａｎｃｅｄＧＪＫ算法ｆｌｌｌ。空间分解法主要是先将整个虚拟空间划分为相等体积的小的单元格，将对象分配给一个或多个单元格，然后对占据了同一单元格或相邻单元格的所有对象对进行碰撞检测。空间划分法比较典型的例子有ｋ－ｄ树【１２】。八叉树［２，１３１，ＢＳＰ树【１４＇１５】，四面体网和规则网格等。空间分解法通常适用于稀疏的环境中分布比较均匀的几何对象间的碰撞检测。采用层次划分方法进行空间分解，如八叉树，ＢＳＰ树等，可以进一步提高算法的速度。空间分解法存在的问题是何时终止划分空间单元格以及设置单元格大小。层次包围盒方法是碰撞检测算法中广泛使用的一种方法，它曾经在计算机图形学的许多应用领域（如光线跟踪等）０６，１７’１８＇１９１中得到深入的研究。该方法主要是将对象以层次方式（即包围盒树）组织起来。初检测时根据包围盒间的相交测试快速排除不相交的对象，再对包围盒相交的对象进行精确的碰撞检测。基于包围盒的碰撞检测方法的不同点在于树的节点的包围盒类型不同或者采用不同的技术来建立、更新和平衡包围盒树。典型的包围盒有轴对齐包围盒（ＡＡＢＢ）、球包围盒、方向包围盒（ＯＢＢ）和离散方向凸包围盒（ｋ．Ｄｏｐ）。近些年，随着图形硬件计算性能的迅速增长，一类基于图像空间的碰撞检测算法进入了一个新的快速发展阶段。该方法一般将三维几何对象通过投影绘制到图像平面上，降维得到一个二维的图像空间；然后分析该空间中保存在各类缓存的信息，迸而检测出对象之间是否发生干涉。这类算法优势在于能有效利用图形硬件加速技术来减轻ＣＰＵ的计算负荷，从而达到提高算法效率的目的。图形硬件辅助碰撞检测的方法由Ｓｈｉｎｙａ等和Ｒｏｓｓｉｇｎａｃ等于１９９１年前后开创性地提出Ｉ捌。近年来的研究热点主要集中于变形体对象的碰撞检测。刚体对象在场景中只作平移和旋转运动，其碰撞检测相比变形体对象而言简单些。变形体对象会在运动中发生变形，适用于刚体对象的层次包围盒方法就不能直接的用于变形体对象上。当变形体对象发生变形时，其包围盒树必须实时的重新构建或者更新，而重新构建整个数据结构的时间耗费在一个实时的仿真环境中是不能接受的，因此在层次包围盒方法中必须避免整棵树的重新构建。研究者根据不同包围盒的特性进行改进，将层次包围盒方法也用于变形体对象的碰撞检测。Ｓｍｉｔｈｅｒａｌｌ２ｌＪ提出了一种基于ＡＡＢＢ包围盒的解决变形体对象的方法，该方法在每一步都重新计算对象的包围盒，其缺点是当模型复杂时不能得到实时计算。ＶａｎｄｅｎＢｅｒｇｅｎｌ２２】提出了一种基于ＳＯＬＩＤ库的方法，并在每个时候由叶子节点开始完成自底向上的更新，缺点是发生大尺度变形时，ＡＡＢＢ包围盒的紧密性就比较差并且包围盒与包围盒之间有非常大的重叠区域。ＹａｓｈｉｆｕｍｉＫｉｔａｍｕｒａｔ２３】等人提出了一种用于解决复杂场景下的变形体的碰撞检测算法，这种算法的本质是包围盒方法与空间分解法的结合。此方法的缺点是采用八叉树的数据结构复杂。Ｊ．Ｍｅｚｇｅ一２４Ｊ等人在模仿布料仿真时对层次包围盒结构作了很多优化。它采用的包围盒类型是ｋ－Ｄｏｐｓ，由于ｋ－Ｄｏｐｓ在最坏情况下只需ｋ／２次相交测试，因此Ｊ．Ｍｅｚｇｅｒ等人采用的是四叉树。这样做的优点是减少相交测试时递归调用的深度，从某种意义上减少了内存消耗。另外它还采用了“向量圆锥”来解决自相交问题。ＭａｔｔｈｉａｓＴｅｓｃｈｎｅｒｌ２５】等人提出了用一种优化的哈希表来解决变形体以及自相交问题。国防科学技术大学魏迎梅【ｓｌ等人提出了一种基于固定方向凸包ＦＤＨ包围盒层次的碰撞检测方法，用于虚拟手术仿真，为解决复杂环境中的碰撞检测问题提供了一条有效的途径。浙江大学范昭炜【２０】等人对实时碰撞检测技术进行了研究，利用图形硬件的高计算性能、可编程性及多处理机的并行计算能力来加速碰撞检测过程。４⑨Ｂｏｕｎｄｉｎｇ硕士擘位论文ＭＡＳＴＥＲ’ＳＴＨＥＳｌＳ１．３．２常用的包围盒类型碰撞检测领域中研究最多的包围盒主要有：轴对齐包围盒（ＡｘｉｓＡｌｉｇｎｅｄＢｏｘ）、包围球（Ｓｐｈｅｒｅ）、方向包围盒（ＯｒｉｅｎｔｅｄＢｏｕｎｄｉｎｇＢｏｘ）、离散方向凸包包围盒（ＤｉｓｃｒｅｔｅＯｒｉｅｎｔａｔｉｏｎＰｏｌｙｔｏｐｅ）等。１、轴对齐包围盒轴对齐包围盒ＡＡＢＢ（ＡｘｉｓＡｌｉｇｎｅｄＢｏｕｎｄｉｎｇＢｏｘ）是一个长方体包围盒，其各轴的方向与坐标轴的方向一致，即一个给定对象的ＡＡＢＢ被定义为包含该对象且边平行于坐标轴的最小的正六面体，如图１．１（ａ）所示。ＡＡＢＢ可表示为Ｒ＝｛（ｘ，ｙ，ｚ）ｋ≤ｘ≤吃，‘＜－ｙ＜－ｈｙ，乞＜－ｚ≤吃｝值。其中，‘，吃，‘，哆，乞，吃分别是该ＡＡＢＢ在‘¨ｚ坐标轴上投影的最小和最大坐标值。⑨◇锣（ａ）ＡＡＢＢ包围盒（ｂ）包围球（ｃ）ＯＢＢ包围盒（ｄ）ｋ－ｄｏｐ包围盒（ｋ《）图１．１各种包围盒的二维示意图给定对象的ＡＡＢＢ的计算十分简单．只需分别计算对象中各个元素的顶点的Ｘ坐标、ｙ坐标和Ｚ坐标的最大值和最小值即可。ＡＡＢＢ间的相交测试也比较简单，两个ＡＡＢＢ相交当且仅当它们在三个坐标轴上的投影区间均重叠。定义ＡＡＢＢ的六个最大最小值分别确定了它在三个坐标轴上的投影区间，因此ＡＡＢＢ问的相交测试最多只需要六次比较运算。当对象发生旋转后，需要对ＡＡＢＢ进行更新。根据定义ＡＡＢＢ的６个最大最小值的组合，可以得ＮＡＡＢＢ８个顶点，对这８个顶点进行相应的旋转，并根据旋转后的顶点计算新的ＡＡＢＢ。当对象发生变形后，可以重新计算ＡＡＢＢ树中发生变形了的叶结点。可见，ＡＡＢＢ的优点是包围盒之间的相交检测与方向无关，同时包围盒占内存少，构造和修改方便，因此也适合于可变形的模型。基于ＡＡＢＢ包围盒的碰撞检测算法的相关知识将在第二章作具体介绍。５⑥２、包围球硕士肇位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ包围球（Ｓｐｈｅｒｅ）类似于ＡＡＢＢ，也是简单性好紧密性差的一类包围盒，包围球被定义为包含该对象的最小的球体。包围球可表示为Ｒ＝｛（五乃ｚ）｝（ｘ一巳）２＋（＿），一６）２＋（ｚ一乞）２＜ｒ２｝其中（巳，勺，乞）是球的中心坐标，，是球的半径。如图１．１（ｂ）所示。计算给定对象的包围球，首先需分别计算对象中各个元素的顶点的ｘ坐标、ｙ坐标和ｚ坐标均值以确定包围球的球心，再由球心与三个最大值坐标所确定的点间的距离计算半径ｒ。包围球的计算时间略多于ＡＡＢＢ。３、方向包围盒一个给定对象的方向包围盒ＯＢＢ（ＯｒｉｅｎｔｅｄＢｏｕｎｄｉｎｇＢｏｘ）被定义为包含该对象且相对于坐标轴方向任意的最小的正六面体，如图１．１（ｃ）所示。ＯＢＢ最大特点是它的方向的任意性，这使得它可以根据被包围对象的形状特点尽可能紧密地包围对象。１９９６年Ｇｏｔｔｓｃｈａｌｋ等人完成了一个称为ＯＢＢＴｒｅｅｓ的“ＲＡＰＩＤ”系统【２７１，该系统基于方向包围盒ＯＢＢ，曾经一度被认为是可实现任意多边形问的碰撞检测的领先系统，其算法基于分离轴理论，能大大提高算法的效率。４、ｋ－Ｄｏｐ包围盒ｋ－Ｄｏｐ（ＤｉｓｃｒｅｔｅＯｒｉｅｎｔａｔｉｏｎＰｏｌｙｔｏｐｅ）是由纽约州立大学的ＪａｍｅｓＴ．Ｋｌｏｓｏｗｓｋｉｔ２９】等人１９９６年提出的一种方法，用于复杂环境中运动对象问的碰撞检测。该包围盒是一种凸多面体。它的面由一些半空间所确定，这些半空间的外法向是从ｋ个固定的方向中选取的。这ｋ个固定法向是那些共线但方向完全相反的矢量对。因此，每个ｋ－ｄｏｐ实际上只用到ｋ／２个方向，如图１．１（ｄ）所示。显然，当ｋ的取值越大时，包围盒与所包围的对象的逼近程度越好。１．４研究内容现有的碰撞检测算法中使用较多的是层次包围盒方法。常用的包围盒中，包围球的紧密性比较差，一般很少使用；ＯＢＢ由于方向是任意的，紧密性比较好，但是构造ＯＢＢ树需要大量的矩阵运算，对象变形后需要重新计算每个结点的ＯＢＢ，计算代价太大，不适用于包含变形体对象的复杂环境的碰撞检测；ｋ－Ｄｏｐ紧密性是最好的，对象变形后的更新计算代价相对较小，适用于变形体对象的碰撞检测。ＡＡＢＢ６⑨算法。硕士擘位论文ＭＡＳＴＥＲ７ＳＴＨＥＳｌＳ包围盒平行于空间坐标，很多方面都表现为线性。相对ｋ－Ｄｏｐ而言构造简单些，一个ＡＡＢＢ只需要六个值就可以确定；ＡＡＢＢ间的相交测试比ＯＢＢ简单，可以用于变形体对象的碰撞检测；在为对象构造的二叉树中父结点的ＡＡＢＢ包围盒完全可以由其两个孩子结点的包围盒得到，因此本文研究以ＡＡＢＢ包围盒为基础的碰撞检测采用ＡＡＢＢ的碰撞检测库主要有Ｉ－Ｃｏｌｌｉｄｅ【２９＇３０３１１和Ｄ—Ｃｏｌｌｉｄｅ［３２，３３捌１。Ｉ－Ｃｏｌｌｉｄｅ适用于大量运动着的对象间的碰撞检测，Ｑ—Ｃｏｌｌｉｄｅ是对Ｉ—Ｃｏｌｌｉｄｅ的改进，当对象运动或旋转加快或几何模型复杂时，Ｑ—Ｃｏｌｌｉｄｅ会大大提高碰撞检测的效率。但是Ｉ—Ｃｏｌｌｉｄｅ和Ｑ—Ｃｏｌｌｉｄｅ要求处理对象是刚性并且是凸的，不适合包含软体变形的复杂的虚拟环境情况。后来，Ｐｏｎａｍｇｉ等人将Ｉ—ＣｏｌｌｉｄｅＪ差行扩展【３扪，可以用于非凸多面体的碰撞检测中。荷兰Ｅｉｎｄｈｏｖｅｎ大学开发了一个基于ＡＡＢＢ包围盒层次的碰撞检测系统一ＳＯＬＩＤｌ２２ｊ，它涉及了模型变形的处理，但是仅研究了模型顶点位移的变形，没有包含拓扑结构变化的情况。Ｉ－Ｃｏｌｌｉｄｅ算法的高层算法采用包围盒排序法来快速排除不相交的对象对，文献ｍｌ提出了对排序的改进方法。本文将充分利用对象运动的时空相关性来改进包围盒排序法，提高算法的执行效率。ＳＯＬＩＤ算法的高层算法采用的是“分割轴”方法，低层采用ＡＡＢＢ树算法进行精确的碰撞检测，考虑到ＡＡＢＢ树中每个节点都需要一定数量的存储空间，同时根据ＡＡＢＢ的构造特性，文献【３刀对树中每个节点的包围盒信息进行了存储优化，但是这个优化操作在三角形数目较少时将会增加算法的执行时间，本文将进一步从存储空间的角度进行优化，既减少算法所需的存储空间，又减少算法的执行时间。具体研究内容如下：（１）在碰撞检测算法的全局搜索阶段，利用对象运动的时空相关性快速排序不可能相交的对象。在检测多对象间的相交时采用一维空间排序法，但是排序方法不选用传统的插入排序法，而是借助于希尔排序来完成。传统的排序方法将所有对象在坐标轴上的投影值一起排序，为了避免将实际上不相交但是在某个坐标轴上的投影值却重叠的对象标注为相交的对象对，在排序的过程中将对坐标轴进行划分，提高排序操作的效率，从而减少需要进一步进行精确碰撞检测的对象对。（２）在局部检测阶段通过遍历ＡＡＢＢ树来进行精确检测，通过减少ＡＡＢＢ树的存储空间来提高算法的执行速度。在优化存储树中每个节点的包围盒的同时，对树的叶结点将进一步优化。将叶结点的存储信息放到其父结点中，从树的存储结构中删除叶节点。结合包围盒和叶结点的存储优化，减少算法的存储需求，从而提高７碰撞检测算法效率。本文后面的结构安排如下：第二章介绍了基于ＡＡＢＢ包围盒的碰撞检测算法的相关知识。包括层次包围盒碰撞检测算法的一般步骤；包围盒树的构造及其包围盒树的更新方法；基本的三角形相交测试算法及改进的方法。第三章论述了全局搜索阶段的碰撞检测算法的改进。给出了根据时空相关性加快对象在坐标轴上的投影值的排序过程的方法。第四章论述了ＡＡＢＢ树的存储优化方法。给出了在包围盒树的节点优化基础上，进一步对叶节点进行优化的方法。第五章是总结和展望。在对所做的工作进行总结的基础上，阐述了进一步的工作目标。⑥硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩ￥第二章基于ＡＡＢＢ包围盒的碰撞检测方法综述２．１层次包围盒方法的一般框架基于包围盒的碰撞检测算法在处理包含大量对象的复杂场景时，一般分为两个阶段。在第一阶段首先快速排除多数明显不相交的对象对，这一阶段我们称为碰撞检测算法的全局搜索阶段；在全局搜索之后的后继阶段，算法对可能相交的对象对进行进一步检测，我们称之为碰撞检测算法的局部检测阶段。在局部检测阶段中，基于层次包围盒的碰撞检测算法首先会同时遍历对象对的层次包围盒树，递归检测树节点之间是否相交，直到树叶子节点，进而精确检测叶子节点中所包围的对象多边形面片或基本体素之问是否相交。其中，局部检测阶段又可分为两层，一是逐步求精层：二为精确求交层。在逐步求精层中算法进行层次树的遍历。而精确求交层中算法主要处理多边形面片或基本体素之间的精确相交检测ｆ捌。由此可给出一个基于层次包围盒的一般碰撞检测算法的框架，如图２．１所示：圈２．１碰撞检测算法的一般框架２．１．１全局搜索过程大规模的场景中既包含运动对象也包含静止对象。设有Ⅳ个运动对象和Ｍ个静止对象，每个运动对象可能与其他运动对象相撞，也可能与静态对象相撞。碰撞检测最直接的办法是对（Ⅳ２）＋＾Ｍ个对象对进行逐一检测，然而当Ⅳ和Ｍ很大时，计算量将非常大。为了达到交互速度的要求，碰撞检测算法必须设法减少实际检测的对象对数，这就需要对场景中的对象进行全局搜索。全局搜索的最简单的一种方法是空问剖分法。该方法通常将空间剖分成均匀的单元，每个对象对应到一个或多个单元中。检测碰撞的操作只局限于处在同一个单元中的对象之间。该方法适用于对象在空间中均匀分布的稀疏环境。但对于一般９的环境，很难选择一个最优的剖分尺寸，若选择不当，会导致空间耗费大，计算效率低。另一种常用方法是包围盒方法。包围盒方法被广泛运用于对光线跟踪和求交运算的加速，其基本思路是用一个简单的包围盒将复杂的几何形体围住，当对两个对象作碰撞检测时，首先检测两者的包围盒是否有交，若包围盒不相交，则说明两个对象未相交，否则再进一步对两个对象作检测。因为求包围盒的交比求对象的交简单得多，所以可以快速排除很多不相交的对象，从而加速了算法。Ｉ－Ｃｏｌｌｉｄｅ算法采用的就是包围盒排序法来减少碰撞检测的对象对数，ＳＯＬＩＤ算法则采用的是基于包围盒的“分割轴”方法。此外，还可以利用运动对象的时间连续性和几何连续性来加速，时间连续性是指由于应用状态在帧间的变化较小，所以对象在连续两帧间仅有微小的运动；同时，这一微小运动也带来了几何连续性，即由顶点坐标定义的对象的几何体在两帧间的位置和方向也只有少量变化。此方法能够加速的前提条件是：要求时间步长足够小，以保证对象在连续两帧问的运动距离很小。这一前提在很多应用中都可满足。Ｉ－Ｃｏｌｌｉｄｅ算法同时利用了这两个连续性来加速，但是它在进行排序操作时是将所有对象的投影值一起排序，没有考虑碰撞行为的局部性。２．１．２局部检测过程２．１．２．１包围盒树的遍历在众多复杂的对象中排除不可能相交的对象后，碰撞检测算法将对可能相交的对象对进行进一步的精确的碰撞检测。这就需要为对象建立层次包围盒，即构造包围盒树。关于包围盒树的构造我们将在２．２．１节作具体介绍，这里假设已经为每个待检测的对象构造了包围盒树。在包围盒树中，每个节点上的包围盒都对应于组成该对象的基本几何元素集合的一个子集，根节点为整个对象的包围盒。碰撞检测算法的局部检测过程的核心就是通过遍历这两棵树，确定在当前位置下，两个对象是否发生碰撞。这是一个双重遍历的过程，算法首先用一个对象的包围盒树的根节点遍历另一个对象的包围盒树，如果能到达叶节点，再用该叶节点遍历第一个对象的包围盒树，如果能到达该对象的叶节点，则进一步进行基本几何元素的相交测试。如果两个节点上的包围盒不相交，则它们所包围的对象的基本几何元素的子集必定不相交，从而不需要对子集中的元素做进一步的相交测试。具体算法如图２．２所示。ＩＯ⑥｛硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ输入：ａ＇ｂ两对象的层次包围盒二叉树ＢＶｒ。，ＢＶｒｂ。输出：布尔值。ｔｒｕｅ为相交，ｆａｌｓｅ为不相交。ｂｏｏｌＤｅｔｅｃ＿ｒｅｃｕｒｉｓｖｅ（ＢＶＬ’ＢＶＴｂ）ｉ坟检测到ＢⅥ：与Ｂｙｒｂ两个包围盒之间不相交）返回两对象不发生碰撞的结果；ｉｆ（ＢＶＬ，Ｂ、，ｒｂ均为叶子节点）｛精确检测ＢＶＬ，ＢＶｒｂ所包围的多边形面之间是否相交；返回精确求交检测的结果；）ｅｌｓｅｉｆ０３、７ｒ｜为叶子节点，ＢＶｒｂ为非叶子节点）｛Ｄｅｔｅｃｔ＿ｒｅｃｕｒｓｉｖｅ（ＢＶＴａ，ＢＶＴｂ的左子节点）；Ｄｅｔｅｃｔ＿ｒｅｃｕｒｓｉｖｅ（ＢＶｒａ，ＢＶＴｂ的右子节点）；｝ｅｌｓｅｉｆｍＶｒＩ为非叶子节点，ＢＶｒｂ为叶子节点）｛Ｄｅｔｅｃｔｒｅｃｕｎｉｖｅ（ＢＶＬ的左子节点，ＢＶｒｂ）；Ｄｅｔｅｃｔ＿ｒｅｅｕｒｓｉｖｅ（ＢｙＬ的右子节点，ＢＶＴｂ）；｝ｅｌｓｅ｛／／Ｂ、厂Ｌ，ＢＶｒｂ均为非叶子节点Ｄｅｔｅｃｔ＿ｒｅｃｕｒｓｉｖｅ（ＢＶｒＩ，ＢＶＴｂ的左子节点）；Ｄｅｔｅｃｔ＿ｒｅｃｕｒｓｉｖｅ（ＢＶｒａ，ＢＶｈ的右子节点）：Ｄｅｔｅｃｔ＿ｒｅｃｕｒｓｉｖｅ（ＢＶＬ的左子节点。ＢＶＴｂ）：Ｄｅｔｅｃｔｒｅｅｕｒｓｉｖｅ（ＢＶＴａ的右子节点，ＢＶｒｂ）；｝＇图２．２层次包围盒树的递归遍历算法２．１．２．２基本几何元素间的相交测试在采用层次包围盒方法进行碰撞检测时，如果两对象发生碰撞，那么最终到达算法的底层即两对象叶子节点的包围盒相交，这时需要对它们所包围的基本几何元素对进行两两相交测试，以确定是否有碰撞发生。基本几何元素间的相交测试对碰撞检测算法的效率也有着重要的影响。在对象的几何模型中，基本几何元素大多为三角形或四面体，三角形是最简单的多边形，四面体是最简单的多面体。基本几何元素间的相交测试具体表现为三角形与三角形间的相交测试，或者四面体与四面体间的相交测试，或者三角形与四面体间的相交测试，这取决于对象的建模方法。四面体是由四个三角形构成，与四面体的相交测试可以通过分别与四个面的相交测试完成，因此，最终的测试可归结为三角形与三角形问的相交测试。具体测试方法将在２．３节介绍。２．２包围盒树的建立和更新２．２．１包围盒树的构造方法一个几何对象的包围盒是包含该对象的一个简单的几何体，它可以近似地代替几何对象进行一些粗略地计算。对组成对象的基本几何元素的集合Ｓ构造包围盒树通常有两种方法：自项向下和自底向上。１、自底向上方法该方法是从集合Ｓ的基本几何元素出发，每个元素对应一个叶节点，然后利用任何局部信息递归地对它们进行分组归并，形成父节点，直到得到一个单一的根节点（即集合Ｓ），这一方法的核心就是如何把若干个集合归并为一个父集。２、自顶向下方法该方法以全集Ｓ作为根节点，利用基于全集的信息递归地对这个节点进行划分以形成其子节点，直到到达叶节点，即如何把一个集合划分成若干个子集。这里涉及到一个问题：树的度，即树的最大子节点数。大多数情况下选择树的度为２，因为度为２的树是最简单的。本文的算法选择树的度也为２。采用自顶向下的方法构造包围盒树的过程，实际上就是将给定节点Ｖ的基本几何元素几何墨，划分成两个子集，直到每个元素都是基本几何元素为止。该方法的核心是如何把一个集合划分成若干各不相交的子集，相对而言，自顶向下的方法在碰撞检测中使用的较多，计算也更成熟一些，因此本文采用这一方法。通常对鼠的划分采用基于平面的划分方法，即选定一个平面，根据集合中的基本几何元素相对于平面的几何位置进行划分。一个平面可以把整个空间划分为两个闭半空间，一个基本几何元素或者属于平面的左半空间；或者属于平面的右半空间；或与平面相交，跨越这两个半空间（如基本几何元素为三角形，还可能在平面内）。对于前两种情况可以很自然的把它们划分到两个子集中，而对后一种情况可以这样处理，首先为每个基本几何元素指定其中心为其表现点，然后根据表现点２在平面的哪一侧来分配，如表现点恰好位于平面上，那么将它分配给所含元素较少的子集。这种划分方法简单并且尽可能的把相邻的基本几何元素分在一组。其关键在于平面的选择，通常分两步完成：确定轴（即平面的法线）和确定轴上的点以定位平面。１）确定轴：通常使用最长轴方法，即选择方向轴使得包围盒沿轴线方向最长，对于ＡＡＢＢ包围盒该方法仅需要两次比较即可确定，简单快速。２）确定点：选择好与平面正交的轴线后，必须确定点以定位平面，有两种方法：ａ平均值方法：选择集合中所有基本几何元素的表现点在轴上的投影的平均值。此方法通常可以使子节点的包围盒体积更小，从而提高了碰撞检测的速度；但使树的平衡性有一定的伤害，使梅造树的时间增加。ｂ中值方法：选择集合中所有基本几何元素的表现点在轴上的投影的中值。该方法简单快速，而且可以得到两个大小相等的子集，从而得到一裸基本平衡的包围盒树，尤其当集合中的基本几何元素大小相等不多时，该方法更有效。３、具体构造过程为虚拟环境中的对象构造包围盒树的具体过程如下：①根据根节点ｖ所包含的基本几何元素的坐标值求出各元素的表现点。②求出节点ｖ的包围盒。③确定轴：使用最长轴方法。④确定点，定位平面：使用中值方法。⑤应用基于平面的划分方法将所有元素分为两个子集。⑥把两个子集分别作为根节点，返回步骤②。直到每个基本几何元素的包围盒都是叶子节点。由此得到的包围盒树是一棵完全二叉树，树的每个叶节点仅含有一个基本几何元素，在本文中基本几何元素即为三角形。２．２．２包围盒树的更新虚拟环境中对象运动或变形后，其原来的包围盒树将不再适合要求，必须进行更新，有两种方法来完成包围盒树的更新：重新构造包围盒树和只对包围盒树中的部分包围盒进行更新。显然，前者比后者要多花费大量的宝贵时间。同时根据时空相关性，虚拟环境中的运动对象通常在每个时间采样点上都会由于运动而产生位置和状态的变化，但相邻时间点的变化一般不大；对象的变形通常也只发生在部分基本几何元素中，为保证碰撞检测的实时性，必须在最少的时间内完成包围盒树的更新。因此通常选择后者来处理对象运动或变形后包围盒树的更新。沿Ｘ轴，Ｙ轴和ｚ轴的平移参数，对应于一个平移向量丁＝（ｘ，ｙ，ｚ）７，绕Ｘ轴、Ｙ轴和Ｚ轴的旋转参数口、妒，ｙ，对应于变换矩阵：１Ｒｏｔ（ｘ，Ｏ）＝１０ｅｏｓＯ－ｓｉｎ＃ｌ１０ｓｉｎ０ｃｏｓ＃ｊ『１００Ｒｏｔ（ｙ，力＝Ｉ『ｃｏｓ·ｐ０咖妒１ｏ１ｏｌ『ｃｏｓ缈一ｓｉｎ妒＇０１Ｌ００１Ｊ怩０斟三翻ｓｉｎｑ］Ｉｃ警ｏｓ￥／－誓ｓｉｎｙＶ习性０－捌ｓｉｎＯ三－孟ｅｏｓ伊ｓｉｎｙ∥兰习Ｉｏｓｉｎ口ｃｏｓ护｝ｌ—ｓｉｎ妒ｏｃｏｓ矿Ｉｌｏｏ１ｌ⑥ｌ硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳｃｏｓ矿ｃｏｓ＿；ｆ，－ｃｏｓ妒ｓｍ∥ｃｏｓ矽ｃｏｓ∥一ｓｉｎ曰ｓｉｎ伊ｃｏｓ∥ｓｉｎ口ｃｏｓ妒＋ｃｏｓ秽ｓｉｎ伊ｃｏｓ∥ｓｉｎＩ＝ｌｃｏｓ口ｓｉｎ∥＋ｓｉｎ护ｓｉｎ伊ｃｏｓ妒Ｌｓｉｎｐｓｉｌｌｙ—ｃｏｓＯｓｉｎ·ｏｃｏｓｖ－ｓｉｎＯｃｏｓ伊ＩｃｏｓｏｃｏｓＪ⑥硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ元素变形的幅度不等，无法用一个变换函数来统一描述整个变形。处理方法是：首先重新计算所有发生变形的基本几何元素的ＡＡＢＢ包围盒，然后按照自底向上的方法对包围盒树进行更新，通过两个子节点的包围盒更新其父节点的包围盒，这种更新也是比较简单的，为两个ＡＡＢＢ子节点求其父节点，只需要六次比较即可确定，即分别求出它们在Ｘ、Ｙ、Ｚ三个坐标轴上投影的最大、最小值。ＳＯＬＩＤ算法采用的就是此方法来更新ＡＡＢＢ树。对象拓扑结构的变化是指组成对象的基本几何元素的集合发生变化，包括：增加新的基本几何元素到集合中、从集合中去除某些基本集合元素、某些基本几何元素发生、产生新的基本几何元素。当从集合中去除某个元素时，可以从包围盒树中删除相关的叶节点，并且用它的兄弟节点取代它的父节点。因为是集合中的元素数减少，而所有前代节点上的包围盒依然能够包围相应的基本几何元素的子集，只是它可能不是最小的包围盒，又因为包围盒只是对所包围对象的一个近似，因此这样不会产生错误的碰撞检测结果，可以暂时不对前代节点的包围盒进行更新，而留待同别的节点一起处理。当集合中某个元素发生时，由于该元素是所有新产生元素的并集，所以它所在叶节点上的包围盒仍然是所有新元素的包围盒。因此，只要在该叶节点上构造所有新产生元素的包围盒子树即可实现包围盒树的更新。２．３三角形与三角形问的相交测试虚拟环境中对象之间的碰撞检测最终将归为组成对象的三角形之间的相交测试，下面将介绍常用的三角形间的相交测试方法。此外，本文后面提出的存储空间优化方法是基于改进的三角形问快速相交测试方法和三角形与包围盒的快速相交测试方法，在本节也将介绍这两个方法。２．３．１三维空间中的三角形相交测试点的向量（如二＝石函＝（ｑ，ｎ，，４：）７），顶点为Ａ，Ｂ，Ｃ的三角形记作鲋曰ｃ，定义㈨∞《五醅陋ａ屯ｒ斗“¨匆咿她印巩№饥专ｕｌｑｇ乞ｌ１６⑥硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳＢ、Ｃ呈逆时针顺序排列时，ｄｅｔ（Ａ，Ｂ，ｃ）＞０：当且仅当Ａ、Ｂ、Ｃ呈顺时针顺序排列时有ｄｅｔ（Ａ，Ｂ，ｏ＜０；当且仅当Ａ、Ｂ、Ｃ共线时，ｄｅｔ（Ａ，Ｂ，ｃ）＝Ｏ。设有顶点坐标已知的鲋口Ｃ和△ＰＱＲ，｛ｆ，为ｚｋ４ＢＣ的支撑超平面。按以下步骤判断它们是否相交。（１）判断ａＰＱＲ是否与∥相交如果ｈｄＢＣ和ａｔ＇ＱＲ相交，则△ＰＱ噼的三个顶点必然位于ｈＪＩＢＣ的支撑超平面∥的两侧，这是因为平面∥将空间分成两个不相交的开半空间瓦和瓦，瓦ｎ｛ｆ，＝妒，％ｎ∥＝矿。三角形是三维空间中的一个有界的闭集，如果顶点Ｐ、Ｑ、Ｒ位于某一个开半空间中（位于妒的同一侧），则蚴ｃ虮或必ｃ％，而鲋口Ｃｃ妒，故ＡＰＱＲ和ＡＡＢＣ不相交。计算∥的法线ｎ一＝压×万＝（云一一ａ）ｘ（一ｃ一＿），令ｓｐ＝；．乃，ｓｑ＝二．一ＡＱ，盯＝行．ＡＲ，判断①如果ｓｐ，ｓｑ和盯同时为正或同时为负，则顶点Ｐ、Ｑ、Ｒ位于∥的同一侧，削Ｂｃ和△尸∞不相交；②如果它们全部为０，则ＡｄＢＣ和△ＰＱ暇共面，可转化为二维平面空间中的三角形的相交测试，见２．３．２节。③如果有一个为０，另外两个符号相同，贝ＪＪＡＰＱＲ的一个顶点位于平面缈上，要么这两个三角形不相交，要么相交在该顶点上。此时转化为二维平面空间中判断该项点是否位于＆４ＢＣ的内部。④如果有两个为０，如妒和ｓｑ，贝１］ＡＰＱＲ的一条边只Ｑ位于平面妒上，要么这两个三角形不相交，要么相交在ＰＱ＿Ｉ：。此时转化为二维平面空间中线段与三角形间的相交测试。⑤否则ａｅａＲ与∥相交，进入步骤②继续测试。（２）计算△Ｐ啦与妒的交点顶点Ｐ、Ｑ、Ｒ位于妒的两侧，假设Ｑ和Ｒ同侧，则线段砀、线段葡与妒相交，其交点即为ａｅＱＲ与妒的交点。线段砀上的点可表示成如下向量形式≯＋ｆ．一ＰＱ，其中ｏ≤ｆ≤ｌ，则面与∥的其中ｏ＝（一·二一；）协砀＝一·乃小·乃咄面）＝ｓｐ／（ｓｐ—ｓｑ）ｇ＝ｐ＋ｔ｜‘ＰＲ其中‘＝ｓｐ／（ｓｐ一们ａｔ＇ＯＲ与平面∥相交且交线为ＦＧ，贝Ｉ｜ＡＰＱＲ与削丑Ｃ相交当且仅当ＦＧ与ａｃｔｃ肚。＝ｃ：，；，西＝ｌ至季ｊ＝ｃｑ—ｑ，·ｃｑ一以，＋ｃ吩一勺，·ｃｑ一吒，ｄｅｔ（ＡＢＣ）的值为ＡＡＢＣ的面积的两倍，当且仅当顶点Ａ、Ｂ、Ｃ呈逆时针顺序排列时，ｄｅｔ（一，Ｂ，Ｃ）＞０；当且仅当顶点Ａ、Ｂ、ｃ呈顺时针顺序排列时有ｄｅｔ（Ａ，Ｂ，ｃ）＜ｏ；当且仅当顶点Ａ、Ｂ、Ｃ共线时，ｄｅｔ（Ａ，Ｂ，ｃ）＝ｏ（１）点Ｐ与ＡＡＢＣ的相交测试鲋ＢＣ的顶点呈按逆时针方向排列，点Ｐ位于＆４ＢＣ内部当且仅当ＡＡＢＰ、ＡＢＣＰ、ＡＣＡＰ的项点均为逆时针方向排列。分别计算ｄｅｔ（Ａ，Ｂ，Ｐ），ｄｅｔ（Ｂ，ｃ，Ｐ）和ｄｅｔ（Ｃ，Ａ，Ｐ），如果它们均大于０，则点Ｐ与ＡＡＢＣ相交，否则不相交。（２）线段而与鲋Ｂｃ的相交测试在二维平面中，线段ＦＧ所在的直线ＦＧ将平面分成两个不相交的开半平面，这两个开半平面中的点分另Ⅱ位于而的左侧和右侧。定义点Ｌ位于ｉ舀的左侧是指Ｆ，Ｇ，Ｌ呈逆时针顺序排列，ＯＰ满足ｚｄｅｔ（Ｆ，Ｇ，三）＞０，定义点Ｒ位于丽的右侧是指Ｆ，Ｇ，Ｒ呈顺时针顺序排列，即满足ｄｅｔ（Ｆ，Ｇ，Ｌ）＜０。①如果顶点Ａ、Ｂ、Ｃ位于直线ＦＧ的同一侧，则线段ＦＧ与ＡＡＢＣ不相交；②否则，假设Ａ、Ｂ位于一侧，而ｃ位于另一侧，：牙、否否分别与直线ＦＧ相交。如果Ｆ和Ｇ同时位于ＢＣ的右侧或者同时位于Ｃ■的右侧（Ａ，Ｂ，Ｃ按逆时针顺序），则线段ＦＧ与Ｍ曰Ｃ不相交；否则相交。（３）ＡＡＢＣ和ＡＰｐＲ的相交测试二维平面中两个三角形不相交当且仅当存在某一个三角形的一条边，使得另一个三角形的三个顶点均位于这条边的右侧（三角形的顶点按逆时针顺序排列）。因此，我们只需依次测试寻找这样的一条边即可，如果不存在这样的一条边，则这两个三角形相交。１９⑨硕士擘位论文ＭＡ．ＳＴＥＲ‘ＳＴＨＥＳｌＳ２．３．３改进的三角形与三角形相交测试三角形与三角形快速相交测试算法通过计算两个三角形所属平面的位置关系来快速判定三角形是否相交。假定两个三角形分别为Ｔｌ和Ｔ２，三角形定义为三个顶点的集合，基本步骤如下Ｉ删：（１）计算Ｔ１的平面方程，得到平面Ｆ１。（２）计算Ｔ２的三个顶点‰，匕。，％到平面Ｆ１的有符号距离分别为ｄｉｓｔＶ２０，ｄｉｓｔ吃。，ｄｉｓｔ％·（３）Ｌａｄ较ｄｉｓｔ％，ｄｉｓｔ匕Ｉ，ｄｉｓｔＶ２２的符号。果ｄｉｓｔ‰，ｄｉｓｔ匕．，ｄｉｓｔ％符号相同，并且都不等于０，则两个三角形的平面平行但不共面，即两个三角形不相交，结束算法；如果ｄ衙‰，ｄｉｓｔ匕。，ｄｉｓｔ％２都等于０，则Ｔ１和Ｔ２共面，则转步骤（４）；否则，转（５）。（４）执行二维空间中的三角形相交测试。测试Ｔｌ的三条边与Ｔ２的三条边是否相交，如果有一对边相交，则两个三角形相交；如果每对边都不相交，则进一步进行顶点与三角形的测试，以此来判断Ｔｌ是否在Ｔ２内部或者Ｔ２是否在Ｔ１内部；如果Ｔ１和Ｔ２互不包含，则Ｔｌ和Ｔ２不相交。（５）计算Ｔ２的平面方程，得到平面Ｆ２。（６）计算Ｆｌ和Ｆ２的交线Ｌ。（７）分别计算Ｔ１和Ｔ２的两条边与Ｌ的交点形成的相交区间，即线段‘和ｆ，。如果区间＾和‘不重叠，则Ｔ１和Ｔ２不相交，返回假。否则Ｔｌ和Ｔ２相交，返回真。２．３．４改进的三角形与包围盒相交测试三角形与包围盒的快速相交测试基于“分离轴”理论【４钔。基本步骤如下：（１）将三角形与包围盒平移，使得包围盒的中心与坐标原点重合。（２）计算包围盒与三角形是否能被１３条轴线（从ＢＢ的三个法向量，三角形的法向量，三角形的三条边分别与包围盒的三个法向量的叉积形成的９条轴线）分离到两侧。如果可以，则两者不相交，返回假；否则只要有１个轴线不能将两者分离，则三角形与包围盒相交。当轴线为ＡＡＢＢ的法向量时，转步骤三；当轴线为三角形的法向量时，转步骤四；当轴线为向量叉积形成的９条轴线时，转步骤五。⑨硕士擘住论文ＭＡＳＴＥＲ‘ＳＴＨＥＳＩＳ（３）进行包围盒与三角形的最小包围盒的重叠测试。（４）进行平面与包围盒的快速测试。寻找包围盒的与三角形平面法向量方向最接*齐的对角线的两个端点，如果最小的端点位于平面的正面，则三角形与包围盒不相交，否则两者相交。（５）将三角形的三个顶点和包围盒分别投影到轴线上。三角形的三个顶点投影到轴线上时，寻找投影点的最大值ｍａｘ和最小值ｍｉｌｌ，包围盒投影到轴线上时，寻找投影的区间半径ｒ，如果ｍａｘ＜．，或者ｍｉｎ＞，，则三角形与包围盒不相交，否则相交。２１⑨３．１硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩ￥第三章ＡＡＢＢ包围盒的全局搜索优化ＡＡＢＢ包围盒的相交测试原理三维空间里的对象相交问题可以转化至４二维或一维空间里来处理。通过降低维度来提高处理问题的效率。这里将三维空间的包围盒的重叠测试问题转化到一维空问来进行。两个包围盒有重叠当且仅当它们在三个坐标轴上的投影区段都有重叠。证明过程如下：定理ｌ如果两个凸多面体不相交，那么一定存在一个空间平面，使得该平面的法向量或者垂直于其中一个凸多面体的一个面，或平行于分别来自两个凸多面体的两条边的叉乘积。定理中的空间平面称为分离面，类似可以定义分离轴，即空间中的一条轴且两个凸多面体在该轴上的投影区段不重叠。显然一条分离轴存在当且仅当与它垂直的分离面存在，由此可得如下推理：推理如果两个凸多面体不相交，那么一定存在一条分离轴，使两凸多面体在该轴上的投影区段不重叠，且该轴或垂直于其中一凸多面体的一个面，或平行于分别来自两凸多面体的两条边的叉乘积。对于ＡＡＢＢ包围盒，因为ＡＡＢＢ是凸多面体，所以根据推理可得：若两个ＡＡＢＢ在三个坐标轴上的投影区段均重叠，那么它们必相交。又因为ＡＡＢＢ的三个边方向分别与工、Ｙ、ｚ三个坐标轴平行，面的法向量方向也是分别与三个坐标轴方向平行的，所以可能的分离轴方向也只有三个，即工、Ｙ、ｚ坐标轴方向，因此，若两ＡＡＢＢ相交，则它们不存在分离轴，即它们在三个坐标轴上的投影区段均重叠。由此证明两个ＡＡＢＢ包围盒相交当且仅当它们在三个坐标轴上的投影区段均重叠。这里以二维空间为例，给出了两个对象相交及其ＡＡＢＢ包围盒投影重叠的状态，如图３．１所示。硕士擘住论文ＭＡＳＴＥＲ‘ＳＴＨＥＳＩＳＣａ）对象相交（ｂ）对象的ＡＡＢＢ包围盒相交图３．１二维空间里的对象及其包围盒相交由ＡＡＢＢ的定义知ＡＡＢＢ上具有最小和最大Ｘ、Ｙ、ｚ坐标值的点必定是顶点，且它们在三个坐标轴上的投影值是该ＡＡＢＢ在相应坐标轴上投影的最小和最大值线段。不妨称具有最小坐标值的顶点为最小顶点，同样称具有最大坐标值的顶点为最大顶点，这样判断两ＡＡＢＢ是否相交，只要通过分别比较它们的最小顶点和最大顶点四个点的Ｘ、Ｙ，ｚ坐标值即可。假设两个ＡＡＢＢ的最小顶点和最大顶点分别为日（厶。，厶。，厶：），Ｑｌ（ｑ。，ｑ。，ｑ：）和最（ｚ。，厶。，厶：），Ｑ２（乜。，马。，皿：），判断它们是否相交的具体算法如图３．２所示：图３．２两个ＡＡＢＢ相交测试算法３．２时空相关性假设在一个应用系统中时间采样点间隔足够小以致对象没有经历大的移动，并且（或者）在两个时间采样点里，对象总的数量没有大的增加或减少，这样应用中的一些特征在两个连续的时间采样点里没有大的改变，这个属性称为时空相关性。即从上个时间采样点到当前时间采样点里，对象的移动和变形是微小的，同时，对象总数量的改变在一个可以接受的范围里。大多数动态应用里都提出了时空相关⑥性。硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ在虚拟环境中，对象的运动具有很大的随意性，它通常取决于动态约束或外部力量的作用，不能用关于时间的函数准确地描述，故而无法提前获得它们在下一时间采样点的信息。为了达到实时交互的目的，碰撞检测的时间采样点的取值就十分紧密（为保证视觉上的自然流畅，刷新速度一般不低于２０帧／秒，而在力反馈系统中为保证触觉的真实感，带宽一般不低于３００Ｈｚｔ３８】）；此外对象在虚拟环境中进行六个自由度的旋转和平移运动，其运动路径是连续的。密集的时间采样点使得在一个时间段内活动对象的位置和状态的变化都很小；同时，在上一个时间采样点，如果两个对象没有发生碰撞，则在当前的时间点，它们很可能仍不碰撞；如果两个对象发生碰撞，则在当前的时间点，它们很可能仍发生碰撞，并且碰撞点与上一碰撞点位置邻近，这一特性说明虚拟环境中对象的运动具有时空相关性。时空相关性使得相邻时间采样点上的碰撞检测具有很大的相似性，可以利用这一特性有效地提高碰撞检测的效率。本文引入时空相关性的概念，利用它来加速对象在系统轴上的排序过程。在当前时间采样点得到的排序序列对下一个时间采样点而言可以认为是几乎排好序的序列，这样在碰撞检测算法的全局搜索阶段就可以较快速的从多个对象中找到需要进一步进行精确碰撞检测的对象。同时本文的后续工作也将利用时空相关性来加快对象变形后的更新操作。３．３从明的排序方法假设虚拟环境中的每个对象都被一个ＡＡＢＢ包围盒所包围，如果对所有对象直接进行两个包围盒问的相交测试，那么所需要的计算时间是比较大的。为了减少计算时间，可以对包围盒进行排序来确定相交的包围盒，从而确定需要进一步进行碰撞检测的对象对。如何对包围盒进行排序呢？本文采用降低维度的方法。将三维空间中的ＡＡＢＢ包围盒投影到二维空间，得到一些长方形区域，再对这些区域进行二维空间排序，确定哪些包围盒有相交，把这个方法称为二维空间排序法。类似的，也可将三维空间中的ＡＡＢＢ包围盒投影到一维空间，即ｘ、Ｙ、ｚ坐标轴上，得到一些一维区间，再对三个坐标轴上的投影区间进行排序来确定相交的包围盒，此方法称为一维空间排序法。经典的基于Ａ．ＡＢＢ包围盒的Ｉ－Ｃｏｌｌｉｄｅ算法库采用的是一维空间排序法。本文针对此方法提出了改进方法。文献【３６１也提出了排序的改进方法。在典型的虚拟空间中，任一时刻只有部分对象会发生碰撞，因此在将包围盒向一个坐标轴（Ｊ轴）投影得到一系列区间后，经区间排序，就可以排除掉不与其它任何对象相交的对象。如果重叠的区间对数不多，就按次序验证这些区间对在其它坐标轴（Ｙ轴、ｚ轴）上是否相交。这样不仅节省了存储空间，而且避免了很多无所谓的排序和搜索。有时，第一次投影排序后排除的对象可能很少。比较稳妥的办法是采用二维空间排序法，即将对象包围盒向坐标面（工一Ｙ面）投影，然后用矩形排序算法进行筛选，最后验证重叠的矩形对在另一坐标轴（ｚ轴）上的投影是否相交。由３．１节可知，两个从ＢＢ彼此相交当且仅当他们在相应系统轴上的垂直投影都是重叠的。这就意味着，三维空间的包围盒重叠测试问题可以简化为一维的，排序ＡＡＢＢ的一维投影可以得到重叠区间。对大多数情况，这个排序的列表将拥有时空相关性，即它们在两个时间采样点的改变是微小的。Ｉ－Ｃｏｌｌｉｄｅ算法对投影列表采用的是插入排序法，本文采用一个特殊的排序算法来有效地处理投影列表：希尔排序。希尔排序由Ｓｈｅｌｌ在１９５９年【３９】首次提出，是一个较老的排序算法。一般来说，和快速排序或堆排序相比，它的效率比较差。然而，希尔排序作为插入排序的延伸，对一个近乎排好序的输入，能够达到ｏ（Ｎ）的速度，同时也比插入排序要强健些。因此本文采用希尔排序法对ＡＡＢＢ在三个坐标轴上的投影值进行排序。在排序操作时，保存当前时间采样点的投影列表，在下一个时间采样点就只需要修改运动对象的投影值。同时，还需要跟踪和记录投影区间的重叠状态变化情况，以此来判断包围盒是否相交。３．４排序过程的优化碰撞行为和其它机械现象类型，它也是一个局部行为，比如碰撞中发生的变形。也就是说，一个对象仅能和它附近的对象碰撞，几乎不受离它较远的对象的影响。碰撞的这个属性经常被称为空间定位。例如在图３．３里，对象Ｂ没有和对象Ａ接触，因此它们应该被认为没有碰撞。然而，对象Ａ和８在ｘ轴上的投影重叠，当对所有对象的投影值一起排序时，对象Ａ和Ｂ将不可避免的被记录一次重叠。这样，随着对象数量的增加，重叠测试过程将比排序过程更加费时。为了克服这点，这里在排序过程中将每个坐标轴划分为一系列包含相同数目投影区间的子段。当每个坐标轴上的投影区问数不能等值划分时，使得最后一个子段的投影区间数小于前面的子段含有的投影区阃数。例如在某个坐标轴上有１１０个投影区间，需要划分为４个子段，则前３个子段含有３０个投影区间，第４个子段含有２０个投影区间。一般来说，坐标轴划分的越细，算法的执行速度将越快。但是，图３．３二维空间的轴划分不能无的划分下去，在一个方向上一个ＡＡＢＢ包围盒只能被划分一次。图３．４中对象Ｍ被划分了两次，则中间斜线阴影部分将不会参与碰撞检测。而且在实际应用中，一般也不需要通过细分坐标轴来提高算法的执行性能。如果在应用中碰到了体积非常大的对象，在执行碰撞检测之前算法也会通过预处理过程将对象划分为一些体积较小的部分，以方便算法的执行。图３．４轴划分的伴随着坐标轴的划分，虚拟环境中的对象也被划分为一系列子部分，子部分服从于重叠测试。如图３．３所示，石轴和ｙ轴都被划分为两段，相应的划分被标记为虚线。进行坐标轴划分后，重叠测试将被在每个子段里进行，这样相距较远的对象之间就不会互相影响，从而减少需要进一步进行碰撞检测的对象对数。图３．３⑧硕士擘住论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ里，对象Ａ和Ｂ在不同的子集里，它们彼此之间不会发生干涉。但是需要注意的是，这里提到的坐标轴划分方法虽然被认为是一个相等划分策略，但是却不同于空间划分方法。传统的空间划分方法划分一个仿真空间为相等大小的单元，然而对所有的虚拟空间而言无法选择一个最好的划分尺寸。坐标轴划分考虑的是对象而不是空间，它和排序过程合为一体，因此，算法的效率不受空间大小或对象分布的影响，总的内存需求于空间大小。３．５全局搜索算法全局搜索过程包含三个步骤：为各个对象计算其ＡＡＢＢ包围盒；建立对象在三个坐标轴上的投影列表，扫描列表，对包围盒的最大坐标值和最小坐标值进行排序；确定有重叠的包围盒对。其中后两个步骤在算法中是同时实现的。下面主要介绍后两步操作。初始状态的投影列表是根据对象序号得到的各个对象的顶点值序列，为了叙述简便，这里以二维空间为例，给出后两步操作的实现过程：①对Ｙ轴进行划分，得到Ｙ轴上的投影序列的子序列；②对Ｙ轴的各个投影子序列进行希尔排序；⑨得到Ｙ轴的排序列表Ｙ１：④对Ｘ轴进行划分，执行希尔排序，得到排序列表Ｘ１；⑤根据Ｘ１重新组合列表Ｙｌ，得到列表Ｙ２；⑥循环Ｘ１和Ｙ２的每个子列表，进行如下操作：检查列表ＸＩ的重叠区间检查列表Ｙ２的重叠区问，报告重叠对象对。这里要注意的是，在环境中可能碰到这样的情况：某两个对象在坐标轴划分阶段都被划分为两部分，而且这两个对象实际也是重叠，如图３．５的对象Ａ和对象Ｂ。当对平面左下区间对应的ｘ轴和Ｙ轴子列表进行重叠测试时，可以得出结论对象Ａ和对象Ｂ重叠，算法再对平面右下区间进行重叠测试时就不再需要检查对象Ａ和对象Ｂ是否重叠，减少算法的执行时间。本文设定的虚拟环境中，只考虑两个对象间的碰撞，而不会出现一个对象与多个对象间的碰撞。这里为每一对包围盒都设置一个重叠状态，该状态由３个布尔变量组成，分别对应３个坐标轴的方向。当３个布尔变量都被设为真值时，就说明此对包围盒有重叠，然后将此对包围盒放到重叠列表中。对于图３．５所示的对象Ａ和对象Ｂ，当在平面右下区间进行重叠测试，扫描各个轴的子列表时，就可以将略过对对象Ａ和对象Ｂ的检查，减少冗余的计算时间。图３．５对象对在两个划分区间均重叠３．６实验本文给出的全局搜索过程基于ＡＡＢＢ包围盒，与传统算法相比，主要改进在于对坐标投影值的排序操作。Ｉ－Ｃｏｌｌｉｄｅ算法库的全局搜索算法采用的是基于ＡＡＢＢ包围盒的一维空间排序法，我们对此算法进行了修改，采用坐标轴划分策略，并对投影列表进行希尔排序。这里设定了一些特定场景，人工给出场景中各个对象的包围盒投影坐标值，比较了两种算法在相同场景中检测到碰撞所需的时间，比较结果如图３．６所示。ＡＡＢＢ总数（个）图３．６两种排序方法的比较改进的全局搜索算法在时间性能上优于传统的算法，特别是虚拟环境中对象较多的情第四章ＡＡＢＢ层次包围盒的存储优化４．１存储需求分析由第２章所述的层次包围盒碰撞检测方法，我们可得到此类碰撞检测算法的耗费函数：Ｔ＝Ｎｖ＊Ｃｖ＋Ｎｐ＊Ｃｐ＋Ｎｕ＋Ｃｕ（４．１）其中，ｒ是碰撞检测的总耗费；Ｎｖ是参与重叠测试的包围盒的对数；Ｃｖ是为一对包围盒做重叠测试的耗费；＾ｐ是参与求交的基本几何元素的对数；印是为一对基本几何元素做求交测试的耗费；Ｎｕ是对象运动后其包围盒层次中需要修改的节点的个数；Ｃｋ是修改一个节点的耗费。根据公式４．１和２．２．１节所述的包围盒树的构造方法，我们可以引入如下存储需求函数膨。Ｍ＝∑磁＋∑％＋∑五＋∑Ｄ，ｉ＝ｌ（４．２）卢１＾一ｌＩ＝１其中，Ｍ为总的内存需求字节数；Ｂ‘和肚，分别表示存储ＡＡＢＢ树的一个内部节点和叶节点所需的字节数；五和日分别表示存储一个三角形的顶点值和顶点索引所需的字节数；ｍ和月分别表示ＡＡＢＢ树的内部节点和叶节点的个数。这里要说明的是，在一棵完全ＡＡＢＢ树中，每个叶结点仅含有一个三角形，即ＡＡＢＢ树中三角形的数目和叶节点的数目是相同。４．２存储优化在虚拟的实时环境中对碰撞检测的速度要求是非常高的。当处理任意对象间的碰撞问题时，包围盒方法是非常有效的。对于基于层次包围盒的碰撞检测算法，大部分研究者主要从选择合适的包围盒、采用合适的方法构造包围盒树等方面来提⑨硕士学位论文ＭＡＳＴＥＲ‘ＳＴＨＥＳＩＳ高碰撞检测的速度。这里我们考虑的是从内存需求方面来加速算法。假设环境的输入数据为ｎ个三角形，将所有顶点存到一个数组中，每个顶点的每个轴上坐标值分别用４字节浮点数表示，存储量为３６ｎ字节，即存储一个三角形需要３６个字节。包围盒树中存储每个三角形都需要一个不可忽略的字节数，这引发了我们对包围盒树存储需求问题的关注。文献【３８Ｊ中提到的早期用于减少包围盒树存储需求的方法主要有两种。一是使得包围盒树每个叶节点含有多于一个的三角形，这样得到的包围盒树就不是一棵完全树，减少了包围盒树内部节点和叶节点的个数，但是在遍历包围盒树进行两个叶节点Ｌ１和Ｌ２的重叠测试时需要进行Ｎｌ＋Ｎ２次三角形的相交测试（Ｎ１，Ｎ２分别为Ｌ１和Ｌ２含有的三角形个数），这样增加了算法的执行时间【３９】；二是根据包围盒树节点的左右孩子节点的存储地址总是相邻的，使得一个孩子节点的索引信息变为隐藏信息。两种方法都减少了包围盒树的内存需求，但也一定程度上增加了检测碰撞的时间。文献【３９】中作者对ＡＡＢＢ包围盒进行了存储压缩，减少了存储整棵ＡＡＢＢ包围盒树所需的字节数，但是在获取节点的ＡＡＢＢ的范围值时却要消耗一定的检索时间，在三角片数目小于１０ｋ的时候几乎没有提高算法时间效率。本文的存储优化算法在文献【３９１所提的存储优化方法的基础上进行了改进。为了加速算法，利用ＭＳｌｌｅｒ提出的两种有关三角形的快速检测方法来优化叶节点的存储。实验证明，结合内部节点和叶节点的存储优化减少了包围盒树的内存需求，同时也提高了碰撞检测的速度。４．２．１ＡＡＢＢ包围盒优化ＡＡＢＢ树的内部节点的常规存储结构包括ＡＡＢＢ包围盒、左孩子索引和右孩子索引三个域Ｉ矧。对象的ＡＡＢＢ包围盒是包围该对象并平行于坐标轴的最小的六面体，由其基本几何元素集合中每个元素的顶点坐标在Ｊ，Ｙ，ｚ轴上的最大值和最小值来确定即对对象Ｄ而言州册（ｏ）＝（‰（Ｄ），‰（Ｄ），‰（Ｄ），‰（Ｄ），‰（ｏ），‰（Ｄ））。州ＢＳ（Ｏ）中每个值由一个４字节的浮点数来表示，则存储一个ＡＡＢＢ（０１需要２４个字节。另外，ＡＡＢＢ树中给每个内部节点添加了两个４字节的分别指向左右孩子节点的索引来增加检索的效率。因此ＡＡＢＢ树中存储每个内部节点共需要３２个字节。⑨硕士擘位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩ￥假定￡和五分别为ＡＡＢＢ树中某内部节点ｒ的左右孩子节点。若Ａ４肋（五）＝（—９．８，３．３，４．１，８．６，４．３，ｌｏ．２），丘４胎（不）＝（２．３，１１．２，一８．９，４．９，３．５，９．６），由２．３．１节ＡＡＢＢ树的构造算法可知，ＡＡＢＢ（Ｔ）＝（－９．８，１１．２，－８．９，８．６，３．５，１０．２）。朋船（五）与ＡＡＢＢ（Ｔ）的某些值相同，对于朋肋（五）也一样。两个孩子节点的ＡＡＢＢ包围盒与父节点的ＡＡＢＢ包围盒最多有六个取值不同【４１，４２１，孩子节点与父节点间存在数据冗余。为了减少冗余数据的重复存储，我们在父节点中增设一个字节的标志位，使得冗余的数据只在父节点中存储一次。但ＡＡＢＢ树的根节点包围盒的存储例外，其包围盒信息存储完整的六个坐标值。根节点结构如表４．１所示。表４．１根节点结构范围值（４×６＝２４个字节）Ｉ左子节点索引右子节点索引（４个字节）Ｉ（４个字节）￡ｍ‘。Ｌｍ瓦一正ｍＺ一％ｗ７ｋ标志位（１个字节）标志位的每一位取值为０或者为１。其中瓦。和７乙。表示节点的左右子节点是否为叶节点，若是则取值为ｌ，否则取值为０。标志位前六位的取值对应着左右子节点的包围盒的范围值，按照‰，‰，‰，‰，‰，‰的顺序，如果范围值与左子节点的范围值相同，则对应标志位为ｌ，如果与右子节点的范围值相同，则对应标志位为０。上例中父节点的标志位前六位取值为（１，０，０，１，０，１）。一般而言，标志位前六位的０和１的个数是相同的。但是有两种情况除外，左右子节点在某个轴上有相同的范围值或者一个子节点的包围盒完全包含了另一子节点的包围盒。这两种情况下可以调整子节点包围盒的值使得０和１的个数相同【４３１。冗余的数据在父节点中存储，对于子节点来说只需存储不相同的范围值。即每个内部节点的包围盒信息只需要用３个浮点数（按工。Ｙ，ｚ轴）共１２个字节来表示。上例中爿４８口（正）就简化为（３．３，４．１，４．３）。加上１个字节的标志位，两个４字节的索引，存储一个内部节点共需要２１个字节，其结构如表４．２所示。⑥硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩ￥表４．２内部节点结构范围值（４ｘ３＝１２个字节）左子节点索Ｓ（４个字节）右子节点索｝（４个字节）标志位（１个字节）对于一棵有Ｎ个叶节点的ＡＡＢＢ树来说，共有Ｎ—１个内部节点，忽略根节点添加的１个字节的标志位，可以节省（Ｎ一２）｝（３２－２１）个字节。４．２．２叶节点优化对对象Ａ和对象Ｂ进行碰撞检测，主要是对两者的ＡＡＢＢ树的节点进行重叠测试，遍历ＡＡＢＢ树进行重叠测试的是叶节点与叶节点，叶节点与内部节点，内部节点与内部节点。对两叶节点进行重叠测试时先测试叶节点所含的三角形的ＡＡＢＢ包围盒是否相交，若不相交则测试终止；否则，再执行三角形与三角形之间的相交测试。包围盒的求交比三角形的求交简单，时间消耗少，所以先用包围盒求交剔除不相交的叶结点。但是对于三角形相交的叶节点而言，这一步操作增加了时间消耗。应用Ｍ６ｌｌｅｒ提出的快速三角形与三角形相交测试算法ｆ“朋１，在对叶节点作重叠测试时我们直接进行三角形间的相交测试。这样就不需要使用其ＡＡＢＢ包围盒信息。同样的，当对对象Ａ的叶节点和对象Ｂ的内部节点（或者相反）进行重叠测试时，应用Ｍ６ｌｌｅｒ提出的快速三角形与包围盒相交测试算法Ⅲ】，我们也可以略过包围盒重叠测试的步骤，直接进行三角形与包围盒的相交测试而不增加算法的时间开销。ＡＡＢＢ树叶节点的常规存储结构包括ＡＡＢＢ包围盒信息和三角形索引两个域。对象Ａ和对象Ｂ的ＡＡＢＢ树重叠测试过程中涉及到叶节点的重叠测试都可以不用到包围盒信息而直接用三角形进行测试，这样就可以从叶节点的存储结构中删去包围盒信息。叶节点的存储结构中只有三角形的索引信息，此时就不必再用一个的节点表示叶节点。我们将三角形索引存放到父节点中，从包围盒树的存储空间中删除叶节点。叶节点的三角形索引在父节点中存放时不需要为父节点分配额外的存储空间，直接替换父节点的孩子索引域为孩子叶节点的三角形索引信息。此时，叶节点的父节点结构如表４．３所示。表４．３叶节点的父节点结构范围值（１２个字节）左子节点三角形索｝（４个字节）右子节点三角形索引ｌ（４个字节）标志位（１个字节）ＩＩｌｌＩｆ１１图４．１所示为一棵含有１２个叶节点的ＡＡＢＢ树，我们需要存储１１个内部节点，１２个叶节点。删除叶节点结构后，只需要存储１１个内部节点（图４．２），大大节省了存储空间。图４．１优化前的ＡＡＢＢ树图４．２优化后的允４船一棵含有Ｎ个叶节点的完全ＡＡＢＢ树共有２＊Ｎ一１个节点，存储Ａ，４ＢＢ树时不需要为叶节点分配存储空间，则相当于从包围盒树的节点中删掉了一半的节点，这样大大节省了存储空间，减少了一半的内存需求。经过上述优化之后碰撞检测算法的节点之间的重叠测试算法如图４．３所示：图４．３节点重叠测试算法３３⑨硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳｌＳ４．３实验与结果分析ＳＯＬＩＤ是一个开放的用于检测多个对象间碰撞的算法库，它采用的是ＡＭＢＢ包围盒树算法。我们在Ｐｃ机（ｃＰＵＰ４１．６ＧＨｚ，内存５１２Ｍ，显卡Ｓ３ＧｒａｐｈｉｃｓＰｒｏＳａｖａｇｅＤＤＲ，显存１２８Ｍ）平台上修改了代码。应用三角形之间的快速相交测试算法来删除叶节点，然后优化包围盒结构，使其仅需２１个字节。这使得Ａ，４ＢＢ比标准的ＡＡＢＢ要小，而且仅需要一个标准树的一半节点。我们设置多个场景来测试算法的有效性，其中一个场景如图４．４所示。场景中三角片数分别为８９９４和４４７８２。图４．５显示了修改后的算法与原算法的比较结果。图４．４测试场景（左图未发生碰撞，右图发生碰撞）０ＶＥ垦富嚣掣划型图４．５存储优化前后算法性能比较⑨硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳｌＳ包围盒存储结构的优化减少了存储需求，但是同时又使得内部节点包围盒的取值都要参考根节点的包围盒值，这就需要额外消耗一定的检索时间。所以当三角形的数目较少时，对包围盒优化后的算法（简称为算法１）与未优化算法的执行时间相差无几。但是随着三角形数目的增加，算法１的优越性逐渐表现出来。在相同场景中，算法ｌ的执行时间要快１０％左右。对叶节点优化后的算法（简称为算法２）减少了树的遍历深度，节省了存储空间而没有增加额外的时间消耗，加快了算法的执行。由于算法１要花费时间查找相关信息，所以结合算法１和算法２得到的优化算法（简称为算法３）的执行时间要略慢于算法２。相同场景中，算法２所用的执行时间约为算法３所用时间的０．８８，而算法１所用时间约为算法３所用时间的１．２７倍。算法３将两种优化操作结合起来使得算法在存储空间和执行效率上达到了平衡。⑨硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ第五章总结和展望随着虚拟现实技术的不断发展，应用领域的不断扩大，对虚拟环境的实时性和真实性的要求越来越高。在虚拟环境中，物体的运动和用户的交互经常会导致碰撞的发生，从而破坏虚拟环境的真实感和用户的沉浸感，因此必须进行碰撞检测。层次包围盒方法是常用的碰撞检测方法，本文研究了基于ＡＡＢＢ包围盒的碰撞检测算法的改进方法。５．１主要工作总结本文介绍了传统的基于ＡＡＢＢ包围盒的碰撞检测算法的相关知识，在此基础上针对基于ＡＡＢＢ包围盒的碰撞检测算法的两个层次：全局搜索和局部检测，进行了检测方法的改进，并详细论述了这两种改进方法。第一种改进方法是基于虚拟环境中对象运动的时空相关性，前一时间点的对象包围盒在三个坐标轴上的投影值序列对下一个时间点而言是基本有序的，所以在对包围盒的投影值序歹４进行排序时采用希尔排序而不采用常用的插入排序法。由于虚拟环境中只有相距较近的对象之间才会发生碰撞，而某些相距较远的对象对可能在某个坐标轴上的投影值会重叠，因此在排序之前对坐标轴进行相应的划分，使得排序操作局限于一定的范围内，减少了算法所需的计算时间。第二种改进方法是针对局部检测过程。在全局搜索阶段得到初步相交的对象对将会在局部检测阶段进行精确的碰撞检测，层次包围盒方法通过构造对象的包围盒树，然后遍历包围盒树得出碰撞与否的结论。本文根据ＡＡＢＢ包围盒的构造特性，压缩对象的ＡＡＢＢ树存储，减少算法所需的内存空间来提高碰撞检测的速度。本文在已有的ＡＡＢＢ包围盒压缩方法的基础上进一步对ＡＡＢＢ树的叶结点进行存储优化，将ＡＡＢＢ包围盒和叶节点的优化结合在一起，既减少了算法的存储需求又提高了碰撞检测的速度。本文给出的两种优化方法分别针对碰撞检测算法的不同层次，两种优化算法可以结合在一起使用，也可以分别与别的算法结合在一起使用。例如，我们可以将第三章所述的改进方法作为全局搜索方法，局部检测则采用Ｌｉｎ－Ｃａｎｎｙ算法。本文采用的是ＡＡＢＢ包围盒，所述方法同时适用于刚体对象和变形体对象。５．２研究展望在未来的工作中，我们将围绕以下两个方面继续开展研究工作：⑨硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ（１）变形体对象的基本几何元素的位置或形状会随着时问的推移而变化，因此应处理对象变形后的ＡＡＢＢ树的更新问题。本文在这方面未作详细的讨论，仅仅给出了常用的更新方法。因此进一步的工作是讨论对象变形后的ＡＡＢＢ包围盒更新问题。ＡＡＢＢ包围盒的更新问题可以结合时空相关性来进行。在对象运动的前一时间点和下一时间点状态，考虑根据基本几何元素的包围盒与对象的包围盒的体积之比，或者ＡＡＢＢ树的节点的孩子数目的变化来更新ＡＡＢＢ树。（２）在包围盒存储空间的优化方面也将进行进一步的探索，不再局限于ＡＡＢＢ包围盒。ｋ－ｄｏｐ包围盒在所有包围盒中的紧密性最好，它也能同时适用于刚体对象和变形体对象，也可以考虑从存储空间的角度来优化其树型存储结构。参考文献［１】汪成为，高文，王行仁著．灵境（虚拟现实）技术的理论、实现及应用．北京：清华大学出版社，１９９６，９．【２】Ｍ．ＭｏｏｒｅａｎｄＪ．Ｗｉｌｈｅｌｍｓ．Ｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎａｎｄｒｅｓｐｏｎｓｅｆｏｒｃｏｍｐｕｔｅｒａｎｉｍａｔｉｏｎ．ＡＣＭＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９８８，２２（４）：２８９～２９８．［３】Ｄ．Ｂａｒａｆｆ．Ｉｎｔｅｒａｃｔｉｖｅｓｉｍｕｌａｔｉｏｎｏｆｓｏｌｉｄｒｉｇｉｄｂｏｄｉｅｓ．ＩＥＥＥＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄｂｏｄｉｅｓ．ＡＣＭＡｐｐｌｉｃａｔｉｏｎｓ，１９９５，１５（３）：６３～７５．【４】Ｄ．Ｂａｒａｆｆ．ＦａｓｔｃｏｎｔａｃｔＣｏｍｐｕｔｅｒｆｏｒｃｅｃｏｍｐｕｔａｔｉｏｎｆｏｒｎｏｎｐｅｎｅｔｒａｔｉｎｇｒｉｇｉｄＧｒａｐｈｉｃｓ，１９９４，２８（１）：２３～３４．ｓｕｒｖｅｙｏｆｔｅｃｈｎｉｑｕｅｓｆｏｒｓｉｍｕｌａｔｉｏｎｏｆｄｙｎａｍｉｃｃｏｌｌｉｓｉｏｎ［５】Ｖ．Ｖ．Ｋａｍａｔ．Ａｄｅｔｅｃｔｉｏｎａｎｄｒｅｓｐｏｎｓｅ．Ｃｏｍｐｕｔｅｒ＆Ｇｒａｉ。ｈｉｃｓ，１９９３，１７（４）：３７９—３８５．【６】Ｊ．Ｍ．Ｓｎｙｄｅｒ．ＡｎＡＣＭＣｏｍｐｕｔｅｒｉｎｔｅｒａｃｔｉｖｅｔｏｏｌｆｏｒｐｌａｃｉｎｇｃｕｒｖｅｄｓｕｒｆａｃｅｓｗｉｔｈｏｕｔｉｎｔｅｒｐｅｎｅｔｒａｔｉｏｎ．Ｇｒａｐｈｉｃｓ，１９９５，２９（４）：２０９－，－２１８．【７】石教英．虚拟现实基础及实用算法．北京：科学出版社，２００２，４．［８】魏迎梅，王涌，吴泉源，石教英．虚拟手术仿真中碰撞检测问题的研究．系统仿真学报，２０００，５（１２）：５７２～５７５．【９１Ｃ．Ｆ．Ｌｉ，Ｙ．Ｔ．Ｆｅｎｇ，Ｄ．Ｒ．Ｊ．Ｏｗｅｎ．ＳＭＢ：Ｃｏｌｌｉｓｉｏｎｃｏｈｅｒｅｎｃｅ．Ｃｏｍｐｕｔｅｒｍｅｔｈｏｄｓ１９５：２２５２～２２６９．ｉｎｄｅｔｅｃｔｉｏｎｂａｓｅｄｏｎｔｅｍｐｏｒａｌａｐｐｌｉｅｄｍｅｃｈａｎｉｃｓａｎｄｅｎｇｉｎｅｅｒｉｎｇ，２００６，【１０］ＬｉｎＭＣ，ＪＰｒｏｃＩＥＥＥＥＦＣａｎｎｙ，Ａｆａｓｔａｌｇｏｒｉｔｈｍｆｏｒｉｎｃｒｅｍｅｎｔａｌｄｉｓｔａｎｃｅｃａｌｃｕｌａｔｉｏｎ［ｃ］．Ｉｎ：ＣｏｎｆｏｎＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏｎ，１９９１：１００８－１０１４．ＧＪｏｈｎｓｏｎＤ【１１】ＧｉｌｂｅｒｔＤｉｓｔａｎｃｅＲｏｂｏｔｉｃｓｗ，ＫｅｅｒｔｈｉＳＳ．ＡＦａｓｔＰｒｏｃｅｄｕｒｅｆｏｒＣｏｍｐｕｔｉｎｇｔｈｅＴｒａｍｓｏｎｂｅｔｗｅｅｎＣｏｍｐｌｅｘＯｂｊｅｃｔｓｉｎＴｈｒｅｅ－ＤｉｍｅｎｓｉｏｎａｌＳｐａｃｅ．ＩＥＥＥａｎｄＡｕｔｏｍａｔｉｏｎ，１９８８：４（２）：１９２—２０３．ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅｓＵｓｅｄｆｏｒ【１２】Ｊ．Ｌ．Ｂｅｎｔｌｅｙ．ＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＡｓｓｏｃｉａｔｉｖｅＳｅａｒｃｈｉｎｇ．ＡＣＭＣｏｍｍｕｎｉｃａｔｉｏｎｓ，１９７５，１８（９）：５０９－５１７．【１３】Ｈ．Ｎｏｂｏｒｉｏ，Ｓ．ＦｕｋｕｄａａｎｄＳ．Ａｒｉｍｏｔｏ．ＦａｓｔＩｎｔｅｒｆｅｒｅｎｃｅＣｈｅｃｋＭｅｔｈｏｄＵｓｉｎｇＯｃｔｒｅｅＲｅｐｒｅｓｅｎｔａｔｉｏｎ．ＡｄｖａｎｃｅｄＲｏｂｏｔｉｃｓ，１９８９，３（３）：１９３～２１２．【１４］Ｂ．Ｎａｙｌｏｒ，Ｊ．Ａｍａｎａｔｉｄｅｓ，Ｗ．Ｔｈｉｂａｕｌｔ．ＭｅｒｇｉｎｇＯｐｅｒａｔｉｏｎｓ．ＡＣＭＣｏｍｐｕｔｅｒＢＳＰＴｒｅｅｓＹｉｅｌｄｓＰｏｌｙｈｅｄｒａｌＳｅｔＧｒａｐｈｉｃｓ（ＳＩＧＧＲＡＰＨ’９０Ｐｒｏｃｅｅｄｉｎｇｓ），１９９０，⑥［１６】Ｓｔｅｐｈｅｎ硕士擘位论文ＭＡＳＴＥＲ’Ｓ丁ＨＥＳｌＳ２４（２）：１１５－１２４．【１５】ｗ．１１１ｉｂａｕｌｔ，Ｂ．Ｎａｙｌｏｒ．ＳｅｔｏｐｅｒａｔｉｏｎｓｏｎａｏｌｙｈｅｄｒａＵｓｉｎｇＢｉｎａｒｙＳｐａｃｅＰａｒｔｉｔｉｏｎｉｎｇｔｒｅｅｓ．ＡＣＭＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９８７，２１（４）：１５３～１６２．Ｊ．Ａｄｅｌｓｏｒｔ，ＬａｒｒｙＥＨｏｄｇｅｓ．Ｇｅｎｅｒａｔｉｎｇｅｘａｃｔｒａｙ－ｔｒａｃｅｄａｎｉｍａｔｉｏｎ舳ｍ嚣ｂｙｒｅｐｒｏｊｅｅｔｉｏｎ．ＩＥＥＥＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，１９９５，１５（３）：４３－５２．【１７】Ｔ．Ｌ．ＫａｙａｎｄＪ．Ｔ．Ｋａｊｉｙａ．Ｒａｙｔｒａｃｉｎｇｃｏｍｐｌｅｘｓｇｅｎｇｓ．ＡＣＭＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９８６，２０（４）：２６９～２７８．［１８】Ｊ．ＧｏｌｄｓｍｉｔｈａｎｄＪ．Ｓａｌｍｏｎ．ＡｕｔｏｍａｔｉｃＩＥＥＥＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓｃｒｅａｔｉｏｎｏｆｏｂｊｅｃｔｈｉｅｒａｒｃｈｉｅｓｆｏｒｒａｙｔｒａｃｉｎｇ．ａｎｄＡｐｐｌｉｃａｔｉｏｎ，１９８７，７（１）：１４～２０．ｃｏｍｐｕｔａｔｉｏｎａｌｍｅｔｈｏｄｓｆｏｒｒａｙ［１９】Ｈ．Ｗｅｇｈｏｒｓｔ，ＧＨｏｐｅｒａｎｄＤ．ＥＧｒｅｅｎｂｅｒｇ．Ｉｍｐｒｏｖｅｄｔｒａｃｉｎｇ．ＡＣＭＴｒａｎｓａｃｔｉｏｎｏｎＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９８４，３（１）：５２－－６９．【２０】范昭炜，万华根，高曙明．基于图象的快速碰撞检测算法．计算机辅助设计与图形学学报，２００２，１４（９）：８０５～８０９．［２ｌ】Ａ．Ｓｍｉｔｈ，Ｙｋｉｔａｍｕｒａ，Ｈ．Ｔａｋｅｍｕｒａ，ＥＫｉｓｈｉｎｏ．ＡｓｉｍｐｌｅａｎｄＥｆｆｉｃｉｅｎｔＭｅｔｈｏｄｆｏｒｉｎＡｒｂｉｔｒａｒｙＡｃｃｕｒａｔｅＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎａｍｏｎｇＤｅｆｏｒｍａｂｌｅＰｏｌｙｈｅｄｒａｌＯｂｊｅｃｔｓＭｏｔｉｏｎ．Ｔｈｅ２：１３６－－１４５．ＩＥＥＥＶｉｒｔｕａｌＲｅａｌｉｔｙＡｎｎｕｍＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍ，１９９５，【２２】ＧｖａｎｄｅｔＢｅｒｇｅｎ．ＥｆｆｉｃｉｅｎｔＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎｏｆＣｏｌｌｉｓｉｏｎＤｅｆｏｒｍａｂｌｅＭｏｄｅｌｓｕｓｉｎｇＡＡＢＢＴｒｅｅｓ．ＪｏｕｍａｌｏｆＧｒａｐｈｉｃｓＴｏｏｌｓ，１９９７，２（４）：１－１４．【２３】ＹａｓｈｉｆｕｍｉＫｉｔａｍｕｒａ，ＡｎｄｒｅｗＳｍｉｔｈ，ＨａｒｕｏＴａｋｅｍｕｒａ，ＦｕｍｉｏＫｉｓｈｉｎｏ．ＡＲｅａｌｔｉｍｅＡｌｇｏｒｉｔｈｍｆｏｒＡｃｃｕｒａｔｅＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎｆｏｒＤｅｆｏｒｍａｂｌｅＰｏｌｙｈｅｄｒａｌＯｂｊｅｃｔｓＰｒｅｓｅｎｃｅＶ０１７．Ｎｏ．１Ｆｅｂｒｕａｒｙ１９９８：３每ｖ５２．ＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎ［２４】Ｊ．Ｍｅｚｇｅｒ，Ｓ．Ｋｉｍｍｅｆｌｅ，Ｏ．Ｅｔｚｍｕｂ．Ｈｉｅｒ甜ｃＩｌｉｃａｌＴｅｃｈｎｉｑｕｅｓｉｎｆｏｒＣｌｏｔｈＡｎｉｍａｔｉｏｎ．ＪｏｕｒｎａｌｏｆＷＳＣＧｌｌ，２００３，２：３２２～３２９．【２５】ＭａｔｔｈｉａｓＴｅｓｃｈｎｅｒ，ＢｒｕｎｏＨｅｉｄｅｌｅｂｅｒｇｅｒ，ＭａｔｔｈｉａｓＭｕｌｌｅｒ，ＤａｎａｔＰｏｍｅｒａｎｅｔｓ，ＭａｒｋｎｓＧｒｏｓｓ．ＯｐｔｉｍｉｚｅｄＳｐａｔｉａｌＨａｓｈｉｎｇｆｏｒＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎｏｆＤｅｆｏｒｍａｂｌｅＯｂｊｅｃｔｓＭｕｎｉｓｈ，Ｇｅｒｍａｎｙ，Ｎｏｖｅｒｍｂｅｒ，２００３：１９＾之１．【２６】ＭｉｎｇＣ．Ｌｉｎ，ＳｔｅｆａｎＧｏｔｔｓｃｈａｌｋ．Ｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｂｅｔｗｅｅｎｇｅｏｍｅ证ｃｓｕｒｖｅｙ．ＰｒｏｃｅｅｄｉｎｇｏｆＩＥＥＥＩＣＲＡ．１９９１：２６６－－２７５．ｍｏｄｅｌｓ：ａ【２７】ＧｏｔｔｓｃｈａｌｋＳ，ＬｉｎＭＣ，ＭａｎｏｃｈａＤ，ＯＢＢＴｒｅｅｓ：ＡＨｉｅｒａｒｃｈｉｃａｌＳｔｒｕｃｔｕｒｅｆｏｒＲａｐｉｄＩｎｔｅｒｆｅｒｅｎｃｅＤｅｔｅｃｔｉｏｎ．ＡＣＭＣｏｍｐｍｅｒＧｒａｐｈｉｃｓ（Ｐｒｏｃ．ｏｆＳＩＧＧＲＡＰＨ’９６），１９９６：１７１～１８０．【２８】ＪａｍｅｓＴ．Ｋｌｏｓｏｗｓｋｉ，ＭａｒｔｉｎＨｅｌｄ，ＪｏｓｅｐｈＳ．Ｂ．Ｍｉｔｃｈｅｌｌ．Ｅｆｆｉｃｉｅｎｔｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｕｓｉｎｇｂｏｕｎｄｉｎｇｖｏｌｕｍｅｈｉｅｒａｒｃｈｉｅｓｏｆｋ－ＤＯＰｓ．ＳＩＧＧＲＡＰＨ’９６ＶｉｓｉｕａｌＰｒｏｃｅｅｄｉｎｇｓ，１９９６：２６－３７．【２９］Ｊ．Ｄ．Ｃｏｈｅｎ，Ｍ．Ｃ．Ｌｉｎ，Ｄ．ＭａｎｏｃｈａａｎｄＥｘａｃｔＣｏｌｌｉｓｉｏｎＤｅｔｅｃｔｉｏｎａｎｄＭ．Ｋ．Ｐｏｎａｍｇｉ．Ｉ－ＣＯＬＬＩＤＥ：ＡｎＩｎｔｅｒａｃｔｉｖｅＳｙｓｔｅｍｆｏｒＬａｒｇｅ．ＳｃａｌｅＥｎｖｉｒｏｎｍｅｎｔｓ．ＡＣＭＩｎｔｅｒａｃｔｉｖｅ３ＤＧｒａｐｈｉｃｓＣｏｎｆｅｒｅｎｃｅ，１９９５：１８９～１９６．【３０】Ｐ．Ｍ．Ｈｕｂｂａｒｄ．ＣｏｌｌｉｓｉｏｎＴｒａｎｓａｃｔｉｏｎｓｏｎｄｅｔｅｃｔｉｏｎｆｏｒｉｎｔｅｒａｃｔｉｖｅｇｒａｐｈｉｃｓａｐｐｌｉｃａｔｉｏｎｓ．ＩＥＥＥＶｉｓｕａｌｉｚａｔｉｏｎａｎｄＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，１９９５，１（３）：２１８～２３０．【３１】Ｍ．Ｐｏｎａｍｇｉ，Ｄ．Ｍ粕ｏｃｈａ，Ｍ．Ｌｉｎ．Ｉｎｃｒｅｍｅｎｔａｌｂｅｔｗｅｅｎｐｏｌｙｇｏｎａｌｍｏｄｅｌｓ．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＧｒａｐｈｉｃｓ．１９９７：５１—５．ａｌｇｏｒｉｔｈｍｆｏｒｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｏｎＶｉｓｕａｌｉｚａｔｉｏｎａｎｄＣｏｍｐｕｔｅｒ【３２］Ｋ．Ｃｈｕｎｇ，Ｗ．Ｗａｎｇ．Ｑｕｉｃｋｅｌｉｍｉｎａｔｉｏｎｅｎｖｉｒｏｎｍｅｎｔｓ．３“ＥｕｒｏｐｅａｎＷｏｒｋｓｈｏｐｏｎｏｆｎｏｎ－ｉｎｔｅｒｆｅｒｅｎｃｅｐｏｌｙｔｏｐｅｓｉｎｖｉｒｔｕａｌＶｉｒｔｕａｌＥｎｖｉｒｏｎｍｅｎｔｓ，１９９６：１９～２０．［３３】Ｋ．Ｃｈｕｎｇ，Ｗ．Ｗａｎｇ．ＱｕｉｃｋＡＣＭＳｙｍｐｏｓｉｕｍ［３４】Ｋｅｌｖｉｎｏｎｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｏｆｐｏｌｙｔｏｐｅｓｉｎｖｉｒｔｕａｌｅｎｖｉｒｏｎｍｅｎｔｓ．ＶｉｒｔｕａｌＲｅａｌｉｔｙＳｏｔｔｗａｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ，１９９６：１－－４．ＤｅｔｅｃｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒＰｏｌｙｔｏｐｅｓｉｎｖｉｒｔｕａｌＣｈｕｎｇ．ＡｎＥｆｆｉｃｉｅｎｔＣｏｌｌｉｓｉｏｎＥｎｖｉｒｏｎｍｅｎｔｓ．Ｍ．ＰｈｉｌＴｈｅｓｉｓ，ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＵｎｉｖｅｒｓｉｔｙｏｆＨｏｎｇＫｏｎｇ，１９９６，９．［３５】Ｍ．Ｐｏｎａｍｇｉ，Ｄ．Ｍａｎｏｃｈａ，Ｍ．Ｌｉｎ．ＩｎｃｒｅｍｅｎｔａｌｂｅｔｗｅｅｎａｌｇｏｒｉｔｈｍｆｏｒｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎＳｙｒｎｐｏｓＳｏｌｉｄｇｅｎｅｒａｌｓｏｌｉｄｍｏｄｅｌｓ．Ｐｒｏｃ．ＡＣＭＳｉｇｇｒａｐｈＭｏｄｅｌｉｎｇ，１９９５：２９３～３０４．【３６】董峰，王同洋．虚拟环境中的快速碰撞检测算法，计算机工程与应用，２００３，８：６６～６７．【３７】Ｄ．Ｌ．Ｓｈｅｌｌ．Ａｈｉｇｈ－ｓｐｅｅｄｓｏｒｔｉｎｇｐｒｏｃｅｄｕｒｅ，ＣｏｍｍｕｍＡＣＭ，１９５９，２（７）：３０－－３２．【３８］Ｍ．ｈｅｌｄ，Ｊ．Ｔ．Ｋｌｏｓｏｗｓｋｉ，Ｊ．Ｓ．Ｂ．Ｍｉｔｃｈｅｌｌ．Ｅｖａｌｕａｔｉｏｎｏｆｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｍｅｔｈｏｄｓｆｏｒｖｉｒｔｕａｌｒｅａｌｉｔｙｆｌｙｔｈｒｏｕｇｈｓ．ＩｎＰｒｏｃ．７ｔｈＣａｎａｄ．Ｃｏｎｆ．Ｃｏｍｐｍ．Ｇｅｏｍ，１９９５：２０５－２１０．【３９】潘振宽，李建波．基于压缩的ＡＡＢＢ树的碰撞检测算法，计算机科学，２００５，３３（２）：２１３～２１５．【４０】ＰｉｅｒｒｅＴｅｒｄｉｍａｎ，Ｍｅｍｏｒｙ－ｏｐｔｉｍｉｚｅｄｂｏｕｎｄｉｎｇ－ｖｏｌｕｍｅｈｉｅｒａｒｃｈｉｅｓ，２００１，ｈｔｔｐ：／／ｗｗｗ．ｃｏｄｅｒｃｏｍｅｒ．ｃｏｍ／Ｏｐｃｏｄｅ．ｈｔｍ．【４１】Ｊｉｍ６ｎｅｚＰ，ＴｈｏｍａｓＦ，ＴｏｒｒａｓＣ．３ＤＣｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎ：ａｓｕｒｖｅｙ．ＣｏｍｐｕｔｅｒｓａｎｄＧｒａｐｈｉｃｓ，２００１，２５（２）：２６９～２８５．４０［４２】Ｓ．Ａ．ＥｈｍａｕｎａｎｄＭ．Ｃ．Ｌｉｎ．ＡｃｃｅｌｅｒａｔｅｄｐｒｏｘｉｍｉｔｙｑｕｅｒｉｅｓｂｅｔｗｅｅｎｃｏｎｖｅｘＩＥＥＥＩＲＯＳ，２０００．ｐｏｌｙｈｅｄｒａｕｓｉｎｇｍｕｌｔｉ·ｌｅｖｅｌＶｏｒｏｎｏｉｍａｒｃｈｉｎｇ．ＩｎＰｒｏｃｅｅｄｉｎｇｆ４３】ＷａｎＨＧ，ＦａｎＺＷ，ＧａｏＳＭ，ＰｃｎｇＱＳ，ＡｐａｒａｌｌｅｌＯｉｌｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｈｙｂｒｉｄｂｏｕｎｄｉｎｇｖｏｌｕｍｅｈｉｅｒａｒｃｈｙ．ＩｎＰｒｏｃｅｅｄｉｎｇｓｏｆＣＡＤ＆Ｇｒａｐｈｉｃｓ’２００１，Ｋｕｎｍｉｎｇ，Ｃｈｉｎａ，２００１：５２１～５２８．【４４】ＰｈｉｌｉｐＪ．Ｓｃｈｎｅｉｄｅｒ，ＤａｖｉｄＨ．Ｅｂｅｒｌｙ著，周长发译，计算机图形学几何工具算法详解，北京：电子工业出版社，２００５．【４５】ＭｏｉｌｅｒＴｏｍａｓ．Ａ１９９７，２（２）：２５～３０．【４６】ＭｏｉｌｅｒＴｏｍａｓ．Ｆａｓｔ２００２，６（１）：２９－３３．３ＤＴｒｉａｎｇｌｅ－ＢｏｘＯｖｅｒｌａｐＴｅｓｔｉｎｇ．ＪｏｕｒｎａｌｏｆＧｒａｐｈｉｃｓＴｏｏｌｓ，ｆａｓｔｔｒｉａｎｇｌｅ－ｔｒｉａｎｇｌｅｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔ．ＪｏｕｒｎａｌｏｆＧｒａｐｈｉｃｓＴｏｏｌｓ，４１⑥１、Ｊｉｎ硕士擘位论文ＭＡＳＴ￡Ｒ‘Ｓ丁ＨＥＳＩＳ攻读学位期间发表的论文ｈａｎｊａｎ．Ｗａｎｇｘｉａｏｒｏｎｇ，Ｗａｎｇｙａｎｌｉｎ，Ｚｈａｎｇｙａｏｋａｎ．ＳｔｕｄｙａｎｄＡｐｐｌｉｃａｔｉｏｎｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｉｎＣｏｍｐｕｔｅｒＴｅｓｔＣｏｎｓｔｒｕｃｔｉｏｎ，ＰｒｏｃｅｅｄｉｎｇｏｆＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＣｏｍｍｕｎｉｃａｔｉｏｎｓａｎｄＩｎｆｏｒｍａｔｉｏｎＴｃｃｈｎｏｌｏｇｉｅｓ２００５，２００５，１（２）：４１０－－４１３（ＥＩ收录）２、金汉均，王晓荣，徐星，郭亚军，一种基于ＤｉｒｅｃｔＸ的碰撞检测算法，电子技术应用，２００６，ｌ：５６￣５７３、Ｊｉｎｈａｎｊｕｎ，Ｗａｎｇｙａｎｌｉｎ，Ｗａｎｇｘｉａｏｒｏｎｇ，Ｆｕｊｉａ．Ａｎａｌｇｏｒｉｔｈｍｏｎｃｏｌｌｉｓｉｏｎｄｅｔｅｃｔｉｏｎｂｙｏｆｔｈｅｃｏｍｐｕｔｉｎｇｔｈｅｍｉｎｉｍｕｍｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｗｏｒｌｄｃｏｎｇｒｅｓｓｏｎｔｗｏｃｏｎｖｅｘｐｏｌｙｈｅｄｒａ，Ｐｒｏｃｅｅｄｉｎｇｉｎｔｅｌｌｉｇｅｎｔｃｏｎｔｒｏｌａｎｄａｕｔｏｍａｔｉｏｎ，２００６：９４２５－－９４２８（Ｅｌ收录）４、金汉均，王晓荣，王萌，基于层次包围盒的碰撞检测算法的存储优化，计算机工程与应用（已录用，２００７年１０月刊出）５、王晓荣，金汉均，王萌，基于ＡＡＢＢ的碰撞检测算法的内存优化，计算机工程与设计（已录用，２００８年３月刊出）⑨硕士学位论文ＭＡＳＴＥＲ’ＳＴＨＥＳＩＳ致谢在本论文完成之际，首先感谢我的导师金汉均副教授，感谢金老师对我的热忱帮助。在三年的研究生学习生活中，金老师严谨务实的工作作风、精益求精的治学态度深深影响了我，让我终身受益。从金老师身上不仅学到了知识，更学到了从事科研的方法以及态度。三年来，金老师在学习上严格要求，在生活上关怀备至，给了我亲人般的温暖和精神支持，在此特向金老师致以最衷心的感谢！同时，还要感谢所有的任课教师，是他们教给我许多专业知识；感谢参与我论文开题的各位老师，他们在我论文开题时给出了一些指导性建议，帮助我更好的完成了课题的研究；感谢计算机系的领导和其他老师对我的关心。感谢付佳、王彦林和王世元同学，他们在我学习和生活中给了我很多关心和帮助。感谢我的父母对我的养育和教诲，感谢姐姐全家对我的爱护和支持，感谢我的爱人王萌对我的关心、理解、支持和鼓励。最后，谨向参加论文评审和答辩的各位专家和老师致谢！感谢你们在百忙中抽出时间评阅我的论文。王晓荣２００７年５月于桂子山基于AABB包围盒的碰撞检测算法的研究

作者：

学位授予单位：

王晓荣

华中师范大学

本文链接：http://d.g.wanfangdata.com.cn/Thesis_Y1122669.aspx