凸体碰撞时间的计算法则

对于凸体，碰撞时间的计算仍然是一个迭代的过程。在连续迭代中最近点间移动的距离是单调变化的，因此有一个简化的方法。这是很重要的，因为当几何搜索算法沿着物体的边界表达移动并试图找到在迭代ti＋1时的最近点时，它会舍弃所有与它当前值相比增加的搜索方向，这个当前值是在迭代ti时获得的最近距离。从ti时刻的最近点信息开始，几何搜索能快速收敛到凸体在ti＋1时刻的最近点。因此，当物体还没相交时跟踪凸体间的最近点对于仿真引擎来说是可行的，而不是像非凸体中要求的那样，必须计算每块相交区域的最深贯穿点并将它们作为碰撞点的近似。

在凸体中另一个可能的重要优化就是用保守时间推进算法代替二分法。保守时间推进算法让我们估计能从ti时刻移动的时间总量Δt的一个下界，这个下界保证物体在tm=ti＋Δt时刻不会相交，而不是将每次迭代的时间间隔对分并检测物体在中间点是否相交（碰撞）。幸运的是，保守时间推进算法收敛到碰撞时间所进行的迭代次数要比使用二分法的迭代次数少得多。事实上，所有用保守时间推进算法计算的中间时刻tm值总是处于不相交（不碰撞）状态，因此用tm值更新凸体间的最近点信息。

保守时间推进算法背后的主要原理就是，假设凸体在时间间隔内恒平移和转动，总能计算凸体上的任意一点沿着向量n的方向移动的最大距离的上界。仿真引擎使用保守时间推进算法来计算每个凸体上任意一点沿着它们的最近方向，在时间间隔［ti，ti＋1］内移动的最大距离的上界。这些上界与凸体在ti时刻的最近距离一起，用来估计碰撞时间的下界。这个下界是保守的，即对于任意给定的一个时刻tm（ti＜tm＜ti＋1），可以确保物体在tm时刻很近但是还没有相交。

从间隔［ti，ti＋1］开始，仿真引擎按照下列步骤确定两个凸体间的碰撞时间。

（1）计算t0时刻凸体间的最近点并用它们的距离对最近距离值进行初始化。用来计算凸体间最近点的高效几何搜索算法在第6章中详细介绍。

（2）采用保守时间推进算法计算对应于一个自由状态的中间时刻tm，并计算tm时刻处的最近点信息。第6章介绍的高效几何搜索算法采用ti时刻的最近点信息作为搜索tm时刻的最近点的起始点。ti和tm时刻之间运动的时间连贯性增加了tm时刻的最近点拓扑地在ti时刻的最近点附近的可能性。最近距离的单调性让高效几何搜索算法只关注最近距离值减小的方向。(www.xing528.com)

（3）这时，时间间隔已经减小到［tm，t1］，并且最近点信息得到更新。有3种要考虑的终止条件，如果下列条件都不满足，算法将继续下一次迭代。

①最近点间的距离比用户定义的阈值小。

②当前时间间隔的大小比用户定义的阈值小。

③执行的迭代次数比用户定义的阈值大。

最后，仿真引擎已经把当前时间间隔缩小到［tc，t1］，其中tc为碰撞时间。