计算机网络技术毕业论文哪里有?本文针对传统层次包围盒在构建、检测和更新的过程中耗时多、计算复杂的问题,提出了根节点双层包围盒算法。使用最简单的 sphere 包围盒,自顶向下对布料构建层次包围体。当检测到根节点的 sphere 包围盒发生碰撞时,只对根节点构建紧密率更好的 AABB包围盒,更加精确地剔除没有发生碰撞的基本图元。非根节点的包围盒没有变化,减少了包围盒的构建和更新时间,加快效率。
第一章 绪论
1.2 研究现状
1.2.1 单个包围盒算法
在碰撞检测的过程中,层次包围体(Bounding Volume Hierarchies,简称 BVH)技术是目前使用最多的方法。1980 年,Rubin 等[1]开始使用树的结构对三维对象分层,树的分支表示边界体积,树的终端节点表示原始对象元素。1986 年,Kay 等[2]提出了一种新的层次遍历算法空间中值分割算法。下一年,Goldsmith 等[3]提出了评估层次包围体效率的成本函数,表面启发式(Surface Area Heuristic,简称 SAH)。随后,Havran 等人[4],Wald等人[5,6]和 Ize 等人[7],为了降低复杂度,对 SAH 进行了改进。2007 年,Hunt 等[8]提出了使用有关场景的结构信息来更有效地构建基于 SAH 的加速结构。2013 年,Doyle 等[9]在硬件方面来改善 BVH 结构的性能和效率。2018 年,由于 BVH 前端节点的任意布局导致的 GPU 缓存效率低下成为一个关键的性能问题。Wang 等[10]通过提出一种基于 GPU的快速且强大的基于 BVH 的冲突检测方案,该方案通过对 BVH 前端进行排序和重组来解决此问题。
碰撞检测过程当中,不仅需要减少层次包围盒之间碰撞检测所需的时间,还需要增加包围盒的剔除率,来减少图元之间的碰撞处理时间。包围盒技术就是使用简单的几何体来代替复杂的模型,减少碰撞处理的时间,所以 BVH 结构当中最重要的是包围盒技术。
1993 年,Hubbard 等[11]首先提出了包围盒技术,用四维几何体或者球体来逼近三维模型。为了适应不同的模型,找到紧密率更高的包围盒,2013 年,唐勇等[12]利用椭球包围盒提高碰撞检测效率,采用 K 均值聚类方法生成最小体积包围椭球,快速得到检测结果。随后椭球包围盒多用于人体模型。2019 年,MONAN 等[13]提出了一种基于虚拟球的包围盒层次碰撞检测算法,其检测效率高于串行混合包围盒层次算法和并行混合包围盒层次算法,研究主要集中在虚拟手术方面。
计算机网络技术毕业论文范文
........................
第三章 根节点双层包围盒
3.1 构建根节点双层包围盒
3.1.1 选择合适的包围
盒每个包围盒都有自己的优劣势,要根据实际情况选择适合的包围盒。sphere 的构造简单,更新复杂度低,缺点是包围盒空间冗余大,紧密性差。AABB 通过构建一个边与坐标轴平行的长方体来代替物体碰撞,AABB 之间的碰撞检测计算复杂度低,构造结构简单,但是它的缺点和 sphere 一样冗余空间大。OBB 是一个方向任意的包围盒,所以它的空间冗余小,紧密性高,缺点是碰撞检测过程和构造结构的复杂度高,耗时长。
本文提出的根节点双层包围盒算法所使用的包围盒就是 sphere 和 AABB。利用两者构建速度快、结构简单的优点,来加快系统的检测效率。同时将两者组合起来,消除包围盒空间冗余大的缺点。
3.1.2 构建根节点双层包围盒的 BVH 树
本文算法的 BVH 结构选择二叉树结构,将模拟物体的父集合划分为两个子集合,子集合作为树的节点构建合适的包围盒。将集合递归地划分下去,直到叶子节点。划分策略使用的方法是平面分割,这种方法使用简单,而且划分后在每一个子空间里的基本图元都是相邻的。
平面分割法在父集合中使用分割平面,将父集合划分为左右两个子集合。如果基本图元的中心点位于分割平面的左侧,就把它划分到左边的子集中;如果基本图元的中心点位于分割平面的右侧,就把它划分到右边的子集中;当基本图元的中心点位于分割平面内部时,把它划分到集合数量较少的子集中。分割平面由两个要素来确定,它们是分割点和分割轴。
分割点负责其位置,而分割轴负责其法线,确定方向。分割点的挑选比较简单,在分割轴上面将建好的模型进行投影,中值点就是分割点。分割轴可以挑选包围盒的最长边,例如,sphere 的分割轴可以选择直径;AABB 的分割轴挑选其在对应坐标轴上投影最长距离的包围盒边;OBB 的分割轴挑选与其最长边平行的方向轴。
图 3-1 层次包围盒构建图
..........................
第五章 实验与系统
5.1 实验环境
通过实验来验证本文提出的两个算法是否真实。在实验的过程中,首先设计不同对象的数据结构和碰撞检测算法的具体步骤。然后通过模拟实验得到碰撞检测所消耗的时间,来比较本文算法的优势。最后将本文算法设计为一个可运行的系统。
为了验证本文方法的性能,使用 C++和 OpenGL 技术,在 Windows 平台系统下,利用开发工具 Visual Studio 2017 建立仿真模拟系统。平台配置为:E5-2630 v3、64G RAM、Quadro K5200。
为了验证本文算法不仅在效率上有所提升,同时也保证了模拟效果的真实性,将布料 B 分别与不同模型进行碰撞实验。1)布料受重力作用下落,与木箱子碰撞,停留在木箱子上;2)布料与有着尖锐棱角的游戏角色相碰撞,覆盖在了游戏角色上面;3)布料垂直下落到站立在地面上的人体角色,与人体发生碰撞。
...........................
5.2 实验设计
在碰撞检测系统当中,主要的设计包括建模物体的数据结构和碰撞检测算法两部分。建模物体的数据结构包括:布料粒子、布料之间约束、基本图元三角形、布料结构和层次包围盒 BVH 结构。碰撞检测算法主要包括:sphere 包围盒与 sphere 包围盒、AABB包围盒与 AABB 包围盒、sphere 包围盒与 AABB 包围盒以及层次包围盒 BVH 之间检测。
5.2.1 物体数据结构设计
(1)布料粒子布料粒子是布料的基本元素之一,在设计粒子时需要考虑粒子的各种属性。布料在模拟的场景中,有时需要自由运动,有时需要固定个别粒子漂浮在空中,所以需要一个bool 类型的属性,表示粒子是否固定。布料依靠加速度定律在仿真场景中运动,这需要粒子的质量、所受到的合力和加速度三个属性。在运动过程中,还需要粒子的速度属性和位置属性。其中位置属性比较复杂,分为粒子当前的位置、上一时刻的位置和积分运动以后的位置。
(2)布料约束
对于本文构建的弹簧-质点布料模型,弹簧就是粒子之间的约束。在弹簧-质点模型当中,弹簧一共有三种结构,它们分别是结构弹簧、剪切弹簧和弯曲弹簧。所以在布料约束的数据结构中,需要定义的属性包括:两个粒子,两个粒子之间的距离和约束的类型。
(3)基本图元三角形
在布料模型中,最小的几何图形就是三角形。按照粒子的索引,将相邻的三个粒子组成一个三角形。因此三角形的属性中有三个属性是粒子。在对布料构建 BVH 结构时,采用平面划分的方法将父集合一分为二,三角形究竟被划分到哪个集合,取决于三角形的位置,所以需要一个向量来表示三角形位置这个属性。此外还需要三角形的法向量来进行渲染,需要一个 bool 值来表示三角形是否发生碰撞。
............................
第六章 总结与展望
6.1 总结
本文提出了根节点双层包围盒碰撞检测算法。利用最简单的包围盒,提高了包围盒的剔除率,使碰撞检测算法的效率得到提升。然后结合神经网络,进一步改进了碰撞检测算法,提出了融合神经网络的碰撞检测算法。使算法在一个时间步长内,可以处理大量的布料粒子,减少了包围盒的构造时间,加速了碰撞检测的速度。
本文算法的创新点在于:(1)根节点双层包围盒算法使用最简单的 sphere 包围盒,构建层次包围体,这对于包围盒的构建和更新所消耗的时间是最少的。同时只对根节点构建紧密率更好的 AABB 包围盒,使用一个 AABB 包围盒避免了 sphere 包围盒紧密率差的问题,使本文算法兼顾了效率和剔除率。(2)融合神经网络的碰撞检测算法使用本文自己训练好的神经网络模型,代替碰撞检测复杂的计算过程,来快速预测基本图元是否发生碰撞。在真实性方面效果也有保障。通过与传统包围盒技术的模拟效果相比,没有发生穿透,模拟效果没有太大差别,不影响用户观感。
最后通过实验分析本文算法的性能。根节点双层包围盒算法,在真实性方面,与传统包围盒技术模拟效果一样。在效率方面,比传统混合包围盒算法快,其耗时缩减了5.51%~11.32%。基于神经网络的碰撞检测算法,在真实性方面,与传统包围盒技术模拟效果没有太大差别。在效率方面,当布料模型精度增加 84%时,传统物理方法用时增加96%,融合 DNN 的自碰撞检测算法用时增加 90.11%。而本文算法用时只增加了 68.37%。
参考文献(略)