复杂场景的优化处理技术研究
|
摘要
复杂场景的优化处理技术是解决场景的复杂性和交互实时性矛盾的有效手段,也是虚拟现实技术中的关键技术之一。
虚拟现实技术是以图、文、声为基础进行场景的表现,所以本文首先简要介绍了计算机图形学的基本理论,包括:图形的表示方法、表示图形的数据准备以及图形的显示。在此基础上,介绍了优化场景的几何剖分技术,最常用的几何剖分技术有BSP树、四叉树、八叉树。这些为后期的应用研究奠定了坚实的理论基础。在模型的优化方面,着重讨论了多分辨率模型的简化算法,并对多分辨率模型简化的不同算法进行了划分归类,总结了不同算法的优缺点并进行了比较,对多分辨率模型简化的选择尺度、平滑过渡和误差度量准则这几方面做了详细的论述。递进网格在模型的简化上具有很重要的地位,本文介绍了递进网格的快速生成算法、基于边折叠的网格简化算法以及三角形折叠简化算法。在三维场景的绘制上主要介绍了场景的可见性剔除技术、入口技术、基于图像的加速绘制技术及场景的调度算法。最后以联合站虚拟培训系统为例,将多分辨率模型的平滑过渡、三角形折叠简化算法、入口技术以及场景调度等多种优化方法应用到系统中,提高了联合站虚拟培训系统的运行速度,并在应用中针对三角形折叠简化算法和场景调度策略的缺点进行了改进。
Optimization technique of complex scene is an effective means for solving the contradiction of complexity and real-time interaction, and it also is one of the key techniques of virtual reality.
Virtual reality technique displays the scene based on the graphics, text, and sound. So, this paper introduces the basic theory of computer graphics, including the methods of graphical displaying, the data preparation of graphics displaying and the graphics showing. On the basis of these, the paper introduces the spatial partition technology of the scene optimizing. The techniques used most commonly include BSP tree, quadtree and octree. All of these lay a solid theoretical foundation for the latter part of applied research. In the aspect of the model optimizing, different simplified algorithms of multiple levels of detail model are discussed emphatically and classified. The advantages and disadvantages of different methods are compared, and choosing scale, smooth transition and error metrics of multiple levels of detail model are discussed in detail. Progressive mesh is very important in the model simplification. This paper introduces the rapid generation algorithms of progressive mesh, edge collapsed algorithms of progressive mesh and the folded triangle simplified algorithm.On the drawing of 3D scenes, the scene visibility removed technology, portal technology, accelerated rendering technology basing image and scene scheduling algorithm are researched emphatically. Finally, all kinds of optimization methods that multi-resolution model of smooth transition, triangle folding simplified algorithm, portal technique, and scene scheduling are applied to the system basing on the joint station, which improve the system’s operating, and the simplified algorithm for folding triangle scene and the shortcomings of scheduling strategy are improved in this application.
虚拟现实技术是以图、文、声为基础进行场景的表现,所以本文首先简要介绍了计算机图形学的基本理论,包括:图形的表示方法、表示图形的数据准备以及图形的显示。在此基础上,介绍了优化场景的几何剖分技术,最常用的几何剖分技术有BSP树、四叉树、八叉树。这些为后期的应用研究奠定了坚实的理论基础。在模型的优化方面,着重讨论了多分辨率模型的简化算法,并对多分辨率模型简化的不同算法进行了划分归类,总结了不同算法的优缺点并进行了比较,对多分辨率模型简化的选择尺度、平滑过渡和误差度量准则这几方面做了详细的论述。递进网格在模型的简化上具有很重要的地位,本文介绍了递进网格的快速生成算法、基于边折叠的网格简化算法以及三角形折叠简化算法。在三维场景的绘制上主要介绍了场景的可见性剔除技术、入口技术、基于图像的加速绘制技术及场景的调度算法。最后以联合站虚拟培训系统为例,将多分辨率模型的平滑过渡、三角形折叠简化算法、入口技术以及场景调度等多种优化方法应用到系统中,提高了联合站虚拟培训系统的运行速度,并在应用中针对三角形折叠简化算法和场景调度策略的缺点进行了改进。
Optimization technique of complex scene is an effective means for solving the contradiction of complexity and real-time interaction, and it also is one of the key techniques of virtual reality.
Virtual reality technique displays the scene based on the graphics, text, and sound. So, this paper introduces the basic theory of computer graphics, including the methods of graphical displaying, the data preparation of graphics displaying and the graphics showing. On the basis of these, the paper introduces the spatial partition technology of the scene optimizing. The techniques used most commonly include BSP tree, quadtree and octree. All of these lay a solid theoretical foundation for the latter part of applied research. In the aspect of the model optimizing, different simplified algorithms of multiple levels of detail model are discussed emphatically and classified. The advantages and disadvantages of different methods are compared, and choosing scale, smooth transition and error metrics of multiple levels of detail model are discussed in detail. Progressive mesh is very important in the model simplification. This paper introduces the rapid generation algorithms of progressive mesh, edge collapsed algorithms of progressive mesh and the folded triangle simplified algorithm.On the drawing of 3D scenes, the scene visibility removed technology, portal technology, accelerated rendering technology basing image and scene scheduling algorithm are researched emphatically. Finally, all kinds of optimization methods that multi-resolution model of smooth transition, triangle folding simplified algorithm, portal technique, and scene scheduling are applied to the system basing on the joint station, which improve the system’s operating, and the simplified algorithm for folding triangle scene and the shortcomings of scheduling strategy are improved in this application.
引文
[1]普建涛,查红彬.大规模复杂场景的可见性问题研究[J].计算机研究与发展,2005,42:236~246.
[2]罗运和,戴青.计算机图形学基础(第二版)[M].北京:中国计量出版社,2003,1~10.
[3]银红霞,杜四春,蔡立军.计算机图形学[M].北京:中国水利水电出版社,2005,1～30.
[4]石教英.虚拟现实基础及实用算法[M].北京:科学出版社,2002,76～111.
[5]于文洋,杨崇俊等.三维复杂场景管理研究[J].计算机工程与应用,2006,No.13.
[6]刘文炜.基于虚拟环境技术的实时显示算法的研究与实现[D].北京:中国科学院计算技术研究所,1996.
[7] Frank Luna. Introduction to 3D Game Programming with DirectX 9.0.Wordware [M]. Publishing, 2003:75-145.
[8] Blinn J. Simulation of Wrinkled Surfaces[J]. Computer Graphics, 1978, 12(3):286-292.
[9]曾金发.虚拟现实复杂场景生成、简化和优化技术研究[D].南京:南京理工大学,2004.
[10]张国宣,韦穗.虚拟现实中的LOD技术[J].微机发展,2001,11～16.
[11]周昆,潘志庚,石教英.多细节层次模型间的平滑过渡[J].计算机辅助设计与图形学学报,2000,463～466.
[12]潘志庚,马小虎,石教英.多细节层次模型自动生成技术综述[J] .中国图像图形学报,1998,3(9):754～759.
[13]马小虎.虚拟现实中多细节层次模型的研究[D].浙江:浙江大学,1997.
[14]陈礼民,秦爱红.三维图形简化新算法.中国图像图形学报,1997,2(2):157～160.
[15]华炜.大规模场景快速绘制技术[D].杭州:浙江大学,2002.
[16]刘焕勘.多细节层次模型简化技术的研究[D].武汉:武汉理工大学,2005.
[17]蒋再松.基于不规则三角网的LOD研究[D].成都:西南交通大学,2006.
[18]邵岳伟.基于最新图形处理器的图形引擎技术研究[D].西安:西北工业大学,2006.
[19] Wang Wei-chen, Jiang Xiaohong. Optimizing Real-Time Performance of 3D Virtual Mining Environment with MultiGen Creator[J]. CADDM, 2004, 14(1):61-69.
[20] N. Greene, M. Kass, G. Miller, Hierarchical Z-buffer visibility[J]. Computer Graphics (in proceeding of SIGGRAPH93), 1993,27(2):231~238.
[21] Algorri M-E. Schmitt F. Mesh. Simplification[C]. In proceedings of Euro Graphics’95[C]. 1996.77-86.
[22] Rubin S M. The representation and display of scenes with a wide range of detail.The Graphics and Image Processing, 1982,19: 291～299.
[23] DeHaemer Jr, Michael J. Simplification of Objects Render by PolygonalApproximations. Computer&Graphics,1991,15(2):175-184.
[24] Guezeic A. Surface simplification inside a tolerance. Technical Report, IBM Division, T.J.Watson Research Center, 1996.
[25] Garland M, Heckbert P. Surface simplification using quadric error metrics.Computer Graphics(SIGGRAPH Proceedings), 1997, 31:209-216.
[26]苗福生.数字几何处理的关健技术研究[D].西安:西北大学,2004.
[27]周昆,潘志庚,石教英.基于三角形折叠的网格简化算法[J].计算机学报,1998,No:21.
[28] John S. Falby, Michael J. Hierarchical Data Structures for Real-TimeThree-Dimensional Visual Simulation. Computer&Graphic,2002,17(1): 65~9.
[29] Zhang, H. S., Manocha, D., Hudson. T., et al., Visibility culling using hierarchical occlusion maps[A]. Computer Graphics[C], 1997,31(3):77~88.
[30] Levi O, Zohar R, Barad H, Klimovitski A. A Compact Method for Backface Culling. Computers and Graphics, 1995, 25(S):483-487.
[31]李胜.大规模室外地形场景加速绘制技术研究[D].北京:中国科学院软件研究所,2004.
[32]淮永建.虚拟场景中实时图形绘制关键技术研究[D].西安:西北工业大学,2002.
[33]侯涛.三维仿真场景优化理论与算法研究[D].北京:中国科学院遥感应用研究所,2006.
[34]张毅彬.虚拟现实引擎中的入口生成与路径规划[D].浙江:浙江大学,2005.
[35]李磊.场景快速渲染中的入口生成技术研究[D].浙江:浙江大学,2006.
[36]罗冠,郝重阳,王淑敏等.虚拟现实引擎中的入口技术[J].系统仿真学报,2001,No:13.
[37] McReynolds T, Blythe D, Grantham B, and Nelson S, Programming with OpenGL: Advanced Techniques, Course 17 notes at SIGGRAPH'98, 1998.
[38] Hoppe H. Progressive meshes, Computer Graphics(SIGGRAPH Proceedings),1996, 30:99～108.
[39] Hamann, Bernd. A Data Reduction Scheme for Triangulated Surfaces.Aided Geometric Design, 1994, 11(2):197-214.
[40] H.Hoppe, View-dependent refinement of progressive meshes[J], Preceeding of SIGGRAPH’97, 1997.189-204.
[41] Naylor B F. Binary space partitioning trees:an alternative representation of polytopes[J]. Computer Aided Design, 1990,22(2): 250-253.
[42] Ronfard R, Rossignac J R. Full-range approximation of triangulated polyhedral Computer Graphics Forum(Proceedings of Eurographics), 1996, 15(3): 67～76.
[43]李春雨,邱道尹,谭同德等.计算机图形学理论与实践[M].北京:北京航空航天大学出版社,2004.159～163.
[44]褚彦军,康凤举,高立娥等.视景仿真的三维模型库管理系统的研究与开发[J].计算机仿真,2004,21:174~176.
[45]王超.3D游戏引擎场景渲染技术的研究与实现[D].武汉:武汉理工大学,2006.
[46]淮永建.一个交互实时的多分辨率地形绘制系统[J].计算机工程与科学,2002,No.24.
[47]温菊屏.三维地形数据存储和调度方法研究[D].武汉:华中科技大学,2004.
[48]廖爱国.虚拟现实平台的研究与开发[D].上海:同济大学,2006.
[49]薛安,马蔼乃,李天宏.基于OpenGL实现真实感地形表现的研究[J].中国图像图形学报,2001,6(8):802.
[50]孙红梅.分布式虚拟场景实时绘制技术的研究与实现[D].合肥:中国科学院计算技术研究所,2000.
[51]吴玲达,高宇,魏迎梅.大规模复杂场景交互绘制技术综述[J].计算机研究与发展,2007,44(9):1579～1587.
[52]何晖光,田捷,张晓鹏等.网格模型化简综述[J].软件学报,2002,13(12):2215～2224.
[53]郝齐辉.虚拟现实中复杂形体的LOD模型研究[D].郑州:郑州大学,2006.
[54] Wang, Y. G., Bao, H. J., Peng, Q. S., Accelerated walkthroughs of virtual environments based on visibility preprocessing and simplification[A]. Computer Graphics Forum[C], 1998,17(3):187~194.
[55] Garland M, Heckbert P. Simplifying surfaces with color and texture using quadric error metrics. In IEEE Visualization 98 Conference Proceedings, 1998: 263～269.
[56] Erikson C, Manoch D. GAPS: General and automatic polygonal simplification, 1999 ACM Symposium on Interactive 3D Graphics, Atlanta: ACM,1999,79～88.
[57] Lindstrom P, Turk G. Fast and memory efficient polygonal simplification. Proceedings of the IEEE Visualization'98. Los Alamitos, 1998,279～285.
[2]罗运和,戴青.计算机图形学基础(第二版)[M].北京:中国计量出版社,2003,1~10.
[3]银红霞,杜四春,蔡立军.计算机图形学[M].北京:中国水利水电出版社,2005,1～30.
[4]石教英.虚拟现实基础及实用算法[M].北京:科学出版社,2002,76～111.
[5]于文洋,杨崇俊等.三维复杂场景管理研究[J].计算机工程与应用,2006,No.13.
[6]刘文炜.基于虚拟环境技术的实时显示算法的研究与实现[D].北京:中国科学院计算技术研究所,1996.
[7] Frank Luna. Introduction to 3D Game Programming with DirectX 9.0.Wordware [M]. Publishing, 2003:75-145.
[8] Blinn J. Simulation of Wrinkled Surfaces[J]. Computer Graphics, 1978, 12(3):286-292.
[9]曾金发.虚拟现实复杂场景生成、简化和优化技术研究[D].南京:南京理工大学,2004.
[10]张国宣,韦穗.虚拟现实中的LOD技术[J].微机发展,2001,11～16.
[11]周昆,潘志庚,石教英.多细节层次模型间的平滑过渡[J].计算机辅助设计与图形学学报,2000,463～466.
[12]潘志庚,马小虎,石教英.多细节层次模型自动生成技术综述[J] .中国图像图形学报,1998,3(9):754～759.
[13]马小虎.虚拟现实中多细节层次模型的研究[D].浙江:浙江大学,1997.
[14]陈礼民,秦爱红.三维图形简化新算法.中国图像图形学报,1997,2(2):157～160.
[15]华炜.大规模场景快速绘制技术[D].杭州:浙江大学,2002.
[16]刘焕勘.多细节层次模型简化技术的研究[D].武汉:武汉理工大学,2005.
[17]蒋再松.基于不规则三角网的LOD研究[D].成都:西南交通大学,2006.
[18]邵岳伟.基于最新图形处理器的图形引擎技术研究[D].西安:西北工业大学,2006.
[19] Wang Wei-chen, Jiang Xiaohong. Optimizing Real-Time Performance of 3D Virtual Mining Environment with MultiGen Creator[J]. CADDM, 2004, 14(1):61-69.
[20] N. Greene, M. Kass, G. Miller, Hierarchical Z-buffer visibility[J]. Computer Graphics (in proceeding of SIGGRAPH93), 1993,27(2):231~238.
[21] Algorri M-E. Schmitt F. Mesh. Simplification[C]. In proceedings of Euro Graphics’95[C]. 1996.77-86.
[22] Rubin S M. The representation and display of scenes with a wide range of detail.The Graphics and Image Processing, 1982,19: 291～299.
[23] DeHaemer Jr, Michael J. Simplification of Objects Render by PolygonalApproximations. Computer&Graphics,1991,15(2):175-184.
[24] Guezeic A. Surface simplification inside a tolerance. Technical Report, IBM Division, T.J.Watson Research Center, 1996.
[25] Garland M, Heckbert P. Surface simplification using quadric error metrics.Computer Graphics(SIGGRAPH Proceedings), 1997, 31:209-216.
[26]苗福生.数字几何处理的关健技术研究[D].西安:西北大学,2004.
[27]周昆,潘志庚,石教英.基于三角形折叠的网格简化算法[J].计算机学报,1998,No:21.
[28] John S. Falby, Michael J. Hierarchical Data Structures for Real-TimeThree-Dimensional Visual Simulation. Computer&Graphic,2002,17(1): 65~9.
[29] Zhang, H. S., Manocha, D., Hudson. T., et al., Visibility culling using hierarchical occlusion maps[A]. Computer Graphics[C], 1997,31(3):77~88.
[30] Levi O, Zohar R, Barad H, Klimovitski A. A Compact Method for Backface Culling. Computers and Graphics, 1995, 25(S):483-487.
[31]李胜.大规模室外地形场景加速绘制技术研究[D].北京:中国科学院软件研究所,2004.
[32]淮永建.虚拟场景中实时图形绘制关键技术研究[D].西安:西北工业大学,2002.
[33]侯涛.三维仿真场景优化理论与算法研究[D].北京:中国科学院遥感应用研究所,2006.
[34]张毅彬.虚拟现实引擎中的入口生成与路径规划[D].浙江:浙江大学,2005.
[35]李磊.场景快速渲染中的入口生成技术研究[D].浙江:浙江大学,2006.
[36]罗冠,郝重阳,王淑敏等.虚拟现实引擎中的入口技术[J].系统仿真学报,2001,No:13.
[37] McReynolds T, Blythe D, Grantham B, and Nelson S, Programming with OpenGL: Advanced Techniques, Course 17 notes at SIGGRAPH'98, 1998.
[38] Hoppe H. Progressive meshes, Computer Graphics(SIGGRAPH Proceedings),1996, 30:99～108.
[39] Hamann, Bernd. A Data Reduction Scheme for Triangulated Surfaces.Aided Geometric Design, 1994, 11(2):197-214.
[40] H.Hoppe, View-dependent refinement of progressive meshes[J], Preceeding of SIGGRAPH’97, 1997.189-204.
[41] Naylor B F. Binary space partitioning trees:an alternative representation of polytopes[J]. Computer Aided Design, 1990,22(2): 250-253.
[42] Ronfard R, Rossignac J R. Full-range approximation of triangulated polyhedral Computer Graphics Forum(Proceedings of Eurographics), 1996, 15(3): 67～76.
[43]李春雨,邱道尹,谭同德等.计算机图形学理论与实践[M].北京:北京航空航天大学出版社,2004.159～163.
[44]褚彦军,康凤举,高立娥等.视景仿真的三维模型库管理系统的研究与开发[J].计算机仿真,2004,21:174~176.
[45]王超.3D游戏引擎场景渲染技术的研究与实现[D].武汉:武汉理工大学,2006.
[46]淮永建.一个交互实时的多分辨率地形绘制系统[J].计算机工程与科学,2002,No.24.
[47]温菊屏.三维地形数据存储和调度方法研究[D].武汉:华中科技大学,2004.
[48]廖爱国.虚拟现实平台的研究与开发[D].上海:同济大学,2006.
[49]薛安,马蔼乃,李天宏.基于OpenGL实现真实感地形表现的研究[J].中国图像图形学报,2001,6(8):802.
[50]孙红梅.分布式虚拟场景实时绘制技术的研究与实现[D].合肥:中国科学院计算技术研究所,2000.
[51]吴玲达,高宇,魏迎梅.大规模复杂场景交互绘制技术综述[J].计算机研究与发展,2007,44(9):1579～1587.
[52]何晖光,田捷,张晓鹏等.网格模型化简综述[J].软件学报,2002,13(12):2215～2224.
[53]郝齐辉.虚拟现实中复杂形体的LOD模型研究[D].郑州:郑州大学,2006.
[54] Wang, Y. G., Bao, H. J., Peng, Q. S., Accelerated walkthroughs of virtual environments based on visibility preprocessing and simplification[A]. Computer Graphics Forum[C], 1998,17(3):187~194.
[55] Garland M, Heckbert P. Simplifying surfaces with color and texture using quadric error metrics. In IEEE Visualization 98 Conference Proceedings, 1998: 263～269.
[56] Erikson C, Manoch D. GAPS: General and automatic polygonal simplification, 1999 ACM Symposium on Interactive 3D Graphics, Atlanta: ACM,1999,79～88.
[57] Lindstrom P, Turk G. Fast and memory efficient polygonal simplification. Proceedings of the IEEE Visualization'98. Los Alamitos, 1998,279～285.