Submitted In Total Fullment Of The Requirements For The Degree Of Master In Computer Applications

In recent years, with the development of computer technology, the virtual surgerysystems, which involving the technologies of the computer graphics, digital image pro-cessing, human-computer interaction, soft-tissue modeling, are urgent to be developedfor teaching, training, diagnosis, surgical planning and other applications. Meshes invirtual surgery systems provide the fundamental data structure for simulating the sur-gical operations and soft-tissue deformation computing. Their size and quality willsignificant impact on the accuracy, stability and efficiency of the developed systems.This paper discusses the following two aspects of the meshes in virtual surgerysystems:First one is how to get the meshes from real patients'three-dimensional medicalimages. The proposed work bases on Amenta's r-sample theory, giving fully consid-eration on the characteristics of medical images, using centroidal Voronoi diagram tosample the images, and then build Delaunay triangulation to get the tetrahedral mesheswe needed. The generated meshes are able to accurately express the complicated hu-man tissues, with good quality.The second is how to maintain the quality of the surface meshes in the dynamicscenes and support the typical query requirements of the virtual surgery systems. Theproposed solution bases on loose r-sample theory. It can effectively protect the surfacemeshes'quality during the objects deformation, by maintaining the loose r-sampleproperties of the surface sampling points set S, the dynamic Delaunay triangulationof S, and the labels of the Delaunay cells. In addition, loose r-sample based dynamicmesh allowing users to use point operations instead of mesh operations. It also deliv-ers an uniform data structure which supports the typical mesh operations and greatlyreduces the difficulty of interactive algorithm design for virtual surgery systems. The proposed mesh reconstruction algorithm and loose r-sample based scenemanagement schema are the inheritance and development of the theory of restrictedDelaunay triangulation, r-sample based surface reconstruction algorithm and looser-sample based surface reconstruction algorithm. The proposed mesh reconstructionalgorithm extends the r-sample based surface reconstruction algorithm to solid ob-jects, and generates the tetrahedral meshes; the proposed loose r-sample based scenemanagement schema applies the loose r-sample related theory to keep the quality ofthe dynamic meshes, which the other researchers haven't mentioned before. I believethat the proposed solution is valuable for virtual surgery system development.