变分层次包围体的构建及其在碰撞检测中的应用

论文摘要

实时碰撞检测是机器人、动画仿真、虚拟现实等领域中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测已有了大量有价值的研究成果,但随着诸如虚拟现实等新兴领域的涌现及随之而来的人们对交互实时性、场景真实性要求的不断提高,碰撞检测技术所面临的问题也日益突出,其中最核心的问题是如何有效地提高碰撞检测的速度。层次包围体法是解决碰撞检测问题固有时间复杂性的一种有效的方法,它是用体积略大而几何特性简单的包围体来近似地描述复杂的几何对象。通过构造树状层次结构来逼近对象的几何模型,在对包围体层次树进行遍历的过程中,通过包围体间的快速相交测试来及早地排除明显不可能相交的基本几何元素对,而只对包围体重叠的部分元素进行进一步的相交测试,以提高碰撞检测的速度。本文提出了一种基于迭代的Lloyd分簇方法的变分逼近构建层次包围体方法,为解决构建层次包围体问题提供了一种新的方法,我们的方法所构建的层次包围树以包围体的外部体积为代价函数,利用逼近的思想来解决实现空间面片的划分问题,通过多次迭代,产生的包围体更加逼近原物体,有效提高了碰撞检测中的检测效率。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 虚拟现实和碰撞检测
• 1.2 问题描述
• 1.3 相关工作
• 1.3.1 基于AABB层次包围体树的碰撞检测算法
• 1.3.2 基于层次包围球树的碰撞检测算法
• 1.3.3 基于OBB层次包围体树的碰撞检测算法
• 1.3.4 基于k-DOPs层次包围体树的碰撞检测算法
• 1.3.5 其他方法
• 1.4 本文主要贡献
• 1.5 论文结构
• 第2章 碰撞检测
• 2.1 碰撞检测
• 2.1.1 初步检测阶段
• 2.1.2 详细检测阶段
• 2.2 构建层次包围体
• 2.2.1 自下而上（Down-top Construction）
• 2.2.2 渐进树插（Incremental Tree-insertion）
• 2.2.3 自上而下（Top-down Construction）
• 第3章 用变分方法构建层次包围体
• 3.1 包围体逼近的计算
• 3.1.1 几何模型表示
• 3.1.2 逼近误差度量
• 3.1.3 逼近误差的计算
• 3.1.4 包围体逼近的优化求解
• 第4章 结果比较及分析
• 4.1 测试平台简介
• 4.1.1 ODE（Open Dynamics Engine）
• 4.1.2 Bullet Physics
• 4.2 结果比较
• 4.3 结论与分析
• 4.4 进一步的工作
• 参考文献
• 致谢