本文是一篇计算机论文，本文实验结果表明使用简化90%的模型构建的有向包围盒完全可以替代原模型的有向包围盒，包围盒构造耗时相比于传统OBB包围盒与快速自适应包围盒算法缩短了约6%-71%，碰撞检测耗时缩短了约23-83%。
第一章绪论
1.1研究背景及意义
虚拟仿真技术广泛应用于游戏、动画、医疗等领域，一直以来都是研究热点。虚拟仿真是为了尽可能还原现实世界，使用户没有感觉到与真实世界相违和的计算机系统。在仿真过程中，物体与物体之间的交互是不可避免的，而影响物体之间交互的关键技术就是碰撞检测算法。碰撞检测算法的优劣直接影响着整个仿真过程的实时性和真实性，碰撞检测算法是整个模拟过程中的重要技术难点和计算性能的消耗点，一直以来都是研究的热点。若只过分注重提高碰撞检测算法的效率，而粗略过滤碰撞对，就会出现物体之间穿透的失真情况。若只过分注重碰撞检测算法的真实性，而不考虑算法的实时性，就会出现仿真卡顿帧率过低的情况。一个兼顾实时性和真实性的碰撞检测算法直接影响到整个仿真系统的好坏。布料模拟作为虚拟仿真领域中一大难点，始终是一项热门研究课题。
布料作为典型的柔性物体，有着易于变形，形状不固定的特点。在布料模拟过程中，如果仅使用适用于刚体的碰撞检测方法显然是不合适的，布料模型每一次移动，都会伴随着大量布料粒子的移动，从而产生大量的碰撞对。如果不能及时发现并处理每一个碰撞对，就会发生穿透现象，导致失真情况，甚至会对下一步模拟产生严重影响。布料模拟过程中要求的真实性和实时性更为严苛，想要保证布料模拟过程真实的同时又能使得整个系统更加高效，就必须要对布料模拟过程中的碰撞检测算法进行改进。通过以上介绍，可以看出布料模拟中碰撞检测算法研究有着广泛的应用前景。
1.2研究现状
基于物理仿真的布料模拟算法已经比较成熟，包括有限元法、质点弹簧系统等。此外还有基于数据驱动的算法以及利用深度学习技术实现高质量布料动态效果方法，虽然这些算法已经在电影游戏等领域得到广泛应用，但是布料碰撞检测算法仍然存在问题。现有的碰撞检测算法在处理大规模和高精度布料时性能较差，布料与精细建模物体交互时存在失真和发生穿透的问题，因此优化布料模拟过程中的碰撞检测算法仍然存在着巨大挑战。通常用来优化碰撞检测的算法有包围盒算法、空间分割法和使用机器学习优化的碰撞检测算法。
1.2.1包围盒算法
(1)层次包围盒法
层次包围盒法(BVH)是使用结构简单、体积略大的几何体包围盒来逼近和代替原复杂物体，进而再构建树型结构以此来更好的逼近物体几何结构。在BVH中，构建树型结构的是一个个几何特征简单，易于判断两两是否相交的包围盒。常用的包围盒有轴向包围盒[1](AABB)，有向包围盒[2](OBB)，球形包围盒[3]和离散方向多面体包围盒[4](K-DOPs)。为了使单一包围盒可以充分发挥各自的优势，对于包围盒算法的优化也是一项热门研究课题。胡志刚等人[5]提出了一种基于凸包的最小体积OBB包围盒生成算法用于快速生成拟合效果良好的最小OBB包围盒，进一步提高了OBB包围盒的剔除率。靳雁霞等人[6]为了适应布料自碰撞检测提出了一种无厚度的圆形包围盒，在布料等柔性物体自碰撞足够多的场景下有着明显性能优势。Wang等人[7]提出了一种新的优化求解实体网格模型的层次OBB包围盒的构建方法，该方法加快了碰撞检测的速度。
(2)混合包围盒算法
虽然使用优化改进的单一包围盒算法对碰撞检测效率有提升[16-19]，但是单一包围盒都有自己的劣势，相对简单的Sphere包围盒和AABB包围盒虽然自身有着简单快速的碰撞检测优势，但是其存在碰撞检测剔除率低的缺点；相对复杂的OBB包围盒和k-DOPs包围盒的优劣势恰恰与相对简单的包围盒相反。而混合层次包围盒法可以解决这一问题。使用相对简单的Sphere包围盒、AABB包围盒与相对复杂的OBB包围盒、k-DOPs包围盒构建混合包围盒可以同时发挥简单包围盒检测效率高和复杂包围盒剔除率高的优势[20-22]。
第二章相关理论基础
2.1碰撞检测原理
碰撞检测简单来说就是在虚拟仿真过程中检测两个物体是否相交的技术。在复杂的检测场景下，一般将碰撞检测分为粗略检测和精确检测两个阶段。在粗略碰撞检测阶段使用包围盒算法或是空间分割算法等性能消耗小，效率高，但是剔除率不高的算法，将场景内不可能发生碰撞的碰撞对进行剔除。在精确碰撞检测阶段对前一阶段未能剔除的碰撞对进行精确计算，通过判断其在一时间步长内物体间粒子是否相交来判断是否发生碰撞。
2.2包围盒算法
在每个时间间隔内，若直接对两个模型上每个顶点进行碰撞检测，其对于系统的性能损耗是极其巨大的。所以一般会先使用包围盒等容易检测，构造简单的方法，先进行粗略剔除，排除绝不可能发生碰撞的情况。
包围盒是几何特征简单且易于检测相互之间是否重叠的凸包，常用来替代结构复杂模型进行检测[43]，常见的包围盒有：轴对齐包围盒(AABB)、球形包围盒(Sphere)、方向包围盒(OBB)和离散有向多面体包围盒(K-DOPs)，其各自结构如图2-1所示。可以明显看出，若包围盒之间未发生重叠，则其内的模型更不可能发生碰撞，只对包围盒进行碰撞检测计算量将大大减少，剔除效率也会显著提高。
第三章模型简化的OBB包围盒算法以及相关优化················19
3.1模型简化的OBB包围盒算法···································19
3.1.1基于二次误差的模型表面简化······························19
3.1.2模型简化的OBB包围盒·····························21
第四章双神经网络优化的连续碰撞检测算法·······························31
4.1代数非穿透滤波器优化的CCD算法································31
4.2空间线性投影滤波器优化的CCD算法······························31
4.3双神经网络优化的CCD算法·····································33
第五章布料与精细建模物体间的碰撞检测系统·············45
5.1系统环境········································45
5.2系统设计···································45
第五章布料与精细建模物体间的碰撞检测系统
5.2系统设计
本文的碰撞检测系统设计主要由模型的数据结构和相应的碰撞检测算法组成。模型的数据结构主要有：布料模型、布料模型粒子间的约束、图元三角形结构、BVH数据结构。碰撞检测算法主要有：两个AABB包围盒之间的碰撞检测、两个Sphere包围盒之间的碰撞检测、两个OBB包围盒之间的碰撞检测、AABB包围盒与Sphere包围盒之间的碰撞检测、AABB与OBB包围盒之间的碰撞检测、Sphere与OBB包围盒之间的碰撞检测以及BVH之间的碰撞检测。
5.2.1数据结构设计
(1)布料模型
布料模型是由一个个布料粒子组成，设计布料模型时必须要考虑布料粒子的属性。为了使布料模拟更加贴近现实，布料粒子的质量、受到的外力以及因为外力所产生的加速度属性必不可少。每个布料粒子在运动中需要记录粒子的速度以及位置。当模拟布料悬垂状态或是需要将布料固定在某一位置时，需要使得一些粒子处于静止状态，因此需要定义bool类型属性表示布料粒子是否始终静止。
布料模型总体也存在自己独有的属性，布料的长度、宽度以及厚度。由于在粗略碰撞检测阶段中使用BVH，在检测过程中需要频繁使用根节点，因此需要定义一个节点来储存根节点属性。此外，为了储存布料模型中的节点、布料粒子和粒子之间的约束以及组成布料模型的三角形图元，需要定义四个属性。
第六章总结与展望
6.1总结
本文将布料与精细建模模型间的碰撞检测算法分为粗略和精确碰撞检测两个阶段。在粗略检测阶段，首先使用二次误差度量的表面简化法对精细模型进行简化，将简化后的模型嵌入原模型中，其次使用一种快速自适应的有向包围盒算法对简化后的模型构建包围盒，以此来替代原模型构建包围盒，大大减少了构建包围盒的耗时，并且选择适合的包围盒以及BVH来进一步优化碰撞检测算法。在精确检测阶段，采用全连接神经网络分别学习代数非穿透滤波器剔除碰撞对和空间线性投影滤波器剔除碰撞对方法，将训练后的最优神经网络模型用于优化连续碰撞检测算法，充分发挥深度神经网络高效处理大量数据的优势。
实验结果表明使用简化90%的模型构建的有向包围盒完全可以替代原模型的有向包围盒，包围盒构造耗时相比于传统OBB包围盒与快速自适应包围盒算法缩短了约6%-71%，碰撞检测耗时缩短了约23-83%。在布料与精细建模物体交互的场景下，使用双神经网络优化的连续碰撞检测算法比使用不同类型滤波器优化的连续碰撞检测算法和融合OpenNN神经网络的碰撞检测算法的速度都快，平均耗时缩短了约4%~11%，实验验证本文方法在布料与精细建模物体交互的复杂场景下拥有更好的实时性与稳定性。
参考文献（略）