多分辨率LOD地形建模及简化技术研究
|
摘要
三维真实感地形是可视化系统及虚拟仿真的基本组成部分，随着未来可视化和仿真技术快速发展，具有真实自然视觉效果的三维地形生成和建模技术显得越来越重要。同时随着测绘技术的提高，获得大规模的地形数据已不是难题。然而，由于图形显示硬件及传输线路的限制又导致我们不能很好的实时显示和处理这些庞大的数据。因此，如何简化地形显示，加快绘制速度成为国内外研究的热点。目前在三维地形的建模和简化领域，使用最多的是利用LOD算法生成地形的连续多分辨率模型，进而完成地形的实时多分辨率显示。
本文首先介绍了三维地形建模及简化技术的研究目的、内容及应用领域和发展前景，随后介绍多分辨率LOD地形及分形地形建模技术的相关理论和研究技术。在深入研究地形建模和简化的典型算法的基础上，提出基于层次细节简化和分形的真实感地形生成方法。该方法相对于用DEM数据构造地形，所用数据量减少，能实时生成满足一定需要的真实感场景。针对以往简化算法中单向裂缝消除算法效率低的问题，提出一种新的裂缝消除算法：双向裂缝消除算法，实验结果证明了该算法的正确性和有效性。
Realistic 3D terrain is one of the important components of virtual reality system and real time emulation. With the quickly development of virtual reality and emulation, the generation and modeling of high realistic terrain becomes more and more important. At the same time, with the development of mapping technology, it is easy to get massive terrain data now. But because of the limitation of graphics hardware and transport circuitry, we can't deal with these data in real-time. So how to simply the terrain efficiently and quicken the protract speed become the research hotspots broad and home. Recently the most often used way in this field is to generate multi-resolution terrains with level of detail (LOD) technology.
Firstly, this dissertation presents the purpose, the background, the application and the prospect of terrain generation and simplification. Secondly, the dissertation gives an introduction of LOD and fractal theory. Thirdly, based on the study of classical modeling algorism, the dissertation puts forward a new method to simulate complex terrain using fractal and LOD. It uses much less data than DEM but gives a good result. Finally, thinking of the low efficiency of the old cracks elimination way, a new bi-directional method is given which can simplify the terrain efficiently and increase the rendering speed.
本文首先介绍了三维地形建模及简化技术的研究目的、内容及应用领域和发展前景，随后介绍多分辨率LOD地形及分形地形建模技术的相关理论和研究技术。在深入研究地形建模和简化的典型算法的基础上，提出基于层次细节简化和分形的真实感地形生成方法。该方法相对于用DEM数据构造地形，所用数据量减少，能实时生成满足一定需要的真实感场景。针对以往简化算法中单向裂缝消除算法效率低的问题，提出一种新的裂缝消除算法：双向裂缝消除算法，实验结果证明了该算法的正确性和有效性。
Realistic 3D terrain is one of the important components of virtual reality system and real time emulation. With the quickly development of virtual reality and emulation, the generation and modeling of high realistic terrain becomes more and more important. At the same time, with the development of mapping technology, it is easy to get massive terrain data now. But because of the limitation of graphics hardware and transport circuitry, we can't deal with these data in real-time. So how to simply the terrain efficiently and quicken the protract speed become the research hotspots broad and home. Recently the most often used way in this field is to generate multi-resolution terrains with level of detail (LOD) technology.
Firstly, this dissertation presents the purpose, the background, the application and the prospect of terrain generation and simplification. Secondly, the dissertation gives an introduction of LOD and fractal theory. Thirdly, based on the study of classical modeling algorism, the dissertation puts forward a new method to simulate complex terrain using fractal and LOD. It uses much less data than DEM but gives a good result. Finally, thinking of the low efficiency of the old cracks elimination way, a new bi-directional method is given which can simplify the terrain efficiently and increase the rendering speed.
引文
[Blow2000] Jonat han Blow. Terrain rendering at high levels of detail[A]. Proceedings of Game Developers Conference[C]. San Jos California, 2000.
[CP1994] Y.K.Choi, K.H. Park. A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure. Virsual Computer. (10):372-387,1994
[Cao1997] 曹晓光．随机中点位移算法的改进．中国图象图形学报，1997，2(4)：234-238
[Cui1999] 崔铁军．利用等高线建立高质量数字地面模型[A]．中国地理信息系统协会论文集[C]．1999．881～886．
[CDY1999] 崔铁军，董延春，杨大洲．TIN到格网DEM的内插方法[A]．王家耀．地理信息系统与电子地图技术的进展[C]．长沙：湖南地图出版社，1999，333～341．
[CMW2001] Chen B, Ma Z, Wang G, etal. Network based real-time fly through on massive terrain dataset[A]. 第七届计算机辅助设计与图形学国际学术会议文集[C].北京: 2001,213.
[Dou1986] Douglas D H. Experiments to locate ridges and channels to create a new type of digital elevation model[J]. Cartographica, 1986; 23(4): 29-61.
[DD1995] M. Deberg and K. T. G.Dobrindt. On levels of detail in terrains. Technical Report UU-CS-1995-12,Department of Computer Science, Utrecht University, 1995.
[Dee1995] M. Deering, Geometry Compression, Computer Graphics, Proceedings Siggraph'95,13-20, August 1995.
[DW1997] Mark Duchaineau, Murray Wolinski etal. Roaming terrain: Real-time, optimally adapting meshes[C].In: Proceedings of the Conference on Visualization'97, Phoenix, AZ USA, 1997:81～88.
[ESV1996] F. Evans, S. Skiena and A. Varshney, Optimizing TriangleStrips for Fast Rendering, Proceedings, IEEE Vizualization'96,pp.319-326,1996.
[FL1979] Fowler R J, Little J J. Automatic extraction of irregular network digital terrain models[C].In: Proceeding of SIGGRAPH'79, Computer Graphics, 1979;13(2):144～151.
[FFC1982] Fournier A, Fussell D, Carpenter L. Computer Rendering of Stoch astic Models. Communications of the ACM, 1982
[Flo1983] L.De Floriani.A Delaunay-based method for surface approxlmatlon. In: Eurograpnlcs'83, pages3 33-350, 1983.
[Flo1989] L. De Floriani. A pyramidal data structure for triangle-based surface description IEEE Computer Graphicsand Applications, 9(2):67-78,M archl 989.
[FMP1996] L. De Floriani, P. Marzano, and E. Puppo. Multiresolution models for topographic surface description.The Visual Computer,12(7):317-345,August 1996.
[FMP1998] L. De Floriani, P Magillo, and E. Puppo. Eficient implementation of Multi-Triangulations. In Proceedings IEEE Visualization'98,October1998.
[GG1979] D. Gomez and A. Guzman. Digital model for three-dimensional surface representation.Geo-Processing,1:53-70,1979
[GG1995] M.H.Gross, R.Gati, and O.Staadt.Fast multiresolution surfacemeshing. In Proceedings IEEE Visualization' 95, July 1995.
[GH1997] Michael Garland and Paul S. Heckbert Surface simplification using quadric error metrics.In Turner Whitted, editor, Proceedings of SIGGRAPH 97,Computer Graphics Proceedings, Annual Conference Addison Wesley, August 1997. ISBN 0-89791-896-7.Held in Los Angeles, California.
[He1999] Y. He. Multiple resolution surface representation and their extension for dynamicte rrain:a survey. Technical report, Department of Computer Science, The University of Iowa, February 1999.
[Hopp1996] Hugues Hoppe.Progressive meshes. Computer Graphics(SIGGRAPH'96 Proceedings), pages 99-108, 1996.
[Hoppe1998] Hoppe H.Smooth view dependent level of detail control and it's application to terrain rendering [EB/OL]. http://research.microsoft. com/～hoppe,1998.
[JZ2000] 蒋红斐，詹振炎．利用锥构建DTM生成算法的研究[J]．武汉测绘科技大学学报，2000，25(2)：119～121．
[Kep1989] E. Keppel. Approximating Complex surface interpolation technique for construction 3D objects from serial cross-sections. CVGIP,48(1):124-143,1989.
[KHCl993] 柯正谊，何建邦，池天河．数字地面模型[M]．北京：中国科学技术出版社，1993.
[Kum1994] M.P. Kumler. An intensive comparison of triangulated irregular networks(TINS) and digital elevation models(DEMs).Cartographica,31(2),Summer 1994.
[Kum1994] M.P. Kumler. An intensive comparison of triangulated irregular networks(T INS) and digital elevationmodels(DEMs). Cartographica,31 (2),Summer 1994
[LJ1985] J. Guibas Leonidas, Stolfi Jorge. Primitives for the manipulation of general subdivisions and computation of voronoi diagrams. ACM ,Transactio ns on Graphics,4(2):74-123,1985
[Lee1991] J. Lee. Analyses of visibility sites on topographic surface. Int. J. Geographical Information Systems, 5(4):413-429, 1991.
[LK1996] Peter Lindstrom, David Koller etal. Real-time, continuous level of detail rendering of height fields[C].In: SIGGRAPH'96 Conference Proceeding, New Orleans, Louisiana, USA 1996: 109～118.
[LP1992] L.Scarlatos and T.Pavlidis. Hierarchical triangulation usingcartogra phic coherence.CVGIP:Graphical Models and Image Processi ng,54(2):147-161, March 1992.
[Lou1994] M.Lounsbery.Multiresolution Analysis for Surfaces of Arbitrary To pological Type. PhD thesis, Dept.of Computer Science and Engineering, Uni versity of Washington, 1994.
[LE1997] David Luebke and Carl Erikson. View-dependent simplification of ar bitrary polygonal environments.In Turner Whitted,editor,Proceedings of SIGG RAPH 97, Computer Graphics Proceedings,Annual Conference Series,pages199-208 Addison Wesley, August 1997. ISBN 0-89791-896-7. Held in Los Angeles,California
[Li1999] 李树军．海底数字深度模型(SDDM)的建立及其应用[D]．郑州：解放军信息工程大学测绘学院，1999．
[LC2001] 李杰，陈锦昌．3D 面控制在三维分形地形中的应用[J]．工程图学学报，2001，(1)：113-117．
[LCZ2003] 李旭涛，曹汉强，赵鸿燕．分形布朗运动模型及其在地形分析中的应用．华中科技大学学报(自然科学版)，2003，31(5)：50-52
[LWLL2005] 梁俊，王琪，刘坤良，卢全慧．基于随机中点位移法的三维地形模拟．计算机仿真，2005，22(1)：213-215，223
[LJLW2006] 李胜，冀俊峰，刘学慧，吴恩华．超大规模地形场景的高性能漫游[J]．软件学报March 2006 V01．17．535-545．
[MPH2004] 马照亭，潘懋，胡金星，等．一种基于数据分块的海量地形快速漫游方法[J]．北京大学学报(自然科学版)，2004，40(4)：6192625．
[Ma1998] 马小虎，1998，“虚拟现实中多细节层次模型的研究”，[浙江大学博士论文]，指导老师：石教英，潘志庚．
[PL2001] 彭仪普，刘文熙．分形地形模拟研究[J]．长沙铁道学院学报，2001，19(4)：95-98．
[QHT2000] 齐敏，郝重阳，佟明安．基于分形技术的多分辨率三维地景建模方 法研究[J]．中国图象图形学报，2000,5A(7)：568-572．
[RB1993] Jarek Rossignac and Paul Borrel. Multi-resolution 3d approximations for rendering complex scenes. In Bianca Falciendo an Toshiyasu L.Kunii, editors, Modeling in Computer Graphics, IFIP series on 455-465.Springer-Verlag,1993.
[Ros1998] Jarek Rossignac. Interactive exploration of distributed 3D datasets over the Internet, Computer Graphics International Congress (CGI 98 congress),Hanover, pp.324-355,June 24-26,1998.
[RHS1997] Stefan Rottger, Wolfgang Heidrich, Philipp Slusallek etal, Real-time generation of continuous levels of detail for height fields[R]. Technical Report 13/1997, Universit&t Erlangen Nurnberg.
[RFW2006] 栾元重，范玉红，王永等．塌陷区地形分形生成方法与应用[J]．地球信息科学，2006，8(4)：111-116．
[SJ2004] 孙铁红，焦永和．基于视点和分形理论的真实感地形实时生成方法[J]．系统仿真学报，2004，16(12)：2729-2731．
[TC2003] 谭建荣，陈洪亮．基于FBM约束模型的可控性分形生成方法．软件学报，2003，14(3)：651-659
[Ulr2002] Ulrich T.Rendering massive terrains using chunked level detail control[M].SIGGRAPH 2002,course35.
[WD2000] 王宏武，董士海．一个与视点相关的动态多分辨率地形模型[J]．计算机辅助设计与图形学学报，2000；12(8)：575-579
[Zhu1997] 朱长青．计算方法及其在测绘中的应用[M]．北京：测绘出版社，1997．
[ZSZ2002] 赵友兵，石教英，周骥．一种大规模地形的快速漫游算法[J]．计算机辅助设计与图形学学报，2002，14(7)：6242628．
[ZW2002] 张鑫，王琰．三维地形的分形构造及其虚拟漫游．沈阳工业学院学报，2002，21(4)：25-27
[Pup1996] E. Puppo.Variable resolution triangulations. Te chnical report, IM A-CNR, 1996
[ZZS2005] 卓亚芬，赵友兵，石教英．实时地形绘制算法综述．计算机仿真，2005，22(3)：4-7
[Sun2004] 孙博文．分形算法与程序设计-VC++实现[M]．北京：科学出版社，2004，287-308．
[YX2006] 殷宏，许继恒等．基于四叉树的大规模地形可视化及其实现[J]计算机应用研究，2006，23(5)：151-153．
[CP1994] Y.K.Choi, K.H. Park. A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure. Virsual Computer. (10):372-387,1994
[Cao1997] 曹晓光．随机中点位移算法的改进．中国图象图形学报，1997，2(4)：234-238
[Cui1999] 崔铁军．利用等高线建立高质量数字地面模型[A]．中国地理信息系统协会论文集[C]．1999．881～886．
[CDY1999] 崔铁军，董延春，杨大洲．TIN到格网DEM的内插方法[A]．王家耀．地理信息系统与电子地图技术的进展[C]．长沙：湖南地图出版社，1999，333～341．
[CMW2001] Chen B, Ma Z, Wang G, etal. Network based real-time fly through on massive terrain dataset[A]. 第七届计算机辅助设计与图形学国际学术会议文集[C].北京: 2001,213.
[Dou1986] Douglas D H. Experiments to locate ridges and channels to create a new type of digital elevation model[J]. Cartographica, 1986; 23(4): 29-61.
[DD1995] M. Deberg and K. T. G.Dobrindt. On levels of detail in terrains. Technical Report UU-CS-1995-12,Department of Computer Science, Utrecht University, 1995.
[Dee1995] M. Deering, Geometry Compression, Computer Graphics, Proceedings Siggraph'95,13-20, August 1995.
[DW1997] Mark Duchaineau, Murray Wolinski etal. Roaming terrain: Real-time, optimally adapting meshes[C].In: Proceedings of the Conference on Visualization'97, Phoenix, AZ USA, 1997:81～88.
[ESV1996] F. Evans, S. Skiena and A. Varshney, Optimizing TriangleStrips for Fast Rendering, Proceedings, IEEE Vizualization'96,pp.319-326,1996.
[FL1979] Fowler R J, Little J J. Automatic extraction of irregular network digital terrain models[C].In: Proceeding of SIGGRAPH'79, Computer Graphics, 1979;13(2):144～151.
[FFC1982] Fournier A, Fussell D, Carpenter L. Computer Rendering of Stoch astic Models. Communications of the ACM, 1982
[Flo1983] L.De Floriani.A Delaunay-based method for surface approxlmatlon. In: Eurograpnlcs'83, pages3 33-350, 1983.
[Flo1989] L. De Floriani. A pyramidal data structure for triangle-based surface description IEEE Computer Graphicsand Applications, 9(2):67-78,M archl 989.
[FMP1996] L. De Floriani, P. Marzano, and E. Puppo. Multiresolution models for topographic surface description.The Visual Computer,12(7):317-345,August 1996.
[FMP1998] L. De Floriani, P Magillo, and E. Puppo. Eficient implementation of Multi-Triangulations. In Proceedings IEEE Visualization'98,October1998.
[GG1979] D. Gomez and A. Guzman. Digital model for three-dimensional surface representation.Geo-Processing,1:53-70,1979
[GG1995] M.H.Gross, R.Gati, and O.Staadt.Fast multiresolution surfacemeshing. In Proceedings IEEE Visualization' 95, July 1995.
[GH1997] Michael Garland and Paul S. Heckbert Surface simplification using quadric error metrics.In Turner Whitted, editor, Proceedings of SIGGRAPH 97,Computer Graphics Proceedings, Annual Conference Addison Wesley, August 1997. ISBN 0-89791-896-7.Held in Los Angeles, California.
[He1999] Y. He. Multiple resolution surface representation and their extension for dynamicte rrain:a survey. Technical report, Department of Computer Science, The University of Iowa, February 1999.
[Hopp1996] Hugues Hoppe.Progressive meshes. Computer Graphics(SIGGRAPH'96 Proceedings), pages 99-108, 1996.
[Hoppe1998] Hoppe H.Smooth view dependent level of detail control and it's application to terrain rendering [EB/OL]. http://research.microsoft. com/～hoppe,1998.
[JZ2000] 蒋红斐，詹振炎．利用锥构建DTM生成算法的研究[J]．武汉测绘科技大学学报，2000，25(2)：119～121．
[Kep1989] E. Keppel. Approximating Complex surface interpolation technique for construction 3D objects from serial cross-sections. CVGIP,48(1):124-143,1989.
[KHCl993] 柯正谊，何建邦，池天河．数字地面模型[M]．北京：中国科学技术出版社，1993.
[Kum1994] M.P. Kumler. An intensive comparison of triangulated irregular networks(TINS) and digital elevation models(DEMs).Cartographica,31(2),Summer 1994.
[Kum1994] M.P. Kumler. An intensive comparison of triangulated irregular networks(T INS) and digital elevationmodels(DEMs). Cartographica,31 (2),Summer 1994
[LJ1985] J. Guibas Leonidas, Stolfi Jorge. Primitives for the manipulation of general subdivisions and computation of voronoi diagrams. ACM ,Transactio ns on Graphics,4(2):74-123,1985
[Lee1991] J. Lee. Analyses of visibility sites on topographic surface. Int. J. Geographical Information Systems, 5(4):413-429, 1991.
[LK1996] Peter Lindstrom, David Koller etal. Real-time, continuous level of detail rendering of height fields[C].In: SIGGRAPH'96 Conference Proceeding, New Orleans, Louisiana, USA 1996: 109～118.
[LP1992] L.Scarlatos and T.Pavlidis. Hierarchical triangulation usingcartogra phic coherence.CVGIP:Graphical Models and Image Processi ng,54(2):147-161, March 1992.
[Lou1994] M.Lounsbery.Multiresolution Analysis for Surfaces of Arbitrary To pological Type. PhD thesis, Dept.of Computer Science and Engineering, Uni versity of Washington, 1994.
[LE1997] David Luebke and Carl Erikson. View-dependent simplification of ar bitrary polygonal environments.In Turner Whitted,editor,Proceedings of SIGG RAPH 97, Computer Graphics Proceedings,Annual Conference Series,pages199-208 Addison Wesley, August 1997. ISBN 0-89791-896-7. Held in Los Angeles,California
[Li1999] 李树军．海底数字深度模型(SDDM)的建立及其应用[D]．郑州：解放军信息工程大学测绘学院，1999．
[LC2001] 李杰，陈锦昌．3D 面控制在三维分形地形中的应用[J]．工程图学学报，2001，(1)：113-117．
[LCZ2003] 李旭涛，曹汉强，赵鸿燕．分形布朗运动模型及其在地形分析中的应用．华中科技大学学报(自然科学版)，2003，31(5)：50-52
[LWLL2005] 梁俊，王琪，刘坤良，卢全慧．基于随机中点位移法的三维地形模拟．计算机仿真，2005，22(1)：213-215，223
[LJLW2006] 李胜，冀俊峰，刘学慧，吴恩华．超大规模地形场景的高性能漫游[J]．软件学报March 2006 V01．17．535-545．
[MPH2004] 马照亭，潘懋，胡金星，等．一种基于数据分块的海量地形快速漫游方法[J]．北京大学学报(自然科学版)，2004，40(4)：6192625．
[Ma1998] 马小虎，1998，“虚拟现实中多细节层次模型的研究”，[浙江大学博士论文]，指导老师：石教英，潘志庚．
[PL2001] 彭仪普，刘文熙．分形地形模拟研究[J]．长沙铁道学院学报，2001，19(4)：95-98．
[QHT2000] 齐敏，郝重阳，佟明安．基于分形技术的多分辨率三维地景建模方 法研究[J]．中国图象图形学报，2000,5A(7)：568-572．
[RB1993] Jarek Rossignac and Paul Borrel. Multi-resolution 3d approximations for rendering complex scenes. In Bianca Falciendo an Toshiyasu L.Kunii, editors, Modeling in Computer Graphics, IFIP series on 455-465.Springer-Verlag,1993.
[Ros1998] Jarek Rossignac. Interactive exploration of distributed 3D datasets over the Internet, Computer Graphics International Congress (CGI 98 congress),Hanover, pp.324-355,June 24-26,1998.
[RHS1997] Stefan Rottger, Wolfgang Heidrich, Philipp Slusallek etal, Real-time generation of continuous levels of detail for height fields[R]. Technical Report 13/1997, Universit&t Erlangen Nurnberg.
[RFW2006] 栾元重，范玉红，王永等．塌陷区地形分形生成方法与应用[J]．地球信息科学，2006，8(4)：111-116．
[SJ2004] 孙铁红，焦永和．基于视点和分形理论的真实感地形实时生成方法[J]．系统仿真学报，2004，16(12)：2729-2731．
[TC2003] 谭建荣，陈洪亮．基于FBM约束模型的可控性分形生成方法．软件学报，2003，14(3)：651-659
[Ulr2002] Ulrich T.Rendering massive terrains using chunked level detail control[M].SIGGRAPH 2002,course35.
[WD2000] 王宏武，董士海．一个与视点相关的动态多分辨率地形模型[J]．计算机辅助设计与图形学学报，2000；12(8)：575-579
[Zhu1997] 朱长青．计算方法及其在测绘中的应用[M]．北京：测绘出版社，1997．
[ZSZ2002] 赵友兵，石教英，周骥．一种大规模地形的快速漫游算法[J]．计算机辅助设计与图形学学报，2002，14(7)：6242628．
[ZW2002] 张鑫，王琰．三维地形的分形构造及其虚拟漫游．沈阳工业学院学报，2002，21(4)：25-27
[Pup1996] E. Puppo.Variable resolution triangulations. Te chnical report, IM A-CNR, 1996
[ZZS2005] 卓亚芬，赵友兵，石教英．实时地形绘制算法综述．计算机仿真，2005，22(3)：4-7
[Sun2004] 孙博文．分形算法与程序设计-VC++实现[M]．北京：科学出版社，2004，287-308．
[YX2006] 殷宏，许继恒等．基于四叉树的大规模地形可视化及其实现[J]计算机应用研究，2006，23(5)：151-153．