JavaScript分离轴定理 [英] JavaScript Separating Axis Theorem
问题描述
我正在尝试使用JavaScript中的分离轴定理来绕过我的头，以检测两个正方形发生碰撞（一个旋转，另一个不旋转）。尽我所能，我无法弄清楚JavaScript中的样子，也找不到任何JavaScript示例。请帮忙，用纯数字或JavaScript代码进行解释将是最有用的。
更新：研究了很多几何形状和数学理论我决定在GitHub存储库中推出简化的SAT实现。您可以在JavaScript中找到SAT的工作副本： https://github.com/ashblue/canvas-sat
变换多边形
首先，您必须通过旋转 angle 来变换凸多边形（在这种情况下为正方形）的所有点，以便它们都在同一空间中。 / p>
为了将来支持缩放，平移等，我建议通过矩阵变换来实现。您必须编写自己的 Matrix 类，或找到一些已经具有此功能的库（我敢肯定有很多选择）。
然后您将使用以下代码：
var transform = new Matrix（ ）;
transform.appendRotation（alpha）;
points = transform.transformPoints（points）;
其中点是<$的数组c $ c> Point 个对象左右。
碰撞算法概述
因此，您可以在之前遇到任何碰撞。关于碰撞算法，通常的做法是使用以下步骤尝试分离2个凸多边形（在您的情况下为正方形）：
- 对于每个多边形边（多边形0和多边形1的边）：
- 将两个polgyons分别分类为在边上，跨越或在边上。
- 如果两个多边形都在不同的边上（在前面为1个，在后面为1个），则没有碰撞，可以停止算法（提前退出）。
- 如果您来到这里，则没有边缘能够分离出柱体：多边形相交/碰撞。
请注意，从概念上讲，分离轴是垂直于我们要对多边形进行分类的边缘的轴。
根据边对多边形进行分类
为此，我们将使用以下方法对多边形的点/顶点进行分类关于边缘。如果所有点都在一侧，则多边形在该侧。否则，多边形跨越边缘（部分在一侧，部分在另一侧）。
要对点进行分类，我们首先需要获取边缘的法线：
//此代码假定p0和p1是某些Vector3D类的实例
var p0 = edge [0 ]; //边缘
的第一个点var p1 = edge [1]; //边缘的第二个点
var v = p1.subtract（p0）;
var normal = new Vector3D（0，0，1）.crossProduct（v）;
normal.normalize（）;
上面的代码使用边缘方向与z矢量的叉积得到法线。当然，您应该为每个边缘预先计算。
注意：法线表示与SAT的分离轴。
接下来，我们可以对任意点进行分类，方法是首先使其相对于边缘（减去边缘点），然后将点积与法线一起使用：
//点是要归类为在边上或在边上的点
var point = point.subtract（p0 ）;
var distance = point.dotProduct（normal）;
var inFront =距离> = 0;
现在， inFront 是 true （如果该点位于前面或边缘），否则为 false 。
请注意，当您遍历多边形的点以对多边形进行分类时，如果前面至少有1个点，后面至少有1个点，则也可以提早退出，因为这已经确定该多边形跨越了
因此，如您所见，您仍然需要编写大量代码。用 Matrix 和 Vector3D 类找到一些js库，然后使用它来实现上述功能。将碰撞形状（多边形）表示为 Point 和 Edge 实例的序列。
希望这会帮助您入门。
I'm trying to wrap my head around using the Separating Axis Theorem in JavaScript to detect two squares colliding (one rotated, one not). As hard as I try, I can't figure out what this would look like in JavaScript, nor can I find any JavaScript examples. Please help, an explanation with plain numbers or JavaScript code would be most useful.
Update: After researching lots of geometry and math theories I've decided to roll out a simplified SAT implementation in a GitHub repo. You can find a working copy of SAT in JavaScript here: https://github.com/ashblue/canvas-sat
Transforming polygons
First you have to transform all points of your convex polygons (squares in this case) so they are all in the same space, by applying a rotation of angle.
For future support of scaling, translation, etc. I recommend doing this through matrix transforms. You'll have to code your own Matrix class or find some library that has this functionality already (I'm sure there are plenty of options).
Then you'll use code in the vain of:
var transform = new Matrix();
transform.appendRotation(alpha);
points = transform.transformPoints(points);
Where points is an array of Point objects or so.
Collision algorithm overview
So that's all before you get to any collision stuff. Regarding the collision algorithm, it's standard practice to try and separate 2 convex polygons (squares in your case) using the following steps:
- For each polygon edge (edges of both polygon 0 and polygon 1):
- Classify both polgyons as "in front", "spanning" or "behind" the edge.
- If both polygons are on different sides (1 "in front" and 1 "behind"), there is no collision, and you can stop the algorithm (early exit).
- If you get here, no edge was able to separate the polgyons: The polygons intersect/collide.
Note that conceptually, the "separating axis" is the axis perpendicular to the edge we're classifying the polygons with.
Classifying polygons with regards to an edge
In order to do this, we'll classify a polygon's points/vertices with regards to the edge. If all points are on one side, the polygon's on that side. Otherwise, the polygon's spanning the edge (partially on one side, partially on the other side).
To classify points, we first need to get the edge's normal:
// this code assumes p0 and p1 are instances of some Vector3D class
var p0 = edge[0]; // first point of edge
var p1 = edge[1]; // second point of edge
var v = p1.subtract(p0);
var normal = new Vector3D(0, 0, 1).crossProduct(v);
normal.normalize();
The above code uses the cross-product of the edge direction and the z-vector to get the normal. Ofcourse, you should pre-calculate this for each edge instead.
Note: The normal represents the separating axis from the SAT.
Next, we can classify an arbitrary point by first making it relative to the edge (subtracting an edge point), and using the dot-product with the normal:
// point is the point to classify as "in front" or "behind" the edge
var point = point.subtract(p0);
var distance = point.dotProduct(normal);
var inFront = distance >= 0;
Now, inFront is true if the point is in front or on the edge, and false otherwise.
Note that, when you loop over a polygon's points to classify the polygon, you can also exit early if you have at least 1 point in front and 1 behind, since then it's already determined that the polygon is spanning the edge (and not in front or behind).
So as you can see, you still have quite a bit of coding to do. Find some js library with Matrix and Vector3D classes or so and use that to implement the above. Represent your collision shapes (polygons) as sequences of Point and Edge instances.
Hopefully, this will get you started.
这篇关于JavaScript分离轴定理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
