基于不规则三角网的分块地形网格生成算法

Triangulated irregular network based chunk gridding algorithm for terrain rendering

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

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.