游戏开发的数学和物理——3.3　细长形物体与圆形物体间的碰撞检测 【点与线段的距离、内积、微分】

接下来让我们一起学习圆形与细长形物体的碰撞检测。在游戏中，细长形物体可以被用于显示激光或剑等。 本小节将讲解圆形与细长形物体（如激光或剑）的碰撞检测。比如从某个斜方向发射激光等时，如果仍然使用2D碰撞检测中的常规手段，将光线作为长方形物体处理的话，就会非常麻烦，所以需要对细长形物体做特殊处理。 下面就来一起看一下细长形物体与圆形物体间的碰撞检测吧。请参考示例程序CheckHit_3_1.cpp。程序中重要的部分是CheckHit函数的内容，如代码清单3-3-1 所示。 代码清单3-3-1　执行细长形物体与圆形物体碰撞检测的CheckHit 函数（CheckHit_3_1.cpp 片段） 043 int CheckHit( F_CIRCLE *pcrCircle, F_RECT_CIRCLE *prcRectCircle ) // 碰撞检测 044 { 045 int nResult = false; 046 float dx, dy; // 位置坐标之差 047 float t; 048 float mx, my; // 对应最短距离的坐标 049 float ar; // 两物体的半径之和 050 051 float fDistSqr; 052 053 dx = pcrCircle->x - prcRectCircle->x; // ⊿x 054 dy = pcrCircle->y - prcRectCircle->y; // ⊿y 055 t = ( prcRectCircle->vx * dx + prcRectCircle->vy * dy ) / 056 ( prcRectCircle->vx * prcRectCircle->vx + prcRectCircle->vy * prcRectCircle->vy ); 057 if ( t < 0.0f ) t = 0.0f; // t的下限 058 if ( t > 1.0f ) t = 1.0f; // t的上限 059 mx = prcRectCircle->vx * t + prcRectCircle->x; // 有最短距离的线段上的坐标 060 my = prcRectCircle->vy * t + prcRectCircle->y; 061 fDistSqr = ( mx - pcrCircle->x ) * ( mx - pcrCircle->x ) + 062 ( my - pcrCircle->y ) * ( my - pcrCircle->y ); // 距离的平方 063 ar = pcrCircle->r + prcRectCircle->r; 064 if ( fDistSqr < ar * ar ) { // 直接使用平方比较 065 nResult = true; 066 } 067 068 return nResult; 069 } 函数接收两个参数，一个是代表圆的F_CIRCLE结构体指针，另一个是代表由一个长方形和两端的两个半圆形组成的细长形物体的F_RECT_CIRCLE结构体指针。当两者碰撞时，返回值为true。F_CIRCLE结构体通过圆心坐标与半径来表示一个圆，F_RECT_CIRCLE结构体则通过一个点以及一个向量来表示一个线段，同时该结构体还包含到此线段的有效距离，最终就可以表示一个倾斜的长方形两端附加半圆形的细长图形（参考图3-3-2）。为了检测这两个图形是否碰撞，首先需要计算F_CIRCLE结构体的圆心坐标到F_RECT_CIRCLE 结构体中的线段的最短距离；然后再计算“F_CIRCLE 结构体的圆半径+到F_RECT_CIRCLE结构体中的线段的有效距离”，如果最短距离小于后者，则可认为两者碰撞。 用语言表达可能会比较难理解，这里我们重新用数学算式来表达，设圆心与线段的最短距离为lmin，圆的半径为r1，到线段的有效距离为r2（参考图3-3-3），当满足时，两物体碰撞。 这里面的问题是，点与线段的最短距离lmin要如何计算。如果将点与线段的距离更改为点与直线的距离，则可以利用下面这个有名的公式。 直线ax+by+c=0与点(x0, y0)的最短距离为 a b ax by c 2 2 0 0 + + + 但是目前我们想要计算的，并不是点到一条无限延长的直线的距离，而是点到一条有起点和终点的线段的距离，因此无法直接套用上面的公式。当然如果肯花时间，也可以使用上面的公式得到一个可行的算法，但是我们不打算这样做。这是因为公式中直线是使用ax+by+c=0的形式来表示的，而在程序中，为了适应更多的场景，直线往往都使用向量的形式来表示，即用向量a、b将直线上的位置向量p表示为 p=at+b 这样就可以适用于更多的场景。如果想从事游戏开发，就应该学会用向量这种形式来表示直线。 游戏编程中经常使用向量来表示直线。 可能有人已经注意到了，传给CheckHit 函数的参数F_RECT_CIRCLE结构体，正是使用向量形式表示的线段。其中位置向量b表示直线所通过的一点的位置，向量a表示直线延伸的方向（参考图3-3-4)。 但是上面的式子只能表示一条无限延伸的直线，因此我们认为CheckHit函数中还隐含了条件0GtG1。即结构体最终表示的是以位置向量b与位置向量b+a为两端的线段。此时该线段与点(x0, y0)的最短距离应该如何计算呢？可以从以下两点考虑。 1. 将线段上的点p=at+b (0GtG1) 与点(x0, y0) 的距离表示为t 的函数，然后对t 进行微分，求得距离最小时的t。 2. 过点(x0, y0) 向包含线段的直线p=at+b做一条垂线，使用向量的内积求得距离的最小值t。 下面首先介绍方法1。此时令线段上的点p为 (px, py)，向量a为(ax, ay)，向量b为(bx, by)， p=at+b (0GtG1)可以分解表示为 p at b p at b x x x 0 t 1 y y y = + G G = + ) ] g 设此线段上的点与点(x0, y0)的距离为l，根据勾股定理有 l p x p y a t b x a t b y a t a b x t x a t a b y t y a a t a b x a b y t x y 2 2 2 x y x x y y x x x y y y x y x x y y 2 0 2 0 2 0 2 0 2 2 2 0 0 2 2 2 0 0 2 2 2 2 0 0 0 2 0 2 = - + - = + - + + - = + - + + + - + = + + - + - + + ] ] ] ] ] ] ] ] ] g g g g g g g " g g, 根据我们之前得到的结论，可知当l1H0 且l2H0 时，如果l1 2Hl2 2 则必有l1Hl2。而这里的距离l 必定是大于0 的，所以如果l1 2Hl2 2 则必有l1Hl2 这个结论成立。换言之，求距离平方最小值 对应的t，等同于求距离最小值所对应的t。因此上式 l ax ay t 2 ax bx x ay by y t x y 2 2 2 2 0 0 0 2 0 =] + g + " ] - g+ ] - g, + + 2 中，令l 2 最小的t，就是点到线段的最短距离所对应的t。为了求l 2 的最小值，将等式用t 进行微分， 得到 d d t l 2 ax ay t 2 ax bx x ay by y 2 2 2 = + + - 0 + - 0 ] g ] g " ] g ] g, 要求使d d t ]l2g 为零的t 的值，需要让l 2 取极值（极大值或极小值），在上式中应该为极小值。 因为对l 2 进行t的2 阶微分（即对上式再进行一次微分）, 可得 d d t l 2 2 ax ay 0 2 2 = 2+ 2 2 ] g ] g 　（不过向量a并不是零向量） 等式必然为正，因此函数的2 阶微分为正时所取的极值为极小值。 综上，通过d d t ]l2g 为零的t 的值，我们就可以计算出线段与点的最短距离。下面让我们通过 如下步骤求得t。 d d t l a a t a b x a b y a a t a b x a b y t a a a x b a y b 2 2 0 2 2 x y x x y y x y x x y y x y x x y y 2 2 2 0 0 2 2 0 0 2 2 0 0 ` = + + - + - = + =- - + - = + - + - ] ] ] ] ] ] ] ] ] ] g g g g g g g g g g " " , , 这就是CheckHit函数中 053 dx = pcrCircle->x - prcRectCircle->x; // ⊿ x 054 dy = pcrCircle->y - prcRectCircle->y; // ⊿ y 055 t = ( prcRectCircle->vx * dx + prcRectCircle->vy * dy ) / 056 ( prcRectCircle->vx * prcRectCircle->vx + prcRectCircle->vy * prcRectCircle->vy ); 这部分等式的由来。请注意程序中的变量与数学等式的对应关系为 prcRectCircle vx prcRectCircle v dy dx y a a x b y b > > x y x y 0 0 = - = - - - = ] = ] g g 但是这样计算出的t并不一定满足线段的条件0GtG1。因此在CheckHit函数中，如果t没有在0 到1 的区间内，会通过下面的方式将t收敛在0～1 的范围内。 057 if ( t < 0.0f ) t = 0.0f; // t的下限 058 if ( t > 1.0f ) t = 1.0f; // t的上限 即当t比0 小时令t 等于0，当t比1 大时令t 等于1。这也说明了求线段与点的最短距离t时， l 2是t的二次函数，其极小值只有一个。 ●使用求得的t计算线段与点的最短距离 到目前为止，求得的还不是线段与点的最短距离，而是可以令线段与点有最短距离的t。 CheckHit函数会继续使用t 计算线段与点的最短距离（确切说是最短距离的平方）。为此首先需 要通过以下方法求得有最短距离的线段上的坐标。 059 mx = prcRectCircle->vx * t + prcRectCircle->x; // 有最短距离的线段上的坐标 060 my = prcRectCircle->vy * t + prcRectCircle->y; 这是将t代入线段的等式 p at b p at b x x x 0 t 1 y y y = + G G = + ) ] g 得到的。接下来使用勾股定理，通过如下方法求得最短距离的平方。 061 fDistSqr = ( mx - pcrCircle->x ) * ( mx - pcrCircle->x ) + 062 ( my - pcrCircle->y ) * ( my - pcrCircle->y ); // 距离的平方 将所得最短距离的平方（即变量fDistSqr 的值），与“F_CIRCLE结构体的圆半径+到F_RECT_CIRCLE结构体中的线段的有效距离”的平方相比较，如果前者小于后者，则认为细长形物体与圆碰撞。这在程序中体现为以下的if 语句，如果碰撞则将表示结果的变量nResult 置为true。 063 ar = pcrCircle->r + prcRectCircle->r; 064 if ( fDistSqr < ar * ar ) { // 直接使用平方比较 065 nResult = true; 066 } 而由于变量nResult 在声明时已经设默认值为false，如果上面的if 语句不满足，则变量nResult 仍返回false。最终当碰撞时nResult 为true，未碰撞时nResult 为false，并通过以下语句作为函数的返回值返回。 068 return nResult; 本节我们介绍了两端为圆形的细长形物体的碰撞检测，之所以选择这样一个有点奇怪的图形，而不使用倾斜的长方形，是出于一些考量的。首先，倾斜的长方形与圆形的碰撞检测会有非常多的条件分支，导致程序很长。对于惯用指令流水线（instruction pipeline）和推测执行（speculation execution）的现代CPU来说，过多的分支条件不利于速度的优化。其次，使用 斜长方形作为碰撞检测的区域时，最终呈现的效果可能会有一些不合理的地方（即便从数学的角度来看是正确的）。特别是当另一个图形擦过长方形的四个角时，这种情况会被认为发生了碰撞，而肉眼看上去却是没有碰撞的，这样就在无形中给玩家带来了困扰。因此为了让细长物体的两端更好地符合现实世界的碰撞现象，特意将四角处理为了圆形。 类似本小节这样的复杂图形的碰撞检测判定，基本上很难在大脑中计算整个过程，需要在纸上一步步地演算。而真正的游戏开发，更是不仅要能在纸上完成演算过程，还要能将其代码化，有意成为游戏开发者的读者朋友，请以此为目标努力吧。