Please wait a minute...
浙江大学学报(工学版)
J4  2009, Vol. 43 Issue (10): 1939-1943    DOI: 10.3785/j.issn.1008-973X.2009.10.033
交通与运输、计算机科学     
基于不规则三角网的分块地形网格生成算法
黄争舸,陈建军,郑耀
（浙江大学 航空航天学院,工程与科学计算研究中心,浙江 杭州 310027）
Triangulated irregular network based chunk gridding algorithm for terrain rendering
HUANG Zheng-ge, CHEN Jian-jun, ZHENG Yao
(Center for Engineering and Scientific Computations, College of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China)
 全文: PDF(2036 KB)   HTML
摘要：

利用不规则三角网(TIN）拓扑灵活性,研究了一类基于TIN的分块地形网格生成算法.经典分块层次细节（LOD）程序采用基于半规则三角网（SRN）的网格生成算法,存在冗余顶点过多的缺陷.新算法基于Delaunay网格生成技术,可生成不包含任何冗余顶点的TIN.给出地形绘制算法总体框架以及基于SRN的分块地形网格生成算法,指出冗余节点的产生机理，讨论基于TIN的分块地形网格生成算法,重点研究基于Bowyer-Watson增量插点内核的Delaunay网格生成算法及其健壮性问题,同时给出三角形条带化的技术途径.实验结果表明,在典型的应用中,新算法能使简化后的分块地形网格规模降低3 成左右,这不仅减少了中间文件大小,也有利于提升后续的绘制效率.
Abstract:

A triangulated irregular network (TIN) based chunk gridding algorithm for terrain rendering was presented considering the topological flexibility of TINs. The classic chunked level-of-detail (LOD) codes are mainly based on gridding algorithms of semi-regular triangular network (SRN) and easily produces redundant vertices. The new algorithm can create TIN without redundant vertices based on the Delaunay mesh generation procedure. The mechanism of redundant vertex creation of classic algorithms was pointed out after the review on the framework of the terrain rendering algorithm and the SRN based chunk gridding algorithm. Then the TIN based chunk gridding algorithm was discussed, with emphasis on the algorithm and its robustness of Delaunay mesh generation based on the Bowyer-Watson incremental point insertion technique, and the stripping algorithm of TINs was also addressed. Results show that the algorithm can greatly decrease the grid scale about 30% in typical numerical experiments, thus decreases the interim file sizes and improves the efficiency of subsequent terrain rendering．Key words: gridding algorithm|terrain.
出版日期: 2009-11-29
:  TP 391  
基金资助:

国家自然科学基金资助项目(10872182); 浙江省自然科学基金资助项目(Y607429).
通讯作者: 陈建军, 男, 副教授.     E-mail: chenjj@zju.edu.cn
作者简介: 黄争舸(1969－), 女, 浙江杭州人, 副研究员, 从事计算机图形学、科学可视化和高性能计算的研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

黄争舸, 陈建军, 郑耀. 基于不规则三角网的分块地形网格生成算法[J]. J4, 2009, 43(10): 1939-1943.

HUANG Zheng-Ge, CHEN Jian-Jun, ZHENG Yao. Triangulated irregular network based chunk gridding algorithm for terrain rendering. J4, 2009, 43(10): 1939-1943.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2009.10.033    或    http://www.zjujournals.com/eng/CN/Y2009/V43/I10/1939

［1］ DUCHAINEAU M, WOINSKY M, SIGETI D E, et al. ROAMing terrain: real-time optimally adapting meshes ［C］ ∥ Proceedings of the 8th Conference on Visualization ’97. Los Alamitos, CA, USA: IEEE Computer Society,1997: 8188．
［2］ LINDSTROM P, PASCUCCI V. Terrain simplification simplified: a general framework for view-dependent out-of-core visualization ［J］. IEEE Transaction on Visualization and Computer Graphics, 2002, 8(3):239254．
［3］ HOPPE H. View-dependent refinement of progressive meshes ［C］ ∥ Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York, NY, USA: ACM, 1997: 189198．
［4］ DEWILLEM H B. Fast terrain rendering using geometrical mipmapping ［EB/OL］. ［2000-10-31］. http:∥www.flipcode.org/archives/article_geomipmaps.pdf．
［5］ LOSASSO F, HOPPE H. Geometry clipmaps: terrain rendering using nested regular grids ［C］ ∥ Proceedings of the 2004 SIGGRAPH Conference. New York, NY, USA: ACM, 2004: 769776．
［6］ ULRICH T. Rendering massive terrains using chunked level of detail control ［C］ ∥ Computer Graphics Proceedings Annual Conference Series. San Antonio, Texas, USA: ACM, 2002.
［7］ BOWYER A. Computing dirichlet tessellations ［J］. The Computer Journal, 1981, 24(2): 162166．
［8］ WATSON D. Computing the n-dimensional Delaunay tessellation with application to Vorono polytopes ［J］. The Computer Journal, 1981, 24(2): 167172．
［9］ ZHENG Y, LEWIS R W, GETHIN D T. Three-dimensional unstructured mesh generation: Part 1. fundamental aspects of triangulation and point creation ［J］. Computer Methods in Applied Mechanics and Engineering, 1996, 134(3/4): 249268．
［10］ 陈建军. 非结构化网格生成及其并行化的若干问题研究［D］. 杭州:浙江大学, 2006．
［11］ ULRICH T. Chunked LOD ［CP/OL］. ［2002-08-06］．http:∥prdownloads.sourceforge.net/tu-testbed/chunkdemo-2002-08-06.zip？download．
［12］ LINDSTROM P, KOLLER D, RIBARSKY W, et al. Real-time, continuous level of detail rendering of height fields ［C］ ∥ Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York, NY, USA: ACM, 1996: 109118.
［13］ EVANS F. Stripe V2.0 ［CP/OL］.\[1998-10-05\]. http:∥www.cs.sunysb.edu/～stripe/stripe.tar.gz．
［14］ BAKER T J. Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation ［J］. Engineering with Computers, 1989, 5(3-4): 161175．
［15］ GEORGE P L. Improvements on Delaunay-based three-dimensional automatic mesh generator ［J］. Finite Elements in Analysis and Design, 1997, 25(3-4): 297317．
［16］ Elevation file repository ［DB/OL］. \[2008-11-05\]http:∥vterrain.org/repo/elev/maui_2k.zip
［17］ Large geometric models archive［DB/OL］. \[2008-11-05\].http:∥www.cc.gatech.edu/projects/large_models/ps.html.
[1] 赵建军,王毅,杨利斌. 基于时间序列预测的威胁估计方法[J]. J4, 2014, 48(3): 398-403.
[2] 崔光茫, 赵巨峰, 冯华君, 徐之海, 李奇, 陈跃庭. 非均匀介质退化图像快速仿真模型的建立[J]. J4, 2014, 48(2): 303-311.
[3] 张天煜, 冯华君, 徐之海, 李奇, 陈跃庭. 基于强边缘宽度直方图的图像清晰度指标[J]. J4, 2014, 48(2): 312-320.
[4] 刘中, 陈伟海, 吴星明, 邹宇华, 王建华. 基于双目视觉的显著性区域检测[J]. J4, 2014, 48(2): 354-359.
[5] 王相兵,童水光,钟崴,张健. 基于可拓重用的液压挖掘机结构性能方案设计[J]. J4, 2013, 47(11): 1992-2002.
[6] 王进, 陆国栋, 张云龙. 基于数量化一类分析的IGA算法及应用[J]. J4, 2013, 47(10): 1697-1704.
[7] 刘羽, 王国瑾. 以已知曲线为渐进线的可展曲面束的设计[J]. J4, 2013, 47(7): 1246-1252.
[8] 胡根生,鲍文霞,梁栋,张为. 基于SVR和贝叶斯方法的全色与多光谱图像融合[J]. J4, 2013, 47(7): 1258-1266.
[9] 吴金亮, 黄海斌, 刘利刚. 保持纹理细节的无缝图像合成[J]. J4, 2013, 47(6): 951-956.
[10] 陈潇红,王维东. 基于时空联合滤波的高清视频降噪算法[J]. J4, 2013, 47(5): 853-859.
[11] 朱凡,李悦,蒋 凯,叶树明,郑筱祥. 基于偏最小二乘的大鼠初级运动皮层解码[J]. J4, 2013, 47(5): 901-905.
[12] 吴宁, 陈秋晓, 周玲, 万丽. 遥感影像矢量化图形的多层次优化方法[J]. J4, 2013, 47(4): 581-587.
[13] 王翔,丁勇. 基于Gabor滤波器的全参考图像质量评价方法[J]. J4, 2013, 47(3): 422-430.
[14] 计瑜,沈继忠,施锦河. 一种基于盲源分离的眼电伪迹自动去除方法[J]. J4, 2013, 47(3): 415-421.
[15] 童水光, 王相兵, 钟崴, 张健. 基于BP-HGA的起重机刚性支腿动态优化设计[J]. J4, 2013, 47(1): 122-130.