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

摘要

本发明提供一种基于包围盒树的碰撞检测方法，从树根部出发向树枝最末端检测，该方法包含：步骤a：建立两个物体的包围盒树；步骤b：取两个物体的包围盒树的当前结点两两之间进行检测，判断是否发生碰撞，若发生碰撞，转向步骤c，否则，转向步骤d；步骤c：判断当前结点是否为叶子结点，若是，记下该结点，返回，并进行精确检确定是否真的发生碰撞。否则，取它所有子结点作为该树的当前结点，递归执行步骤b；步骤d：如果当前结点没有未检测的兄弟结点，则计算包含“最近距离”，“速度”，“是否碰撞”在内的节点信息，记下当前结点，返回；否则依次将下个兄弟结点作为该树的当前结点，递归执行步骤b。本发明还提供一种从树枝最末端出发向树根部检测的方法。

主权项

一种基于包围盒树的碰撞检测方法，从树根部出发向树枝最末端检测，其特征在于，该方法包含如下步骤：步骤a：建立两个物体的包围盒树；该步骤a具体包含：步骤a1：建立整个物体的包围盒，该包围盒作为该物体的包围盒树的根节点；步骤a2：利用与局部坐标轴垂直的平面将上述包围盒划分成两个子包围盒以形成根节点的两个子节点，当所有子节点包含的基本几何元素个数少于预先给定的叶节点所包含几何元素个数的最小值时，转向步骤b，否则转向步骤a3；步骤a3：对步骤a2中得到的两个子节点分别递归地执行上述包围盒的分割过程，当递归深度超过了预先给定的最大树深度时，转向步骤b，否则继续执向步骤a2；步骤b：取所述两个物体的包围盒树的当前结点两两之间进行检测，判断是否发生碰撞，若发生碰撞，转向步骤c，若没碰撞，转向步骤d；步骤c：判断当前结点是否为叶子结点，若是，进行精确检测确定是否真的发生碰撞，并根据检测结果更新包含“最近距离”，“速度”，“是否碰撞”在内的节点信息，并记录“最近距离”在搜索树中的路径，记下该结点，返回；若不是叶子结点，则取它所有子结点作为该树的当前结点，递归执行步骤b；步骤d：如果当前结点没有未检测的兄弟结点，表明没发生碰撞，则计算包含“最近距离”，“速度”，“是否碰撞”在内的节点信息，记下当前结点后，返回；如果还有未检测的兄弟结点，则依次将下兄弟结点作为该树的当前结点，递归执行步骤b。