判断是两个形状是否相交(一)-SAT分离轴理论

2024-06-06 12:32

本文主要是介绍判断是两个形状是否相交(一)-SAT分离轴理论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 判断是两个形状是否相交一-SAT分离轴理论
    • 原文地址
    • 简介
    • 凸多边形
    • 投影
    • 算法描述
      • 不相交
      • 相交
      • 得到分离轴
      • 找到MTV
      • 曲边图形
      • 包含
    • 其他需要注意的事情

判断是两个形状是否相交(一)-SAT分离轴理论

原文地址

简介

分离轴理论,简称SAT( SeparatingAxisTheorem ),是一个判断两个凸多边形是否碰撞的理论。此理论可以用于找到最小的渗透向量(感觉应该是模最小的),此向量在物理模拟和其他很多应用中很有用。SAT是一种高效的算法,能够出去每种形状对(譬如圆和圆,圆和多边形,多边形和线段)对碰撞检测代码的需求从而减少代码减轻维护压力。

凸多边形

SAT 就像以前说过的一样,是一个检测两个凸多边形是否相交的方法。对于一个形状,如果对于所有的穿过这个形状的线,这条线只和这个形状至多相交两次。如果多余两次,这个形状就是一个非凸多边形或者说凹多边形。看维基百科的定义 和数学世界的定义来了解更多的数学和官方定义。让我们来看一些例子

图示1:一个凸多边形
上图形被看做凸多边形因为不存在一条穿过它而且和他相交两次的直线。
图示2:一个凹多边形
这一个存在,所以其实一个凹多边形。
图示3:凹多边形的分解
SAT只能处理凸多边形,不多问题不大,因为非凸多边形可以被分解为凸多边形,如上图示。所以如果我们将图示2中的凹多边形分解我们可以得到两个凸多边形。然后我们就可以使用SAT对整个形状进行检测了。

投影

SAT使用的下一个概念叫做投影。想象一下如果你有一个全是平行光的光源。如果你将这个光投向一个物体它就会在一个平面上产生一个阴影。一个阴影是一个三维(3d)物体的二维(2d)的投影。一个二维物体的投影是一个一维“阴影”。具体如下图示
图示4:投影

算法描述

SAT描述为:如果两个凸多边形没有相交,那么存在这两个物体在一个轴上的投影不重叠。

不相交

首先让我们讨论一下SAT如何判断两个形状没有相交。在下图中我们可以看出这两个形状没有相交。可以划出一条线来展示出来。
图示5:没有相交的两个凸多边形

如果我们选择一条和图示中分割线垂直的线,将这两个凸多边形相对于这条垂线投影就会看出,投影没有重叠。那么这条垂线就被称作一条分离轴。在下图中深灰色的线既是一个分离轴,而且各自对应颜色的线就是这两个多边形想这条分离轴的投影。注意:在下图中投影没有重叠,所以根据SAT我们可以得出结论这两个多边形没有相交。
图示6:两个没有相交的凸多边形和他们各自对应的投影
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 axisProjection 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 overlapreturn false;}
}

相交

如果对于所有的轴,两个多边形的投影都相交,那么我们就可以得出结论这两个多边形相交。下图展示出了这种情况。
图示7:两个相交的凸多边形
所有的轴必须都在考虑范围之内,跟改后的伪代码为:

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 axisProjection 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 overlapreturn false;}
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;

得到分离轴

当我使用这个算法的时候第一个问题就是,我怎么知道去测试哪些轴。其实这个东西很简单:
你要测试的轴就是每个边的法向量。边的法向量可以通过对换x,y然后对其中的一个取负就行了。
图示8:边的法向量
举例说明

Vector[] axes = new Vector[shape.vertices.length];
// loop over the vertices
for (int i = 0; i < shape.vertices.length; i++) {// get the current vertexVector p1 = shape.vertices[i];// get the next vertexVector p2 = shape.vertices[i + 1 == shape.vertices.length ? 0 : i + 1];// subtract the two to get the edge vectorVector edge = p1.subtract(p2);// get either perpendicular vectorVector 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 axisProjection 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 overlapreturn false;}
}
// loop over the axes2
for (int i = 0; i < axes2.length; i++) {Axis axis = axes2[i];// project both shapes onto the axisProjection 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 overlapreturn false;}
}
// if we get here then we know that every axis had overlap on it
// so we can guarantee an intersection
return true;

将形状A向一个轴投影:

另一个没有很清晰的事情就是如何将一个图形向一个轴投影。将一个图形向一个轴投影其实是一个很简单的事情。循环所有的顶点执行和待测试轴的点乘,存储下最小值和最大值。

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

找到MTV

到目前为止我们只能判断这两个形状是否相交。除此之外,SAT可以返回一个MTV(Minimum Translation Vector 最小分离向量)。MTV是一个最小量级的将两个相交的图形分离的向量。如果我们回顾一下图示7就会发现 轴C 有着最小的投影重叠。那个轴和那个重叠就是MTV,那个轴指示出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 axisProjection 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 overlapreturn false;} else {// get the overlapdouble o = p1.getOverlap(p2);// check for minimumif (o < overlap) {// then set this one as the smallestoverlap = o;smallest = axis;}}
}
// loop over the axes2
for (int i = 0; i < axes2.length; i++) {Axis axis = axes2[i];// project both shapes onto the axisProjection 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 overlapreturn false;} else {// get the overlapdouble o = p1.getOverlap(p2);// check for minimumif (o < overlap) {// then set this one as the smallestoverlap = 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;

曲边图形

我们已经看到了多边形如何使用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() &amp;&amp; shape2.isCircle()) {// for two circles there is only one axis testaxes[0] = shape1.getCenter().subtract(shape2.getCenter);
}
// then all the SAT code from above

多边形和圆形会带来更多的问题, 图心和图心在多边形的待测试轴上的测试并不奏效,事实上会得到意想不到的错误结果.在这种情况下,你必须要包含另一个轴:那个从距离圆形最近的顶点到圆心的轴.多边形上最近的顶点的求法有很多种,理想的解决办法是Voronoi区域算法,但是不会在这篇文章中涉及.

其他的曲边图形会带来更多的问题,必须要使用各自特定的解决办法.例如一个胶囊形状可以被分解为一个矩形和两个半圆.

包含

一个很多开发者选择忽略的问题就是包含.一个图形包含另一个图形会发生什么么?这个问题并不会带了巨大的影响因为绝大多数的应用都不会让这种情况发生.首先让我介绍一下这个问题然后是如何解决它.然后我会介绍为什么我们要将他置于考虑范围之内.

如果一个图形被另一个图形包含,在我们现有的伪代码中,SAT会返回不对的MTV.方向和量级都有可能不对.下图展示了在轴上的投影的重叠不能够将两个图形分离开来.
图示9:包含
所以我们需要做的是在重叠测试中检测有没有包含.在上面的SAT代码中加上if语句:

if (!p1.overlap(p2)) {// then we can guarantee that the shapes do not overlapreturn false;
} else {// get the overlapdouble o = p1.getOverlap(p2);// check for containmentif (p1.contains(p2) || p2.contains(p1)) {// get the overlap plus the distance from the minimum end pointsdouble 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 minimumif (o < overlap) {// then set this one as the smallestoverlap = o;smallest = axis;}
}

将包含加入其中的原因:

  1. 游戏中给两个如此定义的形状是有可能的.不解决这个问题会要求我们根据两个形状的大小进行两次或者更多的SAT循环来解决这种特殊的碰撞.

  2. 如果你准备支持其他形状的线段分割,你有必要这样做,因为在一些情况下投影的重叠值可能为零,这是因为一个线段的分割是一个极小的图形这个事实(译者注:这些东西后面的翻译中会有).

其他需要注意的事情

  1. 被测试轴的数量可以通过不测试平行轴的方式减少.这就是为什么一个长方形可以只测试两个轴.
  2. 之前的分离轴可以作为下一次SAT循环的基础,这样这个算法在两个形状不想交的时候就会使O(1)的时间复杂度.
  3. SAT在3D情况下就会有可能要测试要非常多的轴.
  4. 我不是一个专家,所以请原谅我的糟糕的几何.

这篇关于判断是两个形状是否相交(一)-SAT分离轴理论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1036115

相关文章

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚: