城市综合管网三维漫游系统的研究与实现
|
摘要
本文讨论了城市综合管网三维漫游系统的关键技术,结合城市管网三维场景对相关技术进行了研究,设计开发了扩展性良好的城市管网三维漫游系统。
本文简单介绍了管线CAD数据提取方法,基于Java3D的三维建模等基础技术,研究了碰撞检测算法和自动最短路径选择及自动避障算法,提出了一种基于线性编码八叉树的混合包围盒碰撞检测算法、结合管网分布特点改进了最短路径算法效率并提出一种漫游中自动避障方法。
碰撞检测是虚拟环境中至关重要的问题,碰撞检测的速度严重影响着虚拟环境的真实性和沉浸感。本文对目前常用的AABB、OBB包围盒算法进行了研究与实验,对这两种方法的优缺点进行了比较分析并提出了混合包围盒方法。针对管网三维场景数据量大、运算复杂的问题,本文提出了基于线性编码的不完全八叉树场景管理算法。实验证明,二者的结合对于提高复杂场景中碰撞检测等运算的效率非常有效。
最短路径和自动避障是管网自动漫游中的基本问题。Dijkstra算法是求解最短路径的经典算法。本文针对管网所具有的空间特征,从拓扑构建和搜索两个方面对Dijkstra算法进行了改进,采取了对管线进行分区编码限制区域构造管网拓扑,搜索过程中采取距离优先和方向优先提高搜索效率。针对管线三维模型自身的特点本文提出了一种漫游自动避障方法。上述二者在本课题的研究中得到了有效验证。
结合相关研究工作,本文对市政管网三维可视化系统进行了系统结构设计,系统功能设计,使用Java3D完成开发工作。
最后,文中给出了本课题相关领域的总结与展望。
This paper discusses the roaming system of city's pipe network, key technology for pipe network 3D scenes, and methods to improve the relevant technology. A 3D roaming system of city's pipe network is developed.
This paper briefly describes the basic technology of 3D roaming system development such as pipeline data extraction from CAD file, and Java3D based 3D modeling. Collision detection algorithm, shortest path algorithm and the automatic obstacle avoidance algorithm are researched, and a collision detection algorithm based on linear encoding octree and mixed bounding box algorithm is proposed, with the feature of pipe network, a method for improving the efficiency of the shortest path is adapted and a method for the automatic obstacle avoidance during automatic-roaming is proposed.
Collision detection is a crucial issue in virtual environments. In this paper, a mix bounding box algorithm is proposed, which has the advantages of both AABB and OBB. With the problem of large amount of data and 'complexity of computation in 3D scene, this paper presents a linear coding based octree for scene management. Experiments show that the effective combination of the two methods above is very effective for improving the efficiency of collision detection.
The shortest path and automatic obstacle avoidance is the basic problems for auto-roaming of pipe network. Dijkstra algorithm is a classical algorithm for solving the shortest path. In this paper, pipe network, with its spatial characteristics, elliptical and direction prefer algorithm is adopted to improve the efficiency of Dijkstra. With features of pipe's 3D model, an automatic obstacle avoidance roaming algorithm based on vector and offset is proposed in this paper. The two methods above have been effectively verified.
Finally, the paper gives a summary of this subject in related fields and prospects.
本文简单介绍了管线CAD数据提取方法,基于Java3D的三维建模等基础技术,研究了碰撞检测算法和自动最短路径选择及自动避障算法,提出了一种基于线性编码八叉树的混合包围盒碰撞检测算法、结合管网分布特点改进了最短路径算法效率并提出一种漫游中自动避障方法。
碰撞检测是虚拟环境中至关重要的问题,碰撞检测的速度严重影响着虚拟环境的真实性和沉浸感。本文对目前常用的AABB、OBB包围盒算法进行了研究与实验,对这两种方法的优缺点进行了比较分析并提出了混合包围盒方法。针对管网三维场景数据量大、运算复杂的问题,本文提出了基于线性编码的不完全八叉树场景管理算法。实验证明,二者的结合对于提高复杂场景中碰撞检测等运算的效率非常有效。
最短路径和自动避障是管网自动漫游中的基本问题。Dijkstra算法是求解最短路径的经典算法。本文针对管网所具有的空间特征,从拓扑构建和搜索两个方面对Dijkstra算法进行了改进,采取了对管线进行分区编码限制区域构造管网拓扑,搜索过程中采取距离优先和方向优先提高搜索效率。针对管线三维模型自身的特点本文提出了一种漫游自动避障方法。上述二者在本课题的研究中得到了有效验证。
结合相关研究工作,本文对市政管网三维可视化系统进行了系统结构设计,系统功能设计,使用Java3D完成开发工作。
最后,文中给出了本课题相关领域的总结与展望。
This paper discusses the roaming system of city's pipe network, key technology for pipe network 3D scenes, and methods to improve the relevant technology. A 3D roaming system of city's pipe network is developed.
This paper briefly describes the basic technology of 3D roaming system development such as pipeline data extraction from CAD file, and Java3D based 3D modeling. Collision detection algorithm, shortest path algorithm and the automatic obstacle avoidance algorithm are researched, and a collision detection algorithm based on linear encoding octree and mixed bounding box algorithm is proposed, with the feature of pipe network, a method for improving the efficiency of the shortest path is adapted and a method for the automatic obstacle avoidance during automatic-roaming is proposed.
Collision detection is a crucial issue in virtual environments. In this paper, a mix bounding box algorithm is proposed, which has the advantages of both AABB and OBB. With the problem of large amount of data and 'complexity of computation in 3D scene, this paper presents a linear coding based octree for scene management. Experiments show that the effective combination of the two methods above is very effective for improving the efficiency of collision detection.
The shortest path and automatic obstacle avoidance is the basic problems for auto-roaming of pipe network. Dijkstra algorithm is a classical algorithm for solving the shortest path. In this paper, pipe network, with its spatial characteristics, elliptical and direction prefer algorithm is adopted to improve the efficiency of Dijkstra. With features of pipe's 3D model, an automatic obstacle avoidance roaming algorithm based on vector and offset is proposed in this paper. The two methods above have been effectively verified.
Finally, the paper gives a summary of this subject in related fields and prospects.
引文
[1]严勇地下管线的三维可视化研究[M].武汉：武汉大学，2003
[2]都志辉.Java3D编程实践：网络上的三维动画[B].北京：清华大学出版社
[3]田应中,张正禄,杨旭.地下管线网探测与信息管理[B].北京：测绘出版社,1997
[4]张超.地理信息系统[B].北京：高等教育出版社,1995
[5]王英杰,袁勘省,余卓渊.多维动态地学信息可视化[B].北京：科学出版社,2003
[6]张卫峰,林端敏.AutoCAD软件的DXF接口技术[J].机械与电子,2004(11)：78-80
[7]梁雪春,宋德明.AutoCAD二次开发技术指南[B].北京：清华大学出版,2001
[8]李培君.基于GIS的地下管网可视化研究[M].中国人民解放军信息工程大学硕士论文,2006：34-47
[9]杜国明,龚健雅,熊汉江.城市三维管网的可视化及其系统功能实现的关键技术[J],武汉大学学报,2002(10)：534-537
[10]高新瑞.Java 3D与计算机几何设计[B].北京：电子工业出版社,2007
[11]Samet H. Neighbor Finding Techniques for Image Represented by Quad trees[J]. Computer Graphics and Image Processing,1982,18(3):37-57
[12]肖乐斌,孟鲁闽.建立八叉树的变长层次编码技术[J].地理信息世界,1996(2)：11-14
[13]丁佳.大型复杂场景中快速碰撞检测技术的研究[M].成都：电子科技大学,2007
[14]傅由甲,杨克俭,胡平飞.基于动态八叉树的复杂场景交互式实时漫游[J].武汉理工大学学报,2005,29(2)：308-311
[15]熊伟,毛善君,马蔼乃.基于观察者的碰撞检测技术在虚拟环境漫游中的应用[J].计算机应用,2002,22(11)：6-8
[16]王志强,洪嘉振,杨辉.碰撞检测问题研究综述[J].软件学报,1999,10(5)：545-551
[17]魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙：国防科学技术大学,2000
[18]马登武,孙隆和,终明安.虚拟场景中的碰撞检测算法[J].火力与指挥控制,2004,8(4)：46-47
[19]章勤,黄昆,李光明.一种基于OBB的碰撞检测算法的改进[J].华中科技大学学报(自然科学版),2003(1)：46-47
[20]李芙玲,张瑾.碰撞检测技术研究[J].华北科技学院学报,2004(6)：71-73
[21]马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006(4)：1058-1064
[22]崔汉国,陈军,王大宇.虚拟环境中优化的OBB碰撞检测算法研究[J].计算机工程与设计,2007(11)：2524-2526
[23]蔡文军,陈虎.基于混合模型的碰撞检测优化算法研究[J].计算机与现代化.2006(7)：49-52
[24]刘涛,王增波,李占利.碰撞检测过程中的包围盒技术及应用研究[J].西安科技大学学报,2006(9)：395-399
[25]翁晓毅,刘晓平.运用改进的八叉树算法实现精确碰撞检测[J].计算机辅助设计与图形学学报.2005(17)：2631-2635
[26]范昭伟,实时碰撞检测技术研究[D]. 浙江：浙江大学,2003
[27]GOTTSCHALK S. Collision queries using oriented bounding boxes[D]. The University of North Carolina at Chapel H ill,2000
[28]宋永军,苏鸿根.一种基于图像的刚体碰撞检测[J].计算机应用与软件,2004,21(5)：82-84
[29]高春晓,刘玉树.碰撞检测技术综述[J].计算机工程与应用.2002,38(5)：9-11
[30]Hubbard P M. Approximating polyhedral with sphere for time critical collision detection[J]. ACM Transaction on Graphics,15(3):179-210
[31]罗自荣.虚拟环境平台及关键技术研究[D].武汉：华中科技大学,2003
[32]罗自荣,常明,肖人彬.面向虚拟环境的场景管理关键技术及实现研究[J].系统仿真学报,2003,15(6)：891-894
[33]Thomas Larsson, Tomas Akenine-Moller. Efficient collision detection for models deformed by morphing[J]. The Visual Computer,2003(11):164-174
[34]张杰.JAVA3D交互式三维图形编程[B].北京：人民邮电出版社,1999
[35]齐晓松,胡青泥.JAVA3D在虚拟切削和碰撞检测中的应用[J].电脑开发与应用,2006,47(03)：47-49
[36]G.Zaclllnaun E.LangetePe. Geometrie Data Structures for Computer GraPhies[J]. ACM Transactions of GraPhies,2003(7),27-31
[37]管青.导航电子地图开发与应用[M].长春：吉林大学,2006
[38]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技 大学学报,1999,24(3)：209-212
[39]张捍东,郑睿等.移动机器人路径规划技术的现状与展望[J].系统仿真学报.2005，17(2)：439-443
[40]黄炳强,曹光益.基于人工势场法的机器人路径规划研究[J].计算机工程与应用.2006,27(1)：26-28
[41]Paige, Kruskal. Parallel Algorithm for Shortest Paths Problems[J]. Journal of the ACM,1985,3(1):10-20
[42]唐文武,施晓东,朱大奎.GIS中使用改进的Dijkstra算法实现最短路径的计算[J].中国图象图形学报,2000,12(1)：11-12
[43]张前哨.基于A*算法的地图寻径的研究[D].武汉：武汉科技大学.2005
[44]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报.2002,23(2)：210-215
[45]陈勇,王栋,陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报,2007,19(11)：2507-2509
[46]周海霞.三维GIS中虚拟漫游路径的优化研究[M].杭州：浙江大学.2005
[47]刘军.虚拟视景中碰撞检测算法的理论研究[M].长春：吉林大学.2008
[2]都志辉.Java3D编程实践：网络上的三维动画[B].北京：清华大学出版社
[3]田应中,张正禄,杨旭.地下管线网探测与信息管理[B].北京：测绘出版社,1997
[4]张超.地理信息系统[B].北京：高等教育出版社,1995
[5]王英杰,袁勘省,余卓渊.多维动态地学信息可视化[B].北京：科学出版社,2003
[6]张卫峰,林端敏.AutoCAD软件的DXF接口技术[J].机械与电子,2004(11)：78-80
[7]梁雪春,宋德明.AutoCAD二次开发技术指南[B].北京：清华大学出版,2001
[8]李培君.基于GIS的地下管网可视化研究[M].中国人民解放军信息工程大学硕士论文,2006：34-47
[9]杜国明,龚健雅,熊汉江.城市三维管网的可视化及其系统功能实现的关键技术[J],武汉大学学报,2002(10)：534-537
[10]高新瑞.Java 3D与计算机几何设计[B].北京：电子工业出版社,2007
[11]Samet H. Neighbor Finding Techniques for Image Represented by Quad trees[J]. Computer Graphics and Image Processing,1982,18(3):37-57
[12]肖乐斌,孟鲁闽.建立八叉树的变长层次编码技术[J].地理信息世界,1996(2)：11-14
[13]丁佳.大型复杂场景中快速碰撞检测技术的研究[M].成都：电子科技大学,2007
[14]傅由甲,杨克俭,胡平飞.基于动态八叉树的复杂场景交互式实时漫游[J].武汉理工大学学报,2005,29(2)：308-311
[15]熊伟,毛善君,马蔼乃.基于观察者的碰撞检测技术在虚拟环境漫游中的应用[J].计算机应用,2002,22(11)：6-8
[16]王志强,洪嘉振,杨辉.碰撞检测问题研究综述[J].软件学报,1999,10(5)：545-551
[17]魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙：国防科学技术大学,2000
[18]马登武,孙隆和,终明安.虚拟场景中的碰撞检测算法[J].火力与指挥控制,2004,8(4)：46-47
[19]章勤,黄昆,李光明.一种基于OBB的碰撞检测算法的改进[J].华中科技大学学报(自然科学版),2003(1)：46-47
[20]李芙玲,张瑾.碰撞检测技术研究[J].华北科技学院学报,2004(6)：71-73
[21]马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006(4)：1058-1064
[22]崔汉国,陈军,王大宇.虚拟环境中优化的OBB碰撞检测算法研究[J].计算机工程与设计,2007(11)：2524-2526
[23]蔡文军,陈虎.基于混合模型的碰撞检测优化算法研究[J].计算机与现代化.2006(7)：49-52
[24]刘涛,王增波,李占利.碰撞检测过程中的包围盒技术及应用研究[J].西安科技大学学报,2006(9)：395-399
[25]翁晓毅,刘晓平.运用改进的八叉树算法实现精确碰撞检测[J].计算机辅助设计与图形学学报.2005(17)：2631-2635
[26]范昭伟,实时碰撞检测技术研究[D]. 浙江：浙江大学,2003
[27]GOTTSCHALK S. Collision queries using oriented bounding boxes[D]. The University of North Carolina at Chapel H ill,2000
[28]宋永军,苏鸿根.一种基于图像的刚体碰撞检测[J].计算机应用与软件,2004,21(5)：82-84
[29]高春晓,刘玉树.碰撞检测技术综述[J].计算机工程与应用.2002,38(5)：9-11
[30]Hubbard P M. Approximating polyhedral with sphere for time critical collision detection[J]. ACM Transaction on Graphics,15(3):179-210
[31]罗自荣.虚拟环境平台及关键技术研究[D].武汉：华中科技大学,2003
[32]罗自荣,常明,肖人彬.面向虚拟环境的场景管理关键技术及实现研究[J].系统仿真学报,2003,15(6)：891-894
[33]Thomas Larsson, Tomas Akenine-Moller. Efficient collision detection for models deformed by morphing[J]. The Visual Computer,2003(11):164-174
[34]张杰.JAVA3D交互式三维图形编程[B].北京：人民邮电出版社,1999
[35]齐晓松,胡青泥.JAVA3D在虚拟切削和碰撞检测中的应用[J].电脑开发与应用,2006,47(03)：47-49
[36]G.Zaclllnaun E.LangetePe. Geometrie Data Structures for Computer GraPhies[J]. ACM Transactions of GraPhies,2003(7),27-31
[37]管青.导航电子地图开发与应用[M].长春：吉林大学,2006
[38]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技 大学学报,1999,24(3)：209-212
[39]张捍东,郑睿等.移动机器人路径规划技术的现状与展望[J].系统仿真学报.2005，17(2)：439-443
[40]黄炳强,曹光益.基于人工势场法的机器人路径规划研究[J].计算机工程与应用.2006,27(1)：26-28
[41]Paige, Kruskal. Parallel Algorithm for Shortest Paths Problems[J]. Journal of the ACM,1985,3(1):10-20
[42]唐文武,施晓东,朱大奎.GIS中使用改进的Dijkstra算法实现最短路径的计算[J].中国图象图形学报,2000,12(1)：11-12
[43]张前哨.基于A*算法的地图寻径的研究[D].武汉：武汉科技大学.2005
[44]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报.2002,23(2)：210-215
[45]陈勇,王栋,陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报,2007,19(11)：2507-2509
[46]周海霞.三维GIS中虚拟漫游路径的优化研究[M].杭州：浙江大学.2005
[47]刘军.虚拟视景中碰撞检测算法的理论研究[M].长春：吉林大学.2008