高等向量数学

平面

单位向量的点积还有一个有趣的性质。请想象垂直于这个向量(通过原点)经过一个平面。平面将整个空间划分为正(在平面上)和负(在平面下),而(与普遍的看法相反)你也可以在 2D 中进行这样的数学运算:

../../_images/tutovec10.png

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

The plane passes by the origin and the surface of it is perpendicular to the unit vector (or normal). The side towards the vector points to is the positive half-space, while the other side is the negative half-space. In 3D this is exactly the same, except that the plane is an infinite surface (imagine an infinite, flat sheet of paper that you can orient and is pinned to the origin) instead of a line.

到平面的距离

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

GDScriptC#

  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方向移动到平面的距离. 例如, 想象一下你想在到达平面上的一个点, 你会这样做:

GDScriptC#

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

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

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);

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

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

GDScriptC#

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

Godot also implements this operator in Plane. So, using the format below will work as expected:

GDScriptC#

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

So, remember, the plane’s main practical use is that we can calculate the distance to it. So, when is it useful to calculate the distance from a point to a plane? Let’s see some examples.

在二维空间中构造平面

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

In the case of a normal and a point, most of the work is done, as the normal is already computed, so calculate D from the dot product of the normal and the point.

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);

The rest is the same as the previous example. Either point_a or point_b will work, as they are in the same plane:

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);

Doing the same in 3D is a little more complex and is explained further down.

平面的一些示例

Here is an example of what planes are useful for. Imagine you have a convex polygon. For example, a rectangle, a trapezoid, a triangle, or just any polygon where no faces bend inwards.

对多边形的每个部分, 我们计算出经过该部分的平面. 一旦我们有了平面的列表, 我们就可以做些分类的事情, 例如检查一个点是否在多边形内部.

我们遍历所有平面, 如果我们能找到使得点到平面的距离为正的平面, 那么点在多边形之外. 如果我们不能, 那么这一点就在多边形内部.

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

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

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

../../_images/tutovec14.png

代码应该是这样的:

GDScriptC#

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

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

三维碰撞检测

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

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

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

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

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

../../_images/tutovec22.png

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

../../_images/tutovec23.png

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

GDScriptC#

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

更多信息

关于在Godot中使用向量数学的更多信息, 请参见以下文章:

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

Previous Next


© 版权所有 2014-present Juan Linietsky, Ariel Manzur and the Godot community (CC BY 3.0). Revision b1c660f7.

Built with Sphinx using a theme provided by Read the Docs.