随着计算机图形学的飞速发展,呈现在人们面前的三维世界越来越逼真,然而技术的进步带来的不仅仅是漂亮的画面,物理模拟给人们带来的是真实的感受。物理模拟在影视制作、计算机游戏等应用领域占据越来越重要的地位,它释放了人们的想象,给我们带来了空前的互动性。作为物理模拟中的重要一部分,碰撞检测引起了人们越来越多的关注,特别是可变形体碰撞检测技术,它不但是近期计算机图形学的研究热点,而且在布料模拟和虚拟手术中有着极为重要的应用,因此,本文对面向布料模拟的可变形体碰撞检测技术进行了描述和讨论。 碰撞检测是整个物理模拟过程中计算负担最重的部分,常常是瓶颈所在,而对于可变形体的碰撞检测,这种瓶颈现象显得更为明显,因为与刚体碰撞检测相比较,可变形体的碰撞检测有更多的问题需要考虑和处理:无法进行有效的预处理、可能存在的自碰撞检测、精确获取碰撞信息等等。在以实时性和交互性为特征的应用中,比如虚拟手术、游戏等,有效的可变形体碰撞检测算法对模拟的性能有着极其重要的意义。 本文以布料模拟为应用对象,对可变形体碰撞检测技术进行了讨论,涉及到两种经典算法,并对算法中的各方面问题进行了描述。从总体上来讲,本文的主要贡献和创新如下: 1.利用基于基元连通性的自底向上方法创建层次包围体,并在创建过程中记录基元的邻接关系,为自碰撞查询提供必要的信息。 2.借鉴混合式更新方法的思想,对自顶向下更新方法进行改进。 3.在自碰撞查询中对层次包围体节点进行“兄弟”方式的碰撞查询,从而消除冗余查询。 4.改进了以基元为对象的空间哈希方法,突破了用于体模型碰撞检测的“点—四面体”碰撞查询。 本文第一章介绍了可变形体碰撞检测的背景知识、研究现状以及本文的研究内容;第二章介绍了用于可变形体碰撞检测的基元碰撞检测以及一些特殊情况下的改进;第三章和第四章分别介绍了层次包围体算法和空间剖分算法,对其中的涉及到众多问题进行了分析,并列出了关键问题和较难理解问题的算法伪码;第五章介绍了CDKit库的设计、实现与应用;第六章总结全文,并对一些将来的研究进行了展望。