【作者】 黄洁；

【导师】 杨杰；

【作者基本信息】 上海交通大学 ， 模式识别与智能系统， 2008， 硕士

【摘要】 颅面整形手术一直以来是一种高风险、高成本的外科手术。传统的手术计划和设计是依赖于医生的经验,结合术前仔细的观测和诊断准备工作,客观精准性较低,且对医生的技术要求很高。然而随着计算机图形学技术的发展,利用计算机设计的辅助手术系统可以将医学影像重建并绘制成三维的模型,然后在此基础上进行一些测量、剖析操作,为手术的设计与计划提供了精确的准备。另一方面,充分利用虚拟现实技术,辅助手术系统可以模拟手术过程,预测手术效果,成为集观测和训练为一体的新功能平台。在辅助手术系统中,交互式的虚拟切割是较为基本且重要的操作,也是目前国内外研究的重点之一。本文基于颅面整形手术的辅助系统,研究刚性物体的交互式切割操作的算法和系统化的实现。主要工作是在三维可视化的基础上,实现三角形网格模型的几种交互式虚拟切割仿真操作。本文的创新点和主要工作体现在:(1)三维表面数据的可视化及预处理本文在经典的Marching-Cube三维表面重建算法基础上,经过三角形网格的平滑、简化和三角网格化后,提出了聚类与等效替代的算法来实现“畸三角形”(或者三角形冗余)的去除,从而弥补了Marching-Cube算法的缺点,在保持物体良好的绘制效果的同时,获得更少且形状更规范的三角形网格数据。(2)切割工具的仿真本文采用了三种交互式切割工具的仿真,点、线、面。同时,对于三种切割工具的交互式方法进行了设计与实现,将切割工具的片元转化到不同半径球形区域内的碰撞检测计算,大大增强了各种切割工具间计算算法上的通用性能。(3)碰撞检测算法的设计与实现本文针对大量的三维三角形网格数据,创新性的提出利用KD(Key Discriminator)树结构的两次碰撞检测法。主要是重点利用三角形重心坐标及最大重心半径域值构成3D树形数据结构来进行全局数据的碰撞预检测;然后再进行切割工具所在邻域内的精确方程求解从而实现碰撞点的计算求取。(4)切割路径的定义本文结合了离散种子点和投影计算方法,在保证一定的精确度的条件下,提出了切割路径定义的近似计算方法。另一方面,提出利用邻接入射框架(Adjacent and Incident Framework)的数据结构,来实现三角形网格连接关系的搜索与查询。(5)三维网格重建方法的实现本文对所有的网格重建模式进行了若干种有限重建模式的归纳,再利用AIF数据结构的局部修改来实现全局网格的重建,从而使得网格重建算法和计算复杂度得到了进一步的简化、高效。(6)切分后连续表面的搜索算法设计与实现本文创新性的利用人工智能的盲目树型搜索算法,实现了切割后连续网格表面的搜索。同时,结合AIF数据结构,提出了基于顶点和边搜索的两种方法,并进行了两者的效率对比实验和算法准确性分析最后,本文利用切割和分离操作,进行了任意医学数据三维模型的交互式操作实验,获得较好的切割分离效果。同时进一步针对本文提出的各种算法以及算法所构成的交互式切割系统进行了应用型的分析举例。列举了利用平面切割和连续曲面的搜索算法,实现三维空间离散模型的选择和分离操作;其次,利用平面切割与对称性法则,实现了颅骨修补的修补块选取和修补手术的仿真实验,验证了交互式切割分离算法的临床应用性能。更多还原

【Abstract】 Craniofacial plastic is always a high-risk and high-cost surgery by now. Traditional surgery plan and design mainly depends on doctors’experiences with careful observation and accurate diagnosis beforehand so that it is high-demanding to the doctors’abilities and along with low-precise practically. However, nowadays with the rapid development of computer graphic technology, new emergence like Computer Aided Surgery System can not only draw 3D models from medical images, but also supply much operation like measurement and analysis based on these models to get precise preparation for the surgery. Furthermore, Computer Aided Surgery System can faultlessly simulate the whole process of surgery from beginning to end, exactly forecast the result of surgery and extremely be a new unified platform for observation and training by making full use of virtual reality technology.Interactive virtual cutting technology is quite basic but very important for the CAS system, and it is one of the focus research areas at home and abroad. This thesis mainly focuses on the algorithm of interactive cutting and systemized implementation for rigid objects in craniofacial plastic CAS system. What’s more, the primary work is based on 3D visualization to realize the triangle mesh model by using several interactive virtual cutting simulations.The innovation points and primary work are following as below:(1) Visualization and pre-processing of 3D surface dataThis thesis is based on the algorithm of classical Marching-Cube 3D surface reconstruction to achieve triangle mesh smoothing, simplifying and meshing, and meanwhile to bring forward the cluster and replacement algorithm to remove“irregular triangle”(redundant triangles) and to make up the shortcoming of Marching-Cube algorithm. This new algorithm can not only keep good rendering effect but also obtain less amount of well-shaped triangle mesh.(2) Cutting tool simulationThis thesis introduces three kinds of interactive cutting tools which are point, line and plane and different interactive methods are designed and implemented respectively for each of them. The usage of these cutting tools is converted into collision check computation in a sphere with different radius which largely enhances the generic capability among different tools in the same algorithm. (3) Collision check algorithm design and implementationThis thesis creatively brings forward twice collision check method based on KD tree structure for substantial 3D triangle mesh data. This method emphasizes to construct a 3D tree data structure with the centre of gravity for each facet and its maximum radius. This 3D tree is firstly used for global data collision pre-check, then for the computation of the equation to get the precise collision point in the neighbor area around the cutting tool.(4) Definition of the cutting pathThis thesis proposes a new method to combine discrete seeds and projection to define an approximate cutting path with better accuracy and also makes full use of AIF (adjacent and incident framework) to search and query connected triangle mesh linkage.(5) Implementation of reconstruction of 3D meshThis thesis sums up several limited patterns of reconstruction for all kinds of mesh patterns and then enhances the local AIF structures to conduct the reconstruction of the global 3D mesh which makes the algorithm of reconstruction and complexity of computation simpler and more effective.(6) Design and implementation of searching algorithm for continuous surface after cuttingThis thesis innovatively utilizes the bind tree searching algorithm from artificial intelligence to query the continuous surface after cutting operation and meanwhile combines AIF structures to propose two methods of searching which are based on vertices and edges. Furthermore, these two methods are compared and analyzed for efficiency of the experiments and accuracy of algorithms.At last, this thesis utilizes the cutting and separating operation for the interactive experiments based on arbitrary medical data from 3D model and gets quite good result of separation. What’s more, several applications are analyzed and described on the basis of each proposed algorithm and constructed interactive cutting system. Among these applications, searching methods based on plane cutting and continuous curve are enumerated to realize the selection and separation operation for 3D space discrete model. Also, plane cutting and symmetry principle are utilized to implement the selection for mending skull and the simulation experiment of mending surgery. All these applications validate the valuable capability of the interactive cutting algorithm and its clinic usage.更多还原