法律状态公告日
法律状态信息
法律状态
2013-02-27
未缴年费专利权终止 IPC(主分类):G06T7/00 授权公告日:20090422 终止日期:20111221 申请日:20061221
专利权的终止
2009-04-22
授权
授权
2007-09-05
实质审查的生效
实质审查的生效
2007-07-11
公开
公开
技术领域
本发明涉及的是一种图像处理技术领域的检测方法，特别是一种虚拟手术系统中形变物体的实时冲突检测方法。
背景技术
随着科学技术的高速发展，高科技医疗设备的不断涌现为医疗的现代化提供了越来越多的帮助。虚拟手术平台的建立在医生的培训、手术导航等方面起到重要作用。在与用户的交互中，碰撞检测作用至关重要。所谓碰撞检测，是指检测物体是否碰到了其它物体。它包括两个不同物体之间的碰撞检测和物体自身的碰撞，并要检测出当物体碰撞发生后，物体的哪一部分被碰到了。在虚拟手术中，两个物体间的碰撞表现为手术器械与器官之间的碰撞，器官与器官间的碰撞；物体自身的碰撞指的是器官本身的碰撞，如血管等碰到自己其他的位置。在碰撞发生后，应该有相应的力施加到物体上被碰到的部分，物体受力产生形变，从而能模拟出真实的手术效果。碰撞检测主要分为静态物体的碰撞检测与动态物体的碰撞检测。其中静态物体的碰撞检测已经是显得较为成熟，而对于形变中物体间的动态碰撞检测技术还面临着很大的难题。这是由于形变中的物体的形状在每一个时间步都在改变，所以计算所需要的数据需要实时更新，故而在检测效率上有很大的局限。
经对现有技术的文献检索发现，M.Teschner等在Proceedings of Vision，Modeling，Visualization VMV’03(03年出版的视觉、建模、可视化会议的论文集)，2003.pages 47-54，上发表的“Optimized spatial hashing for collisiondetection of deformable objects.”(《形变中物体的最优化空间哈希表碰撞检测方法》)中提出了一种利用基于哈希表的动态检测方法，他使形变中的物体的碰撞检测效率大为提高。但这种方法在分割空间时，采用的是规则的大小一致的网格进行检测，存在以下问题：(1)网格的密度对实现的效率有很大的影响。
如果网格定义得过密，虽然检测的精度会提高，但一个测试单元可能存在于多个网格中，这会导致计算量加大；如果网格密度过小，许多检测单元会同是映射到一个哈希表项中，这降低了粗略碰撞检测的效率，增加了精细碰撞检测的时间，程序效率也会降低。(2)网格大小固定，在不同的场景下，对选取网格的大小有很高的要求，每次都要经过很多次实验才能确定出合适的网格大小，方法的通用性受到限制。(3)如果待检测的物体由无规律的四面体组成，确定网格的大小就变得很困难。
综上所诉，对于庞大的数据集而言，现有的碰撞检测方法依然存在着许多未决的难题，而在检测方法的通用性上，现有的方法也面临着很多问题，亟待解决。
发明内容
本发明的目的在于克服现有技术中的不足，提供一种虚拟手术系统中形变物体的实时冲突检测方法，使其对庞大数据集(组成物体的顶点数超过104，组成物体的空间四面体数通常为103～105)，特别是虚拟手术系统中手术器械与软组织交互变得更快速(平均响应时间提高12.9％以上)。
本发明是通过以下技术方案实现的，本发明采用空间层次哈希表的方式，通过映射模块和检测模块来实现，假设物体由m个四面体组成(m为正整数)，映射模块对每个四面体进行动态空间分割，生成哈希表，计算各顶点地址，并将它们映射到相应的哈希表项中；在映射过程中，本发明采用动态调整空间网格大小的形式，即根据各个四面体的大小生成边长不同的网格，而不是像现有方法那样，每个网格的边长是固定的，从而改进了现有方法的不足。碰撞检测模块利用映射模块的结果，检查哈希表项中是否出现冲突项，并利用动态碰撞检测算法检测碰撞是否发生。循环中，两模块交替进行，直到循环结束。
以下对本发明方法作进一步的描述，具体内容如下：
1、所述的映射模块，完成以下的处理：
(1)分割空间
首先，定义网格：本发明将空间分割成层次的网格，这些网格由一系列边长可变的轴向包围盒组成，把这些盒子称为网格，网格的边长定义为k，称之为网格大小。
其次，层次分割：为了为每个四面体找到最适宜的网格，网格的大小必须和四面体的大小相适应。定义s＝size(t)为四面体t的轴向包围盒的最大边长，则用以下公式定义映射t的网格大小k：
