Box2d源码学习<十四>TOI之碰撞时间的实现
//CCD（continuous collision detection，持续碰撞检验）经过局部的分离轴方法。//这种寻求进展通过计算最大的时间保持分离。void b2TimeOfImpact(b2TOIOutput* output, const b2TOIInput* input){//调用次数自加++b2_toiCalls;//赋值outputoutput->state = b2TOIOutput::e_unknown;output->t = input->tMax;//获取距离代理const b2DistanceProxy* proxyA = &input->proxyA;const b2DistanceProxy* proxyB = &input->proxyB;//获取扫频b2Sweep sweepA = input->sweepA;b2Sweep sweepB = input->sweepB;// 大型旋转可以使根检索器失效，所以我们标准化扫频角度sweepA.Normalize();sweepB.Normalize();//获取扫频间隔float32 tMax = input->tMax;//获取两个形状半径之和float32 totalRadius = proxyA->m_radius + proxyB->m_radius;float32 target = b2Max(b2_linearSlop, totalRadius - 3.0f * b2_linearSlop);//允许误差float32 tolerance = 0.25f * b2_linearSlop;//验证有效值b2Assert(target > tolerance);float32 t1 = 0.0f;//最大迭代次数const int32 k_maxIterations = 20;// TODO_ERIN b2Settings//int32 iter = 0;// 初始化距离输入参数b2SimplexCache cache;cache.count = 0;b2DistanceInput distanceInput;distanceInput.proxyA = input->proxyA;distanceInput.proxyB = input->proxyB;distanceInput.useRadii = false;// 外面的循环逐步尝试计算新的分离轴// 当一个轴是重复的(没有进展)，这个循环终止for(;;){b2Transform xfA, xfB;sweepA.GetTransform(&xfA, t1);sweepB.GetTransform(&xfB, t1);// 获取形状之间的距离。我们也可以使用这个结果去获得一个分离轴distanceInput.transformA = xfA;distanceInput.transformB = xfB;b2DistanceOutput distanceOutput;b2Distance(&distanceOutput, &cache, &distanceInput);// 如果形状重叠，我们放弃连续碰撞if (distanceOutput.distance <= 0.0f){//失败！output->state = b2TOIOutput::e_overlapped;output->t = 0.0f;break;}if (distanceOutput.distance < target + tolerance){//胜利！output->state = b2TOIOutput::e_touching;output->t = t1;break;}// 初始化分离轴b2SeparationFunction fcn;fcn.Initialize(&cache, proxyA, sweepA, proxyB, sweepB, t1);#if 0// Dump the curve seen by the root finder{const int32 N = 100;float32 dx = 1.0f / N;float32 xs[N+1];float32 fs[N+1];float32 x = 0.0f;for (int32 i = 0; i <= N; ++i){sweepA.GetTransform(&xfA, x);sweepB.GetTransform(&xfB, x);float32 f = fcn.Evaluate(xfA, xfB) - target;printf("%g %g\n", x, f);xs[i] = x;fs[i] = f;x += dx;}}#endif//在分离轴上计算TOI（碰撞时间），我们先后解决最深处的点。这个循环是以顶点数为终止条件的bool done = false;float32 t2 = tMax;int32 pushBackIter = 0;for (;;){// 在t2上查找最深点，存储见证点索引int32 indexA, indexB;float32 s2 = fcn.FindMinSeparation(&indexA, &indexB, t2);// 是否是最终的外形分离if (s2 > target + tolerance){//胜利！output->state = b2TOIOutput::e_separated;output->t = tMax;done = true;break;}//分离值是否达到误差值if (s2 > target - tolerance){// 推进扫描t1 = t2;break;}// 使用见证点计算最初的间距float32 s1 = fcn.Evaluate(indexA, indexB, t1);// 检验最初重叠。有可能发生根检索器超出了迭代总的次数的现象。if (s1 < target - tolerance){output->state = b2TOIOutput::e_failed;output->t = t1;done = true;break;}// 检查触碰if (s1 <= target + tolerance){// 胜利！t1必须保留TOI(只有可能是0)output->state = b2TOIOutput::e_touching;output->t = t1;done = true;break;}//计算1D root ： f(x) - target = 0int32 rootIterCount = 0;float32 a1 = t1, a2 = t2;for (;;){// 混合使用割线规则和二分法float32 t;if (rootIterCount & 1){// 割线规则来提高收敛t = a1 + (target - s1) * (a2 - a1) / (s2 - s1);}else{// 二分法保证进度t = 0.5f * (a1 + a2);}float32 s = fcn.Evaluate(indexA, indexB, t);if (b2Abs(s - target) < tolerance){// 赋值t2 = t;break;}// 确保我们查找根if (s > target){a1 = t;s1 = s;}else{a2 = t;s2 = s;}//根迭代器++rootIterCount;++b2_toiRootIters;// 循环到达50次后，退出if (rootIterCount == 50){break;}}b2_toiMaxRootIters = b2Max(b2_toiMaxRootIters, rootIterCount);//记录顶点迭代器++pushBackIter;//达到顶点的最大次数，退出if (pushBackIter == b2_maxPolygonVertices){break;}}//根迭代器++iter;//toi的迭代次数自增++b2_toiIters;if (done){break;}if (iter == k_maxIterations){//没有找到根output->state = b2TOIOutput::e_failed;output->t = t1;break;}}//获取toi最大迭代器b2_toiMaxIters = b2Max(b2_toiMaxIters, iter);}关于b2TimeOfImpact函数，主要以3重for循环为主线的，第一层for循环主要是逐步尝试计算新的分离轴，并当出现一个轴是重复的时，终止循环。第二层for循环主要是在分离轴上计算TOI（碰撞时间），我们先后解决最深处的点。这个循环是以顶点数为终止条件的。第三层for循环主要使用割线规则和二分法进行求解在t时间内，两物体碰撞的具体的时间值。这个循环是以找到在误差允许的范围内的时间值或者循环50次为终止条件的。
另外想说一下，在这里我们每个循环的写法是for(;;)这样的，个人感觉不太雅致，也不能看一眼而不用思索的就知道是死循环的写法，如改成while(true)或者while(1)更好。
关于两物体间是否碰撞了？在Box2d中目前我们至少知道3种可以判断的方法，它们分别是：
a)、通过两物体的aabb，判断是否重叠。b)、通过GJK算法算出两物体间的距离，根据距离判断是否碰撞c)、通过SAT分离轴算法看是否能找出两物体间的分离轴，如果找得出就没有碰撞，找不出则碰撞。
Ok，碰撞部分终于学完了，下面我们将继续学习动力学部分。不早了，各位早安。。。
ps：
以上文章仅是一家之言，若有不妥、错误之处，请大家多多指出。同时也希望能与大家多多交流，共同进步。