[译]碰撞检测之分离轴定理算法讲解

   <p>本文翻译自 <a href="/misc/goto?guid=4959735949142225923" rel="nofollow,noindex">@sevenson</a> 的文章 <a href="/misc/goto?guid=4959735949236597673" rel="nofollow,noindex">Separating Axis Theorem (SAT) Explanation</a> 。原文作者用的是ActionScript 3来编写算法，不过文中主要讲述的还是算法原理，我想一旦算法原理被我们掌握了，选择什么编程语言来实现算法都是次要的事情了。 本人并非英文专业，所以文中翻译得有不妥或疏漏之处，欢迎各位指正，谢谢！</p>    <p>正文如下：</p>    <p><img src="https://simg.open-open.com/show/787aaf6f9ec9e880552b9eb82ceef3a1.jpg"></p>    <p>分离轴定理（英文简称SAT）是一项用于检测凸多边形碰撞的技术。</p>    <p>我绝不是这个方面的专家，但当检测碰撞的需求出现在我面前之后，我做了大量的阅读并最终在ActionScript 3中实现了它。</p>    <p>我想，我应该把我所学到的分享给大家，希望大家不会在这方面被坑得很惨：）</p>    <p>当我发现我需要在flash中检测多边形碰撞时，我碰巧地遇到了一个叫“分离轴定理”的方法。但唯一的问题是，为了真正地掌握它，我可费了不少功夫。</p>    <p>在阅读了大量有关碰撞检测的资料，并参看了一些代码示例后，这个方法总算被我领悟了。</p>    <p>为了帮助其他那些不精通数学的开发者，我想我应该写下这一篇能快速阐明这个算法工作原理的简短介绍。我还在下文引入了一个使用分离轴定理实现的demo，以及供大家下载并使用的ActionScript 3源代码。 <strong>（译者：demo和源代码请到原文中查看和下载）</strong></p>    <p>注意：分离轴定理需要一点数学向量的知识，所以在深究这个算法前，你最好复习一下这方面的内容。</p>    <h2>算法简述</h2>    <p>从根本上来讲，分离轴定理（以及其他碰撞算法）的用途就是去检测并判断两个图形之间是否有间隙。分离轴定理中用到的方法使算法本身显得十分独特。</p>    <p>我所听到过分离轴定理的最好类比方式是这样的：</p>    <p>假想你拿一个电筒从不同的角度照射到两个图形上，那么会有怎样的一系列的阴影投射到它们之后的墙壁上呢？</p>    <p><img src="https://simg.open-open.com/show/cb2ed2fa8f31a14d16b31b3d1da1a11f.jpg"></p>    <p>如果你用这个方式从每一个角度上对这两个图形进行处理，并都找不到任何的间隙，那么这两个图形就一定接触。如果你找到了一个间隙，那么这两个图形就显而易见地没有接触。</p>    <p>从编程的角度来讲，从每个可能的角度上去检测会使处理变得十分密集。不过幸运的是，由于多边形的性质，你只需要检测其中几个关键的角度。</p>    <p>你需要检测的角度数量就正是这个多边形的边数。也就是说，你所需检测的角度最大数量就是你要检测碰撞的两个多边形边数之和。举个例子，两个五边形就需要检测10个角度。</p>    <p><img src="https://simg.open-open.com/show/fa90def5f98b8db6bc6603d9369860b3.jpg"></p>    <h2>如何在代码中实现</h2>    <p>这是一个简易但比较啰嗦的方法，以下是基本的步骤：</p>    <p>步骤一：从需要检测的多边形中取出一条边，并找出它的法向量（垂直于它的向量），这个向量将会是我们的一个“投影轴”。</p>    <p><img src="https://simg.open-open.com/show/620a956a851bb8376643fafb81a85564.jpg"></p>    <p>步骤二：循环获取第一个多边形的每个点，并将它们投影到这个轴上。（记录这个多边形投影到轴上的最高和最低点）</p>    <p><img src="https://simg.open-open.com/show/018ac3be94518427046c1a84f8aff89b.jpg"></p>    <p>步骤三：对第二个多边形做同样的处理。</p>    <p><img src="https://simg.open-open.com/show/ce3bd5f08a2c1d1beba6c2bedd0f941f.jpg"></p>    <p>步骤四：分别得到这两个多边形的投影，并检测这两段投影是否重叠。</p>    <p><img src="https://simg.open-open.com/show/9f333bc7d72f0424d644ebdd064d8299.jpg"></p>    <p>如果你发现了这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的。</p>    <p>这个算法基本就是如此的。</p>    <p>顺带提一下，如果你记录了哪个轴上的投影重叠值最小（以及重叠了多少），那么你就能用这个值来分开这两个图形。</p>    <h2>那么如何处理圆呢？</h2>    <p>在分离轴定理中，检测圆与检测多边形相比，会有点点奇异，但仍然是可以实现的。</p>    <p>最值得注意的是，圆是没有任何的边，所以是没有明显的用于投影的轴。但它有一条“不是很明显的”的投影轴。这条轴就是途经圆心和多边形上离圆心最近的顶点的直线。</p>    <p><img src="https://simg.open-open.com/show/f609c4a6d5eed7111237ff38cc86698b.jpg"></p>    <p>在这以后就是按套路遍历另一个多边形的每条投影轴，并检测是否有投影重叠。</p>    <p>噢，对了，万一你想知道如何把圆投影到轴上，那你只用简单地把圆心投影上去，然后加上和减去半径就能得到投影长度了。</p>    <h2>优点与不足</h2>    <p>和其他的碰撞检测技术一样，分离轴定理算法有它自己的优点和不足。以下是其一些优点和不足的简要概述：</p>    <h2>优点</h2>    <p>（译者：原来老外也喜欢先谈优点啊～>～）</p>    <ul>     <li>分离轴定理算法十分得快——它完美地使用了基本的数学向量知识。只要间隙一旦被检测出来，那么你就能马上得出结果，消除不必要的运算。</li>     <li>分离轴定理算法十分得准——至少据我所知是这样的。（译者：突然感觉作者好不靠谱啊，囧……）</li>    </ul>    <h2>不足</h2>    <ul>     <li>分离轴定理算法只适用于凸多边形——复杂的图形（译者：指的是凹多边形，比如五角星）无法使用此方法，除非你把它们分成一些小的凸多边形，然后依次检验这些小的多边形。</li>     <li>分离轴定理算法无法告诉你是那条边发生的碰撞——仅仅是告诉你重叠了多少和分开它们所需的最短距离。</li>    </ul>    <p>可能这个算法会有更多优点和不足之处，但是我想这应该是最主要的几个了。</p>    <h2>总结</h2>    <p>我希望这篇文章能帮助你了解到分离轴定理算法。我已经尽可能地不提供过多的信息并讲解得十分简明了。（我绝不是数学方面的专家，所以如果我遗漏了什么，我深表歉意）</p>    <p>以下是一些帮助我理解分离轴定理算法的页面：</p>    <ul>     <li><a href="/misc/goto?guid=4959735949319683318" rel="nofollow,noindex">harverycartel.org</a> ——有更多详细的表述以及很多很酷的示例。我在这个页面上学到了很多。</li>     <li><a href="/misc/goto?guid=4959735949399377152" rel="nofollow,noindex">GPWiki.org</a> ——有不错的讲解和代码示例，我用这些代码作为编写自己代码的基础。</li>     <li><a href="/misc/goto?guid=4959735949491980761" rel="nofollow,noindex">Tony Pa</a> ——向量教程，学习向量的不错资源。</li>     <li><a href="/misc/goto?guid=4959735949573024892" rel="nofollow,noindex">GameDev.net forum</a> ——一个论坛成员写的分离轴定理碰撞检测系统，带给了我一些计算方面的想法。</li>    </ul>    <p>以下是译者补充的内容</p>    <p>我将文中的算法用JavaScript实现了一遍，大家有兴趣的话，可以到下面提供的链接中下载源代码或查看在线demo。</p>    <h3><a href="/misc/goto?guid=4959735949657668387" rel="nofollow,noindex">源代码下载</a></h3>    <h3><a href="/misc/goto?guid=4959735949744089005" rel="nofollow,noindex">查看在线Demo</a></h3>    <p> </p>    <p>来自：http://blog.csdn.net/yorhomwang/article/details/54869018</p>    <p> </p>