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

《虚拟手术中实时碰撞检测技术探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

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

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

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

6、dBoundingBox,0BB)o离散方向包围盒(k-DiscreteOrientationPolytopes,k-DOPs）等⑵,如图2所示。由于虚拟手术对实时性要求较高，本文选择AABB型包围盒，AABB是平行于坐标轴的，包含几何元素的最小正立方体。其优点是：1）易于构建，只需要计算所包含几何元素的顶点的x,y,z坐标的最大值和最小值，存储6个浮点数即可；2）相交测试计算量小，相交测试时只需对两个包围盒在三个坐标轴上的投影分别进行比较，最多6次比较运算即可。2.2包围盒层次树包围盒层次树即包围盒的层次结构，层次树的根节点包含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到每

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