碰撞响应中对传统几何约束法的改进

靳雁霞 程思岳 王贺 程琦甫 张晋瑞

摘  要： 为了解决目前布料仿真中用隐式积分法预测所得的下一个时间步长位移不精确的情况，提出一种新的平均力法来预测下一个时间步长的位移。该方法通过力来预测一个时间步长内的位移，比起直接预测位移的隐式积分方法更加精确，其位移预测的误差能够减少5%～10%，并且随着时间步长的增加，误差会越来越小。此外，针对碰撞检测后检测到的穿透现象，提出一种基于分离轴的碰撞响应算法解决穿透现象。该方法首先确定碰撞平面以及分离轴，将发生穿透的部分投影到分离轴上，得到穿透深度和穿透方向，给发生穿透的物体一个瞬时的冲量和阻尼力，让物体返回碰撞平面上。通过大量的实验对比可以得出，基于分離轴的碰撞响应算法在解决穿透现象方面是切实可行的。

关键词： 布料仿真; 碰撞检测; 几何约束; 碰撞响应; 平均力法; 分离轴

中图分类号： TN911.1?34; TP391.4                  文献标识码： A                  文章编号： 1004?373X（2020）01?0122?04

Improvement of traditional geometric constraint method in collision response

JIN Yanxia， CHENG Siyue， WANG He， CHENG Qifu， ZHANG Jinrui

Abstract： In view of the imprecise displacement of next time step obtained by the implicit integration method in fabric simulation， a mean force method is proposed to predict the displacement of next time step. As far as this method is concerned， the displacement within a time step is predicted by force， which is more accurate than the implicit integration method which directly predicts the displacement. The error of displacement prediction can be reduced by 5% to 10%， and the error will become smaller and smaller as the time step increases. In addition， a collision response algorithm based on the separation axis is proposed to deal with the detected penetration by the collision detection. In this method， the collision plane and the separation axis are determined firstly， and the penetrating part is projected onto the separation axis to obtain the penetration depth and penetration direction， then an instantaneous impulse and a damping force are exerted to the penetrating object to get the object back to the collision plane. It can be concluded from a large number of comparative experiments that the collision response algorithm based on the separation axis is feasible in solving penetration.

Keywords： cloth simulation; collision detection; geometric constraint; collision response; average force method; separation axis

0  引  言

随着计算机仿真技术的不断提高，各种各样的布料都可以在计算机中模拟，并且应用在各种领域中。在计算机仿真中，布料仿真是重要的研究内容之一，并且在游戏制作、动画影视方面也具有很大的应用价值。但是由于其材料的特性以及结构，使得布料仿真在实际模拟中并没有那么简单。

近20多年计算机仿真技术在不断进步，人们通过对布料结构不断改进，算法效率不断提高，布料仿真技术也有了质的飞跃。但是，在模拟过程中还是会出现比如“超弹”和“穿透”等难以处理的情景，在视觉上呈现出的效果难以达到预期效果。本文通过对碰撞响应的整理分析，对现有的算法做了如下改进：在预测位移时，使用单位时间步长的平均力来预测下一时间步长的位移，减小了预测的误差;在处理“穿透”现象时，提出使用分离轴的方法来修正结果，增强其稳定性，在视觉效果上表现更加真实。

1  布料模型的建立

质点弹簧模型主要分为两种：一种是经典质点弹簧模型，如图1a）所示;另一种是改进后的质点弹簧模型，如图1b）所示。这两种结构模型的不同点是质点之间的弹簧种类不同。文献[1]针对传统服装仿真方法提出了改进。本文在建模时布料采用三角面片组成，因此选择改进后的质点弹簧模型进行布料建模[2]。

改进后的弹簧模型减少了弹簧的种类，提高了计算效率。利用三角网格模拟布料使布料更稳定，避免运动过程中产生的抖动现象[3]。弹簧?质点模型是由质点和无质量、自然长度不为零的线性弹簧组成。由胡可定律可知，在弹性限度内当质点之间弹簧的自然长度发生改变时，无论伸长还是缩短，其改变量和弹簧所受的弹力是成正比的。假设用[i，j]表示两个相邻的质点，其质点之间的弹力计算如式（1）所示：

[Fij=k1-Lxijxij] （1）

式中：[Fij]表示质点[i，j]之间的弹力;[k]表示弹性系数;[xij]表示弹簧在某个时刻的矢量;[L]表示彈簧的自然长度。

本文用泰勒公式一阶展开式对式（1）进行一些简化。因为弹簧的自然长度为[L]，在[x=L]处的一阶泰勒展开式近似表示平方根函数，得到式（2），式中只进行一次除法操作，对于模型的[N]个质点来说，每一帧都只要计算[N]个除法，并且当[L2]初始化时还可以预计算，这样可以节省大量时间，并且还能保证计算的准确性。

[Fij=kL2xij2+L2-12xij] （2）

此外，还要考虑内力对实验的影响。本文的实验并未使用经典方法对内力进行积分，通过牛顿定律计算之后确定质点的位置以及速度，而是在求解了内力之后根据内力对弹簧质点的位置进行修正（距离约束），即当弹簧长度大于或者小于其自然长度[L]时，拉近或者推远两个质点的位置，移动的向量为[L1]：

[L1=L2xij+L2-12xij] （3）

2  布料碰撞检测

在计算机仿真中，布料的运动会受到各种力的作用，还可能会与周围的物体发生碰撞。如果碰撞问题处理的不够好，则可能会发生穿透现象，会影响视觉上的观感，而且还影响模拟结果。文献[4]在ICRA上提出了基于采样的运动规划工作空间中的包围体层次快速碰撞检测。文献[5]提出基于矢量的窄相碰撞检测距离计算方法。文献[6]通过实验确定基于离散导向多面体包围盒（26?DOPs）的包围盒层次树（BVHs）。文献[7]提出一种依赖包围盒紧密率及多层建模结构的混合碰撞检测算法。为了保证正常模拟，本文对布料质点与三角面片进行碰撞检测。

2.1  基元相交检测

对于检测质点和三角面片的碰撞现象用的比较多的是文献[8]提出的碰撞检测算法，该算法的核心思想首先要判断质点是否在三角面片上，然后再判断它们是否发生相交，如图2a）所示。该算法比较简便，但是要找一个阈值[n]，确定这个阈值的值是比较困难的，因为这个[n]值直接决定碰撞检测结果的好坏。

本文参考唐勇等人改进后的算法来进行布料和物体之间的基元相交检测，如图2b）所示。为了简化计算，假设质点在一个时间片段内的运动轨迹[s]是一个线段。步骤如下：

1） 如果质点运动轨迹的两个端点为[M0]和[M1]，[t]是一个时间片段，则线段上任意一点[M]的运动轨迹满足式（4）：

[M=M0+t?ss=M1-M0，0≤t≤1] （4）

若被碰撞物体的三角面片的三个端点分别为[A0]，[A1]，[A2]，则三角面片上任意一点[H]的运动轨迹满足式（5）：

[H=wA0+uA1+vA2w+u+v=1，0≤w，v，u≤1] （5）

2） 假设运动轨迹线段与三角面片相交，则可以通过联立式（4）和式（5）求出交点，解出[w]，[u]，[v]的数值。判断[t，u，v∈[0，1]]，若成立，则相交，如式（6）所示：

[tuv=1（s×（A-A0））?（A1-A0）?（（M0-A0）×（A1-A0））?（A2-A0）（s×（A2-A0））?（M0-A0）（（M0-A0）×（A1-A0））×s] （6）

2.2  包围盒相交检测

在虚拟环境中检测物体是否发生碰撞的主要方法之一是层次包围盒法。层次包围盒法采用包围盒树来逐渐逼近碰撞体的几何特性。本文使用AABB包围盒来进行相交检测[9]，通过图3中的算法流程（二叉树的相交检测）可以大大提高检测速度。

3  碰撞响应

3.1  碰撞响应的处理

处理碰撞响应的方法主要是对碰撞质点施加一个瞬间的力[10]。但是这种方法容易产生“边缘跳动”现象。本文则主要对几何约束法加以改进，在隐式积分法思想的基础上，改变其预测位移的思想，通过计算力对发生碰撞之后的情况进行更加详细的分析和计算，使得布料动画表现更加稳定、真实。

据现有的物理知识可知，布料发生的碰撞基本上是非弹性碰撞。发生碰撞的两个物体表面接触会产生摩擦力。假设一个质点[P]与物体表面在点[H]上相接触，[n]表示物体表面在[H]点的单位法向量，质点会在沿着[H]点法向量方向有一个正压力[FN]，令[FN=（F?n）?n]，[n]为（0，0，1）。而切向方向，有一个[F]的切向分量[FT]，令[FT=（F?n）?n]，[n]为（1，1，0）。根据摩擦力定律得出：

1） 如果[FT

2） 当[FT≥kfFN]时，[FT]为滑动摩擦，摩擦力为滑动摩擦力，大小与[FN]的大小成正比，方向与[FT]反向，此时质点受力如式（7）所示：

[Fs=FT-kf?FN?FTFT] （7）

若估计在下一个时间步长质点的位置，须考虑[FT]的准确度;因为质点的受力情况在一个时间步长内可能会发生变化，此时合力[FT]就与上述所讲不符。

由于合力是变力，本文改进了合力的求解方法，采用这个时间步长内的平均受力来近似地表示在一个时间步长内的力（下文统一称为平均力），如式（8）所示：

[F=FT+FT+Δt2] （8）

联立式（7），式（8）可得式（9），其中，[kf]是摩擦系数，实际上滑动摩擦系数与静摩擦系数并不相等，这里假定两种摩擦系数取值相同。

[Fs=FT+FT+Δt2-kf?FN?FTFT] （9）

式（12）预测的是[T+Δt]时刻质点的力，式（13）是[λ]的计算方法。将式（13）代入式（12）中可以计算出[T+Δt]时刻的力，将式（12）代入到式（9）中则可以求出在一个时间步长的平均受力。这样，得到了更为准确的位移的值。

[pT+Δt=pT+ΔTvT+（Δt）2FT2] （10）

[vT+Δt=vT+λΔtFT] （11）

[FT+Δt=F（pT+Δt，vT+Δt）] （12）

[λ=0.5+T=1N（FT+Δt）（FT-0.5ΔtFDT+Δt）T=1N（FT-0.5ΔtFDT+Δt）2]     （13）

[FDT+Δt=kf?FN?FTFT] （14）

这时，可以求得质点的速度如式（15）所示，质点的位置如式（16）所示。

[v=v+Fsm?Δt] （15）

[p=p+Fsm?Δt] （16）

3.2  穿透现象的处理

当然，在布料仿真的过程中很容易发生穿透现象。对于碰撞过程中发生的穿透现象，本文提出使用分离坐标轴的方法。该方法需要计算出碰撞物的相交深度和碰撞物分离开的方向。相交深度和方向的组合即为最小平移距离，该距离作为将物体分离的最小向量。当两个物体发生相交时，计算两个物体在分离轴上的相交深度，这个相交深度提供一个推动向量，将向量应用到一个物体上，以便物体在轴上的投影停止交叠。

这里需要设定一个分离轴，如果两个面片发生穿透现象的话，可以将其中一个三角面片所在的平面设定为发生碰撞的平面，而将垂直于这个平面的轴设置为分离轴，如图4所示，若以[b]面片所在的面为碰撞平面，垂直于[b]面的轴为分离轴（分离轴的方向为相交深度的返回方向），相交深度[l]通过计算其在分离轴上的投影而得到。

确定了分离轴之后，两个穿透的物体会返回一个相交深度值。此时，给[a]面片一个初始的冲量和力，让其在一个时间段内从穿透的位置返回到碰撞平面上。这里需要计算这个初始冲量和力的大小。为了理解简单一些，从反方向考虑，一个质点受力从静止到加速到[vt]，经过的位移是[l]。根据式（17），可以求得加速度为式（18）。质点初始速度为0，末速度为[vt]，将式（18）代入式（20）中可得[vt]为式（21）。将得到的[vt]作为初速度，给[a]面片一个大小为[mv0]的瞬间冲量，并施加一个大小为[F]的阻尼力，[a]面片位移在达到相交深度[l]时可以刚好停下来。

[l=12at2] （17）

[a=2lt2] （18）

[F=ma] （19）

[v2t-v20=2al] （20）

[vt=2lt] （21）

4  实验结果与分析

本文实验基于Windows操作系统，使用Unity3D模拟布料仿真过程。硬件环境为：Inter[?] Xeon[?] CPU E5?2630 v3 @ 2.40 GHz 64.0GRAM 显卡为NVIDIA Quadro K5200。

本文在碰撞响应的算法中，采用单位步长的平均力来计算加速度，相对于已有的隐式积分法来计算加速度的方法，提高了算法的精确性。

图5为平均力法和传统约束力法得出结果的对比图，从图5中可以明显看出，比起传统约束力法，平均力法得出的预测值更加接近实际值，误差降低5%～10%，并且随着时间步长的增大，平均力法得出的预测值相较于瞬时力法得出的预测值误差会越来越低。

在处理穿透现象时，本文提出的分离轴算法可以解决布料在自碰撞过程中的穿透现象。图6是在未使用分离轴算法的情况下做实验的效果图，从图中标记处可以很明显地看出布料从球面上滑下到落地后静止，一直都会有穿透现象的发生。从图7中可以看到布料从球面滑下直到落地后静止，即使布料发生了自碰撞也并没有穿透现象。所以，分离轴算法解决穿透现象十分可行且稳定。

5  结  论

本文通过实验针对位移的预测和穿透现象得出以下结论：

1） 平均力法计算加速度，预算在下一个时间步长质点的位移。通过计算一个时间步长的平均力来计算加速度，预算在这个时间步长内质点的位移，得到的结果比传统约束法更加精确。但是，只取两个点的话准确度离准确值还有点距离，如果要取更多点的话，会增大计算量，所以下一步还需要改进算法，降低计算量。

2） 针对布料在自碰撞时发生的穿透现象，本文提出基于分离轴的计算方法。解决了仿真过程中的穿透现象，令发生穿透的物体可以在不影响视觉观感的前提下返回到被穿透物体的表面，稳定流畅地表现了布料的仿真运动。

参考文献

[1] 张华忠，侯进.基于碰撞检测算法的动态服装仿真研究[J].科学技术与工程，2017（31）：294?297.

[2] 唐勇，严凯丽，刘宇涵，等.多形态布料仿真中与刚体的实时碰撞检测[J].小型微型计算机系统，2016，37（10）：2347?2350.

[3] 吕梦雅，许立瑶，唐勇，等.随机可控风场中三维布料实时仿真[J].小型微型计算机系统，2015，36（12）：2769?2772.

[4] SCHWESINGER U， SIEGWART R， FURGALE P. Fast collision detection through bounding volume hierarchies in workspace?time space for sampling?based motion planners [C]// 2015 IEEE International Conference on Robotics and Automation. Seattle， WA： IEEE， 2015： 63?68.

[5] SULAIMAN H A， OTHMAN M A， SAAT M S M， et al. Vector?based technique for distance computation in narrow phase collision detection [C]// 2014 International Symposium on Technology Management and Emerging Technologies. Bandung： IEEE， 2014： 506?510.

[6] 周清玲，刘艳，程天翔.大规模柔体的连续碰撞检测算法[J].中国图象图形学报，2016，21（7）：901?912.

[7] 胡春安，谢伟超，王振东.依赖包围盒紧密率及多层建模结构的混合碰撞检测算法[J].科学技术与工程，2018（16）：74?80.

[8] BRIDSON R， ANDERSON J， FEDKIW R. Robust treatment of collisions， contact and friction for cloth animation [J]. ACM transactions on graphics， 2002， 21（3）： 594?603.

[9] HUBER M， EBERHARDT B， WEISKOPF D. Boundary handling at cloth?fluid contact [J]. Computer graphics forum， 2015， 34（1）： 14?25.

[10] 常元章.基于质点—弹簧模型的布料仿真[D].天津：天津大学，2008.

作者简介：靳雁霞（1973—），女，博士，副教授，CCF会员，主要研究方向为虚拟现实、图形图像处理。