原文地址：http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/home.php
视频下载：http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/video.flv
文本格式：http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php
源码下载：http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/collisions.zip
第10课 碰撞检测
提示：这一课比较难！
碰撞检测问题
在视频游戏、模拟仿真和其他应用中经常需要在两个物体相互碰撞时发生一定的事件，比如使它们弹开或者停止。这就用到碰撞检测。碰撞检测的基本思想是计算在任何时刻某个物体将要碰撞的地点，这样可以用适当的方法来处理碰撞(intersection)。通常我们需要实时的处理，因此我们的解决方案需要快速。
这就使得碰撞检测变得很难。因为这个原因，在很多的测试版本或体验版本的游戏的demo中，碰撞检测度是很bug最多的地方，也是最容易出错的(buggy)。
另外，碰撞检测没有一个满意的答案(NP问题？)。这都将取决于你产生的问题。设计碰撞检测机制的关键因素包括：碰撞“通常”以什么方式何时产生，对于用户来说那些缺陷是致命的，那次碰撞是最重要的。特别的，如果只有主角的碰撞是重要的和所有的碰撞都有相同的地位的碰撞检测问题是非常不同的。
我只能涉及碰撞检测中的一部分技术。碰撞检测频繁使用将相近的物体打包的技巧。通常默认在每一帧中场景不会发生大的变化。你可以得到基于物体3维多边形的精确的碰撞检测，但是通常来说，最好使用一个或多个简单的诸如长方体、圆柱体和球体近似的模拟物体。另一个经常使用的技术是在使用一个潜在的可能耗时很长的碰撞检测之前使用一个快速但并不精确的(dirty)方法决定两个物体是否会碰撞。例如，在一个更加复杂的检测之前可以使用两个物体的外接球是否相交进行检测。
我们的问题
在众多的检测技术中，我将详细的讲解其中一个来给你一个碰撞检测策略的概念。首先，来看看我们的要解决的问题。下载并编译这个程序。我们有一个上面和下面显示的盒子；其他的面是不可见的。每次你按下空格键，将会随即的加入10个球在盒子中。他们将会模拟重力下降，也会彼此或者和墙弹开。
程序的基本思想是每隔10毫秒就更新小球的位置和速度，并检查碰撞让所有碰撞的球弹开，然后重复这个工作。我们将注意力集中于碰撞这个部分。
要找到所有的碰撞，我们需要检查每一对小球，看他们之间的距离是否小于他们的半径和。然而，当我们有300个小球时，虽然每次这其中只有很少部分会碰撞，我们每次仍然需要检查大概50,000对潜在的碰撞。或许有更快的方法。
一种方法是将立方体在每个维度上分为两半，变成8个小的立方体。然后计算每个小球在那个小的立方体中，然后在每隔小的立方体中检查每对小球的碰撞可能性(分而治之算法)。来看一下这个技术的2D等价模型。
如果要检查上图的每对小球的碰撞情况，我们需要检查105对小球。然而，如果在4个小的方格中检查每对小球，只需要3+3+15+10＝31对次的检查。
注意其中有两个小球分别出现在两个方格中。这在3维模型中也存在，但并不普遍。
我们已经提高了一点点的速度，但还可以更快。我们寻找一个立方体中潜在的碰撞的基本策略是将立方体分为8个小的立方体，然后在每个小的立方体中给出潜在的碰撞集合。对潜在的碰撞来说，我们将每对小球放入一个小的立方体中(8个小的立方体)。但为什么停止不前呢？我们还可以将小立方体继续划分，这样可以得到更少的检查次数。
我们可以无穷的细分，但是一段时间以后，这就没有什么帮助了。例如，如果立方体中只有非常少的球，假设为3个，直接检查所有的小球对将要比将立方体细分容易的多。另外，我们将立方体划分的越细，一个球在多个立方体中出现的概率会变大，这是不好的，因为这样会引起重复的小球对和否定的答案。因此，我们使用下面的策略：对于一个给定的立方体，如果有很多的小球在里面，就将其划分为8块，然后每个立方体各自找出潜在的碰撞。如果没有许多的小球，就直接检测。这导致一个树型结构；没个立方体是树中的一个节点，如果立方体被划分为更小的立方体，那么它将有8个孩子。这称之为“8叉树”(octree)，(二维的称之为4叉树)。下面是一个2维的树状结构：
通过继续细分方格，我们会继续减少检测的小球对，从31减少到15。
一旦立方体的长度接近小球的直径，继续划分将会导致大量的小球出现在多个立方体中。基于这个原因，我们限制树的深度。就是说，如果我们要细分一个立方体，但是如果这个立方体已经在树中的x深度，我们就不继续细分了。
还有一个事情：场景在每个时刻中变化的并不大。因此，与其不停的创建和销毁一棵八叉树，不如在程序开始的时候就创建一个，当一个球移动或者被创建的时候，只需要修改这棵树。现在我们不仅需要将一个包含太多小球的立方体划分为更小的立方体，同时还需要在小球数量太少时不进行细分。因此，无论什么时候，一个立方体多余x个小球时，我们就细分它(除非已经达到树的最大的深度)，当一个立方体小于y个小球时，不进行拆分。我们希望x将要比y稍微大一点，而不需要将一个立方体频繁的拆分。