一种基于OBB的三维医学碰撞检测算法.pdfVIP

维普资讯 第27卷 第3期 兰 州 交 通 大 学 学 报 Vo1．27No．3 2008年 6月 JournaIOfImnzhouJiaotongUniversity Jun．2008 文章编号：1001—4373(2008)03—0101—03 一 种基于OBB的三维医学碰撞检测算法 赵 军 (兰州交通大学 电子与信息工程学院，甘肃 兰州 730070) 摘 要：在三维医学可视化系统中，对绘制场景 中的多个三维对象进行碰撞检测的研究具有很重要的意义．利用 VTK的面绘制特性，在方向包围盒层次树的基础上，提 出了一种新的快速碰撞检测算法．算法在继承了一般基于 方向包围盒的碰撞检测算法优点的同时，对大部分不可能发生碰撞的三角面片进行 了排除，并使用相交检测法进 行碰撞的精确检测．实验结果证明，该算法提高了碰撞检测的效率． 关键词 ：碰撞检测 ；方向包围盒 ；VTK 中图分类号 ：1_、P391．9 文献标识码：A 、，]rK(VisualizationToolkit)是 由著名的Kitware 预处理，排除不可能发生碰撞的三角面片，然后为剩 公司开发的一个开放源码软件工具包_l1]，由于它在图 余的每个三角面片构建一个 OBB，并将这些 OBB 像处理、三维重建等方面上有着很强大的功能，所以 组织成为层次树，最后使用 OBB碰撞检测算法，依 被广泛应用到三维医学可视化系统的开发中．在三维 次遍历两层次树的所有 OBB，如果其中的两 OBB 医学可视化系统的核心中，如何使用户同绘制场景 存在相交，则通过计算由两OBB所包围的三角面片 中的三维对象进行更真实地交互，需要考虑的一个 是否存在交点或相交线段来准确地判断两对象是否 重要方面就是三维对象之间的碰撞 问题．如果忽略 发生了碰撞．因此，算法主要分为两个部分：预处理 碰撞问题，当对象发生相交 的时候，就会出现 “渗 阶段、两对象的碰撞检测判定阶段． 入”．因此，在构建医学三维可视化系统时，必须能够 1．1 算法的预处理阶段 快速准确地检测出绘制场景中的三维对象是否发生 在算法的预处理阶段，需要对绘制场景中的所 了碰撞．到 目前为止，国内外有关学者已经提出了许 有三维对象进行以下3步的处理： 多算法来实现对三维对象碰撞的检测_l2w一．这些算 1)利用 VTK面绘制的特性，可以方便地获得 法大致可以分为两大类：一类是基于模型的方向包 组成三维重建对象的三角面片及其顶点的相关信 围盒(OBB)的，它可以实现快速的碰撞检测，但检测 息．因此，需要先对三维重建对象进行全局遍历，获 结果却不精确；另一类则需要分解模型所在的空间， 取每个节点的空间坐标 P(x， ，)和向量 ll； 它可以提高碰撞检测效率，但三维对象的结构越复 2)根据三维重建对象给定的移动方向向量 V， 杂 ，需要的检测时间也就越多．而在基于 Vn的医 利用向量间的夹角公式，计算各个顶点的向量 ll同 学三维可视化系统中，绘制对象经过面绘制重建后， 移动方向向量V之间的夹角，并设定一个夹角的限 可以方便地获得组成绘制对象的大量三角面片的相 制范围(例如，可设定为0。～ 90。)，将符合该范围的 关信息．因此，本文利用这个特点，并结合方向包围盒 顶点进行标识．公式如下： 检测算法的优点，提出了一种新的、精确的、基于 ()王 0一 … s ’ (1) 的快速碰撞检测算法．