CN108714303A - 碰撞检测方法，设备及计算机可读存储介质 - Google Patents

Abstract

本发明实施例公开了碰撞检测方法，设备及计算机可读存储介质，其中方法包括：确定第一碰撞体和第二碰撞体所属子区域；所述第一碰撞体和/或所述第二碰撞体能够到达的区域为目标区域，所述子区域由所述目标区域拆分得到；在所述第一碰撞体所属的子区域与所述第二碰撞体所属的子区域相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。通过确定碰撞体的所属的区域，可以排除碰撞体不在同一个区域中的时候进行碰撞检测的情况，因此可以避免大量非必要的碰撞检测，因此可以降低碰撞检测的计算量，提高了碰撞检测的效率。

Description

碰撞检测方法，设备及计算机可读存储介质

技术领域

本发明涉及互联网技术领域，尤其涉及一种碰撞检测方法，设备及计算机可读存储介质。

背景技术

碰撞检测要求碰撞体在场景中可以平滑移动，同时还要做到足够精确和稳定防止碰撞体穿透/交叠。碰撞检测效果较好的情况下不易注意到，因为碰撞本身符合日常生活中的常识；如果效果较差容易被发现，例如碰撞体被卡住或者碰撞体之间穿透的情况。

目前的碰撞检测分为离散点的碰撞检测和连续碰撞检测(continuous collisiondetection，CCD)。其中，离散点的碰撞检测在当检测到碰撞时两个碰撞体已经发生了交迭，需要将交迭的对象分开并按合理的方式运动较为繁琐。连续碰撞检测较为自然，容易避免物体发生交迭或者穿越，但是实现非常复杂，运算开销也很大，所以目前的物理的碰撞检测引擎还是采用了基于离散点的碰撞检测，为了避免物体交迭过深或者彼此穿越，大多采用比较小的模拟步长。但是采用物理引擎以及较小模拟步长进行碰撞检测计算量大，导致碰撞检测效率较低。

发明内容

本发明实施例公开了一种碰撞检测方法，设备及存储介质，用于降低计算量，提高碰撞检测的效率。

本发明实施例第一方面提供了一种碰撞检测方法，包括：

确定第一碰撞体和第二碰撞体所属子区域；所述第一碰撞体和/或所述第二碰撞体能够到达的区域为目标区域，所述子区域由所述目标区域拆分得到；

在所述第一碰撞体所属的子区域与所述第二碰撞体所属的子区域相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

在本实施例中，上述该目标区域通常可以是指显示区域，或者，游戏画面中碰撞体的活动区域。

第二方面本发明实施例还提供了一种碰撞检测设备，包括：

区域确定单元，用于确定第一碰撞体和第二碰撞体所属区域；

碰撞检测单元，用于在所述第一碰撞体所属区域与所述第二碰撞体所属区域相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

在一个可能的实现方式中，所述第一碰撞体和/或所述第二碰撞体能够到达的区域作为目标区域，所述目标区域被划分为子区域；所述目标区域作为树形数据结构的根节点，所述子区域作为所述树形数据结构的非根节点；在所述树形数据结构中，子节点的区域总和等于父节点的区域，且子节点区域之间不交叠；

所述区域确定单元，具体用于使用第一碰撞体和第二碰撞体的位置信息查询所述树形数据结构，确定所述第一碰撞体和所述第二碰撞体对应的节点；

所述碰撞检测单元，具体用于在所述第一碰撞体对应的节点与所述第二碰撞体对应的节点相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

在一个可能的实现方式中，在二维场景下，所述树形数据结构中的叶子节点对应的子区域的面积大于所述第一碰撞体和所述第二碰撞体中面积较大者的面积；或者，在三维场景下，所述树形数据结构中的叶子节点对应的子区域的体积大于所述第一碰撞体和所述第二碰撞体中体积较大者；

或者，

在二维场景下，所述树形数据结构中的叶子节点对应的子区域的面积小于所述第一碰撞体和所述第二碰撞体面积之和；或者，在三维场景下，所述树形数据结构中的叶子节点对应的子节点的体积小于能容纳所述第一碰撞体和所述第二碰撞体的最小体积。

在一个可能的实现方式中，若使用所述第一碰撞体的位置信息查询所述数据结构，确定所述第一碰撞体对应的节点个数大于或等于两个；则所述第一碰撞体对应的节点与所述第二碰撞体对应的节点相同包括：

所述第一碰撞体对应的任意一个节点与所述第二碰撞体对应的节点相同。

在一个可能的实现方式中，所述碰撞检测单元，具体用于若所述第一碰撞体为运动物体，第一运动轨迹区域与所述第二碰撞体有图形交叠，则确定发生碰撞；所述第一运动轨迹为所述第一碰撞体在相邻两帧图像中经过的运动轨迹区域。

在一个可能的实现方式中，所述第一运动轨迹为所述第一碰撞体在相邻两帧图像中经过的运动轨迹区域包括：

所述第一运动轨迹为所述第一碰撞体的投影点分别在所述相邻两帧图像中的位置形成的封闭区域。

在一个可能的实现方式中，所述碰撞检测设备还包括：

位置确定单元，用于在确定发生碰撞之后，确定碰撞位置，所述碰撞位置为所述第一碰撞体等效点在所述第一碰撞体运动方向上与所述第二碰撞体外边缘的交点；

反射确定单元，用于确定反射速度向量，所述反射速度向量为所述第一碰撞体的速度向量与所述碰撞位置的碰撞法向量的乘积。

三方面本发明实施例还提供了一种碰撞检测设备，包括处理器、输入设备、输出设备和存储器，所述处理器、输入设备、输出设备和存储器相互连接，其中，所述存储器用于存储计算机程序，所述计算机程序包括程序指令，所述处理器被配置用于调用所述程序指令，执行本发明实施例提供的任一项所述的方法。

第四方面本发明实施例还提供了一种计算机可读存储介质，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行本发明实施例提供的任一项所述的方法。

第五方面本发明实施例还提供了一种计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行本发明实施例提供的任一项所述的方法。

实施本发明实施例，具有如下有益效果：通过确定碰撞体的所属的区域，可以排除碰撞体不在同一个区域中的时候进行碰撞检测的情况，因此可以避免大量非必要的碰撞检测，因此可以降低碰撞检测的计算量，提高了碰撞检测的效率。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍。

图1为本发明实施例提供的方法流程示意图；

图2为本发明实施例二维区域划分示意图；

图3为本发明实施例三维区域划分示意图；

图4A为本发明实施例二维区域划分示意图；

图4B为本发明实施例四叉树结构示意图；

图4C为本发明实施例二维区域划分与四叉树结合的示意图；

图5A为本发明实施例二维区域划分示意图；

图5B为本发明实施例二叉树结构示意图；

图6为本发明实施例碰撞体对应节点的示意图；

图7A为本发明实施例运动碰撞检测结构示意图；

图7B为本发明实施例轨迹计算的示意图；

图8A为本发明实施例碰撞检测示意图；

图8B为本发明实施例碰撞检测示意图；

图9为本发明实施例一个应用场景的示意图；

图10A为本发明实施例基于距离的碰撞检测示意图；

图10B为本发明实施例基于距离的碰撞检测示意图；

图11为本发明实施例设备结构示意图；

图12为本发明实施例设备结构示意图；

图13为本发明实施例应用环境示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。

如图1所示，是本发明实施例提供的一种碰撞检测方法，本实施例方法执行主体可以是需要执行碰撞检测的设备，例如：终端设备，服务器等，具体方法流程包括：

101：确定第一碰撞体和第二碰撞体所属子区域；上述第一碰撞体和/或上述第二碰撞体能够到达的区域为目标区域，上述子区域由上述目标区域拆分得到；

上述“第一”和“第二”只是为了区分两个不同的碰撞体，不应理解具有其他技术含义。碰撞体是在执行碰撞检测时，可能发生碰撞的对象。例如：游戏画面中的人物、障碍物等。碰撞体应该是不能相互穿透的，因此也可以称为刚体，碰撞刚体等。

上述目标区域是碰撞体可能到达的区域的总和，例如整个游戏画面。如果本发明实施例应用在自动驾驶、机器人等领域，那么目标区域可以是车辆和机器人能够到达的全部区域，那么子区域是全部区域被拆分后的更小的区域。另外，这里的目标区域和子区域，均可以是二维平面的，也可以是三维立体的，本发明实施例不作唯一性限定。另外，子区域还可以再拆分为更小的子区域。

如图2和图3所示，分别为二维和三维场景下，假定最左边部分示意了游戏场景的整体画面，中间部分示意了拆分后的子区域，最右边部分的则示意了子区域被再拆分。子区域被拆分的层级本发明实施例不予限定。

在一个可能的实现方式中，还提供了以树形数据结构来存储以上子区域的实现方式，具体如下：上述目标区域为树形数据结构的根节点，上述子区域为上述树形数据结构的非根节点；在上述树形数据结构中，子节点的区域总和等于父节点的区域，且子节点区域之间不交叠；上述确定第一碰撞体和第二碰撞体所属子区域包括：使用第一碰撞体和第二碰撞体的位置信息查询上述树形数据结构，确定上述第一碰撞体和上述第二碰撞体对应的节点。

采用树形数据结构存储子区域可以更好地将区域包含的空间组织起来，为后续判断碰撞体位置以及是否可能碰撞提供便利。

如图4A、图4B以及图4C所示，其中图4A为图2目标区域以及子区域增加编号后的示意图，图4B为树形数据结构的示意图，图4B中节点的编号与图4A中的目标区域或子区域一一对应，图4C则是图4A和图4B叠加示意图。该树形数据结构是四叉树，在实际应用中，树形数据结构也可以是二叉树，如图5A和5B所示，或者其他树形数据结构，本发明实施例不作唯一性限定。三维场景与以上原理相同，本实施例不再赘述。

在一个可能的实现方式中，还提供了节点区域大小的设定方式，具体如下：在二维场景下，上述树形数据结构中的叶子节点对应的子区域的面积大于上述第一碰撞体和上述第二碰撞体中面积较大者的面积；或者，在三维场景下，上述树形数据结构中的叶子节点对应的子区域的体积大于上述第一碰撞体和上述第二碰撞体中体积较大者；

或者，

在二维场景下，上述树形数据结构中的叶子节点对应的子区域的面积小于上述第一碰撞体和上述第二碰撞体面积之和；或者，在三维场景下，上述树形数据结构中的叶子节点对应的子节点的体积小于能容纳上述第一碰撞体和上述第二碰撞体的最小体积。

以上两种实现方式，提供了节点区域大小的设定方式，可以适应于不同应用场景下碰撞体的大小；使用合适节点区域大小，可以一方面减少树形数据结构的数据量从而提高效率，另一方面又可以减少碰撞体归属于过多子节点的情况导致后续判断计算量大的问题。

以图6为例，图6为图5A增加碰撞体A和碰撞体B后的示意图。基于图6所示，假定图6中只有两层树形数据结构，那么依据图5B的上面两层可知，碰撞体A和碰撞体B均会对应到“11”这个节点；如果图6有三层树形数据结构，那么依据图5B完整的树形数据结构，那么碰撞体A对应到节点“111”，碰撞体B对应到节点“111”和“112”。依据以上说明可知，如果叶子节点区域太小，会增加节点对应到多个区域的可能性；而叶子节点过大，则会有更多碰撞体对应到同一个节点的情况，那么会有更多的碰撞检测需要执行。以上实施例通过限制叶子节点的区域大小，可以一方面减少不必要的碰撞检测，另一方面又可以减少区域划分过小碰撞体过多跨节点的情况发生。

102：在上述第一碰撞体所属的子区域与上述第二碰撞体所属的子区域相同的情况下，检测上述第一碰撞体与上述第二碰撞体之间是否发生碰撞。

通过确定碰撞体的所属的区域，可以排除碰撞体不在同一个区域中的时候进行碰撞检测的情况，因此可以避免大量非必要的碰撞检测，因此可以降低碰撞检测的计算量，提高了碰撞检测的效率。

基于前文以树形数据结构来存储目标区域和子区域的实现方案，上述第一碰撞体所属的子区域与上述第二碰撞体所属的子区域相同包括：

上述第一碰撞体对应的节点与上述第二碰撞体对应的节点相同。

本实施例使用树形数据结构存储子区域，每个树形数据结构的节点可以使用坐标系参数来表示其对应的区域，使用碰撞体的坐标查询树形数据结构，则可以快速确定碰撞体所属的区域。仅需确定碰撞体对应节点相同即可确定碰撞体所属子区域相同，从而初步确定可能发生碰撞，效率较高。

在一个可能的实现方式中，基于前文说明，子区域划分以后碰撞体是有可能跨子区域的，如图6所示，本发明实施例提供了此种情况下的处理方式，如下：若使用上述第一碰撞体的位置信息查询上述数据结构，确定上述第一碰撞体对应的节点个数大于或等于两个；则上述第一碰撞体对应的节点与上述第二碰撞体对应的节点相同包括：

上述第一碰撞体对应的任意一个节点与上述第二碰撞体对应的节点相同。

本实施例仅需确定碰撞体对应节点中有一个相同即可确定碰撞体所属子区域相同，从而初步确定可能发生碰撞，效率较高。

在一个可能的实现方式中，本发明实施例还提供了运动过程中碰撞检测的实现方式，具体如下：若上述第一碰撞体为运动物体，上述检测上述第一碰撞体与上述第二碰撞体之间是否发生碰撞，包括：

若第一运动轨迹区域与上述第二碰撞体有图形交叠，则确定发生碰撞；上述第一运动轨迹为上述第一碰撞体在相邻两帧图像中经过的运动轨迹区域。

本实施例适较为应于快速运动的碰撞体之间的碰撞检测，防止出现泄露。

如图7A所示，其中碰撞体A在两个时刻分别对应到A1和A2，假定碰撞体B没有位置变化，那么粗体区域为运动轨迹区域，由于该这个运动轨迹区域与碰撞体B有图形交叠，那么可以确定发生了碰撞。

在一个可能的实现方式中，基于前文图7A的说明，本实施例还提供了第一运动轨迹的获得方式，具体如下：上述第一运动轨迹为上述第一碰撞体在相邻两帧图像中经过的运动轨迹区域包括：

上述第一运动轨迹为上述第一碰撞体的投影点分别在上述相邻两帧图像中的位置形成的封闭区域。

本实施例采用投影点的方式可以更为快速地获得运动轨迹。

如图7B所示，为图7A的局部放大图，假定矩形碰撞体是水平方向，那么封闭矩形区域的顶点坐标：X＝first_x+r*cosA，Y＝first_y+r*sinA；其中，first_x和first_y分别为圆形碰撞体的前一帧的横坐标和纵坐标，即第一坐标点，r为圆形碰撞体的半径；A为夹角，夹角A的正弦值和余弦值可以可以根据三角函数技术，如图7B中，圆形碰撞体后一帧的横坐标和纵坐标分别为：second_x和second_y，即第二坐标点，那么可以构造出两条直角边，分别为：second_x-first_x和second_y-first_y，那么cosA和sinA可以计算获得。

在一个可能的实现方式中，本发明实施例还提供了回滚碰撞处理的方案，具体如下：在确定发生碰撞之后，上述方法还包括：

确定碰撞位置，上述碰撞位置为上述第一碰撞体等效点在上述第一碰撞体运动方向上与上述第二碰撞体外边缘的交点；

确定反射速度向量，上述反射速度向量为上述第一碰撞体的速度向量与上述碰撞位置的碰撞法向量的乘积。

如图8A和图8B所示，其中图8B为图8A碰撞一的局部放大图，碰撞法向量是一条垂直于碰撞平面，只有方向没有大小的向量。在8B所示，可以根据碰撞角度来确定碰撞平面，再根据前后两帧位置和碰撞平计算碰撞法向量。圆形碰撞体前后两帧靠近碰撞平面的方向的垂直分量的反向就是碰撞法向量的方向。碰撞前速度乘以碰撞法向量，得到碰撞后的反射速度。在本实施例中，没有考虑碰撞后的衰减，因此碰撞前后速度的快慢没有发生变化，碰撞前后的方向以法向量为呈轴对称。如果考虑碰撞后的衰减，可以降低反射速度以及增大反射角度。

以下实施例，将以超文本标记语言第5版(hyper text markup language 5，Html，HTML5)游戏为例进行举例说明，本实施例基于简单模型间快速运动时的刚体碰撞逻辑应用到游戏中。通过判断模型间的最短距离以及上一帧的距离，判断运动物体是否已经穿过碰撞物或未到达碰撞物。如果已经穿过碰撞物，则通过计算移出碰撞刚体并改变运动系数；如果还未碰撞，则预演需要碰撞的时机，可以提前做好准备。

如图9所示，是某游戏的界面，该某游戏的基本玩法是：下方的浮冰板子接住企鹅后，将企鹅反弹回海中，碰到上方的白色冰山即可得分；如果下方的浮冰板子没有接住，企鹅掉下去，游戏结束；白色冰山会随着时间缓慢下降，如果冰山越过大海，砸到了浮冰板子，游戏也结束了。在该应用中，碰撞体包含：上面的冰山、中间的企鹅、下面的浮冰板子。

本发明实施例首先将可能发生碰撞的物体(包括企鹅、浮冰板子、冰山)构造出与其形状和尺寸吻合的碰撞体，然后在每一帧游戏逻辑中，分析这些碰撞体的交叠状态以及他们的运动轨迹，判断他们是否发生了碰撞，如果发生了碰撞，本发明实施例可以根据碰撞角度和碰撞速度，计算出碰撞体的回滚位置和碰撞后的速度，以更新碰撞体的运动系数，从而驱动游戏进程。

具体碰撞检测包含如下几个方面：

1、场景树细化场景：

用四叉树将游戏场景细化，一棵四叉树从一个包围整个世界的节点开始，然后沿着X,Y轴分割。可以参阅图4A～图4C所示。四叉树是树形数据结构的一种，其特点是父节点包含4个子节点。

假定图4A最左侧为图9的整个游戏界面，那么图4A的中间右边的分割图，则是对游戏场景进行分割，分割过程如图4C所示，形成的四叉树如图4B所示。游戏场景被分成4个子场景，子场景又分成四个更小的子场景，以此类推，整个大场景被一颗四叉树表示。由图4B可知，四叉树的叶子节点表示场景的最小粒度，并且都可以由深度遍历访问到。

本发明实施例在碰撞检测前，可以将每个碰撞体划分到一个或多个四叉树的叶子节点中，如果碰撞体恰好处在多个叶子节点的交界处，那它属于这多个叶子节点。因为不在同一个叶子节点的碰撞体相距甚远，所以场景树划分后，在碰撞检测时，可以仅检测属于同一个树节点的碰撞体是否发生碰撞。

2、基于距离的运动碰撞检测：

2.1：交叠碰撞检测：

具体是如果两个碰撞体图形相交了，即发生交叠，则判断发生了碰撞。

如图10A和图10B所示，分别是两个矩形碰撞体发生交叠，和矩形碰撞体与圆形碰撞体发生交叠。

2.2、运动中的碰撞检测：

刚体(即碰撞体)处在运动中，相邻帧之间，速度比较快的刚体，可能会穿越其他碰撞体，这种情况会导致交叠碰撞检测法漏测。刚体在理想状态下是指在运动中和受力作用后，形状和大小不变，而且内部各点的相对位置不变的物体；在实际生活中刚体在受力后会有形状大小的变化，在碰撞检测的应用中，刚体是指那些发生碰撞不能相互穿越或重叠物体，也称为碰撞体，例如前文举例中的浮冰、企鹅。如图7A所示的情况。

针对图7B所示的这种情况，本发明实施例可以首先计算出圆形碰撞体的圆心在前后两帧的移动方向上的四个投影点，用这四个点画一个矩形，作为圆形碰撞体的运动轨迹，用这个矩形与其他碰撞体进行交叠碰撞检测，如果矩形与其他碰撞体有图形交叠，则判断发生了碰撞。

3、计算碰撞反弹速度和反弹位置：

如图8A所示为五种碰撞的可能性，分别为碰撞一至碰撞五。

在图8A所示的五种碰撞的可能性中，箭头表示的是圆形碰撞体的运动方向，即速度方向。可见，箭头方向发生了改变(折射)，这是由于碰撞导致的反弹。其中箭头第一段是指运动方向折射前的部分，箭头第二段是指折射后的部分，例如：碰撞体三，A部分为箭头第一段，B部分为箭头第二段。

箭头第一段：圆形碰撞体碰撞时的速度方向；

箭头第二段：圆形碰撞体碰撞后的速度方向；

远离矩形碰撞体的虚框圆：上一帧圆形碰撞体的位置；如碰撞三种的C位置。

实心圆：当前一帧圆形碰撞体的位置；

靠近矩形碰撞体的虚框圆：碰撞后圆形碰撞体的位置；

xMin:：矩形碰撞体最左边的x位置；

xMax：矩形碰撞体最右边的x位置；

yMin：矩形碰撞体最下面的y位置；

yMax：矩形碰撞体最上面的y位置；

r为圆形碰撞体的半径；

y＝yMax+r、y＝yMin-r，x＝xMin-r以及x＝yMax+r分别是矩形碰撞体外延矩形，圆形碰撞体回滚时圆形碰撞体的圆心会落在这些直线上。

3.1，回滚方案：

回滚(Rollback)指的是程序或数据处理错误，将程序或数据恢复到上一次正确状态的行为。在碰撞检测中是指碰撞体发生碰撞如果按照原运动方向会发生穿越或重叠的情况，因此需要将碰撞体的相对位置恢复到碰撞发生时碰撞体之间碰撞的位置。

如图8B所示为图8A中碰撞一的局部放大图，在圆形碰撞体与板子发生碰撞时，本发明实施例可以精确计算出碰撞瞬间圆形碰撞体的精确位置，并回滚圆形碰撞体的位置，尽量接近现实碰撞效果。

具体计算方式是：在图8B中，以圆形碰撞体的圆心为等效点，回滚位置是圆心移动到的位置，该位置是：圆心在运动方向上的直线与y＝yMax+r的交点。

其他碰撞情况与以上计算方式原来是相同的，本实施例不再赘述。

3.2，反射速度：

碰撞法向量是一条垂直于碰撞平面，只有方向没有大小的向量。如图8B所示，本发明实施例根据碰撞角度来确定碰撞平面，再根据前后两帧位置和碰撞平计算碰撞法向量。圆形碰撞体前后两帧靠近碰撞平面的方向的垂直分量的反向就是碰撞法向量的方向。碰撞前速度乘以碰撞法向量，得到碰撞后的反射速度。在本实施例中，没有考虑碰撞后的衰减，因此碰撞前后速度的快慢没有发生变化，碰撞前后的方向以法向量为呈轴对称。

本实施例介绍的以上碰撞检测可以应用于HTML5，抽象定义了碰撞体，碰撞检测算法，以及碰撞事件处理，为游戏开发人员提供了方便且高效的碰撞系统。该系统通过判断碰撞体之间的最短距离以及上一帧的距离，判断运动中的碰撞体是否已经穿过碰撞物或未到达碰撞物的碰撞系统。如果已经穿过碰撞物，则通过函数计算，回滚碰撞体位置并改变运动系数。相比于静态分析显示对象之间交叠状态，充分考虑运动中的物体碰撞的多样性，避免漏测的情况。每帧检测对应相同叶子节点的碰撞体的碰撞状态，不必检测相距甚远的碰撞体，减少不必要的性能开销。

本发明实施例还提供了一种碰撞检测设备，如图11所示，包括：

区域确定单元1101，用于确定第一碰撞体和第二碰撞体所属区域；

碰撞检测单元1102，用于在上述第一碰撞体所属区域与上述第二碰撞体所属区域相同的情况下，检测上述第一碰撞体与上述第二碰撞体之间是否发生碰撞。

在一个可能的实现方式中，上述第一碰撞体和/或上述第二碰撞体能够到达的区域作为目标区域，上述目标区域被划分为子区域；上述目标区域作为树形数据结构的根节点，上述子区域作为上述树形数据结构的非根节点；在上述树形数据结构中，子节点的区域总和等于父节点的区域，且子节点区域之间不交叠；

上述区域确定单元1101，具体用于使用第一碰撞体和第二碰撞体的位置信息查询上述树形数据结构，确定上述第一碰撞体和上述第二碰撞体对应的节点；

上述碰撞检测单元1102，具体用于在上述第一碰撞体对应的节点与上述第二碰撞体对应的节点相同的情况下，检测上述第一碰撞体与上述第二碰撞体之间是否发生碰撞。

在一个可能的实现方式中，在二维场景下，上述树形数据结构中的叶子节点对应的子区域的面积大于上述第一碰撞体和上述第二碰撞体中面积较大者的面积；或者，在三维场景下，上述树形数据结构中的叶子节点对应的子区域的体积大于上述第一碰撞体和上述第二碰撞体中体积较大者；

或者，

在二维场景下，上述树形数据结构中的叶子节点对应的子区域的面积小于上述第一碰撞体和上述第二碰撞体面积之和；或者，在三维场景下，上述树形数据结构中的叶子节点对应的子节点的体积小于能容纳上述第一碰撞体和上述第二碰撞体的最小体积。

在一个可能的实现方式中，若使用上述第一碰撞体的位置信息查询上述数据结构，确定上述第一碰撞体对应的节点个数大于或等于两个；则上述第一碰撞体对应的节点与上述第二碰撞体对应的节点相同包括：

上述第一碰撞体对应的任意一个节点与上述第二碰撞体对应的节点相同。

在一个可能的实现方式中，上述碰撞检测单元1102，具体用于若上述第一碰撞体为运动物体，第一运动轨迹区域与上述第二碰撞体有图形交叠，则确定发生碰撞；上述第一运动轨迹为上述第一碰撞体在相邻两帧图像中经过的运动轨迹区域。

在一个可能的实现方式中，上述第一运动轨迹为上述第一碰撞体在相邻两帧图像中经过的运动轨迹区域包括：

上述第一运动轨迹为上述第一碰撞体的投影点分别在上述相邻两帧图像中的位置形成的封闭区域。

在一个可能的实现方式中，如图11所示，上述碰撞检测设备还包括：

位置确定单元1103，用于在确定发生碰撞之后，确定碰撞位置，上述碰撞位置为上述第一碰撞体等效点在上述第一碰撞体运动方向上与上述第二碰撞体外边缘的交点；

反射确定单元1104，用于确定反射速度向量，上述反射速度向量为上述第一碰撞体的速度向量与上述碰撞位置的碰撞法向量的乘积。

参见图12，图12是本申请另一实施例提供的一种图像合成设备的示意框图。如图所示的本实施例中的图像合成设备可以包括：一个或多个处理器1201；一个或多个输入设备1202，一个或多个输出设备1203和存储器1204。上述处理器1201、输入设备1202、输出设备1203和存储器1204通过总线12012连接。存储器1202用于存储计算机程序，该计算机程序包括程序指令，处理器1201用于执行存储器1202存储的程序指令。其中，处理器1201被配置用于调用该程序指令执行以下操作：

应当理解，在本申请实施例中，所称处理器1201可以是中央处理单元(CentralProcessing Unit，CPU)，该处理器还可以是其他通用处理器、数字信号处理器(DigitalSignal Processor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现成可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。

输入设备1202可以包括触控板、指纹采传感器(用于采集用户的指纹信息和指纹的方向信息)、麦克风等，输出设备1203可以包括显示器(LCD等)等。

该存储器1204可以包括只读存储器和随机存取存储器，并向处理器1201提供指令和数据。存储器1204的一部分还可以包括非易失性随机存取存储器。例如，存储器1204还可以存储设备类型的信息。

具体实现中，本申请实施例中所描述的处理器1201、输入设备1202、输出设备1203可执行本申请实施例提供的前述方法实施例中所描述的方法步骤，在此不再赘述。

本实施例中的处理器1201可以执行前述碰撞检测设备各单元的全部功能。

本发明实施例还提供了一种计算机可读存储介质，上述计算机存储介质存储有计算机程序，上述计算机程序包括程序指令，上述程序指令当被处理器执行时使上述处理器执行本发明实施例提供的任一项上述的方法。

本发明实施例还提供了一种计算机程序，上述计算机程序包括程序指令，上述程序指令当被处理器执行时使上述处理器执行本发明实施例提供的任一项上述的方法。

实施本发明实施例，具有如下有益效果：通过确定碰撞体的所属的区域，可以排除碰撞体不在同一个区域中的时候进行碰撞检测的情况，因此可以避免大量非必要的碰撞检测，因此可以降低碰撞检测的计算量，提高了碰撞检测的效率。

如图13所示，示出了本发明实施例提供的方法实施环境的示意图。该实施环境可以包括：终端11和服务器12。

其中，终端11安装有应用程序客户端，例如，游戏类应用程序客户端等。当该应用程序客户端启动后，可通过终端11从服务器12上获取该类应用程序的资源，该资源包括但不限于一些游戏需要的素材及数据等。终端11获取到资源后，可据此显示游戏界面，并通过该游戏界面展示一些信息。

实施时，图13所示的终端11可以是诸如手机、平板电脑、个人计算机等电子设备。服务器12可以是一台服务器，也可以是由多台服务器组成的服务器集群，或者是一个云计算服务中心。终端11与服务器12通过有线或无线网络建立通信连接。

本发明实施例的碰撞检测方法可以应用在终端11也可以应用在服务器12，具体方法内容参考前文方法实施例，执行方法的终端11或者服务器12的内部结构参考前文装置实施例，在此不再赘述。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，"计算机可读介质"可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印上述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得上述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，上述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。上述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。

Claims (15)

1.一种碰撞检测方法，其特征在于，包括：

确定第一碰撞体和第二碰撞体所属子区域；所述第一碰撞体和/或所述第二碰撞体能够到达的区域为目标区域，所述子区域由所述目标区域拆分得到；

在所述第一碰撞体所属的子区域与所述第二碰撞体所属的子区域相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

2.根据权利要求1所述方法，其特征在于，所述目标区域为树形数据结构的根节点，所述子区域为所述树形数据结构的非根节点；在所述树形数据结构中，子节点的区域总和等于父节点的区域，且子节点区域之间不交叠；

所述确定第一碰撞体和第二碰撞体所属子区域包括：

使用第一碰撞体和第二碰撞体的位置信息查询所述树形数据结构，确定所述第一碰撞体和所述第二碰撞体对应的节点；

所述第一碰撞体所属的子区域与所述第二碰撞体所属的子区域相同包括：

所述第一碰撞体对应的节点与所述第二碰撞体对应的节点相同。

3.根据权利要求2所述方法，其特征在于，

在二维场景下，所述树形数据结构中的叶子节点对应的子区域的面积大于所述第一碰撞体和所述第二碰撞体中面积较大者的面积；或者，在三维场景下，所述树形数据结构中的叶子节点对应的子区域的体积大于所述第一碰撞体和所述第二碰撞体中体积较大者。

4.根据权利要求2所述方法，其特征在于，

在二维场景下，所述树形数据结构中的叶子节点对应的子区域的面积小于所述第一碰撞体和所述第二碰撞体面积之和；或者，在三维场景下，所述树形数据结构中的叶子节点对应的子节点的体积小于能容纳所述第一碰撞体和所述第二碰撞体的最小体积。

5.根据权利要求2至4任意一项所述方法，其特征在于，若使用所述第一碰撞体的位置信息查询所述数据结构，确定所述第一碰撞体对应的节点个数大于或等于两个；则所述第一碰撞体对应的节点与所述第二碰撞体对应的节点相同包括：

所述第一碰撞体对应的任意一个节点与所述第二碰撞体对应的节点相同。

6.根据权利要求1至4任意一项所述方法，其特征在于，若所述第一碰撞体为运动物体，所述检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞，包括：

若第一运动轨迹区域与所述第二碰撞体有图形交叠，则确定发生碰撞；所述第一运动轨迹为所述第一碰撞体在相邻两帧图像中经过的运动轨迹区域。

7.根据权利要求6所述方法，其特征在于，所述第一运动轨迹为所述第一碰撞体在相邻两帧图像中经过的运动轨迹区域包括：

所述第一运动轨迹为所述第一碰撞体的投影点分别在所述相邻两帧图像中的位置形成的封闭区域。

8.根据权利要求6所述方法，其特征在于，在确定发生碰撞之后，所述方法还包括：

确定碰撞位置，所述碰撞位置为所述第一碰撞体等效点在所述第一碰撞体运动方向上与所述第二碰撞体外边缘的交点；

确定反射速度向量，所述反射速度向量为所述第一碰撞体的速度向量与所述碰撞位置的碰撞法向量的乘积。

9.一种碰撞检测设备，其特征在于，包括：

区域确定单元，用于确定第一碰撞体和第二碰撞体所属子区域；所述第一碰撞体和/或所述第二碰撞体能够到达的区域为目标区域，所述子区域由所述目标区域拆分得到；

碰撞检测单元，用在所述第一碰撞体所属的子区域与所述第二碰撞体所属的子区域相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

10.根据权利要求9所述碰撞检测设备，其特征在于，所述目标区域为树形数据结构的根节点，所述子区域为所述树形数据结构的非根节点；在所述树形数据结构中，子节点的区域总和等于父节点的区域，且子节点区域之间不交叠；

所述区域确定单元，具体用于使用第一碰撞体和第二碰撞体的位置信息查询所述树形数据结构，确定所述第一碰撞体和所述第二碰撞体对应的节点；

所述碰撞检测单元，具体用于在所述第一碰撞体对应的节点与所述第二碰撞体对应的节点相同的情况下，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

11.根据权利要求9所述碰撞检测设备，其特征在于，

所述碰撞检测单元，具体用于若所述第一碰撞体为运动物体，第一运动轨迹区域与所述第二碰撞体有图形交叠，则确定发生碰撞；所述第一运动轨迹为所述第一碰撞体在相邻两帧图像中经过的运动轨迹区域。

12.根据权利要求10所述碰撞检测设备，其特征在于，

所述碰撞检测单元，具体用于若使用所述第一碰撞体的位置信息查询所述数据结构，确定所述第一碰撞体对应的节点个数大于或等于两个，所述第一碰撞体对应的任意一个节点与所述第二碰撞体对应的节点相同，检测所述第一碰撞体与所述第二碰撞体之间是否发生碰撞。

13.根据权利要求9至12任意一项所述碰撞检测设备，其特征在于，所述碰撞检测设备还包括：

位置确定单元，用于在确定发生碰撞之后，确定碰撞位置，所述碰撞位置为所述第一碰撞体等效点在所述第一碰撞体运动方向上与所述第二碰撞体外边缘的交点；

反射确定单元，用于确定反射速度向量，所述反射速度向量为所述第一碰撞体的速度向量与所述碰撞位置的碰撞法向量的乘积。

14.一种碰撞检测设备，包括处理器、输入设备、输出设备和存储器，所述处理器、输入设备、输出设备和存储器相互连接，其中，所述存储器用于存储计算机程序，所述计算机程序包括程序指令，所述处理器被配置用于调用所述程序指令，执行如权利要求1至8任一项所述的方法。

15.一种计算机可读存储介质，其特征在于，所述计算机存储介质存储有计算机程序，所述计算机程序包括程序指令，所述程序指令当被处理器执行时使所述处理器执行如权利要求1至8任一项所述的方法。