爱站网官网查询域名,用数字做域名的网站,html如果制作一个内容多的网站,旅游网站设计完整代码1、AABB碰撞检测算法
AABB碰撞检测指轴对齐碰撞箱(Axis-aligned Bounding Box)#xff0c;是分别从x轴向和y轴向进行碰撞检测的算法。即对于需要检测的物体A和物体B我们需要将其用A盒和B盒套起来#xff0c;判断A盒和B盒在x轴向和y轴向是否发生碰撞#xff0c;只有在x轴向和…
1、AABB碰撞检测算法
AABB碰撞检测指轴对齐碰撞箱(Axis-aligned Bounding Box)是分别从x轴向和y轴向进行碰撞检测的算法。即对于需要检测的物体A和物体B我们需要将其用A盒和B盒套起来判断A盒和B盒在x轴向和y轴向是否发生碰撞只有在x轴向和y轴向都发生碰撞我们才判断它发生了碰撞。 在轴对齐包围矩形Axis Aligned Bounding BoxAABB基础之上更为准确的是 转向包围矩形Oriented Bounding BoxOBB OBB 与 AABB 的差别在于物体旋转之后AABB的大小会发生改变保证每条边与某个坐标轴平行OBB 的大小则不会改变且将随物体一起旋转。 2、OBB碰撞检测算法
OBB 就是找一个最小的包围物体的矩形这在自动驾驶系统中也是最常用的感知模块给出物体的轮廓通常就是此形状。另外为了准确描述物体轮廓感知模块在 bounding box 的基础上通常还会给出 polygon多边形的形式如下图所示。 相对于AABB包围盒来讲OBB在碰撞精度上要高于AABB但是精确度的提高同时带来的就是效率的降低OBB的算法无疑是要比AABB复杂的同样内存消耗也会更大。 在了解OBB算法之前我们需要先学习一下分离轴定理。
分离轴定理(SAT) 分离轴定理(Separating Axis Theorem)的理论依据为超平面分离定理即 令 A 和 B 是两个不相交的非空凸集那么存在一个非零向量 v 和 实数 c使得 x, v ≤ c 且 y, v ≥ c。其中x 属于 Ay 属于 B。 简单来说就是对于两个凸多边形若存在一条直线将两者分开则这两个多边形不相交。 上图中的黑线为分离线Seperating line与之垂直的绿线为分离轴Separating axis图中虚线表示的是多边形在分离轴上的投影。
实际应用中遍历所有角度的分离轴是不现实的受益于多边形的性质对于两个都是多边形的物体只需要依次在每条边的垂直线做投影即可如下图所示。 对于两个都是矩形的物体则更简单只需要做四次投影。 以下图中的两个多边形 A 和 B 为例分离轴定理的具体步骤为
首先根据边1的两个顶点位置坐标计算出边1的向量设为xy进而求出边1的法向量作为分离轴为y, -x或-yx。若需要求两个多边形的最小分离距离这里的法向量还需要化为单位向量若只需判断两个多边形是否相交则不需要化为单位向量依次将多边形 A 和 B的所有顶点与原点组成的向量投影到这个分离轴上并记录两个多边形顶点投影到分离轴上的最小值和最大值PminPmax形成一个投影线段判断这两个投影线段是否发生重叠若不重叠则有 PAmax PBmin||PAmin PBmax若两个投影线段不重叠则代表存在这样一条直线将两个多边形分开两个多边形不相交可以直接退出循环若两个投影线段重叠则回到步骤1继续以边2的法向量作为分离轴进行投影计算当两个多边形的所有边都检查完之后找不到这样一条分离的直线则意味着两个多边形相交。 注意分离轴定理是一种适用于凸多边形的碰撞检测算法对于凹多边形则不适用如下图所示两个多边形没有碰撞但找不到这样一条直线能将两者分开。所以如果是凹多边形的话需要先将其转换成多个凸多边形。 综上分离轴定理是一种适用于 bounding box 和 polygon 的精细碰撞检测算法其优点是算法原理简单可准确判断两个多边形是否相交缺点在于当多边形的边数较多时该算法的效率较低当两个多边形相交时需要遍历完所有边进行判断。 在实际应用中为了提高效率通常先使用 基于轴对齐包围矩形AABB的方法进行粗略的碰撞检测然后再使用分离轴定理SAT做精细碰撞检测。 3、GJKGilbert–Johnson–Keerthi算法
GJK是由GilbertJohnsonKeerthi 三位前辈发明的用来计算两个凸多面体之间的碰撞检测以及最近距离。GJK算法可以在O(MN)的时间复杂度内检测出碰撞算法在每次迭代的过程中都会优先选择靠近原点的方向因此收敛速度会很快。算法的证明过程比较复杂但是原理还是比较容易理解的。
相比 SAT 算法GJK 算法更加高效。 GJK算法的核心就是闵可夫斯基差即若两个多边形相交则它们的闵可夫斯基差必然包括原点。
闵可夫斯基差也可以叫做闵可夫斯基和它的定义也很好理解点集A与B的闵可夫斯基和被定义为 A B {a b |a∈Ab∈B} 如果 A 和 B 是两个凸多边形则 A B 也是凸多边形。
闵可夫斯基和从几何上的直观理解是A集合沿B的边际连续运动一周扫过的区域与B集合本身的并集也可以是B沿着A的边界连续运动扫过区域与A自身的并集。
GJK算法用到的不是闵可夫斯基和而是闵可夫斯基差即 A – B {a – b |a∈Ab∈B} 虽然使用的是减法运算但其仍然是闵可夫斯基和相当于先对B中的所有点做负运算相对原点的镜像然后再与A做加法。
先来看两个例子。
对于两个不相交的多边形shape1为矩形shape2为三角形如下图所示。 它们的闵可夫斯基差如下图所示其闵可夫斯基差不包括原点且两个多边形之间的距离就是其闵可夫斯基差到原点的距离。事实上GJK 算法发明出来的初衷就是为了计算两个凸多边形之间的距离。 对于两个相交的多边形shape1为矩形shape2为三角形如下图所示。 它们的闵可夫斯基差则如下图所示可以看到闵可夫斯基差是包括原点的。这也很好理解两个相交的多边形必然有一点既属于shape1也属于shape2相减则为原点00。 3.1 单纯形 k阶单纯形simplex指的是k维空间中的多胞形该多胞形是k1个顶点组成的凸包。
在GJK算法中单纯形被大量使用。单纯形指的是点、线段、三角形或四面体。例如0阶单纯形是点1阶单纯形是线段2阶单纯形是三角形3阶单纯形是四面体。 对于2维空间的多边形最多用到2阶单纯形。那单纯形到底有什么作用呢
对于上面两个相交的多边形例子实际应用中其实不需要求出完整的闵可夫斯基差只需要在闵可夫斯基差内形成一个多边形如下图所示并使这个多边形尽可能包围原点这个多边形就称为单纯形。即假如单纯形包围原点则闵可夫斯基差必然包围原点。 3.2 Support 函数 Support函数的作用是计算多边形在给定方向上的最远点。如下图所示在向量 a 方向的最远点为 A 点在向量 b 方向的最远点为 B 点。这里在寻找给定方向上的最远点时需要用到向量的点乘。 为什么需要Support函数呢这是因为在构建单纯形时我们希望尽可能得到闵可夫斯基差的顶点而不是其内部的一个点这样产生的单纯形才能包含最大的区域增加算法的快速收敛性。
如下图所示在给定向量 a 方向上shape1 的最远点为42在向量 -a 的方向上shape2 的最远点为53这两个点作差即得到点-1-1。利用这种方式得到的点都在闵可夫斯基差的边上。
