含内部孔洞的面模型虚拟切割仿真研究
|
摘要
虚拟切割广泛应用于CAD/CAM、生物医学仿真、计算机图形学和虚拟现实等领域中。对于三角面模型的虚拟切割实现简单,效果逼真,实时性较强,应用方便。本文分别对三维面模型的切割、封面以及拼接的算法做了研究和程序实现,并对仿真结果进行了分析。
本文主要在传统的Sutherland-Hodgman多边形裁剪算法的基础上,引入顶点移动算法进行切割,该算法在虚拟切割过程中,确保顶点数量的增加量达到最少,因而,运行效率高,实时性好,且无畸形三角面片生成。但由于顶点移动法可能会造成面模型发生形变,因此提出利用网格细分的思想,对切割模型在切割处首先进行网格细分,再采用顶点移动法,从而保证模型的真实性。
切割后的面模型会产生“中空”现象,为逼真仿真效果,需要对其进行封面操作。切割交点形成一个多边形区域,对于凸多边形可以利用逐点插入法很快解决三角化问题,但对于凹多边形和内部包含有孔洞的多边形处理起来较为复杂。本文提出去除算法,即对所有的点按照整体剖分然后去除其中的孔洞部分。算法通用性较强,不仅可以处理凹凸多边形,且可以很好的解决孔洞问题。
在实际应用中,如虚拟手术中会出现模型拼接操作,本文也对相关拼接算法做了初步研究,提出了两种解决网格拼接的思想——增点拼接和不增点拼接。对增点拼接进行了实现。
本课题以VC++6.0和OpenGL为开发工具对上述算法进行了验证,在开发过程中自始至终贯彻了面向对象的编程思想。以虚拟手术中的三维面模型为数据来源,因为其具有面片数量多、几何结构复杂等特点,所以具有一定代表性。程序结果证明,本文提出的移动顶点算法、去除封面算法以及网格拼接算法,切实可行,达到了仿真效果,具有一定的实际应用价值。
最后总结了全文的工作,并指出了存在的不足和今后的研究方向。
Virtual Cutting is applied in the field of CAD/CAM、Biology Simulation、Computer Graphics and Virtual Reality. Virtual cutting of triangle-facet has simple realization, realistic effect, and is real-time, convenience. In the paper, virtual cutting, the algorithms for face-triangulation and gridding connection are researched and realized with programming, and the simulation results are analyzed.
The transferring vertices algorithm is introduced to cut the facet model on the base of traditional Sutherland-Hodgman algorithm. The algorithm makes sure the increment of the number of vertices is the least, so it has high efficiency, good responsiveness and no misshapen triangles. However, the transferring vertices may make the facet model distortion, so gridding subdivision is used to solve the problem. Gridding subdivision is the first step, and transferring vertices are used in the model to keep the shape of the model.
It produces "empty" on the cut model, so face-triangulation is necessary. The cutting vertices form a polygon. It is easy for the convex polygon to solve with incremental insertion points. However, for the concave polygon is a little difficult, an algorithm for deleting triangles is presented in the paper. The algorithm has strong universality, not only solving convex and concave polygons, but also the polyhedron including the holes.
In the reality, for example, gridding connection is operated in the virtual surgey, so the connection algorithms are studied in the paper, and two ideas about it are presented--adding vertices and no adding vertices. Lastly, adding vertices are realized with programming.
This subject is developed with VC 6.0 and object-oriented programming thought is applied in the course of development, using the 3D model in the virtual surgery, because it has many facets and complex structure. The programming results show that the algorithm is effective and good simulation effect, so it has reality application value.
At last, this thesis concludes the work of all the paper and points out the deficiencies and the development oriention.
本文主要在传统的Sutherland-Hodgman多边形裁剪算法的基础上,引入顶点移动算法进行切割,该算法在虚拟切割过程中,确保顶点数量的增加量达到最少,因而,运行效率高,实时性好,且无畸形三角面片生成。但由于顶点移动法可能会造成面模型发生形变,因此提出利用网格细分的思想,对切割模型在切割处首先进行网格细分,再采用顶点移动法,从而保证模型的真实性。
切割后的面模型会产生“中空”现象,为逼真仿真效果,需要对其进行封面操作。切割交点形成一个多边形区域,对于凸多边形可以利用逐点插入法很快解决三角化问题,但对于凹多边形和内部包含有孔洞的多边形处理起来较为复杂。本文提出去除算法,即对所有的点按照整体剖分然后去除其中的孔洞部分。算法通用性较强,不仅可以处理凹凸多边形,且可以很好的解决孔洞问题。
在实际应用中,如虚拟手术中会出现模型拼接操作,本文也对相关拼接算法做了初步研究,提出了两种解决网格拼接的思想——增点拼接和不增点拼接。对增点拼接进行了实现。
本课题以VC++6.0和OpenGL为开发工具对上述算法进行了验证,在开发过程中自始至终贯彻了面向对象的编程思想。以虚拟手术中的三维面模型为数据来源,因为其具有面片数量多、几何结构复杂等特点,所以具有一定代表性。程序结果证明,本文提出的移动顶点算法、去除封面算法以及网格拼接算法,切实可行,达到了仿真效果,具有一定的实际应用价值。
最后总结了全文的工作,并指出了存在的不足和今后的研究方向。
Virtual Cutting is applied in the field of CAD/CAM、Biology Simulation、Computer Graphics and Virtual Reality. Virtual cutting of triangle-facet has simple realization, realistic effect, and is real-time, convenience. In the paper, virtual cutting, the algorithms for face-triangulation and gridding connection are researched and realized with programming, and the simulation results are analyzed.
The transferring vertices algorithm is introduced to cut the facet model on the base of traditional Sutherland-Hodgman algorithm. The algorithm makes sure the increment of the number of vertices is the least, so it has high efficiency, good responsiveness and no misshapen triangles. However, the transferring vertices may make the facet model distortion, so gridding subdivision is used to solve the problem. Gridding subdivision is the first step, and transferring vertices are used in the model to keep the shape of the model.
It produces "empty" on the cut model, so face-triangulation is necessary. The cutting vertices form a polygon. It is easy for the convex polygon to solve with incremental insertion points. However, for the concave polygon is a little difficult, an algorithm for deleting triangles is presented in the paper. The algorithm has strong universality, not only solving convex and concave polygons, but also the polyhedron including the holes.
In the reality, for example, gridding connection is operated in the virtual surgey, so the connection algorithms are studied in the paper, and two ideas about it are presented--adding vertices and no adding vertices. Lastly, adding vertices are realized with programming.
This subject is developed with VC 6.0 and object-oriented programming thought is applied in the course of development, using the 3D model in the virtual surgery, because it has many facets and complex structure. The programming results show that the algorithm is effective and good simulation effect, so it has reality application value.
At last, this thesis concludes the work of all the paper and points out the deficiencies and the development oriention.
引文
1 骆文博,王广志,丁海曙.国外医学生物医学工程分册[J].2001,24(6):245-246.
2 李成军,张驰,汪国平.交互标记控制的快速网格分割[J].北京大学学报(自然科学版),2006,42(5):662-666.
3 Andrew B.Mor.Progressive Cutting with Minimal New Element Creation of Soft Tissue Models for Interactive Surgical Simulation[D].The Robotics Institute Carnegie Mellon University Pittsburgh,PA 15213,2001,10.
4 Daniel Bielser and Markus H.Gross.Interactive Simulation of Surgical Cuts[M].Proceedings of Graphics 2000,IEEE Computer Society Press:116-125.
5 花卫华,邓伟萍,刘修国等.一种改进的不规则三角网格曲面切割算法[J],中国地质大学学报,2006,31(5):619-622.
6 Blythe D.SIGGRAPH 1999 Course Notes.Advanced Graphics Programming Techniques Using OpenGL[CD].New York:Addison-Wesley,1999.
7 梁荣华,Clapworthy Gordon,潘志庚等.预定义形状的三维表面切割算法研究[J].中国图像图形学报,2006,11(12):1865-1868.
8 Gottschalk S,Lin M,Manocha D.OBB-Tree:A hierarchical structure for rapid interference detection[A].In:Proceedings of SIGGRAPH[C],New Orleans,USA,1996:171-180.
9 徐鹏宇,鲍旭东,张林.正颌外科颅面三维虚拟手术系统的建立[J].中国医学影像技术,2003,19(12):1740-1741.
10 刘奇,周明全,刘晓宁.一种基于标识点的三维表面模型的切割方法[J].计算机应用研究,2007(2):163-166.
11 DonaldHearn,M.Pauline Baker.计算机图形学(第三版)[M].北京:电子工业出版社,2005:332.
12 Han-Wen Nienhuys and A.Frank vander Stappen.A surgery simulation supporting cuts and finite element deformation.institute of Information and Computer Science,Utrecht University PO Box 80089,3508 TB Utrecht,The Netherlands.Preparata F P,Shamos M I Computational Geometry.New York:Springer-Veday,1985.
13 Catmull E,Clark J.Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes[J].Computer Aided Design,1978,l 0(6):350~355.
14 Doo D,Sabin M.Analysis of the Behaviour of Recursive Division Surfaces near Extraordinary Points[J].Computer Aided Design,1978,10(6):356-360.
15 Loop C.Smooth Subdivision Surfaces Based on Triangles[D].University of Utah,Department of Mathematics,1987:33-54.
16 Dyn N,Levin D,Gregory J A.A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control[J].ACM Trans.Gr.,1990,9(2):160-169.
17 Zorin D,Schroder P.Subdivision for Modeling and Animation[C].SIGGRAPH 2000 Conference Proceedings,Course Notes,2000.47-115.
18 王金生,韩臻,施寅等.几种经典网格细分算法的比较[J].计算机应用研究,2004,6:139-141.
19 徐涛,周笑天,张晓伟.三角网格细分模式的统一框架研究[J].微型电脑应用,2007,23(4):1-2.
20 吴剑煌,刘伟军,王天然.面向三角网格的自适应细分[J].计算机工程,2006,32(12):14-16.
21 Voronoi G.Nouvelles.Applications des Parameters Continus,a la Theorie des Formes Quadratiques,Deuxieme Memorie:Recherches surles Parrallelloedres Primitifs,Journal furdie Reineund Angewandte Mathematik,1908(134):198-287.
22 Thiessen A H.Precipitation.A verages for Large Areas[J].Monthly Weather Review,1911(39):1082-1084.
23 Delaunay B.Surla Sphere Vide Bulletin of the Academy of Science of the USSR[J].Classedes Sciences Mathematiqueset Naturelles,1934(8):793-800.
24 丁妹.虚拟手术儿何建模中网格自动生成技术的研究[D].青岛:青岛大学,2005.
25 唐泽圣,徐志强.二维点集三角剖分的动态生成与修改[J].计算机辅助设计与图形学学报,1990,3:1-6.
26 D.T.Lee and B.J.Schachter.Two Algorithms for Constructing a Delaunay Trianglulation [J].International Joural of Computer and Information Science,1980,9(3).
27 邵春丽,胡鹏,黄承义等.DELAUNAY二角网的算法详述及其应用发展前景[J].测绘科学,2004,28(6):68-70.
28 Lee D T and Schacher B J.Two algorithms for constructing a delaunay triangulation [J].International Journal of Computer and Information Science,1980,(9):219-242.
29 Dawyer R A.A fast divide and conquer algorithm for constructing Delaunay triangulations [J].Algorithmica,1987,(2):137-151.
30 C.L.Lawson.Generation of a Triangular Grid with Applications to Contour Plotting[J].Technical Memo.99,Iet Propultion Laboratory,Pasadina,California,1972.
31 D.F.Waston..Computer the n-dimensional Delaunay tessellation with application to Voronoi polytopes[J].The Computer Journnal,1981,24(2).
32 Brassel K E and Reif D.Procedure to generate thissen polygons[J].Geographical Analysis,1979,11:289-303.
33 Mirante A and Wein Garten N.The radical sweep algorithem for constructing triangulated irregular networks[J].IEEE Computer Graphics and application,1982:11-21.
34 林报嘉,叶燕林,赵建伟.三角网的生成与简化算法[J].地理学与国土研究,2001,17(1):70-71.
35 周培德.计算儿何--算法设计与分析(第2版)[M].北京:清华大学出版社,2005:49.
36 邓先礼,胡达,杜小平.多连通多边形三角化找桥算法的研究及实现[J].计算机与现代化,2004,5:4-6.
37 闵卫东,唐泽圣.二维区域内点集的Delaunay三角剖分生成算法[J].计算机学报,1995,18(5):365-370.
38 丁永祥.任意多边形的三角剖分[J].计算机学报,1994,17(4):272-273.
39 马小虎,潘志庚,石教英.基于凹凸顼点判定的简单多边形Delaunay三角剖分[J].计算机辅助设计与图形学学报,1999,11(1):1-3.
40 王承翔,黄天泽.平面多边形凹凸性的算法研究[J].湖南大学学报,1995,22(5):87-90.
41 路全胜,冯辛安.平面多边形凹凸性的角度判别法[J].计算机辅助设计与制造,1995,2:38-41.
42 Pan ZhiGeng,Ma XiaoHu,Shi JiaoYing.A graph based algorithm for generating the Delaunay triangulation of a point set with in an arbitrary 2D domain[J].Journal of Software,1996,7(11):656-661.
43 秦绪佳.医学图像三维重建及可视化技术研究[D].大连:大连理工大学,2001,6.
44 周培德.计算几何--算法设计与分析(第2版)[M].北京:清华大学出版社,2005,4.
45 http://3d.deds.cn/teach/Deds14435_7.html.
46 周术诚.三维复杂形状拼接与破碎物体复原技术研究[D].西安:西北大学,2007,5.
47 Dah-Jyh Guan,Zi-Cai Li,Yan-Liang Chen.Wire-Frame Mehtod for Blending Surface Design[J].Proc.Natl.Sci.Counc.ROC(A),1999,23(1):26-28.
48 吴淑芳.计算机辅助网格拼接技术[J].长春理工大学学报,2002,25(2):65-68.
49 施仁奈(美国)等著.OpenGL编程指南(第五版)[M].北京:机械工业出版社,2006,6.
50 殷人昆,陶永雷,谢若阳等.数据结构(用面向对象方法与C++描述)[M].北京:清华大学出版社,2002.
51 戴锋.Visual C++程序设计基础[M],北京:清华大学出版社,2002,6.
52 付心建,花卫华,陆小芳.三维交互技术中通用鼠标旋转控制器的实现[J].现代计算机,2005,2.
53 徐鹏宁.正颌外科虚拟手术计划系统的研究与开发[D].南京:东南大学,2004,3:40-41.
2 李成军,张驰,汪国平.交互标记控制的快速网格分割[J].北京大学学报(自然科学版),2006,42(5):662-666.
3 Andrew B.Mor.Progressive Cutting with Minimal New Element Creation of Soft Tissue Models for Interactive Surgical Simulation[D].The Robotics Institute Carnegie Mellon University Pittsburgh,PA 15213,2001,10.
4 Daniel Bielser and Markus H.Gross.Interactive Simulation of Surgical Cuts[M].Proceedings of Graphics 2000,IEEE Computer Society Press:116-125.
5 花卫华,邓伟萍,刘修国等.一种改进的不规则三角网格曲面切割算法[J],中国地质大学学报,2006,31(5):619-622.
6 Blythe D.SIGGRAPH 1999 Course Notes.Advanced Graphics Programming Techniques Using OpenGL[CD].New York:Addison-Wesley,1999.
7 梁荣华,Clapworthy Gordon,潘志庚等.预定义形状的三维表面切割算法研究[J].中国图像图形学报,2006,11(12):1865-1868.
8 Gottschalk S,Lin M,Manocha D.OBB-Tree:A hierarchical structure for rapid interference detection[A].In:Proceedings of SIGGRAPH[C],New Orleans,USA,1996:171-180.
9 徐鹏宇,鲍旭东,张林.正颌外科颅面三维虚拟手术系统的建立[J].中国医学影像技术,2003,19(12):1740-1741.
10 刘奇,周明全,刘晓宁.一种基于标识点的三维表面模型的切割方法[J].计算机应用研究,2007(2):163-166.
11 DonaldHearn,M.Pauline Baker.计算机图形学(第三版)[M].北京:电子工业出版社,2005:332.
12 Han-Wen Nienhuys and A.Frank vander Stappen.A surgery simulation supporting cuts and finite element deformation.institute of Information and Computer Science,Utrecht University PO Box 80089,3508 TB Utrecht,The Netherlands.Preparata F P,Shamos M I Computational Geometry.New York:Springer-Veday,1985.
13 Catmull E,Clark J.Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes[J].Computer Aided Design,1978,l 0(6):350~355.
14 Doo D,Sabin M.Analysis of the Behaviour of Recursive Division Surfaces near Extraordinary Points[J].Computer Aided Design,1978,10(6):356-360.
15 Loop C.Smooth Subdivision Surfaces Based on Triangles[D].University of Utah,Department of Mathematics,1987:33-54.
16 Dyn N,Levin D,Gregory J A.A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control[J].ACM Trans.Gr.,1990,9(2):160-169.
17 Zorin D,Schroder P.Subdivision for Modeling and Animation[C].SIGGRAPH 2000 Conference Proceedings,Course Notes,2000.47-115.
18 王金生,韩臻,施寅等.几种经典网格细分算法的比较[J].计算机应用研究,2004,6:139-141.
19 徐涛,周笑天,张晓伟.三角网格细分模式的统一框架研究[J].微型电脑应用,2007,23(4):1-2.
20 吴剑煌,刘伟军,王天然.面向三角网格的自适应细分[J].计算机工程,2006,32(12):14-16.
21 Voronoi G.Nouvelles.Applications des Parameters Continus,a la Theorie des Formes Quadratiques,Deuxieme Memorie:Recherches surles Parrallelloedres Primitifs,Journal furdie Reineund Angewandte Mathematik,1908(134):198-287.
22 Thiessen A H.Precipitation.A verages for Large Areas[J].Monthly Weather Review,1911(39):1082-1084.
23 Delaunay B.Surla Sphere Vide Bulletin of the Academy of Science of the USSR[J].Classedes Sciences Mathematiqueset Naturelles,1934(8):793-800.
24 丁妹.虚拟手术儿何建模中网格自动生成技术的研究[D].青岛:青岛大学,2005.
25 唐泽圣,徐志强.二维点集三角剖分的动态生成与修改[J].计算机辅助设计与图形学学报,1990,3:1-6.
26 D.T.Lee and B.J.Schachter.Two Algorithms for Constructing a Delaunay Trianglulation [J].International Joural of Computer and Information Science,1980,9(3).
27 邵春丽,胡鹏,黄承义等.DELAUNAY二角网的算法详述及其应用发展前景[J].测绘科学,2004,28(6):68-70.
28 Lee D T and Schacher B J.Two algorithms for constructing a delaunay triangulation [J].International Journal of Computer and Information Science,1980,(9):219-242.
29 Dawyer R A.A fast divide and conquer algorithm for constructing Delaunay triangulations [J].Algorithmica,1987,(2):137-151.
30 C.L.Lawson.Generation of a Triangular Grid with Applications to Contour Plotting[J].Technical Memo.99,Iet Propultion Laboratory,Pasadina,California,1972.
31 D.F.Waston..Computer the n-dimensional Delaunay tessellation with application to Voronoi polytopes[J].The Computer Journnal,1981,24(2).
32 Brassel K E and Reif D.Procedure to generate thissen polygons[J].Geographical Analysis,1979,11:289-303.
33 Mirante A and Wein Garten N.The radical sweep algorithem for constructing triangulated irregular networks[J].IEEE Computer Graphics and application,1982:11-21.
34 林报嘉,叶燕林,赵建伟.三角网的生成与简化算法[J].地理学与国土研究,2001,17(1):70-71.
35 周培德.计算儿何--算法设计与分析(第2版)[M].北京:清华大学出版社,2005:49.
36 邓先礼,胡达,杜小平.多连通多边形三角化找桥算法的研究及实现[J].计算机与现代化,2004,5:4-6.
37 闵卫东,唐泽圣.二维区域内点集的Delaunay三角剖分生成算法[J].计算机学报,1995,18(5):365-370.
38 丁永祥.任意多边形的三角剖分[J].计算机学报,1994,17(4):272-273.
39 马小虎,潘志庚,石教英.基于凹凸顼点判定的简单多边形Delaunay三角剖分[J].计算机辅助设计与图形学学报,1999,11(1):1-3.
40 王承翔,黄天泽.平面多边形凹凸性的算法研究[J].湖南大学学报,1995,22(5):87-90.
41 路全胜,冯辛安.平面多边形凹凸性的角度判别法[J].计算机辅助设计与制造,1995,2:38-41.
42 Pan ZhiGeng,Ma XiaoHu,Shi JiaoYing.A graph based algorithm for generating the Delaunay triangulation of a point set with in an arbitrary 2D domain[J].Journal of Software,1996,7(11):656-661.
43 秦绪佳.医学图像三维重建及可视化技术研究[D].大连:大连理工大学,2001,6.
44 周培德.计算几何--算法设计与分析(第2版)[M].北京:清华大学出版社,2005,4.
45 http://3d.deds.cn/teach/Deds14435_7.html.
46 周术诚.三维复杂形状拼接与破碎物体复原技术研究[D].西安:西北大学,2007,5.
47 Dah-Jyh Guan,Zi-Cai Li,Yan-Liang Chen.Wire-Frame Mehtod for Blending Surface Design[J].Proc.Natl.Sci.Counc.ROC(A),1999,23(1):26-28.
48 吴淑芳.计算机辅助网格拼接技术[J].长春理工大学学报,2002,25(2):65-68.
49 施仁奈(美国)等著.OpenGL编程指南(第五版)[M].北京:机械工业出版社,2006,6.
50 殷人昆,陶永雷,谢若阳等.数据结构(用面向对象方法与C++描述)[M].北京:清华大学出版社,2002.
51 戴锋.Visual C++程序设计基础[M],北京:清华大学出版社,2002,6.
52 付心建,花卫华,陆小芳.三维交互技术中通用鼠标旋转控制器的实现[J].现代计算机,2005,2.
53 徐鹏宁.正颌外科虚拟手术计划系统的研究与开发[D].南京:东南大学,2004,3:40-41.