虚拟手术中实时碰撞检测技术探究

1、虚拟手术中实时碰撞检测技术探究摘要：碰撞检测是虚拟手术的关键技术，为提高检测速 度，满足系统实时性的要求，提出空间剖分和层次包围盒相 结合的方法。使用八叉树表示法对虚拟场景进行空间剖分， 在叶节点构建层次包围盒。进行碰撞检测时属于不同八叉树 节点的几何元素不会相交，否则使用层次包围盒算法继续进 行检测，对于有可能相交的几何元素再进行精确相交检测。关键词： 虚拟手术；碰撞检测；空间剖分；层次包围 盒0引言虚拟手术是集医学、生物力学、材料学、计算机图形学、 虚拟现实等诸多学科为一体的交叉研究领域。虚拟手术在医 学中的应用主要包括：手术计划与过程模拟、术中导航与监 护、手术教学与训练等。碰撞检测是虚

2、拟手术系统中的关键 技术，贯穿于虚拟手术的整个过程。虚拟手术系统中的对象根据材质可分为刚体组织和软 件组织。骨骼、手术器械等属于刚体组织，而人体的许多器 官如肌肉、血管、肝脏等属于软体组织。以往大部分碰撞检 测的研究工作都是针对刚体对象的。与刚体相比较，软体组 织由于其特殊的物理性质，在外力或某些操作的作用下会发 生几何形状、位置甚至数量上的变化，因此基于软体组织的 碰撞检测需要更详细的信息和更多的处理。最简单的碰撞检测方法是对场景中的几何元素进行两 两相交测试，其时间复杂度为0 (n2),虽然这种方法可以得 到正确的结果，但是当场景中的几何模型稍微增多些，其实 时性便无法满足实际的需求。为了

3、尽可能地减少参与相交测 试的几何元素的数量，提高系统的实时性，目前碰撞检测技 术使用的主要算法有：层次包围盒法，空间分割法，基于网 格剖分的方法1。但是这些经典的算法也都存在着构造难 度大、紧密性差、相交测试复杂、效率低等缺点。本文采用空间剖分和层次包围盒相结合的方法，简化了 几何信息的表示，进行碰撞检测时可排除明显不相交的几何 元素，无法排除的再进行精确相交检测，从而减少计算量， 加速碰撞检测速度，提高系统实时性。1空间剖分技术整个虚拟手术的场景空间递归的剖分成若干个网格单 元，每一个几何元素都属于某个网格单元，处于同一网格单 元内的几何元素才有相交的可能，不在同一网格单元的几何 元素一定不

4、会相交。采用八叉树的表示方法进行空间剖分。即包含整个场景的立方体作为八叉树的根节点，立方体的3条棱边分别与x, y, z轴平行。递归的将立方体剖分为8个小块，如图1 (a)所示，生成8个子节点，直到达到指定的剖分层次为止，如图1 (b)所示，每个叶节点包含有限个几何元素。进行碰撞检测时从八叉树的根节点开始，计算两几何元素是否属于同一节点，如果不属于同一节点则不相交，如果 属于同一节点，递归的到下一级节点进行检查，直到发现两 几何元素属于同一叶节点，则需要进一步使用层次包围盒进 行检查。2层次包围盒对于八叉树的每个叶节点包含的几何元素，建立层次包 围盒(bounding volume hiera

5、rchy, bvh)相对于单纯 的层次包围盒技术，使用空间剖分与层次包围盒相结合的方 法进行碰撞检测，构建的层次树规模更小，计算量更少。层 次包围盒包括包围盒和层次树两种数据结构。2. 1包围盒包围盒技术是减少相交检测次数，降低碰撞检测复杂度 的一种有效的方法。其基本思想是用几何形状相对简单的封 闭表面将一复杂几何元素包裹起来，首先进行包围盒之间的 相交测试，排除明显不相交的几何元素，无法排除的几何元 素，再进一步进行精确的相交测试，从而达到减少相交测试 计算量的目的。常见的包围盒类型有：包围球(bounding sphere)> 沿坐标轴的包围盒(axis aligned boundi

6、ng box, aabb)、方向包围盒(oriented bounding box, 0bb)o 离散方向包围盒(k-discrete orientation polytopes, k-dops）等,如图2所示。由于虚拟手术对实时性要求较高，本文选择aabb型包 围盒，aabb是平行于坐标轴的，包含几何元素的最小正立方 体。其优点是：1）易于构建，只需要计算所包含几何元素 的顶点的x, y, z坐标的最大值和最小值，存储6个浮点数 即可；2）相交测试计算量小，相交测试时只需对两个包围 盒在三个坐标轴上的投影分别进行比较，最多6次比较运算 即可。2. 2包围盒层次树包围盒层次树即包围盒的层次结构

7、，层次树的根节点包 含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到 每个叶节点表示一个基本几何元素。常用的构建策略有自顶 向下和自底向上两种。自顶向下的方法首先建立根结点，利用基于全集的信息 递归地将每个节点分裂为两个或多个子集，直至生成只包含 一个基本图元的叶结点为止，从而建立一棵自顶向下的包围 盒层次树。此方法易于实现，技术成熟，但无法生成最佳树。自底向上的方法首先将基本几何元素作为叶节点，利用 局部信息递归的将两个或多个子集组成新的父节点，直至生 成树的根节点。此方法能够生成最佳树，但层次树的构建过 程较复杂，相关技术不够成熟。本文采用自顶向下的方法构建包围盒层次树。进行碰撞 检测

8、时，从根节点开始，对于两个几何元素，如果属于不同 包围盒，且包围盒不相交，则说明几何元素不相交，算法结 束；如果两个几何元素属于同一节点，或者各自所在的节点 的包围盒相交，则计算各自所在层次树的下一级节点的包围 盒是否相交。以此类推，直到叶节点的两个包围盒也相交， 则需要进行精确相交检测。3精确相交检测如果两个包围盒不相交，则两个几何元素一定不相交； 如果包围盒相交，则需要做进一步的处理，以判断两个几何 元素是否相交。如果层次树的叶节点表示的包围盒也相交， 则需要进行两个基本几何元素（一般用三角形面片表示）的 精确相交测试。其算法如下：1）设两个三角面片a和b,计算b的三条边是否和a的 包围盒

9、立方体相交，如果不相交则算法结束，否则计算a的 三条边是否和b的包围盒相交，如果不相交则算法结束。2）计算b的三条边是否和a所在的平面相交，如果不相交 则算法结束，否则计算b的边和a所在平面的交点（有一个 或两个交点）。3）b的边与a所在平面的两个交点连接成的线段1 （两 个交点重合，则1为一个点），计算1是否与三角形面片a 相交（1与a的边相交或包含在三角形内部）。不相交则算法 结束，否则即可确定a与b真正相交。4结果分析算法以心血管模型为研究对象，对虚拟手术中的碰撞检 测进行模拟。分别采用层次包围盒法，空间分割法、空间剖 分和层次包围盒相结合的方法进行测试。实验数据使用了五 组包含基本几何

10、元素数量不同的场景，分别对其碰撞检测所 用时间进行统计，结果如图3所示。从测试结果可以看出， 本文的方法可以减少碰撞检测所用时间，提高了系统实时性 和效率。5结论虚拟手术是计算机虚拟现实技术在医学领域中的重要 应用。碰撞检测是虚拟手术系统的基本要素。本文提出了空 间剖分和层次包围盒相结合的方法简化了虚拟场景信息的 表示，减少了碰撞检测的计算量，从而能够更好的满足虚拟 手术系统实时性的要求。参考文献：1 魏迎梅，虚拟环境中碰撞检测问题的研究d.湖南: 国防科学技术大学研究生院，2000.2 李艳波、印桂生、张菁、倪军，虚拟手术中基于可 碰撞集的软组织自碰撞检测算法j.计算机应用，2009, 29(8)： 2101-2104.31g0vindaraju n k, kabul i, lin m c, et al. fastcontinuouscollision detectionprocessorsj computers& graphics, 2007, 31 (1)：5-14.4spillmann j,becker m, eschner m,efficientupdatesofboundingspherehierarchiesfor