虚拟环境中可变形体碰撞检测算法研究

摘要

几何模型间的碰撞检测是织物仿真、计算机动画、机器人、CAD/CAM、虚拟手术等多领域的关键问题之一。快速而准确的碰撞检测对提高与人交互的虚拟环境的真实感至关重要，尤其对于需要力触觉感知的虚拟环境。在虚拟环境仿真中，碰撞检测往往是系统计算效率的瓶颈。目前对刚体之间的碰撞检测算法的研究已趋向成熟，但对可变形体碰撞检测的算法研究较少。对于虚拟外科手术训练、织物仿真、计算机动画等实用的虚拟环境中的交互对象，可变形体对象比刚体对象更普遍。 本文面向织物模拟应用，根据模拟过程中时间顺序的不同，从织物的物理建模、粗略碰撞检测和精确碰撞检测三个方面对可变形体碰撞检测技术中的关键问题进行了研究。 论文的内容主要包括如下几个方面： 1.比较了现有的可变形体建模方法，采用质点-弹簧模型对织物进行建模。然后对质点-弹簧模型进行动力学分析，提出了一种改进的变步长策略的自适应龙格-库塔积分法，在织物仿真系统的精确度和计算效率之间实现有效折中。 2．讨论了用于粗略检测阶段的层次包围盒方法，包括包围盒种类的选择，k-DOPs的预处理和更新，k-DOPs的相交测试。针对可变形体要求层次包围盒更新速度快的特点，提出了一种综合应用爬山法和近似法时计算速度最快的方法。提出了采用四叉树的结构来代替以往的二叉树结构的方法，从而提高包围盒重叠测试的效率。同时采用了基于曲率的自碰撞检测方法来确保织物的真实感。 3．深入分析和讨论了基于快捷检测原理的基本几何元素碰撞检测算法：Moller判别算法、Held判别算法和Devillers判别算法，提出了改进的Devillers判别算法，提高了计算效率。具体碰撞点用于碰撞响应来及时调整织物运动，确保仿真过程的真实感。 4．本文综合上述研究方法，通过模拟织物与球体的碰撞过程实验，实现了准确和快速的碰撞检测，验证了本文对面模型类的可变形体碰撞检测算法改进的可行性，并且提高了碰撞检测的实时性和准确性。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2论文研究背景

1.2.1问题描述

1.2.2碰撞检测的实时性与准确性

1.2.3可变形对象碰撞检测的难点

1.2.4研究现状

1.3论文的研究内容和组织结构

1.3.1论文的研究内容及贡献

1.3.2论文的组织结构

第二章可变形体的物理建模和数值求解

2.1引言

2.2可变形体的建模方法

2.3织物模拟的质点——弹簧模型及动力学分析

2.4质点-弹簧模型的数值求解方法

2.4.1欧拉积分法

2.4.2中值积分法

2.4.3龙格-库塔积分法

2.4.4基于龙格-库塔积分法的变步长的策略改进

2.5实验结果

2.6小结

第三章基于层次包围盒的粗略碰撞检测方法

3.1引言

3.2层次包围盒方法

3.2.1层次包围盒

3.2.2包围盒的种类

3.2.3 k-DOPs

3.3层次k-DOPs的预处理

3.4层次k-DOPs树的更新

3.4.1爬山法

3.4.2近似法

3.4.3算法分析与改进

3.5层次k-DOPs四叉树相交测试

3.6自碰撞处理

3.6.1曲率方法

3.6.2自碰撞检测算法的四叉树实现

3.7小结

第四章基本几何元素间的精确碰撞检测

4.1引言

4.2基本几何元素碰撞检测

4.2.1 Moller判别算法和Held判别算法

4.2.2 Devillers判别算法

4.2.3算法分析与改进

4.3碰撞响应

4.4小结

第五章仿真系统设计和实验

5.1 OpenGL概述

5.1.1 OpenGL简介

5.1.2 OpenGL基本功能

5.1.3 OpenGL基本工作流程

5.2系统框架及数据结构设计

5.2.1系统框架

5.2.2关键数据结构

5.3实验与结果分析

5.4小结

总结与展望

参考文献

致 谢

攻读学位期间主要的研究成果