摘要
从计算机诞生至今,计算机的应用已经遍布人们生活的方方面面,从科学计算到日常娱乐无不有计算机的影子。计算机的发展加速了不同学科交流融合的步伐,如今数学、物理、生物、医学等都与计算机科学有着密切联系,而医学虚拟手术模拟系统更是将这些学科全部有机地结合在一起。
虚拟手术系统作为虚拟现实技术的一种,与人体软组织的三维建模都已经成为是计算机图形学的重要研究课题。而其中的软组织形变计算研究也是实时虚拟手术系统和人机交互系统中最具挑战性的内容。
本文讨论了虚拟整形手术系统的需求分析及模块设计,并对其中的软组织形变仿真及其在虚拟手术系统中的应用展开详细分析和实验。考虑到软组织的非线性特性,为了兼顾计算的准确性和计算效率,重点研究讨论了非线性有限元模型的实现及其改进方案。
本研究在传统有限元计算的基础上,提出创新性的混合计算方案,结合线性的快速和非线性的准确性计算软组织形变,并实验验证其可行性和效率;同时介绍了三维网格重建算法、图形处理单元的并行计算加速、人机交互技术等相关内容。
本文的主要工作和创新点如下:
1.详细讨论了有限元方法、相关的力学概念以及对应的数值解法,并针对大形变和材料的非线性问题对求解算法进行整理优化。
2.讨论了有限元分析中网格模型的建立与选取。
3.本文在几何非线性和材料非线性的混合非线性求解算法中融合了线性近似的计算,提升算法的计算效率。
4.利用图形显示卡的并行计算特性进行程序优化。
5.建立验证模拟结果的较合理的机制,通过实验验证形变模拟的真实性和有效性。
6.根据实际实验结论,选取适当的网格模型,并对算法中的参数和材料参数的设定进行调整优化,以达到计算效率和模拟真实性的最优平衡。
7.本论文的新型算法成功地将非线性有限元分析应用于整形手术模拟中,并对形变模拟结果进行应力分析。
Since the birth of the computer, it has been applied in every aspact of people’s daily life. Computer has reached areas from scientific computing to the common entertainment. The development of computer speeds up the pace of integration among different disciplines. Mathematics, physics, biology, medicine and computer science, have had close contact now. And medical virtual surgery simulation system is a subject of all these combination.
Virtual surgery system, as a kind of virtual Reality technology, and the three-dimensional modeling of human soft tissue have become important research topics in Computer Graphics. The study of soft tissue deformation is also one of the most challenging in real-time virtual surgery and human-computer interaction systems.
In this article, we discuss the requirement analysis and module design of virtual surgery system, and propose detailed analysis and experiments on the soft tissue deformation and simulation in virtual surgery system. The soft tissue has non-linear characteristics. So we focus on discussing the non-linear Finite Element Method (FEM) and its improvement in order to achieve a good balance of both accuracy and efficiency of the calculation.
In this research, we propose a novel hybrid approach to calculate soft tissue’s deformation. It’s based on classic FEM, combines the fast speed of linear model and accuracy of non-linear model. Experimental results have been given to evaluate the feasibility and efficiency. Besides, it includes the introduction of three-dimensional meshing algorithm, parallel computing by Graphics Processing Unit (GPU) to accelerate, as well as human-computer interaction technology.
The main works and innovation points are described as follows:
1. The detailed overview of the FEM, related mechanics theories, and numerical algorithm. Optimize the organization of solution for problems with large deformation as well as non-linear material model.
2. Discussion on meshing algorithm and model selection in FEM analysis.
3. We propose hybrid algorithm considering geometrical and material non-linear. And with the proper linear approximation, we could increase the efficiency of FEM solution.
4. With the help of GPU parallel computing, we optimize the speed of calculation.
5. We propose a rational mechanism to evaluate the simulation results. And validate the authenticity and feasibility.
6. Select and optimize mesh model, program coefficient and material parameters based on experiments to find a excellent balance between efficiency and accuracy.
7. Our proposed novel algorithm is successfully applied for craniofacial plastic surgery simulation. Also process stress analysis for the simulation outcome.
引文
[1]罗述谦.医学图像处理与分析.科学出版社, 2003年8月.
[2] Alan Liu et al. A Survey of Surgical Simulation: Applications, Technology, and Education. Presence, Vol. 12, Issue 6, MIT Press December 2003.
[3] M. Ursino, et al, CathSim?. A Survey of Surgical Simulation: Applications on a PC. Medicine Meets Virtual Reality. Convergence of Physical and Informational Technologies: Options for a New Era in Healthcare. MMVR 7, 1999, Netherlands, 360-366.
[4] Joel Brown et al. Real-Time Simulation of Deformable Objects: Tools and Application. The Fourteenth Conference on Computer Animation. Proceedings, 2001.
[5] N. Ayache, S. Cotin et al, and M. Nord, Simulation of Endoscopic surgery, Journal of Minimally Invasive Therapy and Allied Technologies (MITAT), vol. 7, no. 2, pp. 71–77, July 1998.
[6] Keeve E, Girod S, Kikinis R, et al. Deformable modeling of facial tissue for craniofacial surgery simulation. Comput Aided Surg, 1998, 3(5):228.
[7]周轶群,穆雄铮.有限元模拟与颅面外科的发展. Journal of Plastic Reconstructive Surgery, Vol. 1, No.3, 2004
[8] Takács B, Pieper S, Cebral J, Kiss B, Benedek B, SzijártóG. Facial modeling for plastic surgery using magnetic resonance imagery and 3D surface data. SPIE Electronic Imaging 2004;18-22 January, San Jose, Calif.
[9] Pras Pathmanathan et al. Predicting Tumour Location by Simulating Large Deformations of the Breast Using a 3D Finite Element Model and Nonlinear Elasticity. MICCAI 2004, LNCS 3217, pp. 217-224, 2004.
[10] T. W. Sederberg and S. R. Parry, Free-Form Deformation of Solid Geometric Models, Proceedings of SIGGRAPH, Computer Graphics, 1986, 20(4): 151-160.
[11] Yan Chen & Qing-hong Zhu. Physically-based Animation of Volumetric Objects. IEEE 2000.
[12] Luciana Porcher Nedel & Daniel Thalmann. Real Time Muscle Deformations Using Mass-Spring Systems. IEEE Conference 2000.
[13] Francois Conti, Oussama Khatib, Charles Baur. Interactive Rendering of Deformable Objects Based On a Filling Sphere Modeling Approach. Proceedings of the 2003 IEEE International Conference 081 Robotics &Automation, September 14-19, 2003.
[14] Jessica Crouch & Stephen M. Pizer. Medial Techniques to Automate Finite Element Analysis of Prostate Deformation. Transactions on medical imaging, 2004.
[15] Sarah, F., Delingette, H., and Ayache, N. 3D ChainMail: A Fast Algorithm for Deforming Volumetric Objects. 1997 Symposium on Interactive 3D Graphics. pp. 149-154, April 1997.
[16] Doug L. James and Dinesh K. Pai. ArtDefo: Accurate Real Time Deformable Objects. International Conference on Computer Graphics and Interactive Techniques, pp.: 65-72, 1999.
[17]孙艳霞,鲍旭东,蒋春涛.软组织建模中的有限元模型.生物医学工程研究03, 2004.
[18] Qing-hong Zhu et al: Real-time Biomechanically-based Muscle Volume Deformation using FEM. EUROGRAPHICS, 1998.
[19] H. Zhong, MARK P. WACHOWIAK and TERRY M. PETERS. A real time finite element based tissue simulation method incorporating nonlinear elastic behavior. Computer Methods in Biomechanics and Biomedical Engineering. 8(3):177-189, 2005.
[20] Zhuang, Y.: Real-time and Physically Realistic Simulation of Global Deformation. ACM SIGGRAPH 99 Conference. pp. 270, 1999.
[21] M. Bro-Nielsen,“Finite element modeling in surgery simulation,”Proc.IEEE, vol. 86, pp. 490-503, 1998.
[22] S. Cotin, H. Delingette, and N. Ayache.: Real-time Elastic Deformations of Soft Tissues for Surgery Simulation. IEEE Transactions on Visualization and Computer Graphics. VOL. 5, NO. 1, pp. 62-73, January-March, 1999.
[23] Wen Wu, Pheng Ann Heng. An Improved Scheme of an Interactive Finite Element Model for 3D Soft-Tissue Cutting and Deformation. Visual Compute, 2005.
[24] W. WU, P. A. HENG. A hybrid condensed finite element model with GPU acceleration for interactive 3D soft tissue cutting, Comp. Anim. Virtual Worlds 2004; 15: 219-227.
[25] S. Cotin, H. Delingette, and N. Ayache. A Hybrid Elastic Model Allowing Real-Time Cutting, Deformation and Force Feedback for Surgery Training and Simulation. The Visual Computer, 16(8):437-452, 2000.
[26] Fung Y. C. Biomechanics - mechanical properties of living tissues [M] .2th ed , Springer, 1993.
[27] C. Chui, E. Kobayashi, X. Chen, T. Hisada and I. Sakuma. Combined compression and elongation experiments and non-linear modeling of liver tissue for surgical simulation. Med. Biol. Eng. Comput., 2004, 42, 787–798.
[28] Li J, Luo XY, Kuang ZB. A nonlinear anisotropic model for porcine aortic heart valves. J Biomech. 2001 Oct;34(10):1279-1289.
[29] G. Picinbono, H. Delingette, and N. Ayache. Non-linear and anisotropic elastic soft tissue models for medical simulation. In International Conference on Robotics and Automation, pp. 1371-1376,Seoul, South Korea, May 2001.
[30] M. Kauer, V. Vuskovic, J. Dual, G. Szekely, and M. Bajka. Inverse Finite Element Characterization of Soft Tissues. MICCAI 2001, LNCS 2208, pp. 128–136, 2001.
[31] S. Cotin, D. Metaxas. Characterization of soft-tissue material properties: Large deformation analysis, International Symposium on Medical Simulation, Cambridge, MA, Vol. pp. 294. 2004.
[32]王勖成.有限单元法.清华大学出版社. 2003年.
[33] D. Terzopoulos and K. Waters. Physically-based facial modeling, analysis and animation. Journal of Visualization and Computer Animation, 1990.
[34] S. Peiper, J Rosen, and D. Zeltzer. Interactive graphics for plastic surgery: A task-level analysis and implementation. In Symposium on Interactive 3D Graphics, 1992.
[35] E. Keeve, S. Girod, P. Pfeifle, and B. Girod. Anatomy-based facial tissue modeling using the finite element method. IEEE Visualization, 1996.
[36] R.M.Koch, M.H.Gross, D.F.Bueren, G.Frankhauser, Y.Parish, F.R.Carls. Simulating Facial Surgery Using Finite Element Models. SIGGRAPH '96, ACM Computer Graphics, 30, August 1996.
[37] Matthieu Chabanas, Yohan Payan, Christophe Mar′ecaux, Pascal Swider and Franck Boutault. Comparison of linear and non-linear soft tissue models with post-operative CT scan in maxillofacial surgery. LNCS Volume 3078/2004, pp. 19-27, 2004.
[38] Whiteley JP, Gavaghan DJ, Chapman SJ and Brady JM. Non-linear modeling of breast tissue. Math Med Biol. 2007 Sep; 24(3):327-45. Epub 2007 Sep 22.
[39] Pengfei Huang, Lixu Gu, Xiaobo Li, Shaoting Zhang, Jianfeng Xu, Chen Lin, Qi Fang. Real-time Simulation for Global Deformation of Soft Tissue Using Deformable Centerline and Medial Representation. 3rd International Symposium on Biomedical Simulation 2006, Lecture Notes in Computer Science 4072, pp. 67 - 74, July 2006.
[40] Bowden, R. Mitchell, T. A. Sahardi. Real-time Dynamic Deformable Meshes for Volumetric Segmentation and Visualisation. In Proc, BMVC 1997, Vol 1, p310-319, 1997.
[41] Jung Kim, Changmok Choi, Suvranu De, Mandayam A. Srinivasan. Virtual surgery simulation for medical training using multi-resolution organ models. The International Journal of Medical Robotics and Computer Assisted Surgery, vol. 3 Issue 2, pp. 149–158, 2007.
[42] J.R. Shewchuk, Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery, Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp.193-204, 2002.
[43] Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, Mathieu Desbrun. Variational TetrahedralMeshing, ACM Transactions on Graphics, Volume 24, Issue 3, pp. 617-625, July 2005.
[44] Jernej Barbi? and Doug L. James. Real-Time Subspace Integration for St.Venant-Kirchhoff Deformable Models. ACM Transactions on Graphics (SIGGRAPH 2005), August 2005.
[45] NVIDIA Corporation. NVIDIA CUDA Compute Unified Device Architecture Programming Guide 2.0. 2008.
[46] Martin Rumpf, Robert Strzodka. Using Graphics Cards for Quantized FEM Computations, In Proceedings VIIP’01, pages 193–202, 2001.
[47] Jeff Bolz, Ian Farmer, Eitan Grinspun, Peter Schroder. Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid, ACM Trans. Graph., Vol. 22, No. 3. (July 2003), pp. 917-924.
[48] Nina Amenta, Marshall Bern, Manolis Kamvysselis. A New Voronoi-Based Surface Reconstruction Algorithm. International Conference on Computer Graphics and Interactive Techniques, Pages: 415– 421, 1998.
[49]徐荣桥,等.结构分析的有限元法与MATLAB程序设计[M].北京:人民交通出版社, 2006.
[50] Ted Belytschko, Wing Kam Liu, Brian Moran,等.连续体和结构的非线性有限元[M].北京:清华大学出版社,2002。
[51] R.克拉夫,王光远,等。结构动力学(第二版)[M]。北京:高等教育出版社。
[52]徐芝纶。弹性力学[M],上册,北京:人民教育出版社,1982。
[53] Jonathan Richard Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, 1994.
[54]吕斯哲。医学数据网格化及有限元形变建模。本科毕业论文,上海交通大学,2007年。