“等一下，我碰！”——常见的2D碰撞检测
KHRAnd
8年前
<p>“碰乜鬼嘢啊，碰走晒我滴靓牌”。想到“碰”就自然联想到了“麻将”这一伟大发明。当然除了“碰”，洗牌的时候也充满了各种『碰撞』。</p> <p>好了，不废话。直入主题——碰撞检测。</p> <p>在 2D 环境下，常见的碰撞检测方法如下：</p> <ul> <li>外接图形判别法 <ul> <li>轴对称包围盒（Axis-Aligned Bounding Box），即无旋转矩形。</li> <li>圆形碰撞</li> </ul> </li> <li>光线投射法</li> <li>分离轴定理</li> <li>其他 <ul> <li>地图格子划分</li> <li>像素检测</li> </ul> </li> </ul> <p>下文将由易到难的顺序介绍上述各种碰撞检测方法：外接图形判别法 > 其他 > 光线投射法 > 分离轴定理。</p> <p>另外，有一些场景只要我们约定好限定条件，也能实现我们想要的碰撞，如下面的碰壁反弹：</p> <p>See the Pen Boundary collision detection by Jc ( @JChehe ) on CodePen .</p> <p>当球碰到边框就反弹(如 x/y轴方向速度取反 )。</p> <pre> <code class="language-python">if(ball.left < 0 || ball.right > rect.width) ball.velocityX = -ball.velocityX if(ball.top < 0 || ball.bottom > rect.height) ball.velocityY = -ball.velocityY </code></pre> <p>再例如当一个人走到 100px 位置时不进行跳跃，就会碰到石头等等。</p> <p>因此，某些场景只需通过设定到适当的参数即可。</p> <h2>外接图形判别法</h2> <h3>轴对称包围盒（Axis-Aligned Bounding Box）</h3> <p>概念：判断任意两个（无旋转）矩形的任意一边是否无间距，从而判断是否碰撞。</p> <p>算法：</p> <pre> <code class="language-python">rect1.x < rect2.x + rect2.width && rect1.x + rect1.width > rect2.x && rect1.y < rect2.y + rect2.height && rect1.height + rect1.y > rect2.y </code></pre> <p>两矩形间碰撞的各种情况：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/021a715ec6d28ef7020269ad140b05c4.png"></p> <p>在线运行示例（先点击运行示例以获取焦点，下同）：</p> <p>See the Pen AxisAlignedBoundingBox collision detection by Jc ( @JChehe ) on CodePen .</p> <p>缺点：</p> <ul> <li>相对局限：两物体必须是矩形，且均不允许旋转（即关于水平和垂直方向上对称）。</li> <li>对于包含着图案（非填满整个矩形）的矩形进行碰撞检测，可能存在精度不足的问题。</li> <li>物体运动速度过快时，可能会在相邻两动画帧之间快速穿越，导致忽略了本应碰撞的事件发生。</li> </ul> <p>适用案例：</p> <ul> <li>（类）矩形物体间的碰撞。</li> </ul> <h3>圆形碰撞（Circle Collision）</h3> <p>概念：通过判断任意两个圆形的圆心距离是否小于两圆半径之和，若小于则为碰撞。</p> <p>两点之间的距离由以下公式可得：</p> <p><img src="https://simg.open-open.com/show/feb90b66102fc46cebe3d1ed5e574044.png"></p> <p>判断两圆心距离是否小于两半径之和：</p> <pre> <code class="language-python">Math.sqrt(Math.pow(circleA.x - circleB.x, 2) + Math.pow(circleA.y - circleB.y, 2)) < circleA.radius + circleB.radius </code></pre> <p>图例：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/b27fa0837a69a17b2ef1367bafc49b05.png"></p> <p>在线运行示例：</p> <p>See the Pen EZrorG by Jc ( @JChehe ) on CodePen .</p> <p>缺点：</p> <ul> <li>与『轴对称包围盒』类似</li> </ul> <p>适用案例：</p> <ul> <li>（类）圆形的物体，如各种球类碰撞。</li> </ul> <h2>其他</h2> <h3>地图格子划分</h3> <p>概念：将地图（场景）划分为一个个格子。地图中参与检测的对象都存储着自身所在格子的坐标，那么你即可以认为两个物体在相邻格子时为碰撞，又或者两个物体在同一格才为碰撞。另外，采用此方式的前提是：地图中所有可能参与碰撞的物体都要是格子单元的大小或者是其整数倍。</p> <p>蓝色X 为障碍物：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/0287c9f8394ddbea67e47f3983f5b095.png"></p> <p>实现方法：</p> <pre> <code class="language-python">// 通过特定标识指定（非）可行区域 map = [ [0, 0, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 1, 1, 1, 1, 1, 0, 0] ], // 设定角色的初始位置 player = {left: 2, top: 2} // 移动前（后）判断角色的下一步的动作（如不能前行） ... </code></pre> <p>在线运行示例：</p> <p>See the Pen map cell collision detection by Jc ( @JChehe ) on CodePen .</p> <p>缺点：</p> <ul> <li>适用场景局限。</li> </ul> <p>适用案例：</p> <ul> <li>推箱子、踩地雷等</li> </ul> <h3>像素检测</h3> <p>概念：以像素级别检测物体之间是否存在重叠，从而判断是否碰撞。</p> <p>实现方法有多种，下面列举在 Canvas 中的两种实现方式：</p> <ol> <li>如下述的案例中，通过将两个物体在 offscreen canvas 中判断同一位置（坐标）下是否同时存在非透明的像素。</li> <li>利用 canvas 的 globalCompositeOperation = 'destination-in' 属性。该属性会让两者的重叠部分会被保留，其余区域都变成透明。因此，若存在非透明像素，则为碰撞。</li> </ol> <p>注意，当待检测碰撞物体为两个时，第一种方法需要两个 offscreen canvas，而第二个只需一个。</p> <p>offscreen canvas：与之相关的是 offscreen rendering。正如其名，它会在某个地方进行渲染，但不是屏幕。“某个地方”其实是 <strong>内存</strong> 。渲染到内存比渲染到屏幕更快。—— <a href="/misc/goto?guid=4959737578755278746" rel="nofollow,noindex">Offscreen Rendering</a></p> <p>当然，我们这里并不是利用 offscreen render 的性能优势，而是利用 offscreen canvas 保存独立物体的像素。换句话说： onscreen canvas 只是起展示作用，碰撞检测是在 offscreen canvas 中进行 。</p> <p>另外，由于需要逐像素检测，若对整个 Canvas 内所有像素都进行此操作，无疑会浪费很多资源。因此，我们可以先通过运算得到两者 <strong>相交区域</strong> ，然后只对该区域内的像素进行检测即可。</p> <p>图例：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/e2ba2dc09e7ca20c9068afff285d4622.png"></p> <p>下面示例展示了第一种实现方式：</p> <p>See the Pen pixel collision detection by Jc ( @JChehe ) on CodePen .</p> <p>缺点：</p> <ul> <li>因为需要检查每一像素来判定是否碰撞，性能要求比较高。</li> </ul> <p>适用案例：</p> <ul> <li>需要以像素级别检测物体是否碰撞。</li> </ul> <h2>光线投射法（Ray Casting）</h2> <p>概念：通过检测两个物体的速度矢量是否存在交点，且该交点满足一定条件。</p> <p>对于下述抛小球入桶的案例：画一条与物体的速度向量相重合的线( #1 )，然后再从另一个待检测物体出发，连线到前一个物体，绘制第二条线( #2 )，根据两条线的交点位置来判定是否发生碰撞。</p> <p>抛球进桶图例：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/ee3929ae6a4c3a0fc9ec566974c52cd9.png"></p> <p>在小球飞行的过程中，需要不断计算两直线的交点。</p> <p>当满足以下两个条件时，那么应用程序就可以判定小球已落入桶中：</p> <ul> <li>两直线交点在桶口的左右边沿间</li> <li>小球位于第二条线（ #2 ）下方</li> </ul> <p>在线运行示例：</p> <p>See the Pen ray casting collision detection by Jc ( @JChehe ) on CodePen .</p> <p>优点：</p> <ul> <li>适合运动速度快的物体</li> </ul> <p>缺点：</p> <ul> <li>适用范围相对局限。</li> </ul> <p>适用案例：</p> <ul> <li>抛球运动进桶。</li> </ul> <h2>分离轴定理（Separating Axis Theorem）</h2> <p>概念：通过判断任意两个 凸多边形 在任意角度下的投影是否均存在重叠，来判断是否发生碰撞。若在某一角度光源下，两物体的投影存在间隙，则为不碰撞，否则为发生碰撞。</p> <p>图例：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/ef5b81f047e95c314d6e955870e2d05f.png"></p> <p>在程序中，遍历所有角度是不现实的。那如何确定 投影轴 呢？其实 <strong>投影轴的数量与多边形的边数相等即可。</strong></p> <p style="text-align:center"><img src="https://simg.open-open.com/show/4ad9ec45097f9f75f23fdcea04fdb315.png"></p> <p>以较高抽象层次判断两个凸多边形是否碰撞：</p> <pre> <code class="language-python">functionpolygonsCollide(polygon1, polygon2){ var axes, projection1, projection2 // 根据多边形获取所有投影轴 axes = polygon1.getAxes() axes.push(polygon2.getAxes()) // 遍历所有投影轴，获取多边形在每条投影轴上的投影 for(each axis in axes) { projection1 = polygon1.project(axis) projection2 = polygon2.project(axis) // 判断投影轴上的投影是否存在重叠，若检测到存在间隙则立刻退出判断，消除不必要的运算。 if(!projection1.overlaps(projection2)) return false } return true } </code></pre> <p>上述代码有几个需要解决的地方：</p> <ul> <li>如何确定多边形的各个投影轴</li> <li>如何将多边形投射到某条投影轴上</li> <li>如何检测两段投影是否发生重叠</li> </ul> <p>投影轴</p> <p>如下图所示，我们使用一条从 p1 指向 p2 的向量来表示多边形的某条边，我们称之为 <strong>边缘向量</strong> 。在分离轴定理中，还需要确定一条垂直于边缘向量的法向量，我们称之为“ <strong>边缘法向量</strong> ”。</p> <p>投影轴平行于边缘法向量。投影轴的位置不限，因为其长度是无限的，故而多边形在该轴上的投影是一样的。该轴的方向才是关键的。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/5fafe9f889de95c487257a33aa9a0957.png"></p> <pre> <code class="language-python">// 以原点(0,0)为始，顶点为末。最后通过向量减法得到 边缘向量。 var v1 = new Vector(p1.x, p1.y) v2 = new Vector(p2.x, p2.y) // 首先得到边缘向量，然后再通过边缘向量获得相应边缘法向量（单位向量）。 // 两向量相减得到边缘向量 p2p1（注：上面应该有个右箭头，以表示向量）。 // 设向量 p2p1 为(A,B)，那么其法向量通过 x1x2+y1y2 = 0 可得：(-B,A) 或 (B,-A)。 axis = v1.edge(v2).normal() </code></pre> <p>以下是向量对象的部分实现，具体可看源码。</p> <pre> <code class="language-python">var Vector = function(x, y){ this.x = x this.y = y } Vector.prototype = { // 获取向量大小（即向量的模），即两点间距离 getMagnitude: function(){ return Math.sqrt(Math.pow(this.x, 2), Math.pow(this.y, 2)) }, // 点积的几何意义之一是：一个向量在平行于另一个向量方向上的投影的数值乘积。 // 后续将会用其计算出投影的长度 dotProduct: function(vector){ return this.x * vector.x + this.y + vector.y } // 向量相减 得到边 subtarct: function(vector){ var v = new Vector() v.x = this.x - vector.x v.y = this.y - vector.y return v }, edge: function(vector){ return this.substract(vector) }, // 获取当前向量的法向量（垂直） perpendicular: function(){ var v = new Vector() v.x = this.y v.y = 0 - this.x return v }, // 获取单位向量（即向量大小为1，用于表示向量方向），一个非零向量除以它的模即可得到单位向量 normalize: function(){ var v = new Vector(0, 0) m = this.getMagnitude() if(m !== 0) { v.x = this.x / m v.y = this.y /m } return v }, // 获取边缘法向量的单位向量，即投影轴 normal: function(){ var p = this.perpendicular() return p .normalize() } } </code></pre> <p style="text-align:center"><img src="https://simg.open-open.com/show/4d80cf3eeb991b760fecfac5e7b9382d.png"></p> <p>向量相减</p> <p>更多关于向量的知识可通过其它渠道学习。</p> <p>投影</p> <p>投影的大小：通过将一个多边形上的每个顶点与原点(0,0)组成的向量，投影在某一投影轴上，然后保留该多边形在该投影轴上所有投影中的最大值和最小值，这样即可表示一个多边形在某投影轴上的投影了。</p> <p>判断两多边形的投影是否重合： projection1.max > projection2.min && project2.max > projection.min</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/9229f06107bb3680808d7299986e4eb2.png"></p> <p>为了易于理解，示例图将坐标轴 原点(0,0) 放置于三角形 边1 投影轴的适当位置。</p> <p>由上述可得投影对象：</p> <pre> <code class="language-python">// 用最大和最小值表示某一凸多边形在某一投影轴上的投影位置 var Projection = function(min, max){ this.min this.max } projection.prototype = { // 判断两投影是否重叠 overlaps: function(projection){ return this.max > projection.min && projection.max > this.min } } </code></pre> <p>如何得到向量在投影轴上的长度？</p> <p>向量的点积的其中一个几何含义是：一个向量在平行于另一个向量方向上的投影的数值乘积。</p> <p>由于 <strong>投影轴</strong> 是单位向量（长度为 1 ），投影的长度为 x1 * x2 + y1 * y2</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/d5707c59cb62ebb899dc7a82df408767.png"></p> <pre> <code class="language-python">// 根据多边形的每个定点，得到投影的最大和最小值，以表示投影。 functionproject=function(axis){ var scalars = [], v = new Vector() this.points.forEach(function(point){ v.x = point.x v.y = point.y scalars.push(v.dotProduct(axis)) }) return new Projection(Math.min.apply(Math, scalars), Math.max,apply(Math, scalars)) } </code></pre> <p>圆形与多边形之间的碰撞检测</p> <p>由于圆形可近似地看成一个有无数条边的正多边形，而我们不可能按照这些边一一进行投影与测试。我们只需将圆形投射到一条投影轴上即可，这条轴就是圆心与多边形顶点中最近的一点的连线，如图所示：</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/559d2a18d03426f94f86561b4ca2721e.png"></p> <p>因此，该投影轴和多边形自身的投影轴就组成了一组待检测的投影轴了。</p> <p>而对于圆形与圆形之间的碰撞检测依然是最初的两圆心距离是否小于两半径之和。</p> <p>分离轴定理的整体代码实现，可查看以下案例：</p> <p>See the Pen <a href="/misc/goto?guid=4959737578850894200" rel="nofollow,noindex">SeparatingAxisTheorem</a> by Jc ( <a href="/misc/goto?guid=4959737578952399594" rel="nofollow,noindex">@JChehe</a> ) on <a href="/misc/goto?guid=4958528714030324811" rel="nofollow,noindex">CodePen</a> .</p> <p>优点：</p> <ul> <li>精确</li> </ul> <p>缺点：</p> <ul> <li>不适用于凹多边形</li> </ul> <p>适用案例：</p> <ul> <li>任意凸多边形和圆形。</li> </ul> <p>更多关于分离轴定理的资料：</p> <ul> <li><a href="/misc/goto?guid=4959735949236597673" rel="nofollow,noindex">Separating Axis Theorem (SAT) explanation</a></li> <li><a href="/misc/goto?guid=4959737579112820565" rel="nofollow,noindex">Collision detection and response</a></li> <li><a href="/misc/goto?guid=4959737579214707885" rel="nofollow,noindex">Collision detection Using the Separating Axis Theorem</a></li> <li><a href="/misc/goto?guid=4959737579325908524" rel="nofollow,noindex">SAT (Separating Axis Theorem)</a></li> <li><a href="/misc/goto?guid=4959737579427262432" rel="nofollow,noindex">Separation of Axis Theorem (SAT) for Collision Detection</a></li> </ul> <p>延伸：最小平移向量（MIT）</p> <p>通常来说，如果碰撞之后，相撞的双方依然存在，那么就需要将两者分开。分开之后，可以使原来相撞的两物体彼此弹开，也可以让他们黏在一起，还可以根据具体需要来实现其他行为。不过首先要做的是，还是将两者分开，这就需要用到最小平移向量（Minimum Translation Vector, MIT）。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/276a29185e3f86c65aa9eb089e479975.png"></p> <h3>碰撞性能优化</h3> <p>若每个周期都需要对全部物体进行两两判断，会造成浪费（因为有些物体分布在不同区域，根本不会发生碰撞）。所以，大部分游戏都会将碰撞分为两个阶段：粗略和精细（broad/narrow）。</p> <p>粗略阶段（Broad Phase）</p> <p>Broad phase 能为你提供有可能碰撞的实体列表。这可通过一些特殊的数据结构实现，它们能为你提供信息：实体存在哪里和哪些实体在其周围。这些数据结构可以是：四叉树（Quad Trees）、R树（R-Trees）或空间哈希映射（Spatial Hashmap）等。</p> <p>读者若感兴趣，可以自行查阅相关信息。</p> <p>精细阶段（Narrow Phase）</p> <p>当你有了较小的实体列表，你可以利用精细阶段的算法（如上述讲述的碰撞算法）得到一个确切的答案（是否发生碰撞）。</p> <h3>最后</h3> <p>无论你碰不碰，我都会自摸:mahjong:️:v:。</p> <p>完！</p> <p> </p> <p>来自：https://aotu.io/notes/2017/02/16/2d-collision-detection/</p> <p> </p>