持续碰撞检测预防误差

1、持续碰撞检测预防误差摘要： 在持续碰撞检测中由于人为的原因会引入一些数值误差和舍入误差。利用误差公差可以解决这些误差，但是对于用户来说找到最优误差比较困难。大的误差会引起错报现象，小的误差不易被检测出来。我们面临的最大问题就是不知道什么时候CCD会产生误差，虽然误差比较小。在这篇文章中，我们对所做的基础CCD出现的故障根进行了修改，采用误差分析，我们可以证明这个方法的可靠性并且产生合理的公差值减少假性误差，这个方法所产生的结果是可靠的、自动的、高效的并且易于执行。关键字：浮点算法、舍入误差、数值误差、持续碰撞检测、二三次求解器1 介绍 在持续碰撞检测中检测一个时步内顶点和三角形面及边与边的交点

2、是基本步骤。由于数值和舍入误差，检测结果会出现两种错误：漏报：CCD不能检测到实际碰撞事件；错报：CCD检测出的碰撞没有发生。错报比漏报更严重，他们认为碰撞检测故障必须避免。Bridson et al提出使用经典方法会比设置误差公差更能够检测到碰撞事件，这个方法可以减少碰撞故障，但是不清楚多大的公差可以完全避免，要确保安全性，用户会选择更大的误差值，但是额外的错报也许会产生其他问题，像视觉效果、计算负担和在碰撞操作中的收敛问题。为了解决这些问题Brochu and Bridson 2012从几何领域来研究CCD，并得出了一个碰撞推测，能够剔除漏报和错报，不足的是，在精度和区间运算中需要更多的算

3、法操作。经典的CCD算法解一个三次方程找到两个参考体共面的时间和用它来检测交点，这个方法是平庸的、没有用的“failure-proof”如果其播报正面，我们就要同时避免错误和减少错报。不好的是，通过已存的算法来限制故障的产生是困难的。为了解决这个问题，我们的观点是引入一些条件，用顶点/三角形面和边/边测试用来保证错误。在一个时间步内如果顶点/边的距离低于一定的阈值就播报碰撞。利用有效的大的距离阈值，我们确保任何碰撞事件都可以检测。 然而我们的观点是简单地，它执行需要我们面临两大挑战：怎样进行顶点和边测试。当顶点/边的欧几里德距离等于一个阈值时要计算时间就要解一个二次方程，它的计算简单并且易于产

4、生很多错误。Brochu and Bridson提出了基于体积的算法，该算法不能检测距离且不用计算时间，但是用精确算法来避免舍入误差。第二个挑战就是怎样估计整个测试误差。因为数值误差是由三次求解器产生的、舍入误差是由浮点算法产生的，我们不能直接进行误差分析。 这篇文章中我们的贡献是：1）顶点和边测试与误差有关新的实行方法，其是机器数；2）对于cubic-based进行系统误差分析3）对于cubic-based测试错误根进行一系列修改4）我们的算法对于误差公差下限的选定从以下几个方面考虑： 可靠 我们可以无条件的证明基于立方体连续碰撞测试算法的错误根是应用我们的方法后产生的。 简单 我们的修改是

5、简单的并且易于合并到已存在的系统中。 高效 我们的实验显示我们方法的计算成本仅仅是原始测试成本的一部分。 自动 基于误差分析，连续碰撞检测算法能够自动决定所有的公差值，用户不需要特定一个参数。 精确 我们的方法通过当错误产生时来最小化顶点/三角形面或者边边距离来计算公差值。因此他们能够减少错误。2 预备知识碰撞检测： 误差、近似退化以及交点测试在之前已被研究了，基于这些测试又提出了离散碰撞检测算法，其只能在离散的时间进行碰撞检测，而且这个算法物体快速移动的时候会遗失碰撞，最经典的是”隧道效应“。解决方法是逐步接近模拟时间直到发生碰撞。还有连续碰撞检测算法，当两个参考体共面时来计算可能的碰撞时间

6、。对于顶点三角形到面和边到边的碰撞，其时间可以通过解三次方程来获得。Bridson et al. 通过顶点/面、线与线距离以及重心坐标的舍入误差公差来改善这个方法的鲁棒性，然而目前找到最优误差公差是个难题，并且也没有方法来保证检测到每个碰撞事件。为了避免碰撞故障，Brochu and Bridso n 提出了把碰撞检测和碰撞时间查询分开，并得出一个利用精确算法的root-parity-base d CCD算法。Stam2009提出当两个参考体的距离小于一个阈值就播报碰撞，则碰撞测试的鲁棒性就得以改善。这就要求处理顶点/三角形面或者边/边碰撞时，解six-order多项式方程。碰撞选择和处理 目

7、前在碰撞选择上的研究产生了许多高效的技术，我们的算法和那些技术都是可以兼容的，一旦发现了碰撞，下一个问题就是怎样解决物体对碰撞的反应。这个方法在复杂的多碰撞事例中比较困难。经典的算法不能解决碰撞后的许多处理步骤，其被作为在影响区的刚体。Thomaszews 建议对于更精确的碰撞响应异步的处理碰撞，他们的方法是依赖于异步碰撞处理来避免残余碰撞。单纯的异步系统保证每一个碰撞处理都在一个有限的时间进行并且碰撞没有穿透。Ainsley et al. 2012把连续碰撞检测和异步系统结合起来可以减少重新碰撞的数目和使系统运行更快，因此在CCD中利用我们的算法可以减少错报和使碰撞更精确，它也会改善碰撞处理

8、的鲁棒性。3 连续碰撞检测 在本节，我们给出顶点/顶点（VV）连续碰撞检测、顶点/边(VE)连续碰撞检测、顶点/三角形面(VT)连续碰撞检测和边/边(EE)连续碰撞检测算法，我们的观点是把VV测试和VE测试合并，和把VE测试、VT和EE测试合并。如图二所示，我们注明由于利用公差，本节所给出的伪码和描述的有所不同。我们会在第4节中深入讨论。3.1 顶点/顶点碰撞检测其给出的碰撞，如果在时间域（0,1）之内的任意时间点存在欧几里德距离小于阈值D。欧几里德距离定义为：（xji+tvji)*(xji + tvji),此算法给出的碰撞如算法1所示。3.2 顶点/边碰撞测试 给出的碰撞是欧几里德距离小于阈

9、值R.，x0做顶点且xixj是边，欧几里德距离就是在时间t顶点到边的距离是：，算法过程如图2所示给出这五种情况，我们能得到顶点到边的CCD算法有两步，第一步它计算了一系列碰撞候选点，第二步尽管有许多候选点，只有（0,1）之间是有用的、需要进一步检测。现存在一个问题怎样通过顶点到顶点CCD来决定阈值D的距离来获得遗失的碰撞事件，t0是F0ij(t)最小化的点、tE0是欧几里德最小化的时间点，如果在时间tE0顶点的投影在边的外面，就设D>=R，如果在时间t0顶点的投影在边的里面，就不用顶点到顶点CCD，碰撞会遗失当顶点的投影在t0的外面但是在t0的里面，如图3所示，因为t0是F0ij（t）的

10、最小值接近于t0,F0ij(t)<=0并且顶点/线的距离在任意内都小于S。当顶点的投影从边的内部移到外部，顶点的投影在端点处肯定存在时间t.。我们用D>=S=3R来获得有顶点/顶点连续碰撞检测在时间t上的碰撞。3.3 顶点/三角形面碰撞检测顶点/三角形CCD算法如算法3所示，我们用顶点到边CCD之后还要进行cubic-based测试，来避免遗失碰撞。三次方程的闭合解要求有立方根，在IEEE754标准下是不正确的。相反，数值求解器会找到t，t0,其残余误差是低于阈值.，使用这个阈值会遇到两个问题。小三角形和平行运动。3.3.1 误差和错报（False Positives） 这里我们不

11、考虑舍入误差只研究全面的误差，我们有两个目的，1）剔除漏报（false negatives）。2）尽可能减少错报（false positives）。 是三次求解器的收敛阈值，在顶点到三角形近似测试中的厚度阈值，R是在顶点到边CCD中的欧几里德距离阈值。t0是顶点到三角形的相交时间、t0是计算的得到的。F(t)=A(t)C(t),A(t)是三角形面积的二倍,C(t)是顶点到面的距离。三角形面积测试：如图3b所示。因为所以近似测试失败了。如果有三角形内切圆的最大二次半径为并且在时间t0上至少一个二次欧几里德距离是小于，因此通过设置我们能得到顶点到边CCD获得碰撞。另一方面我们有图3c知，因为A(t

12、)和顶点的投影是两个时间的连续函数，时间t 在，和顶点的投影在三角形内部如图3d所示，或者和顶点的投影在三角形的边上图3e，以上分析可以得到任意如果A(t)<=我们都可以用t0代替t用以上分析得到这是高效的得到碰撞检测，因此当任意时间我们只要考虑A(t)>= 这种情况即可。重心测试：如果A(t0)>，只因为重心测试近似测试可能会失败。t是顶点的投影相交于三角形边的时间，这种情况时间t0上顶点的投影在三角形的外面，t是顶点相交于三角形边的时间。根据前面的分析A(t)>= ，顶点到面的距离由来限定并且我们能用R>=来检测时间t上的碰撞总结 是有效的检测顶点到边CCD的

13、遗失碰撞事件。R尽可能小可以减少错报，假定 ，,我们可以设 来最小化R。简单来说就是利用和 。我们会在4.4中讨论有舍入误差产生的变化。3.4 边/边碰撞检测 检测X0X1和X2X3两个边的之间的碰撞，我们得出边/边CCD和顶点/三角行CCD类似，但是N是两个边的叉积。|N|2是四边形面积的2倍，四边形是由四个顶点沿着N方向上的投影构成的，立方函数定义为：F（t）=(X20+tV20)*(X10+tV10)*(X32+tV32)，.这个算法也有小四边形，有两个边构成的四边形是小的；垂直运动，边的运动近似和N正交。我们的解决方案是用顶点/边CCD。 下面也有和顶点到边CCD相同的情况误差和错报、

14、四边形面积测试、重心测试。误差和错报是通过忽略舍入误差，剔除漏报和减少错报。是立方体求解器的收敛阈值，是线到线距离的厚度阈值，R是在顶点到边CCD的距离阈值。定义F(t)=A(t)C(t),A(t)是四边形面积的二倍,C(t)是线到线的距离，面积测试;重心测试，如果任何一步出现碰撞故障，就必须要用顶点/边CCD来测试。过程和顶点到边CCD相似，总而言之，可以有效的避免遗失碰撞事件的发生 。使R尽可能的小可以减少错报。给定，我们通过设定来最小化R，这种情况下，简单来说就是，我们利用和。4 错误分析由浮点算法所产生的舍入误差比数值误差更复杂，我们会在4.1中研究其特性然后讨论其在CCD中的影响。舍

15、入误差特性：a是一个实际的数字，舍入过程就是把a转化为一个浮点数a，像，其中是机器数。单精度的浮点数形式为，双精度的浮点数为，对浮点数进行的计算操作是浮点算法，根据IEEE754标准，浮点数算法的操作包括加减乘除和二次根，这些都必须要进行正确的舍入。换句话说，给定一个确切的算术运算符*和它对应的单精度符号，。当存在多浮点数操作时，就积累舍入误差并且误差的范围不直接进行计算。处理这个问题我们基于前面的误差分析给出了误差估计方法,f是包含多个运算操作的函数，它的舍入误差被限定：，其中在|f|中是上限和是指数系数，假定在f上所有的变量都由B0限定上限B,我们可以制定一个f操作树并找到Bf和kf：如果

16、i是一个叶节点，Bi=B0和ki=0;如果i不是叶节点类似与加或者减并且它有两个子节点l和r，Bi=Bl+Br并且ki=max(kl,kr)+1.如果i不是叶节点类似与乘或者除并且它有两个子节点l和r，Bi=BlBr并且ki=kl+kr+1.我们用下面4.1原理证明这些规则的正确性。在误差分析中，对于向量部分我们会给出一个上限，也只有当真正的碰撞发生时才会考虑这种情况4.2 在顶点/顶点CCD误差我们首先研究在顶点/顶点CCD中的碰撞时间t0, ，我们从4.1原理可知和图4a和假定，我们有。因为应用在之后这个结果是刚性的，会使更小。是时间t上的欧几里德距离。因为，我们必须有。然而。近似测试不能

17、准确评估。因此部分有B来限定，我们能够设置公差避免漏报。4.3 顶点/边CCD误差 我们首先研究的误差是关于顶点/线的距离。为了简化分析，我们通过删除在Xa和Xb的组件来修改，如果小于。结果为。因为是小的。的最小值接近的最小值。在算法2中，有四个关于的例子。我们设置公差阈值，来避免由于舍入误差产生的故障。为了更进一步减少错报，我们介绍了边长测试。我们的目的是为了确保如果长度测试和重心测试都产生了真正的碰撞故障，顶点/顶点CCD必须能够检测到。边长测试这个测试可以避免当边长小于（）的时候产生大的错报。其中在时间上被计算为欧几里德边长。重心测试边长测试之后，重心测试也许会失败。通过边长测试得，或者

18、因为重心的重量不是由点来计算的，其误差由限定并且重心测试误差是由来限定，重心测试所得值等于顶点投影到端点的距离的边长时间，因此重心测试失败，顶点投影到一个端点的距离在时间没有超过，我们获得有效的条件是：。错报一个错报可能由顶点/边CCD本身检测出。因为在顶点/顶点CCD中误差是小的，我们考虑把D作为一个上限在二次顶点/边距离这两种情况，为了减少错报，我们会找到最优来最小化D.暂时忽略S和简便执行后，我们选择和我们设作为顶点/边CCD一个有效条件。4.4 顶点/三角形面CCD误差 顶点/三角形面CCD算法有四步：1）找到立方等式的根；2）测试三角形的面积；3）确定三角形的高度；4）测试重心坐标。

19、 找根解决等式的第一步。的精确根和的不同有两个原因。第一个原因是误差和系数有关，根据定理4.1，和是由所限定的如图4b和4c所示。 第二个原因是误差是由立方求解器产生的。附录B显示了如果我们的求解器保证对于每个t0都会有的存在，并且对于任意都有。 三角形面积测试在这步骤，我们测试三角形面积是否足够大可以计算碰撞时间参数。为了简化误差分析，我们测试，其中是面积阈值。用定理4.1和图4d，我们知道关于N的误差由限定。如果三角形面积测试失败，在时间上就有。从3.3节分析我们得到是可以有效获得许多碰撞检测，其中，另一方面，如果一个顶点和一个三角形通过面积测试，然后，由定义顶点到面的距离必须由来限定。我

20、们知道如果任意碰撞满足，是可以获得检测的。根据3.3.1的分析，我们假定和下一个任一顶点/面的距离由限定。三角形高度测试当三角形是小的，在重心测试中舍入误差会导致大的错报。因此我们给出一个三角形高度测试来测试他们，而不是发送他们给顶点/边CCD。在时间我们把高度阈值和三角形的高度进行比较：，其中ij是三角形的边，因为这个测试发生在面积测试之后，我们必须要。h是三角形的高度。所有的高度必须比大，如果三角形通过三角形高度测试，另一方面，如果一个三角形没有通过高度测试，我们必须确保一个真正的碰撞可以通过顶点/边CCD测试得到。当任意三角形的边在时间小于E则高度测试失败。如果任意边在时间t0上小于E，

21、我们能简单的利用这个条件：，如果不是，通过定义两个事件：1）最短边的长度是E2）顶点的投影在三角形边上，我们能够根据3.3.1的两个事件进行分析得到一个有效的条件：，其中是在任意时间顶点到面距离的的上限。而且，没有边在时间上小于E则高度测试就是失败的。重心测试 重心测试计算重心的权重和0或者比较，每个权重包含最多误差，如图4e所示。因此每个重心标准的所有误差必须由来限定。如果重心测试确实失败了，则在时间 顶点投影到三角形的外面，根据我们之前在3.3.1节的分析，R>=r可以有效获得由顶点/边CCD测试的一些情况。如果重心测试误差失败，在时间顶点的投影应该一直在三角形的里面。有定义，由图5

22、a知，重心权重分配到X1和是相同的。边的长度是顶点-边-线距离L的数倍，因为顶点和三角形通过了面积测试和高度测试，我们知道和所有的高度都大于，给定没有边小于最短距离，得到，当顶点的投影在三角形的里面，它到边线距离也是他到边的距离。因此是有效的可以获得在时间上由顶点/边CCD测试的情况。4.4.1 错报 研究错报，会得到在时间当错报发生时顶点/三角形距离的一个上限。近似测试 当错误的通过三个测试，错报就会发生。基于以前的分析，我们知道顶点到面的距离在时间由r来限定。问题就是顶点的投影和三角形边的距离是多少，由于重心测试错报才发生。有前面我们知道，重心测试的舍入误差是由来限定的。顶点/边测试 如果

23、三个测试都发生假性错误，它通过了顶点/边CCD，根据4.3，平房距离由来限定。总之，我们的目标是最小化：，其中，尽管最小化是复杂的，许多关系是没有意义的。简化和近似之后，我们给出用，顶点到三角形的距离近似为，用双倍精度形式，这大约是边长最大值的百分之0.5，假性错误是预测顶点到三角形距离的最槽糕的方法并且它不是准确的。4.5 边/边CCD误差 相似与顶点/三角形CCD、边/边CCD都要用立方求解器来计算时间上的每个可能碰撞。如果对于任意计算根满足，这个分析和余下步骤不同。四边形面积测试 相似与4.4中的三角形面积测试，用来测试是否四边形的面积足够大。如果测试失败，在时间则，有3.4节给出的分析

24、，知道 是有效条件，其中，用相同的分析，我们知道如果两个边通过面积测试，我们必须有。如果在任意时间，必须有在顶点/边CCD上测得。随后在任意时间，我们假定和线到线的距离由r来限定。四边形的高度测试和4.4的三角形高度测试相似，四边形高度测试为了减少假性错误。对于每个边，我们定义它的四边形高度为：。在测试中我们把每个高度和阈值进行对比：，相似于三角形高度测试，如果高度h通过高度测试，必须有，来确保每个碰撞事件的测试，这个测试当真正的碰撞失败我们考虑两个可能性：在时间任意一边小于E，这个测试也许会失败，在相交时间t0，任意边小于E，我们可以简单地利用条件：来获得在时间上的碰撞，如果高度测试失败，则

25、在时间没有边小于E，在时间至少一个高度是小于，其中是高度测试误差的上限。 重心测试相似与顶点/边CCD重心权重，关于每个权重的误差都有来限定。如果重心测试确实失败了，两个边的投影在时间不相交，如果重心测试误差失败，两个边的投影在时间相交，两个边通过面积测试和高度测试，得到比大和高度比大。给定没有边比更短的边小，在投影的空间上顶点-边-线的距离由来限定。我们用来检测一些碰撞。4.5.1 假性错误 下面我们研究当假性错误发生，在时间边到边的距离的上限。近似测试三个测试都通过了，一个假性错误会发生。在时间线到线的距离由r来限定。这个问题就是在时间两个投影边的最大距离是多少，什么时候假性错误发生？顶点

26、/边测试 任意三个测试有假性错误故障，只能通过顶点/边CCD.4.3的分析显示平方距离是由来限定的。总结可得：有，化简和近似以后，我们提出利用，边到边的距离近似为，利用双倍精度形式，其大约是边长最大值的百分之0.5。5 总结基于现有的基础立方体CCD系统，我们在小于一个小时内进行修改。我们也在CCD测试中进行基本面选择（不包括AABB选择），这是由Brochu and Bridson 2012提出的。不使用离散算法，我们通过引用另一个误差公差来避免舍入误差对基本面选择的影响，随着我们算法的深入，我们提出了对于顶点到边测试的另一种算法，给出已知的碰撞时间,我们首先测试是否三次函数值的大小在超过，

27、如果在时间t0发生碰撞，就有 。 给定B作为相对速度的上限，顶点的投影和三角形之间的距离在时间必须有来限定，并且至少一个重心权重是在，换句话说就是没有碰撞会发生，如果权重超过这个范围。因为是小的，这个测试可以剔除向我们实验所展示的百分之99.9的VE测试。 我们现在还没有解决的问题是在向量计算中的误差。拿VV CCD举例，目的就是找到之间的碰撞，但是算法测试的是。因为一些误差是由来限定的，如果碰撞因为这个发生故障，顶点到三角形的距离在最后必须由来限定。这个问题可能由像许多系统一样在时间末尾做近似测试来解决。公差越大，就更要进行碰撞测试。 另一个问题来自上限B,每一个时间步都要计算，B0是上限的

28、最初时间步并且B1是上限的下一个时间步。如果B1>B0就会在下一步的开始时间检测到碰撞，在碰撞处理中会产生收敛问题。解决办法是返回到最初的时间步，用B1在最后时间上进行碰撞检测。为了简单，我们重新定义B并且假定它在整个动画中都是有用的。我们甚至可以分别定义每个顶点/三角形或者边边对的B,利用它们其余的形态，做这些可以减少B，并且对长边和短边的采样网格分别进行处理。特性： 我们对图1和图7的四个衣服动画进行我们算法特性的测试。用一个单核一个2.67GHZ的Intel Xeon X5650处理器，之后进行AABB选择，每个基础VT或者EE CCD的平均计算时间是350ns,用来我们的修改之后

29、计算时间是355ns，因此超过基础成本的1.4%。没有基础面的选择，使用我们修改前后的成本分别为409ns和416ns。为了更好的理解复杂环境的特性，我们通过对向量位置和一个单元格的速度进行随意采样来构造一个综合实例，我们能详尽测试100亿个例子。我们修改前后每个测试的成本分别为364ns和369ns。综合例子和动画例子时间的不同是由于更多正面的情况。由于动画例子显得更逼真的，所以和综合实例的时间不同。和精确的算法相比，我们的测试比碰撞选择后的精准测试还要快20到40倍。这在综合例子中尤其突出，这里有接近一半的例子通过AABB选择和接近1/3的例子通过基本面选择。我们的实验表明AABB选择之后

30、精准测试的平均时间是4.962ns,对比我们的测试是快的甚至没有选择。在实际的动画例子中，由于碰撞选择不同是不显著。仅仅能发现在顶端时间的不同，我们的方法比精确方法快20%。一旦碰撞选择的成本在整个碰撞处理的成本中占得比较低，我们的方法有效性更加明显。假性错误（错报） 根据前面的分析，在仿真中错报的点/三角形距离的最大值接近20 。错报对动画例子的影响，我们不能简单的计算大多数的正面例子，错报会让碰撞处理提前并且避免之后正面的产生。要计算所有的测试例子和它们正面结果，我们用我们的方法和精确的方法分别模拟了动画实例。用我们的方法可能检测到百分之十的正面例子。我们的实验表明用两种方法整个例子的数目大约是一样的，用我们的方法能检测出超过10%的更多正面情况。幸运的是，更多的结果还是反面的。那些额外的正面对碰撞检测的特性没有影响。可靠性： 如果没有用公差误差，碰撞检测的失败可能