持续碰撞检测预防误差..doc

持续碰撞检测预防误差 摘要： 在持续碰撞检测中由于人为的原因会引入一些数值误差和舍入误差。利用误差公差可以解决这些误差，但是对于用户来说找到最优误差比较困难。大的误差会引起错报现象，小的误差不易被检测出来。我们面临的最大问题就是不知道什么时候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 建议对于更精确的碰撞响