持续碰撞检测预防误差

持续碰撞检测预防误差摘要：在持续碰撞检测中由于人为的原因会引入一些数值误差和舍入误差。利用误差公差可以解决这些误差，但是对于用户来说找到最优误差比较困难。大的误差会引起错报现象，小的误差不易被检测出来。我们面临的最大问题就是不知道什么时候CCD会产生误差，虽然误差比较小。在这篇文章中，我们对所做的基础CCD出现的故障根进行了修改，采用误差分析，我们可以证明这个方法的可靠性并且产生合理的公差值减少假性误差，这个方法所产生的结果是可靠的、自动的、高效的并且易于执行。关键字：浮点算法、舍入误差、数值误差、持续碰撞检测、二—三次求解器1介绍在持续碰撞检测中检测一个时步内顶点和三角形面及边与边的交点是基本步骤。由于数值和舍入误差，检测结果会出现两种错误：漏报：CCD不能检测到实际碰撞事件；错报：CCD检测出的碰撞没有发生。错报比漏报更严重，他们认为碰撞检测故障必须避免。Bridsonetal提出使用经典方法会比设置误差公差更能够检测到碰撞事件，这个方法可以减少碰撞故障，但是不清楚多大的公差可以完全避免，要确保安全性，用户会选择更大的误差值，但是额外的错报也许会产生其他问题，像视觉效果、计算负担和在碰撞操作中的收敛问题。为了解决这些问题BrochuandBridson[2012]从几何领域来研究CCD，并得出了一个碰撞推测，能够剔除漏报和错报，不足的是，在精度和区间运算中需要更多的算法操作。经典的CCD算法解一个三次方程找到两个参考体共面的时间和用它来检测交点，这个方法是平庸的、没有用的“failure-proof”如果其播报正面，我们就要同时避免错误和减少错报。不好的是，通过已存的算法来限制故障的产生是困难的。为了解决这个问题，我们的观点是引入一些条件，用顶点/三角形面和边/边测试用来保证错误。在一个时间步内如果顶点/边的距离低于一定的阈值就播报碰撞。利用有效的大的距离阈值，我们确保任何碰撞事件都可以检测。然而我们的观点是简单地，它执行需要我们面临两大挑战：怎样进行顶点和边测试。当顶点/边的欧几里德距离等于一个阈值时要计算时间就要解一个二次方程，它的计算简单并且易于产生很多错误。BrochuandBridson提出了基于体积的算法，该算法不能检测距离且不用计算时间，但是用精确算法来避免舍入误差。第二个挑战就是怎样估计整个测试误差。因为数值误差是由三次求解器产生的、舍入误差是由浮点算法产生的，我们不能直接进行误差分析。这篇文章中我们的贡献是：1）顶点和边测试与误差有关新的实行方法，其是机器数；2）对于cubic-based进行系统误差分析3）对于cubic-based测试错误根进行一系列修改4）我们的算法对于误差公差下限的选定从以下几个方面考虑：可靠我们可以无条件的证明基于立方体连续碰撞测试算法的错误根是应用我们的方法后产生的。简单我们的修改是简单的并且易于合并到已存在的系统中。高效我们的实验显示我们方法的计算成本仅仅是原始测试成本的一部分。自动基于误差分析，连续碰撞检测算法能够自动决定所有的公差值，用户不需要特定一个参数。精确我们的方法通过当错误产生时来最小化顶点/三角形面或者边边距离来计算公差值。因此他们能够减少错误。2预备知识碰撞检测：误差、近似退化以及交点测试在之前已被研究了，基于这些测试又提出了离散碰撞检测算法，其只能在离散的时间进行碰撞检测，而且这个算法物体快速移动的时候会遗失碰撞，最经典的是”隧道效应“。解决方法是逐步接近模拟时间直到发生碰撞。还有连续碰撞检测算法，当两个参考体共面时来计算可能的碰撞时间。对于顶点三角形到面和边到边的碰撞，其时间可以通过解三次方程来获得。Bridsonetal.通过顶点/面、线与线距离以及重心坐标的舍入误差公差来改善这个方法的鲁棒性，然而目前找到最优误差公差是个难题，并且也没有方法来保证检测到每个碰撞事件。为了避免碰撞故障，BrochuandBridson提出了把碰撞检测和碰撞时间查询分开，并得出一个利用精确算法的root-parity-basedCCD算法。Stam[2009]提出当两个参考体的距离小于一个阈值就播报碰撞，则碰撞测试的鲁棒性就得以改善。这就要求处理顶点/三角形面或者边/边碰撞时，解six-order多项式方程。碰撞选择和处理目前在碰撞选择上的研究产生了许多高效的技术，我们的算法和那些技术都是可以兼容的，一旦发现了碰撞，下一个问题就是怎样解决物体对碰撞的反应。这个方法在复杂的多碰撞事例中比较困难。经典的算法不能解决碰撞后的许多处理步骤，其被作为在影响区的刚体。Thomaszews建议对于更精确的碰撞响应异步的处理碰撞，他们的方法是依赖于异步碰撞处理来避免残余碰撞。单纯的异步系统保证每一个碰撞处理都在一个有限的时间进行并且碰撞没有穿透。Ainsleyetal.[2012]把连续碰撞检测和异步系统结合起来可以减少重新碰撞的数目和使系统运行更快，因此在CCD中利用我们的算法可以减少错报和使碰撞更精确，它也会改善碰撞处理的鲁棒性。3连续碰撞检测在本节，我们给出顶点/顶点（VV）连续碰撞检测、顶点/边(VE)连续碰撞检测、顶点/三角形面(VT)连续碰撞检测和边/边(EE)连续碰撞检测算法，我们的观点是把VV测试和VE测试合并，和把VE测试、VT和EE测试合并。如图二所示，我们注明由于利用公差，本节所给出的伪码和描述的有所不同。我们会在第4节中深入讨论。3.1顶点/顶点碰撞检测其给出的碰撞，如果在时间域（0,1）之内的任意时间点存在欧几里德距离小于阈值D。欧几里德距离定义为：（xji+tvji)*(xji+tvji),此算法给出的碰撞如算法1所示。3.2顶点/边碰撞测试给出的碰撞是欧几里德距离小于阈值R.，x0做顶点且xixj是边，欧几里德距离就是在时间t顶点到边的距离是：，算法过程如图2所示给出这五种情况，我们能得到顶点到边的CCD算法有两步，第一步它计算了一系列碰撞候选点，第二步尽管有许多候选点，只有（0,1）之间是有用的、需要进一步检测。现存在一个问题怎样通过顶点到顶点CCD来决定阈值D的距离来获得遗失的碰撞事件，t0是F0ij(t)最小化的点、t^E0是欧几里德最小化的时间点，如果在时间t^E0顶点的投影在边的外面，就设D=R，如果在时间t0顶点的投影在边的里面，就不用顶点到顶点CCD，碰撞会遗失当顶点的投影在t0的外面但是在t0E的里面，如图3所示，因为t0是F0ij（t）的最小值接近于t0E,F0ij(t)=0并且顶点/线的距离在任意内都小于S。当顶点的投影从边的内部移到外部，顶点的投影在端点处肯定存在时间t.。我们用D=S=3R来获得有顶点/顶点连续碰撞检测在时间t上的碰撞。3.3顶点/三角形面碰撞检测顶点/三角形CCD算法如算法3所示，我们用顶点到边CCD之后还要进行cubic-based测试，来避免遗失碰撞。三次方程的闭合解要求有立方根，在IEEE754标准下是不正确的。相反，数值求解器会找到t，ˆt0,其残余误差是低于阈值μ.，使用这个阈值会遇到两个问题。小三角形和平行运动。3.3.1误差和错报（FalsePositives）这里我们不考虑舍入误差只研究全面的误差，我们有两个目的，1）剔除漏报（falsenegatives）。2）尽可能减少错报（falsepositives）。μ是三次求解器的收敛阈值，在顶点到三角形近似测试中的厚度阈值，R是在顶点到边CCD中的欧几里德距离阈值。t0是顶点到三角形的相交时间、t^0是计算的得到的。F(t)=A(t)C(t),A(t)是三角形面积的二倍,C(t)是顶点到面的距离。三角形面积测试：如图3b所示。因为所以近似测试失败了。如果有三角形内切圆的最大二次半径为并且在时间t0上至少一个二次欧几里德距离是小于，因此通过设置我们能得到顶点到边CCD获得碰撞。另一方面我们有图3c知，因为A(t)和顶点的投影是两个时间的连续函数，时间t在，和顶点的投影在三角形内部如图3d所示，或者和顶点的投影在三角形的边上图3e，以上分析可以得到任意如果A(t)=我们都可以用t^0代替t用以上分析得到这是高效的得到碰撞检测，因此当任意时间我们只要考虑A(t)=这种情况即可。重心测试：如果A(t^0)，，只因为重心测试近似测试可能会失败。t是顶点的投影相交于三角形边的时间，这种情况时间t^0上顶点的投影在三角形的外面，t是顶点相交于三角形边的时间。根据前面的分析A(t)=，顶点到面的距离由来限定并且我们能用R=来检测时间t上的碰撞总结是有效的检测顶点到边CCD的遗失碰撞事件。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相同的情况误差和错报、四边形面积测试、重心测试。误差和错报是通过忽略舍入误差，剔除漏报和减少错报。是立方体求解器的收敛阈值，是线到线距离的厚度阈值，R是在顶点到边CCD的距离阈值。定义F(t)=A(t)C(t),A(t)是四边形面积的二倍,C(t)是线到线的距离，面积测试;重心测试，如果任何一步出现碰撞故障，就必须要用顶点/边CCD来测试。过程和顶点到边CCD相似，总而言之，可以有效的避免遗失碰撞事件的发生。使R尽可能的小可以减少错报。给定，我们通过设定来最小化R，这种情况下，简单来说就是，我们利用和。4错误分析由浮点算法所产生的舍入误差比数值误差更复杂，我们会在4.1中研究其特性然后讨论其在CCD中的影响。舍入误差特性：a是一个实际的数字，舍入过程就是把a转化为一个浮点数a^，像，其中是机器数。单精度的浮点数形式为，双精度的浮点数为，对浮点数进行的计算操作是浮点算法，根据IEEE754标准，浮点数算法的操作包括加减乘除和二次根，这些都必须要进行正确的舍入。换句话说，给定一个确切的算术运算符*和它对应的单精度符号，。当存在多浮点数操作时，就积累舍入误差并且误差的范围不直接进行计算。处理这个问题我们基于前面的误差分析给出了误差估计方法,f是包含多个运算操作的函数，它的舍入误差被限定：，其中在|f|中是上限和是指数系数，假定在f上所有的变量都由B0限定上限B,我们可以制定一个f操作树并找到Bf和kf：如果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上的欧几里德距离。因为，我们必须有。然而。近似测试不能准确评估。因此部分有B来限定，我们能够设置公差避免漏报。4.3顶点/边CCD误差我们首先研究的误差是关于顶点/线的距离。为了简化分析，我们通过删除在Xa和Xb的组件来修改，如果小于。结果为。因为是小的。的最小值接近的最小值。在算法2中，有四个关于的例子。我们设置公差阈值，来避免由于舍入误差产生的故障。为了更进一步减少错报，我们介绍了边长测试。我们的目的是为了确保如果长度测试和重心测试都产生了真正的碰撞故障，顶点/顶点CCD必须能够检测到。边长测试这个测试可以避免当边长小于（）的时候产生大的错报。其中在时间上被计算为欧几里德