Implementation Of Virtual Cutting Algorithm Based On Triangle Mesh

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.