NSDT工具推荐: Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器 - REVIT导出3D模型插件 - 3D模型语义搜索引擎 - AI模型在线查看 - Three.js虚拟轴心开发包 - 3D模型在线减面 - STL模型在线切割
分离轴定理(Seperating Axis Theorem)是一种确定两个凸多边形是否相交的方法。该算法还可用于查找最小穿透向量,这对于物理模拟和许多其他应用非常有用。SAT 是一种快速通用算法,可以消除对每个形状类型对进行碰撞检测代码的需求,从而减少代码和维护。
1、凸度
如前所述,SAT 是一种确定两个凸形是否相交的方法。如果任何穿过该形状的线只相交两次,则该形状被认为是凸形(convex)。如果一条线可以穿过该形状并相交两次以上,则该形状为非凸形或凹形(concave)。有关更正式的定义,请参阅 Wiki 的定义和 MathWorld 的定义。
让我们看一些例子:
![](http://www.bimant.com/blog/content/images/2024/06/image-65.png)
![](http://www.bimant.com/blog/content/images/2024/06/image-66.png)
第一个形状被认为是凸的,因为不存在可以穿过该形状并相交超过两次的线。第二个形状不是凸的,因为确实存在相交超过两次的线。
SAT 只能处理凸形状,但这是可以的,因为非凸形状可以用凸形状的组合来表示,这被称为凸分解(convex decomposition)。因此,如果我们采用图 2 中的非凸形状并执行凸分解,我们可以得到两个凸形状。然后我们可以测试每个凸形状以确定整个形状的碰撞。
![](http://www.bimant.com/blog/content/images/2024/06/image-67.png)
2、投影
SAT 使用的下一个概念是投影(projection)。想象一下,你有一个光源,它的光线都是平行的。如果你把这束光照射到一个物体上,它会在表面上产生阴影。阴影是三维物体的二维投影。二维物体的投影是一维“阴影”。
![](http://www.bimant.com/blog/content/images/2024/06/image-68.png)
3、SAT算法
SAT 指出:“如果两个凸面物体不相交,则存在一个轴,物体的投影不会在该轴上重叠。”
3.1 不相交
首先让我们讨论一下 SAT 如何确定两个形状不相交。在图 5 中,我们知道这两个形状不相交。在它们之间画一条线来说明这一点。
![](http://www.bimant.com/blog/content/images/2024/06/image-69.png)
如果我们选择图 5 中两个形状之间的垂直线,并将形状投影到该线上,我们可以看到它们的投影没有重叠。形状投影(阴影)不重叠的线称为分离轴。图 6 中的深灰色线是分离轴,相应的彩色线是形状在分离轴上的投影。请注意,图 6 中的投影没有重叠,因此根据 SAT,形状没有相交。
![](http://www.bimant.com/blog/content/images/2024/06/image-70.png)
SAT 可能会测试多个轴的重叠情况,但是,如果投影不重叠的第一个轴,算法可以立即退出,并确定形状不相交。由于这种提前退出,SAT 非常适合具有许多对象但很少发生碰撞的应用程序(游戏、模拟等)。
为了进一步解释,请查看以下伪代码:
Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = 0; i < axes.length; i++) {
Axis axis = axes[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}
3.2 相交
如果对于所有轴,形状的投影都重叠,那么我们可以得出结论,形状是相交的。图 7 展示了在多个轴上测试的两个凸形状。形状在这些轴上的投影全部重叠,因此我们可以得出结论,形状是相交的。
![](http://www.bimant.com/blog/content/images/2024/06/image-71.png)
必须测试所有轴的重叠度才能确定相交。上面修改后的代码为:
Axis[] axes = // get the axes to test;
// loop over the axes
for (int i = 0; i < axes.length; i++) {
Axis axis = axes[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;
3、获取分离轴
我在实施此算法时遇到的第一个问题是如何知道要测试哪些轴?这实际上非常简单:
你必须测试的轴是每个形状边缘的法线。
![](http://www.bimant.com/blog/content/images/2024/06/image-72.png)
可以通过翻转坐标并取负一来获得边缘的法线。例如:
Vector[] axes = new Vector[shape.vertices.length];
// loop over the vertices
for (int i = 0; i < shape.vertices.length; i++) {
// get the current vertex
Vector p1 = shape.vertices[i];
// get the next vertex
Vector p2 = shape.vertices[i + 1 == shape.vertices.length ? 0 : i + 1];
// subtract the two to get the edge vector
Vector edge = p1.subtract(p2);
// get either perpendicular vector
Vector normal = edge.perp();
// the perp method is just (x, y) => (-y, x) or (y, -x)
axes[i] = normal;
}
在上述方法中,我们返回形状每个边缘的垂直向量。这些向量称为“法线”向量。但是,这些向量并未标准化(不是单位长度)。如果你只需要 SAT 算法的布尔结果,这就足够了,但如果你需要碰撞信息(稍后将在 MTV 部分讨论),则需要标准化这些向量(请参阅将形状投影到轴上部分)。
对每个形状执行此操作以获取要测试的两个轴列表。这样做会将上面的伪代码更改为:
Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();
// loop over the axes1
for (int i = 0; i < axes1.length; i++) {
Axis axis = axes1[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}
// loop over the axes2
for (int i = 0; i < axes2.length; i++) {
Axis axis = axes2[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
}
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;
4、将形状投影到轴上
另一件不清楚的事情是如何将形状投影到轴上。将多边形投影到轴上相对简单;循环遍历所有顶点,与轴执行点积并存储最小值和最大值。
double min = axis.dot(shape.vertices[0]);
double max = min;
for (int i = 1; i < shape.vertices.length; i++) {
// NOTE: the axis must be normalized to get accurate projections
double p = axis.dot(shape.vertices[i]);
if (p < min) {
min = p;
} else if (p > max) {
max = p;
}
}
Projection proj = new Projection(min, max);
return proj;
5、查找 MTV
到目前为止,我们只在两个形状相交时返回 true 或 false。除此之外,SAT 还可以返回最小平移向量 (Minimum Translation Vector)。MTV 是用于将形状推离碰撞的最小幅度向量。如果我们回顾图 7,我们可以看到轴 C 具有最小重叠。该轴和重叠是 MTV,轴是向量部分,重叠是幅度部分。
要确定形状是否相交,我们必须循环遍历两个形状的所有轴,这样我们就可以同时跟踪最小重叠和轴。如果我们修改上面的伪代码以包含这一点,我们可以在形状相交时返回 MTV。
double overlap = // really large value;
Axis smallest = null;
Axis[] axes1 = shape1.getAxes();
Axis[] axes2 = shape2.getAxes();
// loop over the axes1
for (int i = 0; i < axes1.length; i++) {
Axis axis = axes1[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
} else {
// get the overlap
double o = p1.getOverlap(p2);
// check for minimum
if (o < overlap) {
// then set this one as the smallest
overlap = o;
smallest = axis;
}
}
}
// loop over the axes2
for (int i = 0; i < axes2.length; i++) {
Axis axis = axes2[i];
// project both shapes onto the axis
Projection p1 = shape1.project(axis);
Projection p2 = shape2.project(axis);
// do the projections overlap?
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
} else {
// get the overlap
double o = p1.getOverlap(p2);
// check for minimum
if (o < overlap) {
// then set this one as the smallest
overlap = o;
smallest = axis;
}
}
}
MTV mtv = new MTV(smallest, overlap);
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return mtv;
6、弯曲形状
我们已经了解了如何使用 SAT 测试多边形,但是像圆形这样的弯曲形状呢?弯曲形状对 SAT 来说是一个问题,因为弯曲形状有无数个分离轴需要测试。解决这个问题的方法是将“圆与圆”和“圆与多边形”测试分开,然后做一些更具体的工作。另一种选择是根本不使用弯曲形状,而是用高顶点数多边形代替它们。第二种选择不需要更改上述伪代码,但我想介绍第一种选择。
让我们首先看看“圆与圆”。通常,你会执行以下操作:
Vector c1 = circle1.getCenter();
Vector c2 = circle2.getCenter();
Vector v = c1.subtract(c2);
if (v.getMagnitude() < circle1.getRadius() + circle2.getRadius()) {
// then there is an intersection
}
// else there isnt
如果两个圆心之间的距离小于圆半径之和,我们就知道它们相撞了。这个测试实际上是一个类似 SAT 的测试。为了在 SAT 中实现这一点,我们可以执行以下操作:
Vector[] axes = new Vector[1];
if (shape1.isCircle() && shape2.isCircle()) {
// for two circles there is only one axis test
axes[0] = shape1.getCenter().subtract(shape2.getCenter);
}
// then all the SAT code from above</pre>
圆形与多边形的问题更大。中心到中心测试以及多边形轴是不够的(事实上,中心到中心测试可以省略)。在这种情况下,您必须包含另一个轴:从多边形上最近的顶点到圆心的轴。可以通过多种方式找到多边形上最近的顶点,公认的解决方案是使用 Voronoi 区域,我不会在这篇文章中讨论。
其他弯曲形状将是一个更大的问题,必须以自己的方式处理。例如,胶囊形状可以分解为一个矩形和两个圆形。
7、包容性
许多开发人员选择忽略的问题之一是包容性。当一个形状包含另一个形状时会发生什么?这个问题通常不是什么大问题,因为大多数应用程序永远不会发生这种情况。首先让我解释一下这个问题以及如何处理它。然后我会解释为什么应该考虑它。
![](http://www.bimant.com/blog/content/images/2024/06/image-73.png)
如果一个形状包含在另一个形状 SAT 中,根据我们目前拥有的伪代码,将返回不正确的 MTV。矢量和幅度部分可能都不正确。图 9 显示返回的重叠不足以将形状移出相交。所以我们需要做的是在重叠测试中检查包含情况。仅从上面的 SAT 代码中获取 if 语句:
if (!p1.overlap(p2)) {
// then we can guarantee that the shapes do not overlap
return false;
} else {
// get the overlap
double o = p1.getOverlap(p2);
// check for containment
if (p1.contains(p2) || p2.contains(p1)) {
// get the overlap plus the distance from the minimum end points
double mins = abs(p1.min - p2.min);
double maxs = abs(p1.max - p2.max);
// NOTE: depending on which is smaller you may need to
// negate the separating axis!!
if (mins < maxs) {
o += mins;
} else {
o += maxs;
}
}
// check for minimum
if (o < overlap) {
// then set this one as the smallest
overlap = o;
smallest = axis;
}
}
原因 1:形状有可能处于这种配置类型。如果不处理这种情况,则需要两次或更多次 SAT 迭代来解决碰撞,具体取决于形状的相对大小。
原因 2:如果您计划支持线段与其他形状,则必须这样做,因为在某些情况下重叠可能为零(这是因为线段是无限薄的形状)。
8、其他注意事项
其他一些注意事项:
- 通过不测试平行轴可以减少要测试的轴数。这就是为什么矩形只有两个轴要测试的原因。
- 如果某些形状(如矩形)具有自己的投影和 getAxes 代码,则可以执行得更快,因为矩形不需要测试 4 个轴,而实际上只需要 2 个。
- 最后一个分离轴可用于启动 SAT 的下一次迭代,以便在非相交情况下算法可以是 O(1)。
- 3D 中的 SAT 最终可能会测试很多轴。
原文链接:SAT (Separating Axis Theorem)
BimAnt翻译整理,转载请标明出处