论文部分内容阅读
摘要： 碰撞检测是虚拟手术的关键技术，为提高检测速度，满足系统实时性的要求，提出空间剖分和层次包围盒相结合的方法。使用八叉树表示法对虚拟场景进行空间剖分，在叶节点构建层次包围盒。进行碰撞检测时属于不同八叉树节点的几何元素不会相交，否则使用层次包围盒算法继续进行检测，对于有可能相交的几何元素再进行精确相交检测。
关键词： 虚拟手术；碰撞检测；空间剖分；层次包围盒
0 引言
虚拟手术是集医学、生物力学、材料学、计算机图形学、虚拟现实等诸多学科为一体的交叉研究领域。虚拟手术在医学中的应用主要包括：手术计划与过程模拟、术中导航与监护、手术教学与训练等。碰撞检测是虚拟手术系统中的关键技术，贯穿于虚拟手术的整个过程。
虚拟手术系统中的对象根据材质可分为刚体组织和软件组织。骨骼、手术器械等属于刚体组织，而人体的许多器官如肌肉、血管、肝脏等属于软体组织。以往大部分碰撞检测的研究工作都是针对刚体对象的。与刚体相比较，软体组织由于其特殊的物理性质，在外力或某些操作的作用下会发生几何形状、位置甚至数量上的变化，因此基于软体组织的碰撞检测需要更详细的信息和更多的处理。
最简单的碰撞检测方法是对场景中的几何元素进行两两相交测试，其时间复杂度为O（n2），虽然这种方法可以得到正确的结果，但是当场景中的几何模型稍微增多些，其实时性便无法满足实际的需求。为了尽可能地减少参与相交测试的几何元素的数量，提高系统的实时性，目前碰撞检测技术使用的主要算法有：层次包围盒法，空间分割法，基于网格剖分的方法[1]。但是这些经典的算法也都存在着构造难度大、紧密性差、相交测试复杂、效率低等缺点。
本文采用空间剖分和层次包围盒相结合的方法，简化了几何信息的表示，进行碰撞检测时可排除明显不相交的几何元素，无法排除的再进行精确相交检测，从而减少计算量，加速碰撞检测速度，提高系统实时性。
1 空间剖分技术
整个虚拟手术的场景空间递归的剖分成若干个网格单元，每一个几何元素都属于某个网格单元，处于同一网格单元内的几何元素才有相交的可能，不在同一网格单元的几何元素一定不会相交。采用八叉树的表示方法进行空间剖分。即包含整个场景的立方体作为八叉树的根节点，立方体的3条棱边分别与x，y，z轴平行。递归的将立方体剖分为8个小块，如图1（a）所示，生成8个子节点，直到达到指定的剖分层次为止，如图1（b）所示，每个叶节点包含有限个几何元素。
进行碰撞检测时从八叉树的根节点开始，计算两几何元素是否属于同一节点，如果不属于同一节点则不相交，如果属于同一节点，递归的到下一级节点进行检查，直到发现两几何元素属于同一叶节点，则需要进一步使用层次包围盒进行检查。
2 层次包围盒
对于八叉树的每个叶节点包含的几何元素，建立层次包围盒（Bounding Volume Hierarchy，BVH）。相對于单纯的层次包围盒技术，使用空间剖分与层次包围盒相结合的方法进行碰撞检测，构建的层次树规模更小，计算量更少。层次包围盒包括包围盒和层次树两种数据结构。
2.1 包围盒
包围盒技术是减少相交检测次数，降低碰撞检测复杂度的一种有效的方法。其基本思想是用几何形状相对简单的封闭表面将一复杂几何元素包裹起来，首先进行包围盒之间的相交测试，排除明显不相交的几何元素，无法排除的几何元素，再进一步进行精确的相交测试，从而达到减少相交测试计算量的目的。常见的包围盒类型有：包围球（Bounding Sphere）、沿坐标轴的包围盒（Axis Aligned Bounding Box，AABB）、方向包围盒（Oriented Bounding Box，OBB）。离散方向包围盒（k-Discrete Orientation Polytopes，k-DOPs）等[2]，如图2所示。
由于虚拟手术对实时性要求较高，本文选择AABB型包围盒，AABB是平行于坐标轴的，包含几何元素的最小正立方体。其优点是：1）易于构建，只需要计算所包含几何元素的顶点的x，y，z坐标的最大值和最小值，存储6个浮点数即可；2）相交测试计算量小，相交测试时只需对两个包围盒在三个坐标轴上的投影分别进行比较，最多6次比较运算即可。
2.2 包围盒层次树
包围盒层次树即包围盒的层次结构，层次树的根节点包含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到每个叶节点表示一个基本几何元素。常用的构建策略有自顶向下和自底向上两种。
自顶向下的方法首先建立根结点，利用基于全集的信息递归地将每个节点分裂为两个或多个子集，直至生成只包含一个基本图元的叶结点为止，从而建立一棵自顶向下的包围盒层次树。此方法易于实现，技术成熟，但无法生成最佳树。
自底向上的方法首先将基本几何元素作为叶节点，利用局部信息递归的将两个或多个子集组成新的父节点，直至生成树的根节点。此方法能够生成最佳树，但层次树的构建过程较复杂，相关技术不够成熟。
本文采用自顶向下的方法构建包围盒层次树。进行碰撞检测时，从根节点开始，对于两个几何元素，如果属于不同包围盒，且包围盒不相交，则说明几何元素不相交，算法结束；如果两个几何元素属于同一节点，或者各自所在的节点的包围盒相交，则计算各自所在层次树的下一级节点的包围盒是否相交。以此类推，直到叶节点的两个包围盒也相交，则需要进行精确相交检测。
3 精确相交检测
如果两个包围盒不相交，则两个几何元素一定不相交；如果包围盒相交，则需要做进一步的处理，以判断两个几何元素是否相交。如果层次树的叶节点表示的包围盒也相交，则需要进行两个基本几何元素（一般用三角形面片表示）的精确相交测试。其算法如下：
1）设两个三角面片A和B，计算B的三条边是否和A的包围盒立方体相交，如果不相交则算法结束，否则计算A的三条边是否和B的包围盒相交，如果不相交则算法结束。 2）计算B的三条边是否和A所在的平面相交，如果不相交则算法结束，否则计算B的边和A所在平面的交点（有一个或两个交点）。
3）B的边与A所在平面的两个交点连接成的线段l（两个交点重合，则l为一个点），计算l是否与三角形面片A相交（l与A的边相交或包含在三角形内部）。不相交则算法结束，否则即可确定A与B真正相交。
4 结果分析
算法以心血管模型为研究对象，对虚拟手术中的碰撞检测进行模拟。分别采用层次包围盒法，空间分割法、空间剖分和层次包围盒相结合的方法进行测试。实验数据使用了五组包含基本几何元素数量不同的场景，分别对其碰撞检测所用时间进行统计，结果如图3所示。从测试结果可以看出，本文的方法可以减少碰撞检测所用时间，提高了系统实时性和效率。
5 結论
虚拟手术是计算机虚拟现实技术在医学领域中的重要应用。碰撞检测是虚拟手术系统的基本要素。本文提出了空间剖分和层次包围盒相结合的方法简化了虚拟场景信息的表示，减少了碰撞检测的计算量，从而能够更好的满足虚拟手术系统实时性的要求。
参考文献：
[1]魏迎梅，虚拟环境中碰撞检测问题的研究[D].湖南：国防科学技术大学研究生院，2000.
[2]李艳波、印桂生、张菁、倪军，虚拟手术中基于可碰撞集的软组织自碰撞检测算法[J].计算机应用，2009，29（8）：2101-2104.
[3]GOVINDARAJU N K， KABUL I， LIN M C， et al. Fast continuous collision detection among deformable models using graphics processors[J].Computers & Graphics， 2007，31（1）：5-14.
[4]SPILLMANN J， BECKER M， ESCHNER M，Efficient updates of bounding sphere hierarchies for geometrically deformable models[J].Journal of Virtual Communication and Image Representation，2007，18（2）：101-108.
作者简介：
彭磊（1977-），男，汉族，山东泰安人，硕士，副教授，泰山医学院教师，主要从事图形学、图像处理、虚拟手术研究
关键词： 虚拟手术；碰撞检测；空间剖分；层次包围盒
0 引言
虚拟手术是集医学、生物力学、材料学、计算机图形学、虚拟现实等诸多学科为一体的交叉研究领域。虚拟手术在医学中的应用主要包括：手术计划与过程模拟、术中导航与监护、手术教学与训练等。碰撞检测是虚拟手术系统中的关键技术，贯穿于虚拟手术的整个过程。
虚拟手术系统中的对象根据材质可分为刚体组织和软件组织。骨骼、手术器械等属于刚体组织，而人体的许多器官如肌肉、血管、肝脏等属于软体组织。以往大部分碰撞检测的研究工作都是针对刚体对象的。与刚体相比较，软体组织由于其特殊的物理性质，在外力或某些操作的作用下会发生几何形状、位置甚至数量上的变化，因此基于软体组织的碰撞检测需要更详细的信息和更多的处理。
最简单的碰撞检测方法是对场景中的几何元素进行两两相交测试，其时间复杂度为O（n2），虽然这种方法可以得到正确的结果，但是当场景中的几何模型稍微增多些，其实时性便无法满足实际的需求。为了尽可能地减少参与相交测试的几何元素的数量，提高系统的实时性，目前碰撞检测技术使用的主要算法有：层次包围盒法，空间分割法，基于网格剖分的方法[1]。但是这些经典的算法也都存在着构造难度大、紧密性差、相交测试复杂、效率低等缺点。
本文采用空间剖分和层次包围盒相结合的方法，简化了几何信息的表示，进行碰撞检测时可排除明显不相交的几何元素，无法排除的再进行精确相交检测，从而减少计算量，加速碰撞检测速度，提高系统实时性。
1 空间剖分技术
整个虚拟手术的场景空间递归的剖分成若干个网格单元，每一个几何元素都属于某个网格单元，处于同一网格单元内的几何元素才有相交的可能，不在同一网格单元的几何元素一定不会相交。采用八叉树的表示方法进行空间剖分。即包含整个场景的立方体作为八叉树的根节点，立方体的3条棱边分别与x，y，z轴平行。递归的将立方体剖分为8个小块，如图1（a）所示，生成8个子节点，直到达到指定的剖分层次为止，如图1（b）所示，每个叶节点包含有限个几何元素。
进行碰撞检测时从八叉树的根节点开始，计算两几何元素是否属于同一节点，如果不属于同一节点则不相交，如果属于同一节点，递归的到下一级节点进行检查，直到发现两几何元素属于同一叶节点，则需要进一步使用层次包围盒进行检查。
2 层次包围盒
对于八叉树的每个叶节点包含的几何元素，建立层次包围盒（Bounding Volume Hierarchy，BVH）。相對于单纯的层次包围盒技术，使用空间剖分与层次包围盒相结合的方法进行碰撞检测，构建的层次树规模更小，计算量更少。层次包围盒包括包围盒和层次树两种数据结构。
2.1 包围盒
包围盒技术是减少相交检测次数，降低碰撞检测复杂度的一种有效的方法。其基本思想是用几何形状相对简单的封闭表面将一复杂几何元素包裹起来，首先进行包围盒之间的相交测试，排除明显不相交的几何元素，无法排除的几何元素，再进一步进行精确的相交测试，从而达到减少相交测试计算量的目的。常见的包围盒类型有：包围球（Bounding Sphere）、沿坐标轴的包围盒（Axis Aligned Bounding Box，AABB）、方向包围盒（Oriented Bounding Box，OBB）。离散方向包围盒（k-Discrete Orientation Polytopes，k-DOPs）等[2]，如图2所示。
由于虚拟手术对实时性要求较高，本文选择AABB型包围盒，AABB是平行于坐标轴的，包含几何元素的最小正立方体。其优点是：1）易于构建，只需要计算所包含几何元素的顶点的x，y，z坐标的最大值和最小值，存储6个浮点数即可；2）相交测试计算量小，相交测试时只需对两个包围盒在三个坐标轴上的投影分别进行比较，最多6次比较运算即可。
2.2 包围盒层次树
包围盒层次树即包围盒的层次结构，层次树的根节点包含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到每个叶节点表示一个基本几何元素。常用的构建策略有自顶向下和自底向上两种。
自顶向下的方法首先建立根结点，利用基于全集的信息递归地将每个节点分裂为两个或多个子集，直至生成只包含一个基本图元的叶结点为止，从而建立一棵自顶向下的包围盒层次树。此方法易于实现，技术成熟，但无法生成最佳树。
自底向上的方法首先将基本几何元素作为叶节点，利用局部信息递归的将两个或多个子集组成新的父节点，直至生成树的根节点。此方法能够生成最佳树，但层次树的构建过程较复杂，相关技术不够成熟。
本文采用自顶向下的方法构建包围盒层次树。进行碰撞检测时，从根节点开始，对于两个几何元素，如果属于不同包围盒，且包围盒不相交，则说明几何元素不相交，算法结束；如果两个几何元素属于同一节点，或者各自所在的节点的包围盒相交，则计算各自所在层次树的下一级节点的包围盒是否相交。以此类推，直到叶节点的两个包围盒也相交，则需要进行精确相交检测。
3 精确相交检测
如果两个包围盒不相交，则两个几何元素一定不相交；如果包围盒相交，则需要做进一步的处理，以判断两个几何元素是否相交。如果层次树的叶节点表示的包围盒也相交，则需要进行两个基本几何元素（一般用三角形面片表示）的精确相交测试。其算法如下：
1）设两个三角面片A和B，计算B的三条边是否和A的包围盒立方体相交，如果不相交则算法结束，否则计算A的三条边是否和B的包围盒相交，如果不相交则算法结束。 2）计算B的三条边是否和A所在的平面相交，如果不相交则算法结束，否则计算B的边和A所在平面的交点（有一个或两个交点）。
3）B的边与A所在平面的两个交点连接成的线段l（两个交点重合，则l为一个点），计算l是否与三角形面片A相交（l与A的边相交或包含在三角形内部）。不相交则算法结束，否则即可确定A与B真正相交。
4 结果分析
算法以心血管模型为研究对象，对虚拟手术中的碰撞检测进行模拟。分别采用层次包围盒法，空间分割法、空间剖分和层次包围盒相结合的方法进行测试。实验数据使用了五组包含基本几何元素数量不同的场景，分别对其碰撞检测所用时间进行统计，结果如图3所示。从测试结果可以看出，本文的方法可以减少碰撞检测所用时间，提高了系统实时性和效率。
5 結论
虚拟手术是计算机虚拟现实技术在医学领域中的重要应用。碰撞检测是虚拟手术系统的基本要素。本文提出了空间剖分和层次包围盒相结合的方法简化了虚拟场景信息的表示，减少了碰撞检测的计算量，从而能够更好的满足虚拟手术系统实时性的要求。
参考文献：
[1]魏迎梅，虚拟环境中碰撞检测问题的研究[D].湖南：国防科学技术大学研究生院，2000.
[2]李艳波、印桂生、张菁、倪军，虚拟手术中基于可碰撞集的软组织自碰撞检测算法[J].计算机应用，2009，29（8）：2101-2104.
[3]GOVINDARAJU N K， KABUL I， LIN M C， et al. Fast continuous collision detection among deformable models using graphics processors[J].Computers & Graphics， 2007，31（1）：5-14.
[4]SPILLMANN J， BECKER M， ESCHNER M，Efficient updates of bounding sphere hierarchies for geometrically deformable models[J].Journal of Virtual Communication and Image Representation，2007，18（2）：101-108.
作者简介：
彭磊（1977-），男，汉族，山东泰安人，硕士，副教授，泰山医学院教师，主要从事图形学、图像处理、虚拟手术研究