基于空间散乱点的复杂曲面建模与可视化研究
|
摘要
曲面重建技术在曲面测量造型与可视化等领域有着广泛的应用背景。基于散乱点集的曲面重建作为最具普遍性的曲面重建问题,无论在理论上还是在应用上都具有非常重要的意义。
本文首先对散乱点曲面重建的应用价值及解决曲面重建问题的几种相关技术,即三角剖分与曲面分割、科学计算可视化等重建技术等作了简要介绍。并提出了本文付诸研究并取得进展的若干问题。
然后介绍了曲面三角剖分、Delaunay三角剖分及约束三角剖分等曲面剖分技术,并分析了曲面重建的现状,对曲面重建技术做了简单分类,然后对一些国内外散乱点曲面重建的经典算法做了介绍,并进行了分析、归纳与对比。
再次讨论了散乱点曲面重建的关键,并在此基础上提出了基于聚类分析的散乱点曲面重建方法。对所用到的主成分分析技术、聚类分析技术、凸壳技术等做了详细的介绍,并在此基础上详细阐述了自己的算法,提出了一种新的边界缝合技术,较好的解决了散乱点曲面重建问题。
然后又介绍了OpenGL的功能、特点及鼠标跟踪球算法,并介绍了怎样利用OpenGL编程实现三维模型可视化,并实现三维模型的显示变换。最后给出了利用OpenGL实现的模型绘制效果图。
最后对本文的研究工作进行了总结,并对曲面重建领域的发展前景及下一步努力的方向进行了展望。
The technique of surface reconstruction has extensive use in surface measuring modification, visualization, and such on fields. The technique of surface reconstruction from scattered points, for its universality, is very important both theoretically and practically.Firstly, a brief introduction is made about practical value of surface reconstruction of scattered points. And then three kinds of techniques including surface triangulation, surface subdivision and scientific visualization are reviewed. Finally, several problems are put forward about surface reconstruction, which have been studied carefully in this dissertation.Secondly, surface triangulation technique, which refers to triangulation of 2d points, Delaunay triangulation and constrained Delaunay triangulation, is introduced at first, and then present work about surface reconstruction is analyzed, and main classifications are made with surface reconstruction method. After that, several kinds of classical surface reconstruction methods are described, and analysis, generalization and comparison are made about them..Thirdly, the key factor of surface reconstruction is discussed, then the surface reconstruction method of scattered points based on clustering technique is put forward. And also relative techniques involved, such as primary component analysis technique and convex technique, are introduced. And based on this, our method of surface reconstruction is described in detail. Still a method of border connection is brought forward. Using our method surface reconstruction can be well finished.Fourthly, function and character of OpenGL are introduced, and also mouse trackball algorithm. Then we explained how to implement the 3d model visualization with OpenGL programming, and also transformation and display is made. Finally, resulted graphics using OpenGL are shown.Finally, we draw some conclusions of this dissertation and suggest the future work to do in related research fields.
本文首先对散乱点曲面重建的应用价值及解决曲面重建问题的几种相关技术,即三角剖分与曲面分割、科学计算可视化等重建技术等作了简要介绍。并提出了本文付诸研究并取得进展的若干问题。
然后介绍了曲面三角剖分、Delaunay三角剖分及约束三角剖分等曲面剖分技术,并分析了曲面重建的现状,对曲面重建技术做了简单分类,然后对一些国内外散乱点曲面重建的经典算法做了介绍,并进行了分析、归纳与对比。
再次讨论了散乱点曲面重建的关键,并在此基础上提出了基于聚类分析的散乱点曲面重建方法。对所用到的主成分分析技术、聚类分析技术、凸壳技术等做了详细的介绍,并在此基础上详细阐述了自己的算法,提出了一种新的边界缝合技术,较好的解决了散乱点曲面重建问题。
然后又介绍了OpenGL的功能、特点及鼠标跟踪球算法,并介绍了怎样利用OpenGL编程实现三维模型可视化,并实现三维模型的显示变换。最后给出了利用OpenGL实现的模型绘制效果图。
最后对本文的研究工作进行了总结,并对曲面重建领域的发展前景及下一步努力的方向进行了展望。
The technique of surface reconstruction has extensive use in surface measuring modification, visualization, and such on fields. The technique of surface reconstruction from scattered points, for its universality, is very important both theoretically and practically.Firstly, a brief introduction is made about practical value of surface reconstruction of scattered points. And then three kinds of techniques including surface triangulation, surface subdivision and scientific visualization are reviewed. Finally, several problems are put forward about surface reconstruction, which have been studied carefully in this dissertation.Secondly, surface triangulation technique, which refers to triangulation of 2d points, Delaunay triangulation and constrained Delaunay triangulation, is introduced at first, and then present work about surface reconstruction is analyzed, and main classifications are made with surface reconstruction method. After that, several kinds of classical surface reconstruction methods are described, and analysis, generalization and comparison are made about them..Thirdly, the key factor of surface reconstruction is discussed, then the surface reconstruction method of scattered points based on clustering technique is put forward. And also relative techniques involved, such as primary component analysis technique and convex technique, are introduced. And based on this, our method of surface reconstruction is described in detail. Still a method of border connection is brought forward. Using our method surface reconstruction can be well finished.Fourthly, function and character of OpenGL are introduced, and also mouse trackball algorithm. Then we explained how to implement the 3d model visualization with OpenGL programming, and also transformation and display is made. Finally, resulted graphics using OpenGL are shown.Finally, we draw some conclusions of this dissertation and suggest the future work to do in related research fields.
引文
1.王家耀,空间信息系统原理[M],北京:科学出版社,2001,5.
2.李志林,朱庆,数字高程模型[M],武汉:武汉大学出版社,2001,7.
3.吴信才,地理信息系统原理与方法[M],西安:电子工业出版社,2002,3.
4.吴立新,史文中,地理信息系统原理与方法[M],北京:科学出版社,2003,10.
5.杨孟达,煤矿地质学[M],北京:煤炭工业出版社.
6.唐荣锡,计算机图形学[M],北京:科学出版社.
7.周培德,卢开澄.计算几何[M],北京:清华大学出版社,2002,5
8.张永春,三维散乱点集的曲面三角剖分[J],中国图象图形学报,2003,12(12):1379～1388.
9. B. Delaunay, Sur la sphere vide, Bull. Acad. Sci. USSR(Ⅶ), Classe Sci. Mat. Nat[M]., 1934, 793—800.
10.胡鑫,反求工程中散乱点云数据的自动分割与曲面重构[J],上海交通大学学报,Vol.38 No,Jan.2004.
11.唐泽胜,等.三维数据场可视化[M],北京:清华大学出版社,1999.
12.吴立新等,3D地学模拟与虚拟矿山系统,测绘学报[J],2002,21 (1).
13..Richard S. Wright, Jr. Michael Sweet, OpenGL超级宝典(第二斑)[M],北京:人民邮电出版社,2001.
14. G. F. Voronoi, Z. Reine Angew, Math[M], 1958, 134.
15. R. E. Miles, On the homogeneous planar Poisson process, Mathematical Bioscience[J], 1970, Vol. 6, 85—127.
16. Cavendish J C, Field D A. Frey W H. An approach to automatic three-dimensional finite element mesh generation[J]. International Journal for Numerical Methods in Engineering. 1985, 21:329-347.
17. C. Lawson. Generation a triangular grid with application of contour plotting. Technical Memo. 299. Jet Propulation Laboratory, Pasadena, California. 1972.
18. Lewis B A. and Robinson J S. Triangulation of Planar Regions with Applications, The Computer Journal, 1978, 21(4): 324～332.
19.崔汉国等,三维任意区域中点集的三角剖分算法[J],计算机辅助设计与图形学学报,第7卷第2期1995年4月.
20.周晓云,刘慎权,实现约束Delaunay三角剖分的健壮算法[J],计算机学报Vol.19 No.8,Aug.1996.
21.梅承力,肖高逾,周源华,一种新的带特征约束的Delaunay三角剖分算法[J],电子学报,Vol.29 No July 2001.
22.易法令,韩德志,带特征线约束的Delaunay三角剖分最优算法的研究及实现[J],计算机工程,2001年6月第27卷第6期.
23.郭仁忠,空间分析(第二版)[M],北京:高等教育出版社,2001,10.
24.武强,三维地质建模与可视化方法研究,中国科学D辑,地球科学[J]2004.
25. AZERNIKOV, S., FISCHER, A., "Surface Reconstruction of Freeform Objects based on Multiresolution Volumetric Methods", Special Issue on Geometric Modeling and Computer graphics, in J. of Shape Modeling[J], Vol. 9, No. 2, pp. 177-190.
26. Sergei Azernikov, Alex Miropolsky, Surface reconstruction of freeform objects based on multiresolution volumetric method. Symposium on Solid Modeling and Applications[J] 2003: 115-126.
27. H oppe H, De R T, Ducham p T. Surface reconstruction from unorganized points[J]. Computer Graphics, 1992. 26(2):71—78.
28. Hoppe. H. (1994). Surface Reconstruction from Unorganized Point Clouds[D], PhD. Thesis, Univercity of Washington.
29. H. Edelsbrutmer and E. Mucke, 3D Alpha Shapes, ACM Trans. on Graphics[J], 13(1), pp. 43—72(1994).
30. B. Guo, J. Menon and B. Willette. Surface reconstruction using Alpha Shapes. Computer Graphics forum[J]. 1997, 16(4): 177190.
31. Marek Teichmann, Michael Capps. Surface Reconstruction with Anisotropic Density-Scaled Alpha Shapes. Technical Report[J], 1998. Laboratory for computer science, Massachusetts institute of technology.
32. Nina Ainenta, Marshall Bern and Manolis Kamvysselis. A New Voronoi-Based Surface Reconstruction Algorithm. SIGGRAPH98[J], pages 415-421.
33.王青,王融清,鲍虎军,彭群生。散乱数据点的增量快速曲面重建算法.软件学报[J].2000,11(9):12211227.
34.谭建荣,李立新,基于曲面局平特性的散乱数据拓扑重建算法[J],软件学报,Vol.13,No.11.
35.李立新,谭建容.散乱点集曲面重建的理论、方法及应用研究[D].杭州:浙江大学博士学位论文,2001.
36. B. Joe. Construction of three-dimensional Delaunay triangulations using local transformations[J]. Computer Aided Geometric Design, 1991, 8: 123-142..
37. S. Gumhold, X. Wang and R. MacLeod, "Feature extraction from point clouds"[J], pp.293-305, 10IMR, 2001.
38. Ye Duan and Hong Qin, "A Novel Modeling Algorithm for Shape Recovery of Unknown Topology." Proceedings of The Eighth IEEE International Conference on Computer Vision[J] (ICCV 2001), pages 402-409, July 2001, Vancouver, Canada.
39. Jan Hradek, Methods of surface reconstruction from scattered data. Technical Report[J] No. DCSE/TR-2003-02March, 2003.
40. C. Grimm and Jughes, Modeling surfaces of arbitrary topology using manifolds, SIGGRAPH'95 Proceedings[J], 1995: 359368.
41.尤成业,基础拓扑学讲义[M],北京:北京大学出版社,1997.
2.李志林,朱庆,数字高程模型[M],武汉:武汉大学出版社,2001,7.
3.吴信才,地理信息系统原理与方法[M],西安:电子工业出版社,2002,3.
4.吴立新,史文中,地理信息系统原理与方法[M],北京:科学出版社,2003,10.
5.杨孟达,煤矿地质学[M],北京:煤炭工业出版社.
6.唐荣锡,计算机图形学[M],北京:科学出版社.
7.周培德,卢开澄.计算几何[M],北京:清华大学出版社,2002,5
8.张永春,三维散乱点集的曲面三角剖分[J],中国图象图形学报,2003,12(12):1379～1388.
9. B. Delaunay, Sur la sphere vide, Bull. Acad. Sci. USSR(Ⅶ), Classe Sci. Mat. Nat[M]., 1934, 793—800.
10.胡鑫,反求工程中散乱点云数据的自动分割与曲面重构[J],上海交通大学学报,Vol.38 No,Jan.2004.
11.唐泽胜,等.三维数据场可视化[M],北京:清华大学出版社,1999.
12.吴立新等,3D地学模拟与虚拟矿山系统,测绘学报[J],2002,21 (1).
13..Richard S. Wright, Jr. Michael Sweet, OpenGL超级宝典(第二斑)[M],北京:人民邮电出版社,2001.
14. G. F. Voronoi, Z. Reine Angew, Math[M], 1958, 134.
15. R. E. Miles, On the homogeneous planar Poisson process, Mathematical Bioscience[J], 1970, Vol. 6, 85—127.
16. Cavendish J C, Field D A. Frey W H. An approach to automatic three-dimensional finite element mesh generation[J]. International Journal for Numerical Methods in Engineering. 1985, 21:329-347.
17. C. Lawson. Generation a triangular grid with application of contour plotting. Technical Memo. 299. Jet Propulation Laboratory, Pasadena, California. 1972.
18. Lewis B A. and Robinson J S. Triangulation of Planar Regions with Applications, The Computer Journal, 1978, 21(4): 324～332.
19.崔汉国等,三维任意区域中点集的三角剖分算法[J],计算机辅助设计与图形学学报,第7卷第2期1995年4月.
20.周晓云,刘慎权,实现约束Delaunay三角剖分的健壮算法[J],计算机学报Vol.19 No.8,Aug.1996.
21.梅承力,肖高逾,周源华,一种新的带特征约束的Delaunay三角剖分算法[J],电子学报,Vol.29 No July 2001.
22.易法令,韩德志,带特征线约束的Delaunay三角剖分最优算法的研究及实现[J],计算机工程,2001年6月第27卷第6期.
23.郭仁忠,空间分析(第二版)[M],北京:高等教育出版社,2001,10.
24.武强,三维地质建模与可视化方法研究,中国科学D辑,地球科学[J]2004.
25. AZERNIKOV, S., FISCHER, A., "Surface Reconstruction of Freeform Objects based on Multiresolution Volumetric Methods", Special Issue on Geometric Modeling and Computer graphics, in J. of Shape Modeling[J], Vol. 9, No. 2, pp. 177-190.
26. Sergei Azernikov, Alex Miropolsky, Surface reconstruction of freeform objects based on multiresolution volumetric method. Symposium on Solid Modeling and Applications[J] 2003: 115-126.
27. H oppe H, De R T, Ducham p T. Surface reconstruction from unorganized points[J]. Computer Graphics, 1992. 26(2):71—78.
28. Hoppe. H. (1994). Surface Reconstruction from Unorganized Point Clouds[D], PhD. Thesis, Univercity of Washington.
29. H. Edelsbrutmer and E. Mucke, 3D Alpha Shapes, ACM Trans. on Graphics[J], 13(1), pp. 43—72(1994).
30. B. Guo, J. Menon and B. Willette. Surface reconstruction using Alpha Shapes. Computer Graphics forum[J]. 1997, 16(4): 177190.
31. Marek Teichmann, Michael Capps. Surface Reconstruction with Anisotropic Density-Scaled Alpha Shapes. Technical Report[J], 1998. Laboratory for computer science, Massachusetts institute of technology.
32. Nina Ainenta, Marshall Bern and Manolis Kamvysselis. A New Voronoi-Based Surface Reconstruction Algorithm. SIGGRAPH98[J], pages 415-421.
33.王青,王融清,鲍虎军,彭群生。散乱数据点的增量快速曲面重建算法.软件学报[J].2000,11(9):12211227.
34.谭建荣,李立新,基于曲面局平特性的散乱数据拓扑重建算法[J],软件学报,Vol.13,No.11.
35.李立新,谭建容.散乱点集曲面重建的理论、方法及应用研究[D].杭州:浙江大学博士学位论文,2001.
36. B. Joe. Construction of three-dimensional Delaunay triangulations using local transformations[J]. Computer Aided Geometric Design, 1991, 8: 123-142..
37. S. Gumhold, X. Wang and R. MacLeod, "Feature extraction from point clouds"[J], pp.293-305, 10IMR, 2001.
38. Ye Duan and Hong Qin, "A Novel Modeling Algorithm for Shape Recovery of Unknown Topology." Proceedings of The Eighth IEEE International Conference on Computer Vision[J] (ICCV 2001), pages 402-409, July 2001, Vancouver, Canada.
39. Jan Hradek, Methods of surface reconstruction from scattered data. Technical Report[J] No. DCSE/TR-2003-02March, 2003.
40. C. Grimm and Jughes, Modeling surfaces of arbitrary topology using manifolds, SIGGRAPH'95 Proceedings[J], 1995: 359368.
41.尤成业,基础拓扑学讲义[M],北京:北京大学出版社,1997.