持续碰撞检测预防误差

持续碰撞检测预防误差

摘要：

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

关键字：浮点算法、舍入误差、数值误差、持续碰撞检测、二—三次求解器 1 介绍

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

经典的CCD 算法解一个三次方程找到两个参考体共面的时间和用它来检测交点，这个方法是平庸的、没有用的“failure-proof ”如果其播报正面，我们就要同时避免错误和减少错报。不好的是，通过已存的算法来限制故障的产生是困难的。为了解决这个问题，我们的观点是引入一些条件，用顶点/三角形面和边/边测试用来保证错误。在一个时间步内如果顶点/边的距离低于一定的阈值就

播报碰撞。利用有效的大的距离阈值，我们确保任何碰撞事件都可以检测。 然而我们的观点是简单地，它执行需要我们面临两大挑战：怎样进行顶点和边测试。当顶点/边的欧几里德距离等于一个阈值时要计算时间就要解一个二次方程，它的计算简单并且易于产生很多错误。Brochu and Bridson提出了基于体积的算法，该算法不能检测距离且不用计算时间，但是用精确算法来避免舍入误差。第二个挑战就是怎样估计整个测试误差。因为数值误差是由三次求解器产生的、舍入误差是由浮点算法产生的，我们不能直接进行误差分析。

这篇文章中我们的贡献是：1）顶点和边测试与误差有关新的实行方法，其是机器数；2）对于cubic-based 进行系统误差分析3）对于cubic-based 测试错误根进行一系列修改4）我们的算法对于误差公差下限的选定从以下几个方面考虑：

可靠 我们可以无条件的证明基于立方体连续碰撞测试算法的错误根是应用我们的方法后产生的。

简单 我们的修改是简单的并且易于合并到已存在的系统中。

高效 我们的实验显示我们方法的计算成本仅仅是原始测试成本的一部分。

自动 基于误差分析，连续碰撞检测算法能够自动决定所有的公差值，用户不需要特定一个参数。

精确 我们的方法通过当错误产生时来最小化顶点/三角形面或者边边距离来计算公差值。因此他们能够减少错误。

2 预备知识

碰撞检测： 误差、近似退化以及交点测试在之前已被研究了，基于这些测试又提出了离散碰撞检测算法，其只能在离散的时间进行碰撞检测，而且这个算法物体快速移动的时候会遗失碰撞，最经典的是”隧道效应“。解决方法是逐步接近模拟时间直到发生碰撞。还有连续碰撞检测算法，当两个参考体共面时来计算可能的碰撞时间。对于顶点三角形到面和边到边的碰撞，其时间可以通过解三

次方程来获得。Bridson et al. 通过顶点/面、线与线距离以及重心坐标的舍入误差公差来改善这个方法的鲁棒性，然而目前找到最优误差公差是个难题，并且也没有方法来保证检测到每个碰撞事件。为了避免碰撞故障，Brochu and Bridso n 提出了把碰撞检测和碰撞时间查询分开，并得出一个利用精确算法的

root-parity-base d CCD算法。Stam[2009]提出当两个参考体的距离小于一个阈值就播报碰撞，则碰撞测试的鲁棒性就得以改善。这就要求处理顶点/三角形面或者边/边碰撞时，解six-order 多项式方程。

碰撞选择和处理 目前在碰撞选择上的研究产生了许多高效的技术，我们的算法和那些技术都是可以兼容的，一旦发现了碰撞，下一个问题就是怎样解决物体对碰撞的反应。这个方法在复杂的多碰撞事例中比较困难。经典的算法不能解决碰撞后的许多处理步骤，其被作为在影响区的刚体。Thomaszews 建议对于更精确的碰撞响应异步的处理碰撞，他们的方法是依赖于异步碰撞处理来避免残余碰撞。单纯的异步系统保证每一个碰撞处理都在一个有限的时间进行并且碰撞没有穿透。Ainsley et al. [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的外面但是在t0的里面，如图3所示，因为t0是F0ij （t ）的最小值接近于t0,F0ij(t)=S=3R来获得有顶点/顶点连续碰撞检测在时间t 上的碰撞。

3.3 顶点/三角形面碰撞检测

顶点/三角形CCD 算法如算法3所示，我们用顶点到边CCD 之后还要进行cubic-based 测试，来避免遗失碰撞。三次方程的闭合解要求有立方根，在IEEE754标准下是不正确的。相反，数值求解器会找到t ，ˆt0, 其残余误差是低于阈值μ. ，使用这个阈值会遇到两个问题。

小三角形和平行运动。

3.3.1 误差和错报（False Positives）

这里我们不考虑舍入误差只研究全面的误差，我们有两个目的，1）剔除漏报（false negatives）。2）尽可能减少错报（false positives）。

μ是三次求解器的收敛阈值，在顶点到三角形近似测试中的厚度阈值，R 是在顶点到边CCD 中的欧几里德距离阈值。t0是顶点到三角形的相交时间、t^0是计算的得到的。F(t)=A(t)C(t),A(t)是三角形面积的二倍,C(t)是顶点到面的距离。

三角形面积测试：

如图3b 所示。因为形内切圆的最大二次半径为

小于，因此通过设置所以近似测试失败了。如果有三角并且在时间t0上至少一个二次欧几里德距离是我们能得到顶点到边CCD 获得碰撞。另一方面我们有图3c 知，因为A(t)和顶点的投影是两个时间的连续函数，时间t

在，和顶点的投影在三角形内部如图3d 所示，或者和顶点的投影在三角形的边上图3e ，以上分析可以得到任意

们都可以用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 必须能够检测到。

边长测试 这个测试可以避免当边长小于（

在时间上被计算为欧几里德边长。

重心测试 边长测试之后，重心测试也许会失败。通过边长测试得

因为重心的重量不是由点来计算的，其误差由

是由限定并且重心测试误差，或者）的时候

产生大的错报。其中来限定，重心测试所得值等于顶点投影到端点的距离的边长时间，因，我们此重心测试失败，顶点投影到一个端点的距离在时间没有超过

获得有效的条件是：

。

错报

一个错报可能由顶点/边CCD 本身检测出。因为在顶点/顶点CCD 中误差是小的，我们考虑把D 作为一个上限在二次顶点/边距离这两种情况，为了减少错报，我们会找到最优

来最小化D. 暂时忽略S 和简便执行后，我们选择

和我们设

作为顶点/边CCD 一个有效条件。

4.4 顶点/三角形面CCD 误差

顶点/三角形面CCD 算法有四步：1）找到立方等式的根；2）测试三角形的面积；3）确定三角形的高度；4）测试重心坐标。

找根解决等式的第一步。的精确根和的不同有两个原因。第一个原因是误差和系数有关，根据定理4.1

，和

所限定的如图4b 和4c

所示。是由

第二个原因是误差是由立方求解器产生的。附录B 显示了如果

我们的求解器保证对于每个t0都会有的存在，并且对于任意

。

三角形面积测试在这步骤，我们测试三角形面积是否足够大可以计算碰撞时间参数。为了简化误差分析，我们测试，其中是面积阈值。用定理都有

4.1和图4d ，我们知道关于N 的误差由

三角形面积测试失败，在时间上就有

3.3

节分析我们得到限定。如果。从是可以有效获得许多碰撞检测，其中

，另一方面，如果一个顶点和一个三角形通过面积测试，然后

，由定义顶点到面的距离必须由来限定。我们知道如果任意碰撞满足

以获得检测的。根据3.3.1的分析，我们假定顶点/面的距离由限定。

三角形高度测试

当三角形是小的，在重心测试中舍入误差会导致大的错报。因此我们给出一个三角形高度测试来测试他们，而不是发送他们给顶点/边CCD 。在时间我们把高度阈值和三角形的高度进行比较：

因为这个测试发生在面积测试之后，我们必须要

形的高度。所有的高度必须比大，

如果三角形通过三角形高度测试，另一方面，如果一个三角形没有通过高度测试，我们必须确保一个真正的碰撞可以通过顶点/边CCD 测试得到。 当任意三角形的边在时间小于E 则高度测试失败。如果任意边在时间t0上小于E ，我们能简单的利用这个条件：，如果不是，通过定义两个事，其中ij 是三角形的边，。h 是三角，是可和下一个任一件：1）最短边的长度是E2）顶点的投影在三角形边上，我们能够根据3.3.1的两个事件进行分析得到一个有效的条件：意时间，其中是在任顶点到面距离的的上限。而且，没有边在时间上小于E 则高度测试就是失败的。

重心测试 重心测试计算重心的权重和0或者

比较，每个权重包含最多

误差，如图4e 所示。因此每个重心标准的所有误差必须由来限定。如果重心测试确实失败了，则在时间 顶点投影到三角形的外面，根据我们之前在

3.3.1节的分析，R>=r可以有效获得由顶点/边CCD 测试的一些情况。如果重心测试误差失败，在时间顶点的投影应该一直在三角形的里面。有定义，由图5a 知，重心权重分配到X1和是相同的。边的长度是顶点-边-线距离L

的数倍，因为顶点和三角形通过了面积测试和高度测试，我们知道和所有的高度都大于

，给定没有边小于最短距离，得到

，当顶点的投影在三角形的里面，它到边线距离也是他到边的距离。因此况。

4.4.1 错报

研究错报，会得到在时间当错报发生时顶点/三角形距离的一个上限。 近似测试

当错误的通过三个测试，错报就会发生。基于以前的分析，我们知道顶点到面的距离在时间由r 来限定。问题就是顶点的投影和三角形边的距离是多少，由于重心测试错报才发生。有前面我们知道，重心测试的舍入误差是由限定的。

顶点/边测试

如果三个测试都发生假性错误，它通过了顶点/边CCD ，根据4.3，平房距离由来限定。 来是有效的可以获得在时间上由顶点/边CCD 测试的情

总之，我们的目标是最小化：

，其中，尽管最小化是

复杂的，许多关系是没有意义的。简化和近似之后，我们给出用

，

顶点到三角形的距离近似为

，用双倍精度形式，这大约是边长最大值的百分之0.5，假性错误是预测顶点到三角形距离的最槽糕的方法并且它不是准确的。

4.5 边/边CCD 误差

相似与顶点/三角形CCD 、边/边CCD 都要用立方求解器来计算时间上的每个可能碰撞。如果个分析和余下步骤不同。

四边形面积测试

相似与4.4中的三角形面积测试，用

够大。如果测试失败，在时间

则

出的分析，知道

是有效条件，其中，用相同的分析，我们知道来测试是否四边形的面积足，有3.4节给对于任意计算根满足，这

如果两个边通过面积测试，我们必须有

，必须有在顶点/边CCD 上

，我们假定

四边形的高度测试 。如果在任意时间测得。随后在任意时间和线到线的距离由r 来限定。

和4.4的三角形高度测试相似，四边形高度测试为了减少假性错误。对于每个边，我们定义它的四边形高度为：。在测试中我们把每个高度和阈值进行对比：

测试，必须有，相似于三角形高度测试，如果高度h 通过高度，来确保每个碰撞事件的测试，这个测试当真正的碰撞失败我们考虑两个可能性： 在时间任意一边小于E ，这个测试也许会失败，在相交时间t0，任意边小于E ，我们可以简单地利用条件：来获得在时间上的碰撞， 如果高度测试失败，则在时间没有边小于E ，在时间至少一个高度是小于重心测试

相似与顶点/边CCD 重心权重，关于每个权重的误差都有来限定。如，其中是高度测试误差的上限。 果重心测试确实失败了，两个边的投影在时间不相交，如果重心测试误差失败，两个边的投影在时间相交，两个边通过面积测试和高度测试，得到比大和高度比大。给定没有边比更短的边小，在投影的空间上顶点-边-线的距离由4.5.1 假性错误

下面我们研究当假性错误发生，在时间边到边的距离的上限。 来限定。我们用来检测一些碰撞。

近似测试 三个测试都通过了，一个假性错误会发生。在时间线到线的距离由r 来限定。这个问题就是在时间两个投影边的最大距离是多少，什么时候假性错误发生？

顶点/边测试

任意三个测试有假性错误故障，只能通过顶点/边CCD.4.3的分析显示平方距离是由来限定的。总结可得：

有

利用

，边到边的距离近似为

，利用双倍精度形式，其大约是边长最大值的百分之0.5。 ，化简和近似以后，我们提出

5 总结

基于现有的基础立方体CCD 系统，我们在小于一个小时内进行修改。我们也在CCD 测试中进行基本面选择（不包括AABB 选择），这是由Brochu and Bridson

[2012]提出的。不使用离散算法，我们通过引用另一个误差公差来避免舍入误差对基本面选择的影响，随着我们算法的深入，我们提出了对于顶点到边测试的另一种算法，给出已知的碰撞时间, 我们首先测试是否三次函数值的大小在超过，如果在时间t0发生碰撞，就有

。

给定B 作为相对速度的上限，顶点的投影和三角形之间的距离在时间必须有来限定，并且至少一个重心权重是在，换句话说就是没有碰撞会发生，如果权重超过这个范围。因为是小的，这个测试可以

剔除向我们实验所展示的百分之99.9的VE 测试。

我们现在还没有解决的问题是在向量计算中的误差。拿VV CCD举例，目的就是找到

之间的碰撞，但是算法测试的是。因为一些误差是由

撞因为这个发生故障，顶点到三角形的距离在最后必须由来限定的，如果碰来限定。这个问题可能由像许多系统一样在时间末尾做近似测试来解决。公差越大，就更要进行碰撞测试。

另一个问题来自上限B, 每一个时间步都要计算，B0是上限的最初时间步并且B1是上限的下一个时间步。如果B1>B0就会在下一步的开始时间检测到碰撞，在碰撞处理中会产生收敛问题。解决办法是返回到最初的时间步，用B1在最后时间上进行碰撞检测。为了简单，我们重新定义B 并且假定它在整个动画中都是有用的。我们甚至可以分别定义每个顶点/三角形或者边边对的B, 利用它们其余的形态，做这些可以减少B ，并且对长边和短边的采样网格分别进行处理。 特性：

我们对图1和图7的四个衣服动画进行我们算法特性的测试。用一个单核一个2.67GHZ 的Intel Xeon X5650处理器，之后进行AABB 选择，每个基础VT 或者EE CCD的平均计算时间是350ns, 用来我们的修改之后计算时间是355ns ，因此超过基础成本的1.4%。没有基础面的选择，使用我们修改前后的成本分别为409ns 和416ns 。为了更好的理解复杂环境的特性，我们通过对向量位置和一个单元格的速度进行随意采样来构造一个综合实例，我们能详尽测试100亿个例子。我们修改前后每个测试的成本分别为364ns 和369ns 。综合例子和动画例子时间的不同是由于更多正面的情况。由于动画例子显得更逼真的，所以和综合实例的时间不同。和精确的算法相比，我们的测试比碰撞选择后的精准测试还要快20到40倍。这在综合例子中尤其突出，这里有接近一半的例子通过AABB 选择和接近1/3的例子通过基本面选择。我们的实验表明AABB 选择之后精准测试的平均时间是4.962ns, 对比我们的测试是快的甚至没有选择。在实际的动画例子中，由于碰撞选择不同是不显著。仅仅能发现在顶端时间的不同，我们的方法比

精确方法快20%。一旦碰撞选择的成本在整个碰撞处理的成本中占得比较低，我们的方法有效性更加明显。

假性错误（错报）

根据前面的分析，在仿真中错报的点/三角形距离的最大值接近20 。错报对动画例子的影响，我们不能简单的计算大多数的正面例子，错报会让碰撞处理提前并且避免之后正面的产生。要计算所有的测试例子和它们正面结果，我们用我们的方法和精确的方法分别模拟了动画实例。用我们的方法可能检测到百分之十的正面例子。我们的实验表明用两种方法整个例子的数目大约是一样的，用我们的方法能检测出超过10%的更多正面情况。幸运的是，更多的结果还是反面的。那些额外的正面对碰撞检测的特性没有影响。

可靠性：

如果没有用公差误差，碰撞检测的失败可能是基本立方体CCD 测试的问题，甚至当用到公差，如3.3节所示，基于两个退化的例子还是有可能产生失败情况。有趣的是，很少看到衣服动画的故障，图7b 衣服碰撞例子是我们看到的仅有的故障。在这个例子中，基础的CCD 测试会遗失多重碰撞，不久之后，检测到一些突发碰撞和碰撞处理无法收敛，我们不会应用其他技术（像影响区域）来修补，在衣服动画碰撞的故障有两个主要原因，第一个原因是基于物理的模拟通常会遗失小三角形和数值稳定的短边的情况。如果我们假定三角形的面积和边的长度保持恒定，就可以大幅减少边界误差。第二个原因是单个情况的故障不会导致整个碰撞处理过程的失败。目前ill-shaped 三角形和边也许由good-shaped 那个组成的，其正确的测试结果会避免故障的发生。大家会很感兴趣看到在其他情况下

（像毛发动画）是否基础CCD 更可能出现故障。

优势和局限性：

基础CCD 算法很少看到碰撞故障，这个疑问：为什么一定要用我们的算法？这是由于碰撞检测故障的不确定性。不管我们用的公差误差多么大和碰撞检测故障多么大，基础CCD 算法都存在风险，这个风险可以通过增加公差值来减少，但是会产生更多的假性错误，对比我们的算法不仅可以剔除假性错误，还可以用一个自动的方法可以减少假性错误，我们的方法是可靠的并且易于执行。

由于我们在分析中做了简化，误差边界和所建议的公差值不是紧密地联系。然而不用我们的方法连续的修改，它们也不会逐渐的变小。在这篇文章中我们给的情况和修改是有效的，但是不清楚是否那些都是必要的。在我们的分析中我们假设误差是独立的，并且我们得到的边界和条件都在恶劣的情况下，实际上，一些误差都是相互联系的并且它们数值不大。

6 总结和以后的研究方向

本文提出了用cubic-basedCCD 算法可以有效地剔除碰撞检测故障。基于前面的分析可以得到两个结论：1）使用双精度比使用单精度要好，在我们的方法使用单精度浮点算法形式，由假性错误产生的误差可能是边长最大值的一半2）大的时间步不仅会产生在仿真过程中的数值不稳定，而且还会增加错报，使B 向量边界变大。

以后，我们要致力于当机器精度变化时的误差，在浮点型下的扩展。一些计算步骤，像标准的计算比其他方法更重要。我们要分析是否值的用精准的算法来计算他们。最后我们要去研究我们这种算法对GPU 的兼容性和性能，以及进行单精度优化。

致谢

作者想要感谢Nvidia and Adobe对他们的资金和设备支持。