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