虚拟漫游系统场景管理与路径规划的研究
摘要
虚拟现实技术的创建和发展为人类提供了一个认识客观世界和发挥想象力的直观的有效途径。虚拟现实技术应用的一个重要领域是实现对建筑物实体的虚拟构建和智能漫游。通过虚拟建筑模型,建筑设计师可以预先验证设计方案的创意可行性和论证技术合理性。另外,通过虚拟建筑模型,可以向来访者预先展示建筑的内部结构和空间分布,避免了来访者对建筑物内部目标的盲目找寻。
本文分析了虚拟现实系统的主要特征,提出了构建虚拟漫游系统的两项主要工作：虚拟建筑场景建模管理和漫游路径规划。对于虚拟场景建模,本文总结了目前主要采用的场景绘制技术,包括多边形建模、模型导入、图像绘制、混合模式。本文所采用的是混合模式。文中在归纳总结已有的场景管理技术的基础上,提出了对于规则三维环境中的四叉树场景绘制的方法,提高了场景绘制的效率。同时,文中还研究了三维虚拟场景的路径规划问题。通过对三维虚拟建筑的数学分析和抽象建模,把三维空间等价为二维平面,利用图搜索理论中的A*算法,实现了在三维虚拟空间中快速搜索最优路径。
文中设计并实现了一个基于VRML和JAVA的虚拟图书馆漫游系统Virtual Library。该系统具有先进的三层架构设计,实现系统对于分布式的扩展支持。在虚拟场景建模的过程中,本文提出了在虚拟建筑建模过程中对多种建模方式和技术手段进行结合应用的方法,有效的提高了建模的质量和效率。同时,对于虚拟漫游,本文采取将三维场景简化成二维平面,并基于改进的A*算法给出了具体的程序设计实现,优化了路径图的数据结构,提高了路径搜索的效率和成功率。
The development of Virtual reality provide an effective way that people understand the world and give the rein to their imagination.Virtual scene mangement and intelligent roaming play an important part among various reasearch in the field of virtual reality.Through the virtual scene, architect can verify the feasibility and rationality of the design beforehand. In addition,people can browse the vitual building before they visit the real buiding in order to avoid searching the destination everywhere blindly.
In this paper,we first analyze the character of VR,and provide two mainly tasks:building of virtual scene and path planning.we summerize some important scene modeling technology, including polygon modeling,model importing,image protracting, hybrid modeling. And the lastway is this paper use.second, based on there scene mangement research,we provide quadtree to manage the Three-dimensional enviroment and improve protracting efficiency.Besides,we study the path planning problem. Through Mathematical Analyzing and abstract modeling,we use some method to improve the A* algorithm based on graph searching which can find the shortest path of the three-dimensional model.
This paper develops a Virtual Library based on VRML and JAVA.The system ues three layer architecture design. In the process of virtual scene modeling,this paper presents the modeling process in the virtual construction of a variety of modeling methods and techniques to combine the application of methods, effectively improve the quality and efficiency of the modeling.Through combining several modeling technology,the quality and efficiency of virtual building is improved obvious.Meanwhile, this paper simplify three-dimensional scene into two-dimensional plane, and based on an improved A* algorithm,implement path planning to improve the efficiency of the path search and success rate.
本文分析了虚拟现实系统的主要特征,提出了构建虚拟漫游系统的两项主要工作：虚拟建筑场景建模管理和漫游路径规划。对于虚拟场景建模,本文总结了目前主要采用的场景绘制技术,包括多边形建模、模型导入、图像绘制、混合模式。本文所采用的是混合模式。文中在归纳总结已有的场景管理技术的基础上,提出了对于规则三维环境中的四叉树场景绘制的方法,提高了场景绘制的效率。同时,文中还研究了三维虚拟场景的路径规划问题。通过对三维虚拟建筑的数学分析和抽象建模,把三维空间等价为二维平面,利用图搜索理论中的A*算法,实现了在三维虚拟空间中快速搜索最优路径。
文中设计并实现了一个基于VRML和JAVA的虚拟图书馆漫游系统Virtual Library。该系统具有先进的三层架构设计,实现系统对于分布式的扩展支持。在虚拟场景建模的过程中,本文提出了在虚拟建筑建模过程中对多种建模方式和技术手段进行结合应用的方法,有效的提高了建模的质量和效率。同时,对于虚拟漫游,本文采取将三维场景简化成二维平面,并基于改进的A*算法给出了具体的程序设计实现,优化了路径图的数据结构,提高了路径搜索的效率和成功率。
The development of Virtual reality provide an effective way that people understand the world and give the rein to their imagination.Virtual scene mangement and intelligent roaming play an important part among various reasearch in the field of virtual reality.Through the virtual scene, architect can verify the feasibility and rationality of the design beforehand. In addition,people can browse the vitual building before they visit the real buiding in order to avoid searching the destination everywhere blindly.
In this paper,we first analyze the character of VR,and provide two mainly tasks:building of virtual scene and path planning.we summerize some important scene modeling technology, including polygon modeling,model importing,image protracting, hybrid modeling. And the lastway is this paper use.second, based on there scene mangement research,we provide quadtree to manage the Three-dimensional enviroment and improve protracting efficiency.Besides,we study the path planning problem. Through Mathematical Analyzing and abstract modeling,we use some method to improve the A* algorithm based on graph searching which can find the shortest path of the three-dimensional model.
This paper develops a Virtual Library based on VRML and JAVA.The system ues three layer architecture design. In the process of virtual scene modeling,this paper presents the modeling process in the virtual construction of a variety of modeling methods and techniques to combine the application of methods, effectively improve the quality and efficiency of the modeling.Through combining several modeling technology,the quality and efficiency of virtual building is improved obvious.Meanwhile, this paper simplify three-dimensional scene into two-dimensional plane, and based on an improved A* algorithm,implement path planning to improve the efficiency of the path search and success rate.
引文
[1]乐小虬,陈飞翔.基于OpenGL的桌面型虚拟场馆漫游系统的研究与实现[D].山东：山东大学.2008.
[2]刘文亮,吕锋.基于VRML的虚拟现实中三维建模技术的研究[D].武汉：武汉理工大学.2002.
[3]Grigore C. Burdea, Philipe Coiffet.虚拟现实技术[M].西安：电子工业出版社,2005.
[4]王健宁,董社勤,石教英.虚拟建筑实时漫游算法综述[J].计算机工程与应用,2000,(1)：29-31.
[5]Y. Takase, N. Sho, A. Sone, K. Shimiya. Generation of Digital City Model [J]. Journal of the Visualization Soeiety of japan,2003,23(88):21-27
[6]王洪,朱清新.用VRML实现虚拟校园的实时漫游[J].计算机应用,2004,24：141-143.
[7]刘晓东,马华东.大规模场景管理与漫游技术的研究与实现[D].北京：北京邮电大学,2007.
[8]黄晓康,唐振民.基于BSP和四叉树的场景管理研究[D].南京：南京理工大学,2008.
[9]Yongji Wang, Liu Han. A real-time path planning approach without the computation of space obstacles [J]. Journal Intelligent and Robotic Systems,2007,103(2):32-39.
[10]刘作军.基于电路地图的移动机器人路径规划方法研究[D].天津：南开大学.2005
[11]于红斌,李孝安.基于栅格法的机器人快速路径规划[J].微电子学与计算机,2005,22(6)：98-100
[12]M. A. Mansor, A. S. Morris. Path planning in unknown environment with obstacle using virtual window[J]. Journal of Intelligent and Robotic Systems,1995,24,235-251.
[13]Kurpati, Azarm. Immune Network Simulation with Multiobjeetive Genetic algorithms for Multidisciplinary Design Optimization[C].//Engineering Optimization,2000.
[14]于文洋,杨崇俊,乐小虬,陈飞翔.三维复杂场景管理研究[J].计算机工程与应用,2006,(13)：13-16.
[15]Meng M. Real-time collision-free path planning of robot manipulators using neural network approaches[J].Autonom ous Robots,2000,9(1):27-39.
[16]Jinhai, Guochang.Path planning in construction sites:performance evaluation of the Dijkstra, A*, and GA search algorithms[J]. Advanced Engineering Informatics,2002.
[17]陈杰.基于蚁群算法的机器人路径规划研究[D].南京：南京理工大学,2009.
[18]刘关俊.基于粒子群算法的移动机器人路径规划研究[D].长沙：中南大学,2007.
[19]Ge S S, Cui YJ. New Potential funetions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation,2000,16(5):615-620.
[20]M. Dorigo, E. Bonabeau, G. Theraulaz. Ant algorlthms and stigmergy[M], Future Generation Computer Systems,2000,16(8):851-871.
[21]Xie Xiaofeng, Zhang Wenjun, YangZhilian. Incorporating knowledge in genetic algorithm for device synthesis[J].6th Int Conf on Solid-state and Integrated Circuit Technology,2001.
[22]冯岩.基于聚类排挤小生境遗传算法的多路径规划技术研究[D].哈尔滨：哈尔滨工业大学,2009.
[23]许振红.动态路径诱导系统的最优路径算法研究及相关软件实现[D].南京：南京理工大学,2004.
[24]阳化冰,刘忠丽,刘忠轩,王庆华.虚拟现实构造语言VRML[M].北京：北京航空航天大学出社,2005.
[25]Mbede, Bosco J, Wei W. Fuzzy and recurrent neural network motion control among dynamic obstacles for robot manipulators[J]. Journal of Intelligent and Robotic Systems, 2001,30(2):155-177.
[26]Yang S, Meng M. Real-time collision-free path planning of robot manipulators using neural network approaches[J]. Autonomous Robots,2000,9(1):27-39.
[27]Gerke M. Genetic Path Planning for Mobile Robots[C].//Proc of American control conference. San Diego, CA, USA,1999:596-601.
[28]Weihua Wang, Qingping Lin. a Collaborative Virtual Environment System with Behavior Based Interaetion Management[J]. Information Systems,2002.
[29]ChangHun R, Heedong Ko. Multi-Resolution Spatial Model for Large-Scale Virtual Environment [J]. Proceedings of the IEEE International Conference on e-Business Engineering. Washington,2005:134-141.
[30]陈勇,王栋,陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报,2007,6(19)：51-57
[31]Cagatay Basdogan, Chih-Hao Ho. PrineiPles of HaPtic Rendering for Virtual Environmenis. [J].Integrated Design and Process Science,2003,7(3):40-77.
[32]张毅彬.虚拟现实引擎中的入口生成与路径规划[D].杭州：浙江大学,2005.
[33]Le Roux O, Gaildrat V. Constraint-based 3d isothetic object layout for declarative scene modeling[J]. Lecture Notes In Computer Science,2008,5331:392-408.
[34]丙小平.一种基于不完全四义树的LOD生成算法[J].中国图象图形学报,2005.
[35]李磊,叶涛,谭民等.移动机器人技术研究现状与未来[J].机器人,2002,24(5)：475-480
[36]Samet H. The design and analysis of spatial data struetures. [C]//Proceedings of the 1st Workshop on E-Business, Spain:Barcelona,2002:154-165.
[2]刘文亮,吕锋.基于VRML的虚拟现实中三维建模技术的研究[D].武汉：武汉理工大学.2002.
[3]Grigore C. Burdea, Philipe Coiffet.虚拟现实技术[M].西安：电子工业出版社,2005.
[4]王健宁,董社勤,石教英.虚拟建筑实时漫游算法综述[J].计算机工程与应用,2000,(1)：29-31.
[5]Y. Takase, N. Sho, A. Sone, K. Shimiya. Generation of Digital City Model [J]. Journal of the Visualization Soeiety of japan,2003,23(88):21-27
[6]王洪,朱清新.用VRML实现虚拟校园的实时漫游[J].计算机应用,2004,24：141-143.
[7]刘晓东,马华东.大规模场景管理与漫游技术的研究与实现[D].北京：北京邮电大学,2007.
[8]黄晓康,唐振民.基于BSP和四叉树的场景管理研究[D].南京：南京理工大学,2008.
[9]Yongji Wang, Liu Han. A real-time path planning approach without the computation of space obstacles [J]. Journal Intelligent and Robotic Systems,2007,103(2):32-39.
[10]刘作军.基于电路地图的移动机器人路径规划方法研究[D].天津：南开大学.2005
[11]于红斌,李孝安.基于栅格法的机器人快速路径规划[J].微电子学与计算机,2005,22(6)：98-100
[12]M. A. Mansor, A. S. Morris. Path planning in unknown environment with obstacle using virtual window[J]. Journal of Intelligent and Robotic Systems,1995,24,235-251.
[13]Kurpati, Azarm. Immune Network Simulation with Multiobjeetive Genetic algorithms for Multidisciplinary Design Optimization[C].//Engineering Optimization,2000.
[14]于文洋,杨崇俊,乐小虬,陈飞翔.三维复杂场景管理研究[J].计算机工程与应用,2006,(13)：13-16.
[15]Meng M. Real-time collision-free path planning of robot manipulators using neural network approaches[J].Autonom ous Robots,2000,9(1):27-39.
[16]Jinhai, Guochang.Path planning in construction sites:performance evaluation of the Dijkstra, A*, and GA search algorithms[J]. Advanced Engineering Informatics,2002.
[17]陈杰.基于蚁群算法的机器人路径规划研究[D].南京：南京理工大学,2009.
[18]刘关俊.基于粒子群算法的移动机器人路径规划研究[D].长沙：中南大学,2007.
[19]Ge S S, Cui YJ. New Potential funetions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation,2000,16(5):615-620.
[20]M. Dorigo, E. Bonabeau, G. Theraulaz. Ant algorlthms and stigmergy[M], Future Generation Computer Systems,2000,16(8):851-871.
[21]Xie Xiaofeng, Zhang Wenjun, YangZhilian. Incorporating knowledge in genetic algorithm for device synthesis[J].6th Int Conf on Solid-state and Integrated Circuit Technology,2001.
[22]冯岩.基于聚类排挤小生境遗传算法的多路径规划技术研究[D].哈尔滨：哈尔滨工业大学,2009.
[23]许振红.动态路径诱导系统的最优路径算法研究及相关软件实现[D].南京：南京理工大学,2004.
[24]阳化冰,刘忠丽,刘忠轩,王庆华.虚拟现实构造语言VRML[M].北京：北京航空航天大学出社,2005.
[25]Mbede, Bosco J, Wei W. Fuzzy and recurrent neural network motion control among dynamic obstacles for robot manipulators[J]. Journal of Intelligent and Robotic Systems, 2001,30(2):155-177.
[26]Yang S, Meng M. Real-time collision-free path planning of robot manipulators using neural network approaches[J]. Autonomous Robots,2000,9(1):27-39.
[27]Gerke M. Genetic Path Planning for Mobile Robots[C].//Proc of American control conference. San Diego, CA, USA,1999:596-601.
[28]Weihua Wang, Qingping Lin. a Collaborative Virtual Environment System with Behavior Based Interaetion Management[J]. Information Systems,2002.
[29]ChangHun R, Heedong Ko. Multi-Resolution Spatial Model for Large-Scale Virtual Environment [J]. Proceedings of the IEEE International Conference on e-Business Engineering. Washington,2005:134-141.
[30]陈勇,王栋,陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报,2007,6(19)：51-57
[31]Cagatay Basdogan, Chih-Hao Ho. PrineiPles of HaPtic Rendering for Virtual Environmenis. [J].Integrated Design and Process Science,2003,7(3):40-77.
[32]张毅彬.虚拟现实引擎中的入口生成与路径规划[D].杭州：浙江大学,2005.
[33]Le Roux O, Gaildrat V. Constraint-based 3d isothetic object layout for declarative scene modeling[J]. Lecture Notes In Computer Science,2008,5331:392-408.
[34]丙小平.一种基于不完全四义树的LOD生成算法[J].中国图象图形学报,2005.
[35]李磊,叶涛,谭民等.移动机器人技术研究现状与未来[J].机器人,2002,24(5)：475-480
[36]Samet H. The design and analysis of spatial data struetures. [C]//Proceedings of the 1st Workshop on E-Business, Spain:Barcelona,2002:154-165.