三角网格剖切算法的研究
摘要
在三维模型重建及可视化中,为了对模型截面(大小和形状)进行观察和分析,需要对三维重建模型施以剖切操作。因此,对三维表面模型进行剖切操作也就成为科学可视化研究中一个重要的研究方向。一般来讲,三维模型都是由数量巨大的三角网格重构而成的,而网格在进行重构时不仅包含其空间信息(坐标信息),而且还包含网格几何元素之间连接关系的拓扑信息。因此,对三维模型进行切割就是对重构三维模型的三角网格进行剖切。虽然关于三角网格剖切算法的研究很多文献上都有介绍,但都仅仅是利用三角网格与剖切平面的空间位置关系得到模型剖切后三角网格的空间信息。然而,在三维模型剖切时如果仅仅处理网格空间信息的改变,而不处理网格拓扑信息的话,就将导致网格数据在进行剖切操作时丢失其拓扑信息,从而无法对剖切后的三维模型进行其他的操作。
因此,在对三角网格进行剖切时,为了要避免网格数据在剖切过程中丢失其拓扑信息,本文在前人三角网格剖切算法的研究基础上进行了进一步的研究,使得算法不仅能够处理网格的空间信息,同时还可以对网格的拓扑信息进行恢复。
本文首先对三角网格剖切算法中的理论知识进行了叙述。其次,本文使用的网格数据是数字虚拟人重建中提出的网格数据文件,其中的网格信息不仅存储了网格的空间信息,同时还存储了其几何元素(顶点、边、三角形)之间连接关系的拓扑信息,所以本文三维模型重建和重构三维模型的这种网格数据进行了详细的描述。第三,基于该网格数据文件,本文对三角网格剖切算法进行了研究,从三角网格剖切过程中的网格信息的变化(空间信息和拓扑信息同时改变)入手,不但正确处理了剖切网格所导致的网格空间信息的改变,而且对剖切造成的网格拓扑信息的破坏进行了恢复,使剖切后的三维模型仍能保持网格空间信息的正确性和其拓扑信息一致性。最后,进行了实验及结果分析,验证了本文三角网格剖切算法对重构三维模型的三角网格进行剖切时同时处理了网格的空间信息和拓扑信息,为其他的操作提供了数据基础。
In order to observe the model’s sections (size and shape) of reconstructed model in 3D model reconstructed and visualization, cutting the 3D reconstructed model is needed. So the methods of cutting the 3D reconstructed model have been an important research aspect. Commonly, the 3D models are reconstructed by enormous meshes, which contain space information (coordinate information ) and topological information about connecting of meshes’geometry element, so cutting the 3D model means cutting the triangle meshes reconstructed the 3D model. While there are many instructions about cutting of triangular meshes arithmetic in the literatures, but most of them only deal with the cut nets’space information. Therefore, if we only deal with the meshes’space information when cutting the 3D model, the meshes’topological information will be lost, and then we can’t process the further step.
To avoid the topological information missing when cutting the 3D model, this article develops the method of cutting triangular meshes of others, make it dispose the nets’space information and renew the topological information.
This article introduces the foundations of theory about cutting of triangle cutting method Firstly. Secondly, the data of this article using is the data of Visible Chinese Human (VCH), which contain meshes’space information and topological information, so this article introduces the meshes’topological theory and 3D model reconstructed and then describes the meshes data format. Thirdly, based on the meshes dada format, this article studies the method of cutting triangle meshes, and achieves the cutting of triangular meshes arithmetic, by which we obtain meshes space information and keep meshes topological information consistency. Finally, using the result to validate the method, we know this method is useful to deal with cutting triangle meshes, and provide the foundation for other works.
因此,在对三角网格进行剖切时,为了要避免网格数据在剖切过程中丢失其拓扑信息,本文在前人三角网格剖切算法的研究基础上进行了进一步的研究,使得算法不仅能够处理网格的空间信息,同时还可以对网格的拓扑信息进行恢复。
本文首先对三角网格剖切算法中的理论知识进行了叙述。其次,本文使用的网格数据是数字虚拟人重建中提出的网格数据文件,其中的网格信息不仅存储了网格的空间信息,同时还存储了其几何元素(顶点、边、三角形)之间连接关系的拓扑信息,所以本文三维模型重建和重构三维模型的这种网格数据进行了详细的描述。第三,基于该网格数据文件,本文对三角网格剖切算法进行了研究,从三角网格剖切过程中的网格信息的变化(空间信息和拓扑信息同时改变)入手,不但正确处理了剖切网格所导致的网格空间信息的改变,而且对剖切造成的网格拓扑信息的破坏进行了恢复,使剖切后的三维模型仍能保持网格空间信息的正确性和其拓扑信息一致性。最后,进行了实验及结果分析,验证了本文三角网格剖切算法对重构三维模型的三角网格进行剖切时同时处理了网格的空间信息和拓扑信息,为其他的操作提供了数据基础。
In order to observe the model’s sections (size and shape) of reconstructed model in 3D model reconstructed and visualization, cutting the 3D reconstructed model is needed. So the methods of cutting the 3D reconstructed model have been an important research aspect. Commonly, the 3D models are reconstructed by enormous meshes, which contain space information (coordinate information ) and topological information about connecting of meshes’geometry element, so cutting the 3D model means cutting the triangle meshes reconstructed the 3D model. While there are many instructions about cutting of triangular meshes arithmetic in the literatures, but most of them only deal with the cut nets’space information. Therefore, if we only deal with the meshes’space information when cutting the 3D model, the meshes’topological information will be lost, and then we can’t process the further step.
To avoid the topological information missing when cutting the 3D model, this article develops the method of cutting triangular meshes of others, make it dispose the nets’space information and renew the topological information.
This article introduces the foundations of theory about cutting of triangle cutting method Firstly. Secondly, the data of this article using is the data of Visible Chinese Human (VCH), which contain meshes’space information and topological information, so this article introduces the meshes’topological theory and 3D model reconstructed and then describes the meshes data format. Thirdly, based on the meshes dada format, this article studies the method of cutting triangle meshes, and achieves the cutting of triangular meshes arithmetic, by which we obtain meshes space information and keep meshes topological information consistency. Finally, using the result to validate the method, we know this method is useful to deal with cutting triangle meshes, and provide the foundation for other works.
引文
[1] 李衷怡, 胡薇, 吴勇等. 海量断层数据的三维重建. 计算机工程与科学, 2006(9)
[2] 李衷怡, 吴勇. 海量断层网格数据的并行简化. 计算机与数字工程, 2006(8)
[3] RhodesM ichael L, Roberstson DouglasD. Applications in surgery and therapy. Computer Graphics and Applications, 1996, 16(1): 28-29
[4] U.Tiede, T.Schiemann, K.H. H?hne. Visualizing the Visible Human. IEEE Compute Graphics. 1996, 1(16)
[5] V. Spitzer, M. J. Ackerman, A. L. Scherzinger, and D. Whitlock, "The Visible Human Male: A technical report," Journal of the American Medical Informatics Association, 1995
[6] 张小宁. 三维地质重构相关算法研究及应用. 西安电子科技大学硕士学位论文, 2005
[7] Han-Wen Nienhuys, A Frank van der. A Delaunay approach to interactive cutting in triangulated surfaces. Institute of information and computing sciences, Utrecht university technical report, UU-CS-2002-044
[8] Olivier Devillers. On Deletion in delaunay Triangulations. arXiv:CS.CG/9907023 v1 16 Jul 1999
[9] 闵卫东, 唐泽圣. 二维任意域内点集的 Delaunay 三角划分的研究. 计算机学报, 1995, 18(5)
[10] Prepatata F P, Shamos M I. Computational geometry, an introduction. New York:Springer-Verlag, 1985
[11] Lawson C L. Properties of n-dimensional triangulation. CAGD, 1986, 3: 231-246
[12] 丁永祥, 夏巨谌, 王英等. 任意多边形的 Delaunay 三角剖分. 计算机学报, 1994, 4(17): 270-275
[13] 秦绪佳, 欧宗瑛, 侯建华. 医学图像三维重建模型的剖切与立体视窗剪裁. 计算机辅助设计与图形学学报, 2002, 14(3): 275 -279
[14] 孙家广, 杨长贵. 计算机图形学. 清华大学出版社, 1995: 390-391
[15] 王彦妮. 三维地层建模及可视化方法研究, 山东科技大学硕士学位论文, 2004
[16] Lorensen W. E., H. E. Cline. Marching cubes: a high resolution 3D surface construction algorithm. SIGGRAPH ’87 Proc., 1987, 21(4): 163 - 169
[17] Hoppe H. Progressive mesh. Computer Graphics, Annual Conference Series, New Orleans, USA: Addison-Wesley, 1996: 99-108
[18] Zhou Yong, ChenWei-hai, Tang Ze-sheng. An elaborate ambiguity detection method for constructing iso surfaces with in tetra-hedralmeshes. Computer & Graphics, 1995, 19 (3): 355-364
[19] 陈矛, 唐泽圣, 唐龙. 三维表面模型的快速切割算法. 软件学报, 1998, 9(9): 661-664
[20] Atherton P, Weiler W, Greenberg D P. Polygon Shadow Generation[J]. Computer Graphics, 1978, 12(3): 275-81
[21] 鲁爱东, 唐龙, 徐玉华. 一种基于轮廓线的三维表面模型的快速切割算法. 计算机工程, 2001, 19: 98-100
[22] 唐泽圣等编著. 三维数据场可视化. 清华大学出版社, 1999
[23] 崔毅. 医学技术可视化和肝肿瘤介入手术仿真系统的实现. 清华大学硕士学位论文, 1999
[24] 唐龙, 崔毅, 刘振西. 基于三维超声图象的肝肿瘤治疗手术仿真. CMIA 99 论文集, 总 98 期增刊, 电子工程师, 苏州:1999, 10: 331-335
[25] Kim Yougmin, Kin Jin H., Basoglu Christopher et al. Programmable ul-trasound imaging using multimedia technologies:a nextgeneration ul-trasound machine. IEEE Transaction on Information Technology in Biomedicine. 1997. 3, 1(1): 19-29
[26] 秦续佳. 医学图像三维重建及可视化技术研究. 大连理工大学博士学位论文, 2001
[27] Philip J.Schneider David H.Eberly 著 周长发 译. 计算机图形学几何工具算法详解. 电子工业出版社, 2005. 1
[28] 欧宗瑛, 宋涛, 李晖等. 基于 CT、MRI 断层图像的人体三维建模. 焦作大学学报, 2003, 2: 55-58.
[29] 陈闯, 周淑秋, 黎刚. 医学 CT 三维重建. 首都师范大学学报(自然科学版), 2004, 25: 29-36
[30] 于海龙, 韦中亚, 高振纪. 基于表面模型的三维数据重建方法的研究与实现. 地理学与国土研究, 2002, 2(18): 38-40
[31] 管群, 刘浩吾. 基于 VR-GIS 地质景观的三维重建. 岩土工程学报, 2001, 23(4): 499 - 501
[32] 田捷. 三维医学图像处理与分析系统. CT 理论与应用研究, 1999, 8(2): 39-43
[33] 安新伟, 张晓兵, 尹涵春. 医学图像三维重建的研究. 电子器件, 2001, 3(24): 207-212
[34] Keppel E. Approximating complex surfaces by triangulation of contour lines. IBM Journal of Research and Development, 1975, 19(1): 2-11
[35] Herman G.. T., Liu H. K. Three-dimensional display of human organs from computed tomograms. Computer Graphics and Image Processing, 1979, 9(1): 1-21
[36] 耿国华, 赵杰, 赵宗涛. 医学图像处理中三维模型的快速重构与简化. 西北大学学报(自然科学版), 2000, 32(3): 221-224
[37] 吕晟珉, 杨勋年, 汪国昭. 海量数据的曲面分层重建算法. 软件学报, 2003, 14(8): 1448-1455
[38] Soetebier I., Birthelmer H., Sahm J. et al. Managing large progressive meshes. Computers & Graphics, 2004, 28: 691-701
[39] 何晖光, 田捷, 张晓鹏等. 网格模型化简综述. 软件学报, 2002, 12(13): 2215-2224
[40] Hoppe H. Progressive meshes. Computer Graphics (SIGGRAPH ’96 Proceedings), 1996: 99-108
[41] J. Popovic, H. Hoppe. Progressive simple complexes. Computer Graphics (SIGGRAPH 1997 Proceedings): 217-224
[2] 李衷怡, 吴勇. 海量断层网格数据的并行简化. 计算机与数字工程, 2006(8)
[3] RhodesM ichael L, Roberstson DouglasD. Applications in surgery and therapy. Computer Graphics and Applications, 1996, 16(1): 28-29
[4] U.Tiede, T.Schiemann, K.H. H?hne. Visualizing the Visible Human. IEEE Compute Graphics. 1996, 1(16)
[5] V. Spitzer, M. J. Ackerman, A. L. Scherzinger, and D. Whitlock, "The Visible Human Male: A technical report," Journal of the American Medical Informatics Association, 1995
[6] 张小宁. 三维地质重构相关算法研究及应用. 西安电子科技大学硕士学位论文, 2005
[7] Han-Wen Nienhuys, A Frank van der. A Delaunay approach to interactive cutting in triangulated surfaces. Institute of information and computing sciences, Utrecht university technical report, UU-CS-2002-044
[8] Olivier Devillers. On Deletion in delaunay Triangulations. arXiv:CS.CG/9907023 v1 16 Jul 1999
[9] 闵卫东, 唐泽圣. 二维任意域内点集的 Delaunay 三角划分的研究. 计算机学报, 1995, 18(5)
[10] Prepatata F P, Shamos M I. Computational geometry, an introduction. New York:Springer-Verlag, 1985
[11] Lawson C L. Properties of n-dimensional triangulation. CAGD, 1986, 3: 231-246
[12] 丁永祥, 夏巨谌, 王英等. 任意多边形的 Delaunay 三角剖分. 计算机学报, 1994, 4(17): 270-275
[13] 秦绪佳, 欧宗瑛, 侯建华. 医学图像三维重建模型的剖切与立体视窗剪裁. 计算机辅助设计与图形学学报, 2002, 14(3): 275 -279
[14] 孙家广, 杨长贵. 计算机图形学. 清华大学出版社, 1995: 390-391
[15] 王彦妮. 三维地层建模及可视化方法研究, 山东科技大学硕士学位论文, 2004
[16] Lorensen W. E., H. E. Cline. Marching cubes: a high resolution 3D surface construction algorithm. SIGGRAPH ’87 Proc., 1987, 21(4): 163 - 169
[17] Hoppe H. Progressive mesh. Computer Graphics, Annual Conference Series, New Orleans, USA: Addison-Wesley, 1996: 99-108
[18] Zhou Yong, ChenWei-hai, Tang Ze-sheng. An elaborate ambiguity detection method for constructing iso surfaces with in tetra-hedralmeshes. Computer & Graphics, 1995, 19 (3): 355-364
[19] 陈矛, 唐泽圣, 唐龙. 三维表面模型的快速切割算法. 软件学报, 1998, 9(9): 661-664
[20] Atherton P, Weiler W, Greenberg D P. Polygon Shadow Generation[J]. Computer Graphics, 1978, 12(3): 275-81
[21] 鲁爱东, 唐龙, 徐玉华. 一种基于轮廓线的三维表面模型的快速切割算法. 计算机工程, 2001, 19: 98-100
[22] 唐泽圣等编著. 三维数据场可视化. 清华大学出版社, 1999
[23] 崔毅. 医学技术可视化和肝肿瘤介入手术仿真系统的实现. 清华大学硕士学位论文, 1999
[24] 唐龙, 崔毅, 刘振西. 基于三维超声图象的肝肿瘤治疗手术仿真. CMIA 99 论文集, 总 98 期增刊, 电子工程师, 苏州:1999, 10: 331-335
[25] Kim Yougmin, Kin Jin H., Basoglu Christopher et al. Programmable ul-trasound imaging using multimedia technologies:a nextgeneration ul-trasound machine. IEEE Transaction on Information Technology in Biomedicine. 1997. 3, 1(1): 19-29
[26] 秦续佳. 医学图像三维重建及可视化技术研究. 大连理工大学博士学位论文, 2001
[27] Philip J.Schneider David H.Eberly 著 周长发 译. 计算机图形学几何工具算法详解. 电子工业出版社, 2005. 1
[28] 欧宗瑛, 宋涛, 李晖等. 基于 CT、MRI 断层图像的人体三维建模. 焦作大学学报, 2003, 2: 55-58.
[29] 陈闯, 周淑秋, 黎刚. 医学 CT 三维重建. 首都师范大学学报(自然科学版), 2004, 25: 29-36
[30] 于海龙, 韦中亚, 高振纪. 基于表面模型的三维数据重建方法的研究与实现. 地理学与国土研究, 2002, 2(18): 38-40
[31] 管群, 刘浩吾. 基于 VR-GIS 地质景观的三维重建. 岩土工程学报, 2001, 23(4): 499 - 501
[32] 田捷. 三维医学图像处理与分析系统. CT 理论与应用研究, 1999, 8(2): 39-43
[33] 安新伟, 张晓兵, 尹涵春. 医学图像三维重建的研究. 电子器件, 2001, 3(24): 207-212
[34] Keppel E. Approximating complex surfaces by triangulation of contour lines. IBM Journal of Research and Development, 1975, 19(1): 2-11
[35] Herman G.. T., Liu H. K. Three-dimensional display of human organs from computed tomograms. Computer Graphics and Image Processing, 1979, 9(1): 1-21
[36] 耿国华, 赵杰, 赵宗涛. 医学图像处理中三维模型的快速重构与简化. 西北大学学报(自然科学版), 2000, 32(3): 221-224
[37] 吕晟珉, 杨勋年, 汪国昭. 海量数据的曲面分层重建算法. 软件学报, 2003, 14(8): 1448-1455
[38] Soetebier I., Birthelmer H., Sahm J. et al. Managing large progressive meshes. Computers & Graphics, 2004, 28: 691-701
[39] 何晖光, 田捷, 张晓鹏等. 网格模型化简综述. 软件学报, 2002, 12(13): 2215-2224
[40] Hoppe H. Progressive meshes. Computer Graphics (SIGGRAPH ’96 Proceedings), 1996: 99-108
[41] J. Popovic, H. Hoppe. Progressive simple complexes. Computer Graphics (SIGGRAPH 1997 Proceedings): 217-224