虚拟交互场景中碾压碰撞算法的研究与实现

马永斌 詹华蕊

摘  要：三维虚拟场景中事物之间的交互可以满足场景真实感并提高用户的沉浸感，精确、快速地碰撞检测对提高虚拟环境交互的真实性有着非常重要的作用，而虚拟交互下的碾压场景的复杂性、实时性和精确性又对碰撞检测提出了更高的要求。本文以草体被物体踩压为例，对虚拟场景中事物间的交互过程进行分析和研究。

关键词：三维;虚拟场景;交互;碾压碰撞算法

中图分类号：TP391.9      文献标识码：A 文章编号：2096-4706（2019）09-0171-03

1  交互过程中算法分析

本文以简单的小圆球来代替复杂物体模拟草体被碾压后出现的动态交互过程，具体过程中要解决三个问题，即球体在碾压过程中每个阶段需要变形的草体获得、草体的碾压计算和变形结束后草体的原貌恢复计算[1]。

在获得球体碾压作用下变形的草体时，本文利用包围盒技术将球体用包围盒表示。由于草被小球碾压的过程是连续的、实时的，因此，草体的作用范围的变化与小球滚动的速度密切相关。为了使计算研究中出现的是连续的草体变形轨迹，将球体滚动的当前帧位置和球体的前一帧位置用一条连线来表示，作为球体的碾压作用范围中矩形的一条边，而矩形中的另一条边则由球体包围盒中的边长决定。获得了碾压作用范围的草体，则需要在渲染前确定好这些作用域。为了使CPU和GPU之间拥有高效的数据传送速率，将大规模草地对应的地形分为多个小网格进行渲染，利用球体滚动的当前帧位置与球体的前一帧位置来做判断，仅查询这些帧位置所经过的网格，然后确定這些网格中的草体是否需要变形。由于小球的滚动方向是一个随机草体变形的轨迹，为了方便计算，将任意方向的作用域和我们所要查询确定的草体给定点同时进行平移、旋转至坐标原点，获得一个精确的需要变形的草体作用范围。

接下来，对已经确定变形的草体进行碾压计算。对于单棵草体来说，它的交互变形效果是草体根部的变形程度明显大于其上部的变形程度，碾压向量则由草体根部开始向上进行计算。在建模中，对草体使用三个矩形来简单模拟，如图1所示。节点1、2、3、4是用来调整草体的弯曲变形程度的，而球体的圆心到草体根部点的向量用来确定草体被碾压的方向。由于球体底部正下方的草体是完全被挤压且看不到，因此选择球体刚离开时的草体状态作为临界点来进行模拟。

如图2所示，轨迹a表示草体的原始状态，轨迹b表示草体的临界状态，h表示轨迹b中节点2离地面的高度。为了方便分析，设每一节草体的长度为L且不变，轨迹b中的节点2在x轴方向上的偏移量可以通过L和h的值求得，偏移方向则与碾压轨迹方向一致，节点3和节点4用同样的方法，并在节点2的基础上，可以计算出它们的x轴方向的偏移量和偏移方向。本文还假设草体被碾压前后的相邻节段的草体骨架之间的夹角不变，用它们的补角表示为θ1=φ1，θ2=φ2。通过将轨迹b中节点2的切线方向在切点处顺时针旋转θ1度，在新的方向上加上预设的每节草体的固定长度L，就可以得到变形后轨迹b中节点3的坐标了，节点4的坐标用同样的方法可以计算得到。

为了使草体在碾压后有一个平滑过渡的变形，可以采用一种基于草体骨架线的隐式曲面的计算公式来计算草体的碾压向量[2]：

（1）

如图3所示，在平滑过渡原理中，v0和v1分别表示球体当前帧位置和球体前一帧位置，P代表当前需要变形的草体位置，H点是草体位置在v0、v1上的投影。由公式可知，我们可以调节草体的变形弯曲程度，即改变图中点H的位置，而图中的θ0和θ1则反映了草体位置分别距离球体当前帧与球体前一帧的位置方向。

为了恢复草体为交互变形前的原貌，本文采用Catmull-Rom样条对草体顶点的碾压向量进行插值运算，在GPU中实现碾压向量的更新计算，最后完成草体顶点的更新，将其平滑度恢复到原貌。如图4所示，将草体处于变形状态的时间先保存下来，当前草体的状态就是图中的临界状态，节点2、3、4分别创建样条插值，虚线部分代表插值的过渡状态，其中插值间隔越短说明草体恢复越快。然后在GPU中实现草体的碾压向量的更新计算，分担CPU的工作量，提高运行速率。根据草体当前状态的时间和变形状态的时间记录，在顶点着色器中调用Catmull-Rom插值函数，计算出草体新的碾压向量，将它在正切空间中作用于草体的顶点位置，完成草体顶点的更新，进而恢复草体原貌。

2  碰撞检测计算

本文采用基于骨架线的快速碰撞检测算法[3，4]，使得检测草体间的碰撞转变成单株草体骨架线与另一株草体模型的相交检测。首先获得草体的碰撞作用域，然后对作用域内的草体进行碰撞检测计算，确定草体的位置，避免出现穿透现象。

由于草体被小球碾压时，被挤压的草体只与它周围有限范围内的草体发生碰撞，为了确定草体的碰撞作用域，可以将当前草体的位置作为圆心，以草体的长度作为半径画圆作为碰撞检测范围。其中，碰撞检测范围的大小可以通过改变圆的半径值来进行调节。如图5所示，当前草体的骨架线用Ι1Ι2Ι3Ι4表示，另一株草体用多边形Η1Η2Η3Η4Η5Η6Η7Η8表示，其中，用Ι1'Ι2'Ι3'Ι4'表示草体没有发生碰撞时被碾压后应到达的位置。若线段ΙnΙn'与另一株草体的矩形任一边相交，则说明草体间发生了碰撞。由图5可知，以Ι1为圆心的弧段Ι4Ι4'与Η1Η2Η3Η4Η5Η6Η7Η8相交于点P，那么P点处则为Ι4'碰撞后应该达到的位置，其余点碰撞后的位置可由等比例位移依次得到。

若Ι4'P之间的距离为d，那么Ιn'点的位移则可表示为：

（2）

其中，L和Ln分别表示单株草中草体的总长和第n节草的长，进而计算出发生碰撞后草体应该达到的位置I1"I2"I3"P，最终确定出草体的位置，避免场景中各物体间进行交互时出现穿透的失真现象。

3  实验结果与分析

为了验证本文方法的有效性，相应的交互实验在PC机上进行了多次。该实验中的草地场景拥有草体三角形数目约为50万，分辨率为1024×768。

在场景交互过程中，草体碾压效果的实现可以分为以下三个步骤：

（1）获取球体滚动时的作用范围。

（2）对前面作用范围内的草体进行碾压计算。

（3）使被碾压的草体恢复原状。

实验结果如图6中所示，图6（a）和图6（b）是草体没有采取碰撞检测计算的效果，而图6（c）和图6（d）是草体采取了碰撞检测计算的效果。从两图的对比中可以看出，在没有考虑碰撞检测时，在小球碾压草体的交互过程中会出现部分草体穿透小球的现象;而考虑并采取了碰撞检测的效果图中，草体不再穿透球体，场景的真实感具有明显增强。

（a）草体没有采取碰撞检测计算的效果（单点碰撞）

（b）草體没有采取碰撞检测计算的效果（多点碰撞）

（c）草体采取了碰撞检测计算的效果（单点碰撞）

（d）草体采取了碰撞检测计算的效果（多点碰撞）

4  结  论

本文主要对三维场景中交互过程中的算法进行了分析与研究，以小球碾压草体为例，实现了真实感较好的交互动态变形过程，并同时考虑了交互过程中的碰撞检测。在交互过程中，首先利用球体包围盒获得需要变形的草体，然后以一个临界状态表示单株草体的变形状态，通过草体骨架线的隐式曲面计算公式计算出草体的碾压向量，最后采用Catmull-Rom样条插值方法将草体恢复至原貌。

参考文献：

[1] 韩光辉，徐鹏飞，周明全.实时碰撞检测中的穿透问题研究与解决 [J].北京师范大学学报（自然科学版），2011，47（4）：370-373.

[2] 何援军.计算机图形学 [M].北京：机械工业出版社，2009.

[3] 蔡鹏，赵伟，任大鹏.行人仿真系统中的碰撞检测与避让 [A].中国建筑科学研究院、金融街控股股份有限公司 [C].第十五届全国工程设计计算机应用学术会议，中国黑龙江哈尔滨：中国土木工程学会、中国建筑学会、中国工程图学学会，2010：297-301.

[4] Decaudin P，Neyret F. Rendering Forest Scenes in Real-Time [C]// Fifteenth Eurographics Conference on Rendering Techniques. Eurographics Association，2004：56-63.

[5] 王长波.基于物理模型的自然景物真实感绘制 [D].杭州：浙江大学，2006.

[6] Wan HG，Fan ZW，Gao SM，et al. Streaming Real Time Collision Detection Using Programmable Graphics Hardware [J]. Journal of Software，2004，15（10）：1505-1514.

作者简介：马永斌（1982.10-），男，汉族，河南商丘人，讲师，本科，研究方向：计算机应用及物联网技术;詹华蕊（1986. 03-），女，汉族，河南商丘人，讲师，研究生，研究方向：计算机应用及网络技术。