高等向量数学

平面

单位向量的点积还有一个有趣的性质。请想象一个垂直于这个向量（且经过原点）的平面。平面会将整个空间划分为正（在平面上方）和负（在平面下方）两部分，并且（与普遍的看法相反）你也可以在 2D 中进行这样的数学运算：

../../_images/tutovec10.png

垂直于表面的单位向量称为单位法向量（因此描述的是表面的朝向），不过通常会简称为法线。平面、3D 几何体等场合中都会用到法线（用来确定面或顶点的属于哪一侧）。法线是一种单位向量，因为用途才被称为法线。（就像我们说坐标 (0,0) 是“原点”一样！）。

平面经过原点，它的表面垂直于这条单位向量（即法线）。这条向量指向的一侧为正半空间，而另一侧则为负半空间。以上概念在 3D 中依旧适用，只不过平面不再是直线，而是一个无限的表面（想象一张固定在原点，无限伸展的平坦纸张）。

到平面的距离

现在平面是什么就很清楚了，让我们再回到点积上。单位向量和任何空间点之间的点积（是的，这次我们在向量和位置之间进行点乘），将返回从该点到平面的距离：

GDScriptC#

  1. var distance = normal.dot(point)
  1. var distance = normal.Dot(point);

但返回的不止是距离的绝对值，如果点位于负半空间，那么这个距离也是负的：

../../_images/tutovec11.png

这样我们就能够知道点位于平面的哪一侧。

脱离原点

我知道你在想什么！到目前为止还算不错，但真正的平面在空间中无处不在，并不一定要经过原点。你想要的是真正平面，你现在就想行动起来。

请记住，平面不仅仅是将空间一分为二，这两个空间还有极性。也就是说，如果两个平面完全重合，它们的正负半空间可以相反。

明确了这一点，我们就可以将完整的平面描述为法线 N 和与原点的距离标量 D。这样用 N 和 D 就可以表示我们的平面了。例如：

../../_images/tutovec12.png

对于 3D 空间中的平面，Godot 提供了 Plane 内置类型来处理这些计算。

Basically, N and D can represent any plane in space, be it for 2D or 3D (depending on the amount of dimensions of N) and the math is the same for both. It’s the same as before, but D is the distance from the origin to the plane, travelling in N direction. As an example, imagine you want to reach a point in the plane, you will just do:

GDScriptC#

  1. var point_in_plane = N*D
  1. var pointInPlane = N * D;

This will stretch (resize) the normal vector and make it touch the plane. This math might seem confusing, but it’s actually much simpler than it seems. If we want to tell, again, the distance from the point to the plane, we do the same but adjusting for distance:

GDScriptC#

  1. var distance = N.dot(point) - D
  1. var distance = N.Dot(point) - D;

也可以用内置函数执行同样的计算：

GDScriptC#

  1. var distance = plane.distance_to(point)
  1. var distance = plane.DistanceTo(point);

这同样会返回一个正或负的距离。

Flipping the polarity of the plane can be done by negating both N and D. This will result in a plane in the same position, but with inverted negative and positive half spaces:

GDScriptC#

  1. N = -N
  2. D = -D
  1. N = -N;
  2. D = -D;

在Godot中，同样也可以使用 Plane 中实现这个操作，示范如下：

GDScriptC#

  1. var inverted_plane = -plane
  1. var invertedPlane = -plane;

因此，谨记，向量数学当中，平面的主要用途就是计算某个点到它的距离。那么，什么时候计算点到平面的距离有用呢？下文将提供应用实例。

在二维空间中构造平面

平面不会凭空出现，必须先进行构造。在 2D 空间中构造平面很简单：只需要法线（单位向量）和某一个点，或者空间中任意两点都可以完成。

在法线和点的情况下，由于法线已经被计算出来，大部分计算工作都已完成。因此，只需根据法线和点的点积计算 D 即可。

GDScriptC#

  1. var N = normal
  2. var D = normal.dot(point)
  1. var N = normal;
  2. var D = normal.Dot(point);

而在空间中任意两点的情况下，空间内会有两个平面同时经过两点：这两个平面共享同一个空间，但其法线方向相反。因此，为计算这两点的法线，必须先获得方向向量，然后将其向两侧旋转 90° ：

GDScriptC#

  1. # Calculate vector from `a` to `b`.
  2. var dvec = point_a.direction_to(point_b)
  3. # Rotate 90 degrees.
  4. var normal = Vector2(dvec.y, -dvec.x)
  5. # Alternatively (depending the desired side of the normal):
  6. # var normal = Vector2(-dvec.y, dvec.x)
  1. // Calculate vector from `a` to `b`.
  2. var dvec = pointA.DirectionTo(pointB);
  3. // Rotate 90 degrees.
  4. var normal = new Vector2(dvec.Y, -dvec.X);
  5. // Alternatively (depending the desired side of the normal):
  6. // var normal = new Vector2(-dvec.Y, dvec.X);

剩余步骤与前例相同。point_a 和 point_b 都可以用于计算，毕竟两者位于同一个平面内：

GDScriptC#

  1. var N = normal
  2. var D = normal.dot(point_a)
  3. # this works the same
  4. # var D = normal.dot(point_b)
  1. var N = normal;
  2. var D = normal.Dot(pointA);
  3. // this works the same
  4. // var D = normal.Dot(pointB);

在 3D 空间中构造平面更加复杂，下文会进一步解释。

平面的一些示例

该示例将介绍平面的用途。假设有一个 凸 多边形。比如矩形、梯形、三角形或任何没有面向内弯曲的多边形。

对多边形的每一段，我们通过计算获取经过该段的平面。重复以上操作，直到获得多边形的平面列表后，我们就可以基于该列表，做些简单的事情，例如检查某点是否处于多边形内部。

我们遍历所有平面，如果能找到一个到点的距离为正的平面，那么该点就在多边形外；反之，该点就在多边形内。

../../_images/tutovec13.png

上述思路的代码实现如下：

GDScriptC#

  1. var inside = true
  2. for p in planes:
  3.     # check if distance to plane is positive
  4.     if (p.distance_to(point) > 0):
  5.         inside = false
  6.         break # with one that fails, it's enough
  1. var inside = true;
  2. foreach (var p in planes)
  3. {
  4.     // check if distance to plane is positive
  5.     if (p.DistanceTo(point) > 0)
  6.     {
  7.         inside = false;
  8.         break; // with one that fails, it's enough
  9.     }
  10. }

很酷吧？不过它还能做到更多！只要再花点心思，类似的逻辑也能让我们知道两个凸多边形是否重叠。这就是所谓的分离轴定理 ( Separating Axis Theorem, SAT )，多数物理引擎基于该定理检测碰撞。

对于点的检测，只需检查平面是否返回正距离，就足以判断该点是否在外部。而对于多边形之间的检测，我们必须找到一个平面，使得另一个多边形上的所有点到该平面的距离都为正。在代码实现方面，可以先用多边形 A 的平面对多边形 B 的点进行检查，再用多边形 B 的平面对多边形 A 的点进行检查：

../../_images/tutovec14.png

上述思路的代码实现如下：

GDScriptC#

  1. var overlapping = true
  3. for p in planes_of_A:
  4.     var all_out = true
  5.     for v in points_of_B:
  6.         if (p.distance_to(v) < 0):
  7.             all_out = false
  8.             break
  10.     if (all_out):
  11.         # a separating plane was found
  12.         # do not continue testing
  13.         overlapping = false
  14.         break
  16. if (overlapping):
  17.     # only do this check if no separating plane
  18.     # was found in planes of A
  19.     for p in planes_of_B:
  20.         var all_out = true
  21.         for v in points_of_A:
  22.             if (p.distance_to(v) < 0):
  23.                 all_out = false
  24.                 break
  26.         if (all_out):
  27.             overlapping = false
  28.             break
  30. if (overlapping):
  31.     print("Polygons Collided!")
  1. var overlapping = true;
  3. foreach (Plane plane in planesOfA)
  4. {
  5.     var allOut = true;
  6.     foreach (Vector3 point in pointsOfB)
  7.     {
  8.         if (plane.DistanceTo(point) < 0)
  9.         {
  10.             allOut = false;
  11.             break;
  12.         }
  13.     }
  15.     if (allOut)
  16.     {
  17.         // a separating plane was found
  18.         // do not continue testing
  19.         overlapping = false;
  20.         break;
  21.     }
  22. }
  24. if (overlapping)
  25. {
  26.     // only do this check if no separating plane
  27.     // was found in planes of A
  28.     foreach (Plane plane in planesOfB)
  29.     {
  30.         var allOut = true;
  31.         foreach (Vector3 point in pointsOfA)
  32.         {
  33.             if (plane.DistanceTo(point) < 0)
  34.             {
  35.                 allOut = false;
  36.                 break;
  37.             }
  38.         }
  40.         if (allOut)
  41.         {
  42.             overlapping = false;
  43.             break;
  44.         }
  45.     }
  46. }
  48. if (overlapping)
  49. {
  50.     GD.Print("Polygons Collided!");
  51. }

As you can see, planes are quite useful, and this is the tip of the iceberg. You might be wondering what happens with non convex polygons. This is usually just handled by splitting the concave polygon into smaller convex polygons, or using a technique such as BSP (which is not used much nowadays).

三维环境下的碰撞检测

这是本章的另一个奖励内容，是对你耐心看完这本长篇教程的奖励：以下内容是又一个前人的智慧结晶，虽然它不算是个直接能拿来用的实例（ Godot 的碰撞检测功能已经足够好了），但是接下来的内容是几乎所有物理引擎和碰撞检测库都在使用的一个原理 : )

还记得把 2D 中的凸形转换成 2D 平面阵列可用于碰撞检测吗？你可以检测一个点是否在任何凸面形内，或两个 2D 凸面形是否重叠。

其实，这在 3D 中也同样适用：如果两个 3D 多面体相撞，你将无法找到这两个多面体的分离平面。反之，如果能找到分离平面，那么这两个图形肯定不会发生碰撞。

To refresh a bit a separating plane means that all vertices of polygon A are in one side of the plane, and all vertices of polygon B are in the other side. This plane is always one of the face-planes of either polygon A or polygon B.

不过，在 3D 空间中，这种思路存在一个问题：某些情况下可能找不到分离平面。下文就是这种情况的一个示例：

../../_images/tutovec22.png

为了避免这种情况，一些额外的平面需要作为分隔器被测试，这些平面是多边形 A 的边和多边形 B 的边的叉积

../../_images/tutovec23.png

所以，最后的算法代码差不多像这样：

GDScriptC#

  1. var overlapping = true
  3. for p in planes_of_A:
  4.     var all_out = true
  5.     for v in points_of_B:
  6.         if (p.distance_to(v) < 0):
  7.             all_out = false
  8.             break
  10.     if (all_out):
  11.         # a separating plane was found
  12.         # do not continue testing
  13.         overlapping = false
  14.         break
  16. if (overlapping):
  17.     # only do this check if no separating plane
  18.     # was found in planes of A
  19.     for p in planes_of_B:
  20.         var all_out = true
  21.         for v in points_of_A:
  22.             if (p.distance_to(v) < 0):
  23.                 all_out = false
  24.                 break
  26.         if (all_out):
  27.             overlapping = false
  28.             break
  30. if (overlapping):
  31.     for ea in edges_of_A:
  32.         for eb in edges_of_B:
  33.             var n = ea.cross(eb)
  34.             if (n.length() == 0):
  35.                 continue
  37.             var max_A = -1e20 # tiny number
  38.             var min_A = 1e20 # huge number
  40.             # we are using the dot product directly
  41.             # so we can map a maximum and minimum range
  42.             # for each polygon, then check if they
  43.             # overlap.
  45.             for v in points_of_A:
  46.                 var d = n.dot(v)
  47.                 max_A = max(max_A, d)
  48.                 min_A = min(min_A, d)
  50.             var max_B = -1e20 # tiny number
  51.             var min_B = 1e20 # huge number
  53.             for v in points_of_B:
  54.                 var d = n.dot(v)
  55.                 max_B = max(max_B, d)
  56.                 min_B = min(min_B, d)
  58.             if (min_A > max_B or min_B > max_A):
  59.                 # not overlapping!
  60.                 overlapping = false
  61.                 break
  63.         if (not overlapping):
  64.             break
  66. if (overlapping):
  67.    print("Polygons collided!")
  1. var overlapping = true;
  3. foreach (Plane plane in planesOfA)
  4. {
  5.     var allOut = true;
  6.     foreach (Vector3 point in pointsOfB)
  7.     {
  8.         if (plane.DistanceTo(point) < 0)
  9.         {
  10.             allOut = false;
  11.             break;
  12.         }
  13.     }
  15.     if (allOut)
  16.     {
  17.         // a separating plane was found
  18.         // do not continue testing
  19.         overlapping = false;
  20.         break;
  21.     }
  22. }
  24. if (overlapping)
  25. {
  26.     // only do this check if no separating plane
  27.     // was found in planes of A
  28.     foreach (Plane plane in planesOfB)
  29.     {
  30.         var allOut = true;
  31.         foreach (Vector3 point in pointsOfA)
  32.         {
  33.             if (plane.DistanceTo(point) < 0)
  34.             {
  35.                 allOut = false;
  36.                 break;
  37.             }
  38.         }
  40.         if (allOut)
  41.         {
  42.             overlapping = false;
  43.             break;
  44.         }
  45.     }
  46. }
  48. if (overlapping)
  49. {
  50.     foreach (Vector3 edgeA in edgesOfA)
  51.     {
  52.         foreach (Vector3 edgeB in edgesOfB)
  53.         {
  54.             var normal = edgeA.Cross(edgeB);
  55.             if (normal.Length() == 0)
  56.             {
  57.                 continue;
  58.             }
  60.             var maxA = float.MinValue; // tiny number
  61.             var minA = float.MaxValue; // huge number
  63.             // we are using the dot product directly
  64.             // so we can map a maximum and minimum range
  65.             // for each polygon, then check if they
  66.             // overlap.
  68.             foreach (Vector3 point in pointsOfA)
  69.             {
  70.                 var distance = normal.Dot(point);
  71.                 maxA = Mathf.Max(maxA, distance);
  72.                 minA = Mathf.Min(minA, distance);
  73.             }
  75.             var maxB = float.MinValue; // tiny number
  76.             var minB = float.MaxValue; // huge number
  78.             foreach (Vector3 point in pointsOfB)
  79.             {
  80.                 var distance = normal.Dot(point);
  81.                 maxB = Mathf.Max(maxB, distance);
  82.                 minB = Mathf.Min(minB, distance);
  83.             }
  85.             if (minA > maxB || minB > maxA)
  86.             {
  87.                 // not overlapping!
  88.                 overlapping = false;
  89.                 break;
  90.             }
  91.         }
  93.         if (!overlapping)
  94.         {
  95.             break;
  96.         }
  98.     }
  99. }
  101. if (overlapping)
  102. {
  103.     GD.Print("Polygons Collided!");
  104. }

更多信息

有关在 Godot 中使用向量数学的更多信息，请参阅以下文章：

如果你需要进一步的解释，你可以看看 3Blue1Brown 的绝佳的系列视频《线性代数的本质》：http://www.bilibili.com/video/BV1ys411472E?p=2