一种改进的动态OBB层次结构碰撞算法.pdfVIP

北京石油化工学院学报 第 19卷 第 1期 VoI．19 No．1 JournalofBeijingInstituteof 2011年 3月 M ar．2011 Petro—chem icalTechnology 一 种改进的动态 OBB层次结构碰撞算法* 黄松柏 (北京化工大学信息科学与技术学院，北京 100029) 摘 要 在虚拟场景中普遍采用基于OBB包 围盒 的碰撞检测技术 ，然而传统算法对于大数 据量模型的检测仍然效率不高，难 以保证实时性 。在分析 了OBB及其改进算法 的基础上 ，采用改进的 OBB中心计算方法 ．使包 围盒能够更紧密的包 围模 型 ，提高碰撞检测的准确性和 时间效率 。在碰撞检 测过程 中动态地建立 OBB层次结构 ，减少 了时间复杂度和空间复杂度 。分析和实验结果证 明，改进后 的算法在处理一般 曲面模型尤其是大数据曲面模型时 ，碰撞检测的稳定性和效率都有 明显提高 。 关 键 词 OBB；动态层次结构 ；碰撞检测 ；大数据 曲面模型 中图法分类号 TP301．6 碰撞检测在计算机图形学 、计算机动画、虚 它的相交测试变得复杂。尽管 ()BB间相交测试 拟现实等应用系统中具有广泛 的应用 ，一直是 的代价比较大，但它的紧密性是最好 的，可以成 研究热点之一 。碰撞检测算法主要有基于包围 倍地减少参与相交测试 的包围盒的数 目和基本 盒的碰撞检测算法、基于距离计算的碰撞检测 几何元素的数 目，在大多数情况下其总体性能要 算法以及基于维诺图的碰撞检测算法等三类 ， 优于AABB和包围球 。 其中前两种算法只能解决凸多面体之间的碰撞 基于 OBB的碰撞算法 已经有很 多改进 。 检测并且难 以进行精确的计算 ；基于包 围盒的 根据 曲面特征和应用不同提出的改进算法 ，如 碰撞检测算法不仅可 以检测 凸多面体 ，同时也 针对复杂形状 改进 的 OBB碰撞算法 [4j，提 高 可 以检测凹多面体 ，是一种 比较有效的快速碰 OBB层次结构树的更新速度_s]，修改 OBB层 撞检测算法 。比较典型的包围盒有沿坐标轴 次结构树 的遍历策略 6，基于虚拟环境 的OBB 的 包 围 盒 AABB (Axis—Aligned Bounding 碰撞算法 等。显然 ，由于 OBB层次结构树的 Box)、包 围球 (Sphere)、方 向包 围盒 OBB 内在并行性，并行技术可 以提高算法效率。王 (OrientedBoundingBox)、固定方 向凸包 FDH 兆其等在基于并行处理技术提高 OBB算法的 (FixedDirectionConvexHul1)、离散方 向包 围 运行效率方面给 出了一种面 向对象的碰撞算 盒 K—DOP(Diserete()rientationPolygons)等 。 法L8。 ，讨论了分布式环境 中碰撞 检测的完全 方 向包 围盒 OBB是基于分离轴的相交测试理 性和唯一性问题 j。改进 的并行碰撞算法如使 论 ，由 S．Gottschalk在 1996年 实 现 的 RAPID 用并行处理 中的流水线技术 ，算法可运行于多 (Robust and Accurate Polygon Interference 处理器或单处理器上 ；将复杂的凸多面体剖 Detection)系统中首先提出 ]。一个给定对象的 分为简单 四面体 ，利 用基于 MPI(Message OBB被定义为包含该