[发明专利]一种基于包围盒树法的并行碰撞检测方法

摘要

本发明涉及一种基于包围盒树法的并行碰撞检测方法，在对两个物体做碰撞检测时，先增加包围盒的方法进行碰撞检测，如不发生碰撞，就无需做下一步检测，如果发生碰撞，则做两个物体精确碰撞检测。在对两个物体做精确碰撞检测时，引入并行的思想，实现了并行碰撞检测。由此将两个物体间的碰撞检测转化为系列四面体间的并行碰撞检测，在保证高精度的前提条件下，有效的满足了碰撞检测的实时要求，提高了检测效率，同时也解决了一般碰撞检测算法只适用于凸多面体的不足。

主权项

一种基于包围盒树法的并行碰撞检测方法，其特征在于，包括如下步骤：步骤(S1)：提供两个待检测是否发生碰撞的物体；步骤(S2)：建立每个所述物体整体的包围盒，所述包围盒作为所述物体的包围盒树的根节点；步骤(S3)：利用与局部坐标轴垂直的平面将所述包围盒划分成两个子包围盒，即左包围盒和右包围盒，以形成根节点的两个子节点，即左子节点和右子节点；步骤(S4)：对上述步骤得到的所述两个子节点分别递归地执行所述包围盒的分割过程，以得到最终的包围盒树，并且给定最大树深度和叶子节点所包含的几何元素的个数；步骤(S5)：将上述步骤得到的两个物体的所述包围盒树的当前节点两两之间进行检测，判断是否发生碰撞，若发生碰撞，执行步骤(S6)，否则执行步骤(S7)；步骤(S6)：若所述当前结点为叶子结点，记下该结点，返回，并检测是否发生碰撞；若所述当前结点不是叶子结点，则取所述当前结点的所有子结点作为所述包围盒树的当前结点，递归执行步骤(S5)；步骤(S7)：若所述当前结点无未检测的兄弟结点，表明未发生碰撞，记下所述当前结点后，返回；若仍有未检测的兄弟结点，表明发生碰撞，则依次将下所述兄弟结点作为所述包围盒树的当前结点；递归执行步骤(S5)。