一种虚拟手术中可变形对象切割仿真的网格变形优化方法

技术领域

本发明涉及一种虚拟手术切割仿真中的方法，尤其是涉及一种虚拟手术中可变形对象切割仿真的网格变形优化方法。

背景技术

虚拟手术为医生提供虚拟的手术环境以及可交互的操作平台，可以用于手术规划，手术训练，手术模拟教学等。与传统的手术训练及手术教学相比，虚拟手术成本低，并且可重复操作。随着虚拟现实技术的不断发展和计算机硬件性能的不断提升，虚拟手术得到了越来越广泛的研究。可变形对象的切割仿真是虚拟手术中的一项基本的、关键的技术，虚拟手术要求可变形对象的切割仿真具有较高的准确性和实时性。

当前可变形对象的切割仿真大部分是基于网格的方法，而基于四面体网格的切割仿真方法是目前应用最广的方法。四面体网格可以通过网格细分构造出几乎任意形状的模型，但是在网格生成和网格划分过程中会出现病态单元，病态单元会极大的降低变形仿真的计算效率和稳定性，并且网格划分会大大增加网格数量，造成计算负担过大，影响仿真的准确性和实时性。因此对于网格的处理一直是切割仿真的研究热点，如何有效的控制网格的数量和质量，到目前为止仍然是一个很有挑战性的问题。

本发明提出了一种虚拟手术中可变形对象切割仿真的网格变形优化方法。采用几何优化和拓扑优化，并结合多线程方法对多个任务并行处理，可以在解决切割仿真过程中出现的病态单元问题的同时减少网格数量，有效的提高网格模型变形计算的效率和稳定性。

发明内容

本发明的目的是为了解决虚拟手术可变形对象切割仿真中的病态单元问题，改善模型的网格质量，提高切割仿真的效率和稳定性，而提出的一种虚拟手术中可变形对象切割仿真的网格变形优化方法。

本发明提供一种虚拟手术中可变形对象切割仿真的网格变形优化方法，该方法包括四个步骤：

第一步，搜索目标单元，根据网格质量搜索需要处理的网格单元，每个目标单元交给一个线程做后续处理，具体如下：

(a)对于体网格，根据体网格质量的体积长度比率标准在执行切割操作的局部搜索目标单元；

(b)对于面网格，根据面网格质量的面积长度比率标准在执行切割操作的搜索目标单元；

(c)若搜索到两个或以上的目标单元相邻，则将其所构成的多边形或多面体作为新的目标单元；

(d)将搜索到的目标单元储存到目标单元队列中，并依次分配给子线程执行后续步骤。

第二步，网格优化预处理，根据搜索到的目标单元对局部目标区域进行处理，具体如下：

(a)确定周边单元，利用K-D树数据结构邻近搜索的优势搜索与目标单元(表面网格或体网格)顶点有连接关系的周边单元；

(b)删除目标单元的顶点，并删除每个顶点与周边单元的连接关系，从而得到目标区域，目标区域为一个多边形(或多面体)；

(c)根据顶点之间的连接关系更新网格模型的拓扑结构。

第三步，网格拓扑优化过程，对执行完预处理步骤的网格模型重新划分网格并更新拓扑结构，改善目标单元网格质量，具体如下：

(a)对目标区域重新划分网格，利用目标区域的边界及内部点集执行Delaunay剖分；

(b)判断网格质量是否满足要求，若满足要求则执行(d)，否则执行(c)，根据第一步搜索目标单元中所述的质量标准(1)和(2)判断目标区域内的单元是否符合要求；

(c)在目标区域内添加新顶点并确定顶点位置，之后执行(a)，所述新顶点位置为目标区域内最大三角形或四面体的外接圆圆心，最大三角形或四面体为目标区域内外接圆半径最大的单元；

(d)根据顶点之间的连接关系更新网格模型的拓扑结构，若没有添加新的节点，则直接执行第四步的表面拉普拉斯平滑。

第四步，网格几何优化过程，对执行完拓扑优化的网格，做几何优化，调节顶点位置，进一步的改善网格质量，具体如下：

(a)对目标区域体网格执行网格松弛；

(b)对切割后的局部表面网格执行拉普拉斯平滑，将局部表面网格的每个节点移动到其相邻节点的平均位置。

其中步骤二、三、四中涉及的每个目标区域都作为一个单独的任务投递到线程池做并行处理。

本发明与现有技术相比优点在于：

1.单独处理每个病态单元，分别对其进行局部优化，可以改善网格质量，并且不会影响其他网格。

2.采用几何优化和拓扑优化，并结合多线程方法对多个任务并行处理，可以在解决切割仿真过程中出现的病态单元问题的同时减少网格数量，有效的提高网格模型变形计算的效率和稳定性。

3.采用K-D树结构结合多线程加速对周边单元的搜索过程，有效的提高搜索速度，满足虚拟切割中的实时性要求。

附图说明

图1：一种虚拟手术中可变形对象切割仿真的网格变形优化方法的流程图；

图2：目标单元和目标区域的二维示意图；

具体实施方式

图1给出了一种虚拟手术中可变形对象切割仿真的网格变形优化方法的流程图，下面结合具体实施方式进一步说明本发明。

本发明提供了一种虚拟手术中可变形对象切割仿真的网格变形优化方法，主要步骤介绍如下：

第一步，搜索目标单元，根据网格质量搜索需要处理的网格单元，每个目标单元交给一个线程做后续处理，

(a)将网格模型的节点存储在三维K-D树中，将不同节点相关的网格单元(四面体或三角面片)保存到一个哈希表中并对其实时更新；

(b)对于体网格，根据体网格质量的体积长度比率标准在执行切割操作的局部搜索目标单元

其中e_j(j＝1，2，3，4，5，6)是四面体网格的六条边的长度，V是四面体网格的体积，Q_V∈(0，1)，Q_V的值越接近1，说明四面体网格的质量越高，Q_V＝1时，网格单元为正四面体，设定阈值为0.3，搜索Q_V值小于0.3的四面体单元；

(c)对于面网格，根据面网格质量的面积长度比率标准在执行切割操作的搜索目标单元

其中e_j(j＝1，2，3)是三角面片的三条边的长度，A是三角面片的面积，Q_F∈(0，1)，Q_F的值越接近1，说明三角形网格的质量越高，Q_F＝1时，网格单元为正三角形，如图2所示以2D情况为例，图中三角形ABC为搜索到的一个目标单元，设定阈值为0.3，搜索Q_F值小于0.3的四面体单元；

(d)若搜索到两个或以上的目标单元相邻，则将其所构成的多边形或多面体作为新的目标单元；

(e)将搜索到的目标单元储存到目标单元队列中，并依次分配给子线程执行后续步骤。

第二步，网格优化预处理，根据搜索到的目标单元对局部目标区域进行处理，

(a)确定周边单元，利用K-D树数据结构邻近搜索的优势搜索与目标单元(表面网格或体网格)顶点有连接关系的周边单元，如图2所示，ABC为目标单元，虚线表示于周边单元的连接；

(b)删除目标单元的顶点，并删除每个顶点与周边单元的连接关系，从而得到目标区域，目标区域为一个多边形(或多面体)，如图2所示，实线表示得到的目标单元；

(c)根据顶点之间的连接关系更新网格模型的拓扑结构。；

第三步，网格拓扑优化过程，对执行完预处理步骤的网格模型重新划分网格并更新拓扑结构，改善目标单元网格质量，

(a)对目标区域重新划分网格，利用目标区域的边界及内部点集执行Delaunay剖分；

(b)判断网格质量是否满足要求，若满足要求则执行(d)，否则执行(c)，根据第一步搜索目标单元中所述的质量标准(1)和(2)判断目标区域内的单元是否符合要求；

(c)在目标区域内添加新顶点并确定顶点位置，之后执行(a)，所述新顶点位置为目标区域内最大三角形或四面体的外接圆圆心，最大三角形或四面体为目标区域内外接圆半径最大的单元；

(d)根据顶点之间的连接关系更新网格模型的拓扑结构，若没有添加新的节点，则直接执行第四步的表面平滑。

第四步，网格几何优化过程，对执行完拓扑优化的网格，做几何优化，调节顶点位置，进一步的改善网格质量，

(a)对目标区域体网格执行网格松弛，对于目标区域内的每个节点都执行以下操作，

其中，(x_i,y_i,z_i)为目标节点的坐标，(x_p,y_p,z_p)为目标节点调整后的坐标，N为与目标节点有连接关系的所有节点的总数；

对调整完的网格进行质量判断，判断标准如下：

其中Q_R为关联质量系数(0<Q_R≤1)，Q_Vi为第一步中所述的搜索目标单元的质量标准，其中>Vi为包含目标节点的四面体的质量系数，Q_R越大，网格质量越高；

若调整后的目标节点位于目标区域内并且比调整前目标节点的Q_R值大，则将目标节点移动到调整后的位置，否则令

x_p＝(x_p+x_i)/2,y_p＝(y_p+y_i)/2,z_p＝(z_p+z_i)/2(5)

之后循环进行上述操作，直到网格质量满足质量判据或者循环次数达到上限，循环上限由用户自主设置；

(b)对切割后的局部表面网格执行拉普拉斯平滑，将局部表面网格的每个节点移动到其相邻节点的平均位置。

其中步骤二、三、四中涉及的每个目标区域都作为一个单独的任务投递到线程池做并行处理。