面向虚拟城市的三维空间数据引擎设计与实现
|
摘要
空间数据具有关系复杂、非结构化、数据量大、多比例尺、随时间变化等特点。如何实现海量空间数据的管理、共享与高效访问是有效应用空间数据的关键问题。随着虚拟现实、地理信息系统等领域学科的迅速发展,各种虚拟城市相关的三维空间数据在城市规划、仿真训练、应急指挥、智能信息系统等领域得到了广泛应用,同时,也对软件系统的空间数据调度、存取效率提出了极高的要求。
本论文以面向虚拟城市的空间数据索引、海量数据高效调度模型等空间数据引擎关键技术为研究对象;以构建行之有效的三维空间数据引擎为目标;以实现虚拟城市中海量异构空间数据的高效查询与传输方法为主要研究内容;采用从空间索引算法研究、设计、实现,到内外存交换策略与I/O加速方法研究,再到系统无缝集成的技术路线,对面向虚拟城市的三维空间数据引擎进行了设计与实现,并根据研究成果进行三维空间数据引擎在虚拟地理信息系统VR-GIS平台中的集成与应用。论文的主要工作及所取得的研究成果如下:
(1)基于Cell-Rtree的三维空间数据高效索引与存储方法
本文通过分析面向虚拟城市的三维空间数据的特点,提出了适用于虚拟城市三维空间数据的Cell-Rtree索引方法,并结合Hilbert空间填充曲线对空间数据的存储结构进行了优化,提高了数据的索引和存储效率。实验结果表明,在虚拟城市应用环境下Cell-Rtree索引与R-tree、四叉树等传统索引方法相比具有更高的空间查询效率和空间利用率。
(2)面向虚拟城市的高性能数据服务模型设计
本文针对虚拟城市平台需要承载海量三维空间数据的特点,基于Cell‐Rtree空间索引,利用Out‐of‐core技术和IOCP分发机制实现了对百GB数量级三维空间数据的承载与实时调度能力,构建了高效的空间数据引擎数据服务模型,解决了虚拟城市平台中海量空间数据传输的效率问题。?
(3)空间数据引擎性能优化方法
针对空间数据访问的突发性、离散性,以及在访问过程中需要占用大量的内存、CPU等硬件资源的特点。本文对空间数据索引和内外存数据调度时的系统性能进行了分析,通过建立线程池、内存池和I/O队列管理等方法提升了空间数据引擎的整体性能。
(4)面向虚拟城市的空间数据引擎与VR-GIS平台的无缝集成
本文实现了面向虚拟城市的三维空间数据引擎在VR-GIS平台中的无缝集成,基于空间数据引擎实现了一套面向城市/区域级大场景的虚拟地理信息系统。借助空间数据引擎对海量空间数据的高效索引与调度能力,突破了VR-GIS平台在海量数据承载与实时调度等方面的技术瓶颈,实现了空间数据引擎与虚拟城市应用的有效结合,为空间数据引擎的推广与应用提供了范例和参考。
Spatial information is of complex relationships, unstructured, data volume, multi-scale, time-varying and many other features. To translate and share mass spatial data in an efficient way becomes more and more important to many relative research areas. With the development of virtual reality (VR) and geographic information system (GIS), virtual city oriented massive three-dimensional (3D) spatial data has been wildly used in urban planning, simulation training, emergency command, intelligent information systems and put forward higher requirement to the performance of spatial data scheduling and storage.
The dissertation takes the key technology of the virtual city oriented index and high efficiency scheduling for 3D spatial data as the main research topic and aims to build an effective spatial data engine for massive spatial data processing. The main research contents of this dissertation focuses on preprocessing method and efficiency I/O model for virtual city oriented massive spatial data. By design and implement a new Cell-Rtree index methods, spatial query could be finished in an efficient way under virtual city application environment. We also implemented a new out-of-core processes model and make research on asynchronous I/O acceleration method for spatial data exchanging and scheduling. Based on the research results, a virtual city oriented VR-GIS spatial data engine were developed and integrated. The main contents and results of the research in this dissertation are summarized as follows:
(1) The design of a new Cell-Rtree method for Virtual City oriented 3D spatial data preprocessing and indexing.
By analyzing the features of virtual city oriented 3D spatial data, we proposed a new Cell-R Tree index structure which has better time complexity and less overlapping in virtual city applications and optimized 3D spatial data storage structure through Hilbert curve.
(2) The out-of-core service model for virtual city oriented data swapping based on IOCP
This paper implemented an asynchronous method to load and make real-time scheduling on hundreds GB level spatial data using out-of-core technology and IOCP distribution mechanisms which solves the massive spatial data overload problem in virtual city oriented platform.
(3) System-Level performance optimization methodology for spatial data engine
To resolve performance bottleneck in spatial data random access and concurrent query the dissertation analyzed system performance parameters and introduced some new technologies to improve system performance includes thread pool, memory pool, I/O request management, etc.
(4) The integration and development of virtual city oriented 3D rendering engine and spatial data engine.
The dissertation realized the integration of the virtual city oriented spatial data engine and virtual reality 3D rendering engine. Based on the efficient indexing and scheduling ability which provided by spatial data engine, the dissertation implemented dynamic integration between spatial data engine and virtual city application which breaks out the data carrying capacity and performance capacity limits in the conventional 3D rendering engine which applied in virtual city-level applications.
本论文以面向虚拟城市的空间数据索引、海量数据高效调度模型等空间数据引擎关键技术为研究对象;以构建行之有效的三维空间数据引擎为目标;以实现虚拟城市中海量异构空间数据的高效查询与传输方法为主要研究内容;采用从空间索引算法研究、设计、实现,到内外存交换策略与I/O加速方法研究,再到系统无缝集成的技术路线,对面向虚拟城市的三维空间数据引擎进行了设计与实现,并根据研究成果进行三维空间数据引擎在虚拟地理信息系统VR-GIS平台中的集成与应用。论文的主要工作及所取得的研究成果如下:
(1)基于Cell-Rtree的三维空间数据高效索引与存储方法
本文通过分析面向虚拟城市的三维空间数据的特点,提出了适用于虚拟城市三维空间数据的Cell-Rtree索引方法,并结合Hilbert空间填充曲线对空间数据的存储结构进行了优化,提高了数据的索引和存储效率。实验结果表明,在虚拟城市应用环境下Cell-Rtree索引与R-tree、四叉树等传统索引方法相比具有更高的空间查询效率和空间利用率。
(2)面向虚拟城市的高性能数据服务模型设计
本文针对虚拟城市平台需要承载海量三维空间数据的特点,基于Cell‐Rtree空间索引,利用Out‐of‐core技术和IOCP分发机制实现了对百GB数量级三维空间数据的承载与实时调度能力,构建了高效的空间数据引擎数据服务模型,解决了虚拟城市平台中海量空间数据传输的效率问题。?
(3)空间数据引擎性能优化方法
针对空间数据访问的突发性、离散性,以及在访问过程中需要占用大量的内存、CPU等硬件资源的特点。本文对空间数据索引和内外存数据调度时的系统性能进行了分析,通过建立线程池、内存池和I/O队列管理等方法提升了空间数据引擎的整体性能。
(4)面向虚拟城市的空间数据引擎与VR-GIS平台的无缝集成
本文实现了面向虚拟城市的三维空间数据引擎在VR-GIS平台中的无缝集成,基于空间数据引擎实现了一套面向城市/区域级大场景的虚拟地理信息系统。借助空间数据引擎对海量空间数据的高效索引与调度能力,突破了VR-GIS平台在海量数据承载与实时调度等方面的技术瓶颈,实现了空间数据引擎与虚拟城市应用的有效结合,为空间数据引擎的推广与应用提供了范例和参考。
Spatial information is of complex relationships, unstructured, data volume, multi-scale, time-varying and many other features. To translate and share mass spatial data in an efficient way becomes more and more important to many relative research areas. With the development of virtual reality (VR) and geographic information system (GIS), virtual city oriented massive three-dimensional (3D) spatial data has been wildly used in urban planning, simulation training, emergency command, intelligent information systems and put forward higher requirement to the performance of spatial data scheduling and storage.
The dissertation takes the key technology of the virtual city oriented index and high efficiency scheduling for 3D spatial data as the main research topic and aims to build an effective spatial data engine for massive spatial data processing. The main research contents of this dissertation focuses on preprocessing method and efficiency I/O model for virtual city oriented massive spatial data. By design and implement a new Cell-Rtree index methods, spatial query could be finished in an efficient way under virtual city application environment. We also implemented a new out-of-core processes model and make research on asynchronous I/O acceleration method for spatial data exchanging and scheduling. Based on the research results, a virtual city oriented VR-GIS spatial data engine were developed and integrated. The main contents and results of the research in this dissertation are summarized as follows:
(1) The design of a new Cell-Rtree method for Virtual City oriented 3D spatial data preprocessing and indexing.
By analyzing the features of virtual city oriented 3D spatial data, we proposed a new Cell-R Tree index structure which has better time complexity and less overlapping in virtual city applications and optimized 3D spatial data storage structure through Hilbert curve.
(2) The out-of-core service model for virtual city oriented data swapping based on IOCP
This paper implemented an asynchronous method to load and make real-time scheduling on hundreds GB level spatial data using out-of-core technology and IOCP distribution mechanisms which solves the massive spatial data overload problem in virtual city oriented platform.
(3) System-Level performance optimization methodology for spatial data engine
To resolve performance bottleneck in spatial data random access and concurrent query the dissertation analyzed system performance parameters and introduced some new technologies to improve system performance includes thread pool, memory pool, I/O request management, etc.
(4) The integration and development of virtual city oriented 3D rendering engine and spatial data engine.
The dissertation realized the integration of the virtual city oriented spatial data engine and virtual reality 3D rendering engine. Based on the efficient indexing and scheduling ability which provided by spatial data engine, the dissertation implemented dynamic integration between spatial data engine and virtual city application which breaks out the data carrying capacity and performance capacity limits in the conventional 3D rendering engine which applied in virtual city-level applications.
引文
[1]高建新. GIS空间数据研究.测绘科技情报, 2006,1:18-22
[2] ESRI. Products development timeline[OL], http://ww.esri.com/company/about/timeline/ flash/index.html,2003
[3] Oracle. What can Oracle Spatial do for you.[OL], http://otn.oracle.com/products/spatial/ content.html, 2002
[4] BM. DB2 Spatial Extender for linux, Unix and windows[OL], http://www-3.ibm.com/ software/data/spatial/features.html, 2003
[5]李德仁.数码城市(CyberCity)的概念、技术支撑和典型应用.数字湖北与湖北经济研讨会论文集,2001
[6]韩勇.基于VR-GIS的海滨城市VGE系统研究与开发:[博士学位论文].青岛:中国海洋大学,2006
[7]张晶,贾利,臧淑英.地理信息系统的虚拟环境系统构造方法.哈尔滨工业大学学报,2008,40(11):1820-1824
[8]江绵康.“数字城市”的理论与实践:[博士学位论文].上海:华东师范大学,2005
[9]何雄.空间数据库引擎关键技术研究:[博士学位论文].北京:中国科学院计算技术研究所,2006
[10]崔铁军.地理空间数据库原理.北京:科学出版社,2007
[11] Raphael Finkel, J.L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1): 1–9. doi:10.1007/BF00288933.
[12] Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57.
[13] NAKORN Na, CHONGSTIVATANA Tanin. The RD - tree Allowing Data in Interior Nodes of the R-tree[C] // IEEE Conference on Cybernetics and Intelligent Systems, 2006.
[14]郭薇,郭箐,胡志勇.空间数据库索引技术.上海交通大学出版社, 2006.
[15] XIA Tian, ZHANGDonghui. Improving the R3 - tree with outlier handling techniques. Proceedings of the 13 th annual CMinternational workshop on Geographic information systems, 2005:125 - 134.
[16]宋扬,潘懋,朱雷.三维GIS中的R树索引研究.计算机工程与应用, 2004, 14: 9 - 10.
[17]邓红艳,武芳,翟仁健,赵倩.一种用于空间数据多尺度表达的R树索引结构.计算机学报,2009,32(1):177-184
[18] Zhang D H, Xia T. A Novel Improvement to the R*-tree Spatial Index using Gain/Loss Metrics. Proceedings of the 12th annual ACM international workshop on Geographic information systems, 2004: 204 - 213.
[19] Reinhard Wolfinger. Plug-in architecture and design guidelines for customizable enterprise applications. Companion to the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, USA, 2008. 893-894
[20] Miao Song, Serguei A. Mokhov, Alison R.Loader, Maureen J. Simmonds. A stereoscopic OpenGL-based interactive plug-in framework for Maya and beyond. Proceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in Industry, Yokohama, Japan, 2009. 363-368
[21]马纯永.城域景观VRGIS一体化仿真平台研究与实现:[博士学位论文].青岛:中国海洋大学,2010
[22] Bertino Elisa, Ooi Beng Chin. Indispensability of dispensable indexes. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(1): 17-27
[23]黄铎.三维城市模型的数据内容:[博士学位论文].武汉:武汉大学,2004
[24]胡久乡,何松,钟瑜.空间数据库网格索引机制的最优划分.计算机学报,2002,25(11):1227-1230
[25]陆锋,周成虎.一种基于Hilbert排列码的GIS空间索引方法.计算机辅助设计与图形学学报, 2001,13(5):424-429.
[26] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式.北京:机械工业出版社,2000
[27] Ravi Pendse, Ravi Bhagavathula. Performance of LRU Block Replacement Algorithm with Pre-Fetching. Proceedings of the 1998 Midwest Symposium on Systems and Circuits, Washington, DC, USA, 1998. 86
[28]李中,王刚,刘璟.用异步I/O请求处理提高流媒体服务器支持并发访问的性能.计算机科学,2005,32(2):20-24
[29] Jeffery Richter, Christophe Nasarre. Windows via C/C++(葛子昂,周靖,廖敏).北京:清华大学出版社, 2008. 306-308
[30] Scott Meyers. Effecttive C++(侯捷).北京:电子工业出版社,2006
[31] Anthony Jones. Windows网络编程技术.北京:机械工业出版社,2000
[32] Chunyong-Ma ect. An integrated VR-GIS navigation platform for city/region simulation. Proceedings of The 7th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry, Singapore, Article No: 16
[33]马照亭,潘懋等.多源空间数据的共享与集成模式研究.计算机工程与应用,2002, 38, 31-34
[34]李满春,陈奇,周炎坤,李响.基于空间数据引擎的企业化GIS数据组织与处理.中国图象图形学报,2000 (8) : 179-184
[35]郭龙江,李建中.空间数据库的索引技术.黑龙江大学自然科学学报,2005,22(3):288-293.
[36]李德仁,朱欣焰,龚健雅.从数字地图到空间信息网格.武汉大学学报(信息科学版) ,2003,28 (6) : 642-649
[2] ESRI. Products development timeline[OL], http://ww.esri.com/company/about/timeline/ flash/index.html,2003
[3] Oracle. What can Oracle Spatial do for you.[OL], http://otn.oracle.com/products/spatial/ content.html, 2002
[4] BM. DB2 Spatial Extender for linux, Unix and windows[OL], http://www-3.ibm.com/ software/data/spatial/features.html, 2003
[5]李德仁.数码城市(CyberCity)的概念、技术支撑和典型应用.数字湖北与湖北经济研讨会论文集,2001
[6]韩勇.基于VR-GIS的海滨城市VGE系统研究与开发:[博士学位论文].青岛:中国海洋大学,2006
[7]张晶,贾利,臧淑英.地理信息系统的虚拟环境系统构造方法.哈尔滨工业大学学报,2008,40(11):1820-1824
[8]江绵康.“数字城市”的理论与实践:[博士学位论文].上海:华东师范大学,2005
[9]何雄.空间数据库引擎关键技术研究:[博士学位论文].北京:中国科学院计算技术研究所,2006
[10]崔铁军.地理空间数据库原理.北京:科学出版社,2007
[11] Raphael Finkel, J.L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1): 1–9. doi:10.1007/BF00288933.
[12] Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57.
[13] NAKORN Na, CHONGSTIVATANA Tanin. The RD - tree Allowing Data in Interior Nodes of the R-tree[C] // IEEE Conference on Cybernetics and Intelligent Systems, 2006.
[14]郭薇,郭箐,胡志勇.空间数据库索引技术.上海交通大学出版社, 2006.
[15] XIA Tian, ZHANGDonghui. Improving the R3 - tree with outlier handling techniques. Proceedings of the 13 th annual CMinternational workshop on Geographic information systems, 2005:125 - 134.
[16]宋扬,潘懋,朱雷.三维GIS中的R树索引研究.计算机工程与应用, 2004, 14: 9 - 10.
[17]邓红艳,武芳,翟仁健,赵倩.一种用于空间数据多尺度表达的R树索引结构.计算机学报,2009,32(1):177-184
[18] Zhang D H, Xia T. A Novel Improvement to the R*-tree Spatial Index using Gain/Loss Metrics. Proceedings of the 12th annual ACM international workshop on Geographic information systems, 2004: 204 - 213.
[19] Reinhard Wolfinger. Plug-in architecture and design guidelines for customizable enterprise applications. Companion to the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, USA, 2008. 893-894
[20] Miao Song, Serguei A. Mokhov, Alison R.Loader, Maureen J. Simmonds. A stereoscopic OpenGL-based interactive plug-in framework for Maya and beyond. Proceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in Industry, Yokohama, Japan, 2009. 363-368
[21]马纯永.城域景观VRGIS一体化仿真平台研究与实现:[博士学位论文].青岛:中国海洋大学,2010
[22] Bertino Elisa, Ooi Beng Chin. Indispensability of dispensable indexes. IEEE Transactions on Knowledge and Data Engineering, 1999, 11(1): 17-27
[23]黄铎.三维城市模型的数据内容:[博士学位论文].武汉:武汉大学,2004
[24]胡久乡,何松,钟瑜.空间数据库网格索引机制的最优划分.计算机学报,2002,25(11):1227-1230
[25]陆锋,周成虎.一种基于Hilbert排列码的GIS空间索引方法.计算机辅助设计与图形学学报, 2001,13(5):424-429.
[26] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式.北京:机械工业出版社,2000
[27] Ravi Pendse, Ravi Bhagavathula. Performance of LRU Block Replacement Algorithm with Pre-Fetching. Proceedings of the 1998 Midwest Symposium on Systems and Circuits, Washington, DC, USA, 1998. 86
[28]李中,王刚,刘璟.用异步I/O请求处理提高流媒体服务器支持并发访问的性能.计算机科学,2005,32(2):20-24
[29] Jeffery Richter, Christophe Nasarre. Windows via C/C++(葛子昂,周靖,廖敏).北京:清华大学出版社, 2008. 306-308
[30] Scott Meyers. Effecttive C++(侯捷).北京:电子工业出版社,2006
[31] Anthony Jones. Windows网络编程技术.北京:机械工业出版社,2000
[32] Chunyong-Ma ect. An integrated VR-GIS navigation platform for city/region simulation. Proceedings of The 7th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry, Singapore, Article No: 16
[33]马照亭,潘懋等.多源空间数据的共享与集成模式研究.计算机工程与应用,2002, 38, 31-34
[34]李满春,陈奇,周炎坤,李响.基于空间数据引擎的企业化GIS数据组织与处理.中国图象图形学报,2000 (8) : 179-184
[35]郭龙江,李建中.空间数据库的索引技术.黑龙江大学自然科学学报,2005,22(3):288-293.
[36]李德仁,朱欣焰,龚健雅.从数字地图到空间信息网格.武汉大学学报(信息科学版) ,2003,28 (6) : 642-649