高等向量数学

平面

点乘对于单位向量还有一个有趣的性质.想象垂直于这个向量(通过原点)经过一个平面.平面将整个空间划分为正(在平面上)和负(在平面下),(与普遍的看法相反)您也可以在2D中使用它们的数学:

../../_images/tutovec10.png

垂直于表面的单位向量(因此,它们描述了表面的方向)称为 单位法向量 .不过,它们通常只是缩写为 法线 .法线出现在平面、3D几何中(以确定每个面或顶点的侧边),等等.一个 法线 就是一个 单位向量,但是由于它的使用,它被称为 法线 .(就像我们说坐标(0,0)就是原点一样！).

它就像看起来那样简单.平面经过原点,它的表面垂直于单位向量(或 法线 ).指向向量的一边是正半空间,而另一边是负半空间.在3维空间中,这完全相同,除了平面是一个无限的表面(想象一张无限伸展的平坦纸张,它固定在原点)而不是直线.

到平面的距离

现在,我们很清楚了平面是什么,让我们再回到点乘上. 单位向量 和任何 空间点 之间的点乘(是的,这次我们在向量和位置之间进行点乘),将返回 从点到平面的距离 :

GDScript

C#

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

但不仅仅是绝对距离,如果点在负半空间中,距离也是负的:

../../_images/tutovec11.png

这使我们能够知道点在平面的哪一侧.

远离原点

我知道您在想什么！到目前为止,这还不错,但 真正的 平面在空间中无处不在,而不仅仅是通过原点的平面.您想要真正的 平面 ,您 现在 就想行动起来.

记住,平面不仅把空间分成两半,而且它们还有 极性 .这意味着有可能有完全重叠的平面,但是它们的负半空间和正半空间是相反的.

记住这一点,让我们将整个平面描述为 法线 N 和 距原点的距离 标量 D .因此,我们的平面将由N和D表示,例如:

../../_images/tutovec12.png

对于3维的情况,Godot提供了一个 Plane 内置类型来处理这个问题.

基本上,N和D可以表示空间中的任何平面,无论是对于2D还是3D(取决于变量N的维数),数学上对于两者都是一样的.和以前差不多,但D是原点沿N方向移动到平面的距离.例如,想象一下您想在到达平面上的一个点,您会这样做:

GDScript

C#

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

这将拉伸(调整大小)法线向量并使其接触平面.这个数学可能看起来很疑惑,但实际上比看起来简单得多.如果我们想再说一遍,从点到平面的距离,我们也会这样做,但是要调整距离:

GDScript

C#

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

使用内置函数做同样的事情:

GDScript

C#

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

这将再次返回一个正或负的距离.

翻转平面的极性可以通过同时对N和D取负来完成.这将导致平面处于相同的位置,但是具有反转的负半空间和正半空间:

GDScript

C#

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

当然,Godot也在 Plane 中实现这个操作,像这样:

GDScript

C#

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

这将按预期工作.

所以,记住,平面就是这样,它的主要用途就是计算到它的距离.那么,为什么计算一个点到一个平面的距离是有用的呢？非常有用！让我们来看一些简单示例.

在二维空间中构造平面

平面显然不是从哪儿冒出来的,所以必须构造.在2D中构造它们很简单,这可以从法线(单位向量)和点,或者用2维空间中的两个点来完成.

针对法线和点的情况,大部分工作已经完成,因为当法线已经计算出来时,只需从法线和点的点乘得到D.

GDScript

C#

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

对于空间中的两个点,实际上会有两个平面同时经过它们,它们共享相同的空间,但是法线方向相反.为了从这两个点计算面的法线,必须首先获得方向向量,然后将向任何一边旋转90°:

GDScript

C#

  1. # Calculate vector from `a` to `b`.
  2. var dvec = (point_b - point_a).normalized()
  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 = (pointB - pointA).Normalized();
  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都可以工作,因为它们在相同的平面中:

GDScript

C#

  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

代码应该是这样的:

GDScript

C#

  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. }

很酷,是吧？但这可以变得更好！稍加努力,类似的逻辑将让我们知道两个凸多边形是否重叠.这叫做分离轴定理(或SAT),大多数物理引擎都用这个来检测碰撞.

对于一个点,仅仅检查一个平面是否返回正距离就足以判断该点是否在外面.对于一个多边形,我们必须找到一个平面,使得另一个多边形上的所有点到它的距离为正.这种可以用A平面对B点进行检查,然后用B平面对A点进行检查:

../../_images/tutovec14.png

代码应该是这样的:

GDScript

C#

  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. }

正如您所看到的,平面是非常有用的,然而这只是冰山一角.您可能想知道非凸多边形会发生什么.这通常只是通过将凹多边形分割成较小的凸多边形来处理,或者使用诸如BSP(现在使用得不多)之类的技术.

三维碰撞检测

这是另一个奖励,是对耐心并跟上这个漫长的教程的奖励.这是另一条锦囊妙计.这可能不能直接拿来使用(Godot已经可以进行了相当棒的碰撞检测了),但是几乎所有的物理引擎和碰撞检测库都使用它的原理:)

还记得把2D中的凸形转换成2D平面阵列对碰撞检测有用吗？您可以检测一个点是否在任何凸形状内,或者两个2D凸形状是否重叠.

嗯,这在3D中也适用,如果两个3D多面体形状碰撞,您将无法找到分离平面.如果发现一个分离平面,那么形状肯定不会发生碰撞.

要得到分离平面意味着多边形A的所有顶点都在平面的一侧,而多边形B的所有顶点都在另一侧.该平面始终是多边形A或多边形B的面向平面之一.

然而在3D中,这种方法存在一个问题,因为在某些情况下可能找不到分离平面.下面就是这种情况的一个示例:

../../_images/tutovec22.png

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

../../_images/tutovec23.png

所以最后的算法是这样的:

GDScript

C#

  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的绝佳的系列视频 “线性代数的本质”: https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab