实时三维漫游系统中关键技术研究与实现
|
摘要
实时三维漫游是虚拟现实领域的一个重要的研究方向,其在沉浸感、交互性与实时性综合效果方面的优势是传统平面效果图与动画技术所无法比拟的。目前,实时三维漫游技术以其特有的优势被广泛地运用于军事、娱乐、医学、地理信息系统等各领域。本文旨在研究实时三维漫游技术的关键技术,如建模、场景组织、可见性裁剪、碰撞检测等,并实现一个实时三维漫游演示系统。主要内容包括:
1)研究了常用的建模技术,并比较其优缺点。介绍了三维建模工具3DS MAX的特点以及3DS文件格式及读取方式。
2)对室内外场景组织方式进行了比较并着重介绍了基于BSP树的室内场景组织方式。介绍了本文采用的基于BSP树的场景组织方式,提出了回避三角形分割及回避物体分割的BSP树构建算法,树叶子节点上存储的物体用于基于视锥的可见性裁剪和第一阶段基于包围球的碰撞检测。
3)讨论了常见的可见性裁剪算法,包括视锥裁剪、背面裁剪、遮挡裁剪等。提出了一种基于改进BSP树的快速视锥裁剪算法。根据BSP树中存储的物体信息,在物体级别上进行粗略的可见性裁剪,计算量小,速度快,可以有效减少需要绘制的物体数量,并利用现代图形硬件的硬件加速提高绘制速度。
4)研究了碰撞检测的基本原理,提出了基于空间分割和包围球技术的双重碰撞检测算法。通过查找BSP树来确定视点所在的最小子空间。第一阶段先检测视点与物体的位置关系来进行粗略的碰撞定位,进而再对可能发生碰撞物体进行基于三角形面片的碰撞检测,提高碰撞检测的速度。
本文采用三维建模工具3DS MAX建立了一个室内模型,采用VC++2005和Direct3D技术开发了一个实时三维漫游演示系统,验证了本文提出的可见性裁剪算法和碰撞检测算法的有效性。
Real-time three-dimensional roaming is an important research direction in the field of virtual reality. Real-time three-dimensional Roaming has been widely used in military, entertainment, medicine, geographic information systems, etc. This paper is intended to probe into the key technologies of real-time three-dimensional roaming, including modeling, scene organization, visibility culling, collision detection and the implementation of a real-time three-dimensional roaming demo system. The main contents are as follows;
1) Common modeling technologies and their advantages and disadvantages are discussed. Then introduce the Features of 3DS MAX and discuss the 3DS file format and the method of reading.
2) The differences between indoor and outdoor scene organization are discussed with an emphasis on indoor scene organization based on BSP-Tree. The avoiding triangle and object partition' s BSP-Tree building algorithm is proposed. Objects in scene are stored in leaf of BSP-Tree for visibility culling and first stage collision detection.
3) Visibility culling technologies are discussed. This paper proposes a fast cone culling algorithm based on improved BSP-Tree using the objects which are stored in leaf nodes. This algorithm can fast choose objects in cone and discard the others so can rapidly reduce the objects sent to Direct3D rendering instruction.
4) Basic theory of collision detection is introduced and a double stage collision detection algorithm based on space division and bounding sphere was used to accelerate the speed. First the smallest sub space is picked out and detects collision based on objects' bounding sphere and then does accurate collision detection using object' s triangles if needed.
This paper finally sets up an indoor scene using 3DS MAX and implements a real-time 3D roaming demo system using VC2005 and Direct3D. The cone culling algorithm and collision detection algorithm we proposed are proved to be effective.
1)研究了常用的建模技术,并比较其优缺点。介绍了三维建模工具3DS MAX的特点以及3DS文件格式及读取方式。
2)对室内外场景组织方式进行了比较并着重介绍了基于BSP树的室内场景组织方式。介绍了本文采用的基于BSP树的场景组织方式,提出了回避三角形分割及回避物体分割的BSP树构建算法,树叶子节点上存储的物体用于基于视锥的可见性裁剪和第一阶段基于包围球的碰撞检测。
3)讨论了常见的可见性裁剪算法,包括视锥裁剪、背面裁剪、遮挡裁剪等。提出了一种基于改进BSP树的快速视锥裁剪算法。根据BSP树中存储的物体信息,在物体级别上进行粗略的可见性裁剪,计算量小,速度快,可以有效减少需要绘制的物体数量,并利用现代图形硬件的硬件加速提高绘制速度。
4)研究了碰撞检测的基本原理,提出了基于空间分割和包围球技术的双重碰撞检测算法。通过查找BSP树来确定视点所在的最小子空间。第一阶段先检测视点与物体的位置关系来进行粗略的碰撞定位,进而再对可能发生碰撞物体进行基于三角形面片的碰撞检测,提高碰撞检测的速度。
本文采用三维建模工具3DS MAX建立了一个室内模型,采用VC++2005和Direct3D技术开发了一个实时三维漫游演示系统,验证了本文提出的可见性裁剪算法和碰撞检测算法的有效性。
Real-time three-dimensional roaming is an important research direction in the field of virtual reality. Real-time three-dimensional Roaming has been widely used in military, entertainment, medicine, geographic information systems, etc. This paper is intended to probe into the key technologies of real-time three-dimensional roaming, including modeling, scene organization, visibility culling, collision detection and the implementation of a real-time three-dimensional roaming demo system. The main contents are as follows;
1) Common modeling technologies and their advantages and disadvantages are discussed. Then introduce the Features of 3DS MAX and discuss the 3DS file format and the method of reading.
2) The differences between indoor and outdoor scene organization are discussed with an emphasis on indoor scene organization based on BSP-Tree. The avoiding triangle and object partition' s BSP-Tree building algorithm is proposed. Objects in scene are stored in leaf of BSP-Tree for visibility culling and first stage collision detection.
3) Visibility culling technologies are discussed. This paper proposes a fast cone culling algorithm based on improved BSP-Tree using the objects which are stored in leaf nodes. This algorithm can fast choose objects in cone and discard the others so can rapidly reduce the objects sent to Direct3D rendering instruction.
4) Basic theory of collision detection is introduced and a double stage collision detection algorithm based on space division and bounding sphere was used to accelerate the speed. First the smallest sub space is picked out and detects collision based on objects' bounding sphere and then does accurate collision detection using object' s triangles if needed.
This paper finally sets up an indoor scene using 3DS MAX and implements a real-time 3D roaming demo system using VC2005 and Direct3D. The cone culling algorithm and collision detection algorithm we proposed are proved to be effective.
引文
[1]毛玉姣,王梅,陈远.虚拟现实技术及其应用[J].图书情报知识,1997.12
[2]赵国英.体视动态图象的生成技术及应用[D].北京:北方工业大学,2002
[3]王宏武.面向数字地球的虚拟现实系统及若干问题研究[D].北京:北京大学,1999
[4]杨建华,吴朝晖,潘云鹤.基于攻防对抗仿真的虚拟战场技术研究[J].系统仿真学,2005.4,17(4):922
[5]赵沁平.DVENET:一个分布式虚拟环境[J].计算机研究与发展,1998.12,35(12)
[6]Zhong Yongmin,Ma Weiyin,Shirinzadeh Bijan.A Methodology for Solid Modeling in a Virtual Reality Environment[J].Robotics and Computer-Integrated Manufacturing,2005.12,21(6):528-549
[7]谭珂,王勇军等.虚拟现实技术在医学手术仿真训练中的应用[J].军医进修学院学报,2002.1,23(1)
[8]徐虎.虚拟现实技术在故宫博物馆的应用[J].中国博物馆,2004.3
[9]Kim Yong-Sik,Yang Jeongsam,HanSoonhung.A Multichannel Visualization Module for Virtual Manufacturing[J].Computers in Industry,2006.9,57(7):653-662
[10]Company Pedro,Contero Manuel,Conesa Julian.An Optimisation-Based Reconstruction Engine for 3D Modelling by sketching[J].Computers & Graphics,2004.12,28(6):955-979
[11]Cfx Ansys.Computer Simulation Helps Design More Efficient Water Pumps[J].World Pumps,2004.6,2004(453):32-34
[12]Seth Teller,Delnaz Khorramabodi.The UC Berkely System for Interactive Visualization of Large Architectual Models[J],Teleoperators and Virtual Environments,1996
[13]郝爱民,张蓓.计算机虚拟北航的建造与人机交互的实现[J],北京航天航空大学学报,2000.8,26(4)
[14]傅晟,彭群生.一个桌面型虚拟建筑环境实时漫游系统的设计与实现[J], 计算机学报.1998.9,21(9)
[15]祝魏玮.国家自然科学基金支持虚拟奥运博物馆[J].科学时报,2007.1
[16]王德才,杨关胜,孙玉萍等.DirectX 3D图形与动画程序设计[M].人民邮电出版社,2007.5
[17]TolgaK,Capin.etc.Virtual Human Representation and Communication in VLNET Networked Virtual Environments[J].IEEE Compputer Graphics and Applications,1997
[18]张国宜等.基于VR的多模式多代理人机交互接口[J].计算机应用研究,2000.10:91-94
[19]张凯,徐桂生,龙怀冰等.3DS MAX6三维与动画设计[M].清华大学出版社,2004
[20]邹益胜,丁国富,许明恒等.实时碰撞检测算法综述[J].计算机应用研究2008.1,25(1)
[21]Michael S.Paterson,F.Frances Yao.Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling[J].Discrete and Computational Geometry,1990.12,5(1)
[22]BE Budge,D Coming,D Norpchen,KI Joy.Accelerated Building and Ray Tracing of Restricted BSP Trees[J].Interactive Ray Tracing,2008.RT 2008.IEEE Symposium on,2008.8
[23]刘恒,江南,魏楠.基于BSP树的启发式阴影生成算法[J].计算机仿真,2006.6,32(6)
[24]Cohen-Or,D.Chrysanthou,Y.L.Silva,C.T.Durand,F.A Survey of Visibility for Walkthrough Applications[J].Visualization and Computer Graphics,IEEE Transactions on.2003,9(3):412-431
[25]S.Teller,C.Sequin.Visibility Computations in Polyhedral Three-dimensional Environments[J].U.C.Berkeley Report No.UCB/CSD 921680,1992.4
[26]Satyan Coorg,Seth Teller.Real-Time Occlusion Culling for Models with Large Occluders[J].ACM Symposium on Interactive 3D Graphics, 1997:83-90
[27]C Andujar,C Saona-Vazquez,I Navazo.LOD Visibility Culling and Occluder Synthesis.Computer Aided Design,2000.7
128]NK Govindaraju,A Sud,SE Yoon,D Manoch.Interactive visibility culling in complex environments using occlusion-switches.Proceedings of the 2003 symposium on Interactive 3D graphics,2003
[29]T M(o|¨)ller,E Haines.Real-Time Rendering[M].AK Peters,Ltd,1999
[30]Hoff,K.,Backface Cluster Culling using Normal-Space Partitioning.1996,http://www.cs.unc.edu/~hoff/techrep/quickbfc.html
[31]彭群生.计算机真实感图形的算法基础[M].科学出版社,1999
[32]Greene N,M.Kass,G.Miller.Hierarchical Z-Buffer Visibility[C],Computer Graphics(SI-GGRAPH'93 Proceedings),1993.8:231-238
[33]Zhang H,D.Manocha,T.Hudson,K.E.Hoff Ⅲ,Visibility Culling using Hierarchical Occlusion Maps[C].Computer Graphics(SIGGRAPH'97Proceedings),1997.8:77-88
[34]D Haumont,O Debeir,F Sillion.Volumetric Cell and Portal Generation.Computer Graphics Forum,2003
[35]李磊,场景快速渲染中的入口生成技术研究[D],杭州:浙江大学,2006.3
[36]David Luebke,Chris Georges,Portals and Mirrors.Simple,Fast Evalluation of Potentially Visible Sets[C],Symposium on Interactive 3D Graphics,Monterey CA USA,1995
[37]Samuel Ranta-Eskola,Binary Space Partitioning Trees and Polygon Removal in Real Time 3D Rendering[D],Uppsala:Uppsala University 2001
[38]潘振宽,崔树娟,张继萍等.基于层次包围盒的碰撞检测方法[J].青岛大学学报:自然科学版,2005,18(1)
[39]张唯,刘修国.三维场景漫游中碰撞检测问题的研究与实现[J].计算机工程与应用,2005.9
[40]马丽娜,马尧海.虚拟漫游中的碰撞检测问题的解决方法[J].计算机仿真,2006.2
[41]LNMC,GOTTSCHALK S.Collision Detection Between GeometricModels:A Survey[C].Proc of MA Conference on Mathematics of Surfaces.1998:37256.
[42]Jmenez P,Thomas F,Torras C.3D Collision Detection:A Survey[J].Computers and Graphics,2001,25(2):269-285.
[43]陈学文,丑武胜,刘静华等.基于包围盒的碰撞检测算法研究[J].计算机工程与应用,2005.4:46-50.
[44]范昭炜.实时碰撞检测技术研究[D].杭州:浙江大学,2003.
[45]魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙:国防科学技术大学,2000
[46]林俊杰.新一代Visual C++2005程序设计.清华大学出版社,2006.11
[47]Charles Petzold.Windows程序设计.北京大学出版社,1999
[2]赵国英.体视动态图象的生成技术及应用[D].北京:北方工业大学,2002
[3]王宏武.面向数字地球的虚拟现实系统及若干问题研究[D].北京:北京大学,1999
[4]杨建华,吴朝晖,潘云鹤.基于攻防对抗仿真的虚拟战场技术研究[J].系统仿真学,2005.4,17(4):922
[5]赵沁平.DVENET:一个分布式虚拟环境[J].计算机研究与发展,1998.12,35(12)
[6]Zhong Yongmin,Ma Weiyin,Shirinzadeh Bijan.A Methodology for Solid Modeling in a Virtual Reality Environment[J].Robotics and Computer-Integrated Manufacturing,2005.12,21(6):528-549
[7]谭珂,王勇军等.虚拟现实技术在医学手术仿真训练中的应用[J].军医进修学院学报,2002.1,23(1)
[8]徐虎.虚拟现实技术在故宫博物馆的应用[J].中国博物馆,2004.3
[9]Kim Yong-Sik,Yang Jeongsam,HanSoonhung.A Multichannel Visualization Module for Virtual Manufacturing[J].Computers in Industry,2006.9,57(7):653-662
[10]Company Pedro,Contero Manuel,Conesa Julian.An Optimisation-Based Reconstruction Engine for 3D Modelling by sketching[J].Computers & Graphics,2004.12,28(6):955-979
[11]Cfx Ansys.Computer Simulation Helps Design More Efficient Water Pumps[J].World Pumps,2004.6,2004(453):32-34
[12]Seth Teller,Delnaz Khorramabodi.The UC Berkely System for Interactive Visualization of Large Architectual Models[J],Teleoperators and Virtual Environments,1996
[13]郝爱民,张蓓.计算机虚拟北航的建造与人机交互的实现[J],北京航天航空大学学报,2000.8,26(4)
[14]傅晟,彭群生.一个桌面型虚拟建筑环境实时漫游系统的设计与实现[J], 计算机学报.1998.9,21(9)
[15]祝魏玮.国家自然科学基金支持虚拟奥运博物馆[J].科学时报,2007.1
[16]王德才,杨关胜,孙玉萍等.DirectX 3D图形与动画程序设计[M].人民邮电出版社,2007.5
[17]TolgaK,Capin.etc.Virtual Human Representation and Communication in VLNET Networked Virtual Environments[J].IEEE Compputer Graphics and Applications,1997
[18]张国宜等.基于VR的多模式多代理人机交互接口[J].计算机应用研究,2000.10:91-94
[19]张凯,徐桂生,龙怀冰等.3DS MAX6三维与动画设计[M].清华大学出版社,2004
[20]邹益胜,丁国富,许明恒等.实时碰撞检测算法综述[J].计算机应用研究2008.1,25(1)
[21]Michael S.Paterson,F.Frances Yao.Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling[J].Discrete and Computational Geometry,1990.12,5(1)
[22]BE Budge,D Coming,D Norpchen,KI Joy.Accelerated Building and Ray Tracing of Restricted BSP Trees[J].Interactive Ray Tracing,2008.RT 2008.IEEE Symposium on,2008.8
[23]刘恒,江南,魏楠.基于BSP树的启发式阴影生成算法[J].计算机仿真,2006.6,32(6)
[24]Cohen-Or,D.Chrysanthou,Y.L.Silva,C.T.Durand,F.A Survey of Visibility for Walkthrough Applications[J].Visualization and Computer Graphics,IEEE Transactions on.2003,9(3):412-431
[25]S.Teller,C.Sequin.Visibility Computations in Polyhedral Three-dimensional Environments[J].U.C.Berkeley Report No.UCB/CSD 921680,1992.4
[26]Satyan Coorg,Seth Teller.Real-Time Occlusion Culling for Models with Large Occluders[J].ACM Symposium on Interactive 3D Graphics, 1997:83-90
[27]C Andujar,C Saona-Vazquez,I Navazo.LOD Visibility Culling and Occluder Synthesis.Computer Aided Design,2000.7
128]NK Govindaraju,A Sud,SE Yoon,D Manoch.Interactive visibility culling in complex environments using occlusion-switches.Proceedings of the 2003 symposium on Interactive 3D graphics,2003
[29]T M(o|¨)ller,E Haines.Real-Time Rendering[M].AK Peters,Ltd,1999
[30]Hoff,K.,Backface Cluster Culling using Normal-Space Partitioning.1996,http://www.cs.unc.edu/~hoff/techrep/quickbfc.html
[31]彭群生.计算机真实感图形的算法基础[M].科学出版社,1999
[32]Greene N,M.Kass,G.Miller.Hierarchical Z-Buffer Visibility[C],Computer Graphics(SI-GGRAPH'93 Proceedings),1993.8:231-238
[33]Zhang H,D.Manocha,T.Hudson,K.E.Hoff Ⅲ,Visibility Culling using Hierarchical Occlusion Maps[C].Computer Graphics(SIGGRAPH'97Proceedings),1997.8:77-88
[34]D Haumont,O Debeir,F Sillion.Volumetric Cell and Portal Generation.Computer Graphics Forum,2003
[35]李磊,场景快速渲染中的入口生成技术研究[D],杭州:浙江大学,2006.3
[36]David Luebke,Chris Georges,Portals and Mirrors.Simple,Fast Evalluation of Potentially Visible Sets[C],Symposium on Interactive 3D Graphics,Monterey CA USA,1995
[37]Samuel Ranta-Eskola,Binary Space Partitioning Trees and Polygon Removal in Real Time 3D Rendering[D],Uppsala:Uppsala University 2001
[38]潘振宽,崔树娟,张继萍等.基于层次包围盒的碰撞检测方法[J].青岛大学学报:自然科学版,2005,18(1)
[39]张唯,刘修国.三维场景漫游中碰撞检测问题的研究与实现[J].计算机工程与应用,2005.9
[40]马丽娜,马尧海.虚拟漫游中的碰撞检测问题的解决方法[J].计算机仿真,2006.2
[41]LNMC,GOTTSCHALK S.Collision Detection Between GeometricModels:A Survey[C].Proc of MA Conference on Mathematics of Surfaces.1998:37256.
[42]Jmenez P,Thomas F,Torras C.3D Collision Detection:A Survey[J].Computers and Graphics,2001,25(2):269-285.
[43]陈学文,丑武胜,刘静华等.基于包围盒的碰撞检测算法研究[J].计算机工程与应用,2005.4:46-50.
[44]范昭炜.实时碰撞检测技术研究[D].杭州:浙江大学,2003.
[45]魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙:国防科学技术大学,2000
[46]林俊杰.新一代Visual C++2005程序设计.清华大学出版社,2006.11
[47]Charles Petzold.Windows程序设计.北京大学出版社,1999