采用缓存和Laplace网格简化技术的三维地形可视化研究
|
摘要
三维地形可视化技术是地理信息学和计算机图形学的交叉课题，也是当今社会研究与应用热点之一，广泛应用于工程设计，气象学，地质勘探，仿真等领域。如何快速逼真的显示大规模的地形网格数据，并支持空间分析和人机交互，是三维可视化技术的难点和重要研究方向。因此，本文着力实现一个功能比较全面，实时处理大规模数据量的三维地形可视化系统。
本文介绍了三维地形数据获取、地形分块以及地形子块调度和地形实时显示。在地形子块调度的过程中，引入了多种裁剪剔除方式来减少需处理的地形子块数量，选定数据调度策略来计算地形子块的优先权，并采用多级缓存机制提高内存命中率。本文使用了四叉树结构来描述地形子块，利用Laplace算子计算网格顶点的视点相关误差，并动态设定误差阈值，有效简化了地形子块网格。在计算视点相关误差的时候，利用CUDA流和多线程编程，有效发挥了GPU并行计算能力。为了完善该系统并增强实用性，本文介绍了多种地形显示模式和图形渲染优化技术，实现了简单的人机交互，空间分析以及地形项目管理等。本文最后介绍了如何按照功能对程序进行模块划分，并使每个模块职责单一，接口清晰。利用类的继承性和多态性，使程序具有更强的健壮性和扩展性。
Nowadays, the modeling and visualization of3D terrain is of great importance inglobal information system. There are a lot of software related with3D data process andmanagement in our society, but they are not specially designed for3D terrain, so the abilityto manage the large scale data of terrain and render the terrain timely is quite poor. Basedon this, the paper is committed to design a visual system of3D terrain, which realizes thereal time rendering of real3D terrain. The system enables the user to conduct spatialanalysis and interact with it.
The research mainly includes: the division of3D terrain, loading and dispatch of thesub-block, multiple buffer strategy, the mesh simplification based on the Laplace operator,GPU-CUDA parallel programming, and how to divide the program into models accordingto their functions.
The paper introduces several methods to acquire data of3D terrain, and it selects DEMand DOM to depict the true terrain. Because the local area of terrain is always shown inrendering, the data of terrain is divided into sub-blocks. Then they are stored into Oracledatabase, which facilitate the access of the data. The quad tree structure is introduced toexpress the sub-block. Relying on the method of level of detail, the showing of3D terrainwith multiple solutions is realized.
Given the view point and direction of sight, we can calculate the sub-blocks which areto be rendered. To diminish the frequency of reading the external storage, the multiplebuffer mechanism and data dispatching strategy are introduced. By calculating the priorityof the sub-blocks, we can tell the sub-block is loaded into memory or is substituted. Themultiple buffer mechanism and data dispatching strategy is realized separately, if thecircumstance is changed, we only need to change the data dispatching strategy. To diminishthe amount of data flown into graphical pipeline, view-dependent frustum culling, back faceclipping and mesh simplication are performed. During the period of mesh simplication, weuse Laplace operator to calculate the sharp degree of the mesh point, which helps tocalculate view-dependent error. This method guarantee an low error with stable rate ofsimplication. The mechanism of negative feedback control is adopted to set the thresholdvalue of error. We add triangles when the fractures are occurred where the resolutions ofnodes of terrain is different. GPU-CUDA programming is introduced because theprevalence of GPU processor. The sub-blocks of terrain is treated as several CUDA flow, and each point is considered as an independent thread. Because several calculations areexecuted simultaneously, the time of computing is reduced sharply.
Several modes are adopted to display the terrain, such as hypsometric tint diagram inwhich points with different heights are paints with correspondent colors. By settinglighting, material and texture, the shade effect and realistic surface of terrain is realized. Toserialize the model of terrain processed by static simplication, the method of optimizing theconfiguration of triangle is introduced, which increases the hit rate of point buffer in visualmemory.
To better perform the interaction and spatial analysis, perspective projection andorthogonal projection are provided. Mouse and keyboard are utilized to control the viewpoint and direction of sight. Through clicking the window,3D coordinate are extracted, thenthe distance of the points are calculated. In the mode of orthogonal projection, functions ofzoom and translation are realized, which help to observe local area.
In the end, the paper indicates how to divide the program into models, which include:display model of OpenGL, OCI model of database, model of geometric object, and modelof terrain. Several classes is divided inside the model. Take the model of terrain as anexample, there are class of buffer mechanism, class of data dispatching strategy, class ofassembling the basic primitives into geometric object. These classes have clear interfaces ofinput and output. The feature of inheritance and polymorphism is utilized to extendfunctions of the program, which meet the ever-changing requirement. MFC mechanism isadopted as the main framework, function of serialization and mode of document-view areapplied. By operating the database, several projects of terrain can be managed.
Above all, database of Oracle is utilized to access the data. To handle the large amountof data, several methods such as dividing the terrain into sub-blocks, multiple buffermechanism, clipping and culling are adopted. To simplify the mesh efficiently, Laplaceoperator is introduced to calculate viewpoint dependent error. The detailed framework isgiven in the end of the paper. The visual system of3D terrain has a broad prospective inpractice.
本文介绍了三维地形数据获取、地形分块以及地形子块调度和地形实时显示。在地形子块调度的过程中，引入了多种裁剪剔除方式来减少需处理的地形子块数量，选定数据调度策略来计算地形子块的优先权，并采用多级缓存机制提高内存命中率。本文使用了四叉树结构来描述地形子块，利用Laplace算子计算网格顶点的视点相关误差，并动态设定误差阈值，有效简化了地形子块网格。在计算视点相关误差的时候，利用CUDA流和多线程编程，有效发挥了GPU并行计算能力。为了完善该系统并增强实用性，本文介绍了多种地形显示模式和图形渲染优化技术，实现了简单的人机交互，空间分析以及地形项目管理等。本文最后介绍了如何按照功能对程序进行模块划分，并使每个模块职责单一，接口清晰。利用类的继承性和多态性，使程序具有更强的健壮性和扩展性。
Nowadays, the modeling and visualization of3D terrain is of great importance inglobal information system. There are a lot of software related with3D data process andmanagement in our society, but they are not specially designed for3D terrain, so the abilityto manage the large scale data of terrain and render the terrain timely is quite poor. Basedon this, the paper is committed to design a visual system of3D terrain, which realizes thereal time rendering of real3D terrain. The system enables the user to conduct spatialanalysis and interact with it.
The research mainly includes: the division of3D terrain, loading and dispatch of thesub-block, multiple buffer strategy, the mesh simplification based on the Laplace operator,GPU-CUDA parallel programming, and how to divide the program into models accordingto their functions.
The paper introduces several methods to acquire data of3D terrain, and it selects DEMand DOM to depict the true terrain. Because the local area of terrain is always shown inrendering, the data of terrain is divided into sub-blocks. Then they are stored into Oracledatabase, which facilitate the access of the data. The quad tree structure is introduced toexpress the sub-block. Relying on the method of level of detail, the showing of3D terrainwith multiple solutions is realized.
Given the view point and direction of sight, we can calculate the sub-blocks which areto be rendered. To diminish the frequency of reading the external storage, the multiplebuffer mechanism and data dispatching strategy are introduced. By calculating the priorityof the sub-blocks, we can tell the sub-block is loaded into memory or is substituted. Themultiple buffer mechanism and data dispatching strategy is realized separately, if thecircumstance is changed, we only need to change the data dispatching strategy. To diminishthe amount of data flown into graphical pipeline, view-dependent frustum culling, back faceclipping and mesh simplication are performed. During the period of mesh simplication, weuse Laplace operator to calculate the sharp degree of the mesh point, which helps tocalculate view-dependent error. This method guarantee an low error with stable rate ofsimplication. The mechanism of negative feedback control is adopted to set the thresholdvalue of error. We add triangles when the fractures are occurred where the resolutions ofnodes of terrain is different. GPU-CUDA programming is introduced because theprevalence of GPU processor. The sub-blocks of terrain is treated as several CUDA flow, and each point is considered as an independent thread. Because several calculations areexecuted simultaneously, the time of computing is reduced sharply.
Several modes are adopted to display the terrain, such as hypsometric tint diagram inwhich points with different heights are paints with correspondent colors. By settinglighting, material and texture, the shade effect and realistic surface of terrain is realized. Toserialize the model of terrain processed by static simplication, the method of optimizing theconfiguration of triangle is introduced, which increases the hit rate of point buffer in visualmemory.
To better perform the interaction and spatial analysis, perspective projection andorthogonal projection are provided. Mouse and keyboard are utilized to control the viewpoint and direction of sight. Through clicking the window,3D coordinate are extracted, thenthe distance of the points are calculated. In the mode of orthogonal projection, functions ofzoom and translation are realized, which help to observe local area.
In the end, the paper indicates how to divide the program into models, which include:display model of OpenGL, OCI model of database, model of geometric object, and modelof terrain. Several classes is divided inside the model. Take the model of terrain as anexample, there are class of buffer mechanism, class of data dispatching strategy, class ofassembling the basic primitives into geometric object. These classes have clear interfaces ofinput and output. The feature of inheritance and polymorphism is utilized to extendfunctions of the program, which meet the ever-changing requirement. MFC mechanism isadopted as the main framework, function of serialization and mode of document-view areapplied. By operating the database, several projects of terrain can be managed.
Above all, database of Oracle is utilized to access the data. To handle the large amountof data, several methods such as dividing the terrain into sub-blocks, multiple buffermechanism, clipping and culling are adopted. To simplify the mesh efficiently, Laplaceoperator is introduced to calculate viewpoint dependent error. The detailed framework isgiven in the end of the paper. The visual system of3D terrain has a broad prospective inpractice.
引文
[1] M Pauline Baker Danald Hearn.计算机图形学[M].北京：电子工业出版社，2005.6:57-123.
[2] Alan Watt.3D Computer Graphics[M]. Pearson Education，2005.7:113-187.
[3] Zuo Zongyi Wei Yuwei, Feng Kaiping Generating random fractal terrain with OpenGLtechnology[C], Proceedings of the11~(th) International conference on Geometry andGraphics. Guangzhou, China,2004.
[4] Song Hanchen, Gao Yu Wei, YingMei, et al. Interactive Generation and Rendering of3-Dimension Terrain[J]. Computer Engineering and Applications,2004,(31):80-82.
[5] Andre Lamothe.3D游戏编程大师技巧[M].北京市：人民邮电出版社，2005:74-223.
[6] Zhou Kun, Pan Zhigeng, Shi Jiaoying. Smooth transition between levels of detail ofmodels[J]. Journal of Computer Aided Design and Computer Graphics,2000,(6):463-467.
[7] Amayri O., Bouguila N.A. A study of spam filtering using support vector machines[J].Artificial Intelligence Review,2010,34(1):73-108.
[8] Pronobis A., Jie L., Caputo B. The more you learn,the less you store:memory controlledincremental SVM for visual place recognition[J]. Image and Vision Computing,2010,28(7):1090-1097.
[9] Zhou Kun;, Pan Zhi-Geng, Shi Jiao-Ying. mesh simplication algorithum based on tranglecollapse[J]. Chinese journal of computers,1998,(6):506-513.
[10] The Khronos OpenGL ARB Working Group Dave Shreiner. OpenGL编程指南[M].BeiJing：China Machine Press，2010:19-59.
[11] Wald I, Dietrich A, Slusallek P. An Interactive out-of-core rendering framework forvisualizing massively complex models[C], Proceedings of ACM SIGGRAPH. New York,2005.
[12] HOPPE H. LOSASSO F. Geometry clipmaps:terrain rendering using nested regulargrids[C], Proceedings of the2004SIGGRAPH Conference. New York,USA,2004.
[13] Xiong H, Liu Z, Qin A H. Predictive occlusion culling for interactive rendering of largecomplex virtual scene[J]. Lecture Notes in Computer Science,2006,(4270):93-102.
[14] Zhang H, Manocha D, Hudson T. Visibility culling using hierarchical occlusion maps[C],Procedings of ACM SIGGRAPH New York,1997.
[15] Silva C T, Chiang Y J, El-Sana J. Out-of-core algorithms for scientific visualization andcomputer graphics.[C], IEEE Visualization. Washington,2003.
[16]侯捷. STL源码剖析[M].武汉：华中科技大学出版社，2002:43-79.
[17] Grinfeld P., Strang G. Laplace eigenvalues on regular polygons: A series in1/N[J].Journal of Mathematical Analysis and Applications,2012,385(1):135-149.
[18] Yoon S E, Salomon B, Gayle R. Quick-VDR:Interactive view-dependent rendering ofmassive models[C], Proceeedings of IEEE Visualization.2004.
[19] Zhou Jie Ding, Xianrong Wang, Deguan;. An efficient method for delaunay triangulationof scattered points on plane[J]. Journal of Geomatics.,2003,(6):21-23.
[20] Gutierrez P D, Bhushan A, Gopi M. Constrained strip generation and management forefficient interactive3D rendering[C], Computer Graphics International Conference NewYork,2005.
[21] GEORGE PL. Improvements on Delaunay-based three dimensional automatic meshgenerator[J]. Finite Elements in Analysis and Design,1997,25(34):297-317.
[22] ULRICH T. Rendering massive terrains using chunked level of detail control[C],Computer Graphics Proceeding Annual Conference Series. San Antonio,Texas,USA,2002.
[23]翟振刚.立体匹配算法研究[M].北京：北京理工大学，2010:12-34.
[24] Tarditi D, Puri S, Oglesby J. Accelerator:Using data-prallelism to program GPUs forgeneral-purpose uses[C], ASPLOS. SanJose,2006.
[25]杨珂, Luo Q,石教英.平行散点图：基于GPU的可视化分析技术[J].计算机辅助设计与图形学学报,2008,20(9):1-10.
[26] Jason Sanders, Edward Kandrot. CUDA By Example an Introduction to General-PurposeGPU Programming[M].北京：机械工业出版社，2011.
[27] Hoppe H. Optimization of mesh locality for transparent vertex caching[C], Proceedingsof ACM SIGGRAPH. Los Angeles,1999.
[28] Niski K, Purnomo B, Cohen J. Multi-grained level of detail using a hierachical seamlesstexture atlas[C], Proceedings of Symposium on Interactive3D Graphics and Games.New York,2007.
[29]王德才,杨关胜,孙玉萍.精通DirectX3D图形与动画程序设计[M].北京：人民邮电出版社，2007:78-92.
[30]王清辉,王彪. Visual C++CAD应用程序开发技术[M].北京：机械工业出版社，2003:89-101.
[2] Alan Watt.3D Computer Graphics[M]. Pearson Education，2005.7:113-187.
[3] Zuo Zongyi Wei Yuwei, Feng Kaiping Generating random fractal terrain with OpenGLtechnology[C], Proceedings of the11~(th) International conference on Geometry andGraphics. Guangzhou, China,2004.
[4] Song Hanchen, Gao Yu Wei, YingMei, et al. Interactive Generation and Rendering of3-Dimension Terrain[J]. Computer Engineering and Applications,2004,(31):80-82.
[5] Andre Lamothe.3D游戏编程大师技巧[M].北京市：人民邮电出版社，2005:74-223.
[6] Zhou Kun, Pan Zhigeng, Shi Jiaoying. Smooth transition between levels of detail ofmodels[J]. Journal of Computer Aided Design and Computer Graphics,2000,(6):463-467.
[7] Amayri O., Bouguila N.A. A study of spam filtering using support vector machines[J].Artificial Intelligence Review,2010,34(1):73-108.
[8] Pronobis A., Jie L., Caputo B. The more you learn,the less you store:memory controlledincremental SVM for visual place recognition[J]. Image and Vision Computing,2010,28(7):1090-1097.
[9] Zhou Kun;, Pan Zhi-Geng, Shi Jiao-Ying. mesh simplication algorithum based on tranglecollapse[J]. Chinese journal of computers,1998,(6):506-513.
[10] The Khronos OpenGL ARB Working Group Dave Shreiner. OpenGL编程指南[M].BeiJing：China Machine Press，2010:19-59.
[11] Wald I, Dietrich A, Slusallek P. An Interactive out-of-core rendering framework forvisualizing massively complex models[C], Proceedings of ACM SIGGRAPH. New York,2005.
[12] HOPPE H. LOSASSO F. Geometry clipmaps:terrain rendering using nested regulargrids[C], Proceedings of the2004SIGGRAPH Conference. New York,USA,2004.
[13] Xiong H, Liu Z, Qin A H. Predictive occlusion culling for interactive rendering of largecomplex virtual scene[J]. Lecture Notes in Computer Science,2006,(4270):93-102.
[14] Zhang H, Manocha D, Hudson T. Visibility culling using hierarchical occlusion maps[C],Procedings of ACM SIGGRAPH New York,1997.
[15] Silva C T, Chiang Y J, El-Sana J. Out-of-core algorithms for scientific visualization andcomputer graphics.[C], IEEE Visualization. Washington,2003.
[16]侯捷. STL源码剖析[M].武汉：华中科技大学出版社，2002:43-79.
[17] Grinfeld P., Strang G. Laplace eigenvalues on regular polygons: A series in1/N[J].Journal of Mathematical Analysis and Applications,2012,385(1):135-149.
[18] Yoon S E, Salomon B, Gayle R. Quick-VDR:Interactive view-dependent rendering ofmassive models[C], Proceeedings of IEEE Visualization.2004.
[19] Zhou Jie Ding, Xianrong Wang, Deguan;. An efficient method for delaunay triangulationof scattered points on plane[J]. Journal of Geomatics.,2003,(6):21-23.
[20] Gutierrez P D, Bhushan A, Gopi M. Constrained strip generation and management forefficient interactive3D rendering[C], Computer Graphics International Conference NewYork,2005.
[21] GEORGE PL. Improvements on Delaunay-based three dimensional automatic meshgenerator[J]. Finite Elements in Analysis and Design,1997,25(34):297-317.
[22] ULRICH T. Rendering massive terrains using chunked level of detail control[C],Computer Graphics Proceeding Annual Conference Series. San Antonio,Texas,USA,2002.
[23]翟振刚.立体匹配算法研究[M].北京：北京理工大学，2010:12-34.
[24] Tarditi D, Puri S, Oglesby J. Accelerator:Using data-prallelism to program GPUs forgeneral-purpose uses[C], ASPLOS. SanJose,2006.
[25]杨珂, Luo Q,石教英.平行散点图：基于GPU的可视化分析技术[J].计算机辅助设计与图形学学报,2008,20(9):1-10.
[26] Jason Sanders, Edward Kandrot. CUDA By Example an Introduction to General-PurposeGPU Programming[M].北京：机械工业出版社，2011.
[27] Hoppe H. Optimization of mesh locality for transparent vertex caching[C], Proceedingsof ACM SIGGRAPH. Los Angeles,1999.
[28] Niski K, Purnomo B, Cohen J. Multi-grained level of detail using a hierachical seamlesstexture atlas[C], Proceedings of Symposium on Interactive3D Graphics and Games.New York,2007.
[29]王德才,杨关胜,孙玉萍.精通DirectX3D图形与动画程序设计[M].北京：人民邮电出版社，2007:78-92.
[30]王清辉,王彪. Visual C++CAD应用程序开发技术[M].北京：机械工业出版社，2003:89-101.