基于分形的真实感地形生成

摘 要: 该文给出了基于中点移位法快速生成地形模型高程场的方法。采用此法生成的地形可以用在仿真系统和游戏中。该文首先分析了真实感地形生成的相关研究工作,然后给出了完整的基于中点移位生成地形模型的方法,最后给出了实验数据。实验数据证明该文的方法是可行的。

关键词: 中点移位; 地形粗糙度; 混沌地形

中图分类号: TP391.41文献标识码: A文章编号: 1009-8631(2010)03-0210-02

地形漫游有着广泛应用,如游戏、军事演习模拟、地理信息系统(GIS)等。地形绘制常使用数字高程模型DEM (Digital Elevation Model)[1]格式的地形高度数据,即按矩形网格采样的地形高度数值。地形可视化算法已经有很多,最为典型算法有Lindstrom[2]的基于Quadtree算法、Duchaineauy……的ROAM (Real-Time Optimally Adapting Meshing)算法、Luebke的HDS (Hierarchical Dynamic Simplification)方法。但这些算法都是基于已经有的DEM数据,而这些DEM数据的购买需要花费很多经费。本文研究一种基于分形的真实感地形的快速生成方法,快速生成DEM高程图,可以用在地形漫游系统、战场仿真系统等系统中。

1. 相关研究工作

Blinn[3]曾提出应用法向扰动法来模拟表面细微的凹凸不平的景物,Fournier等[4]人首次利用分形布朗运动fBm(fractional Brownian motion)来生成地域和各种星球表面的图形。2001年,彭仪普、刘文熙采用分形布朗运动中的随机中点位移法实现了地形的模拟[5]。中科院的李红达等[6]人利用分形插值曲面进行了地形地貌的模拟和研究,但这些算法在表面细节方面模拟的地形表现力不够强,带有较浓的人工痕迹,从而限制了其在实时仿真场景中的应用。

2. 基于分形的地形高程场的生成

自然景物的建模与绘制是计算机图形学中的一个研究热点和难点,而分形方法是自然景物的建模与绘制中常用的方法。地形自身的特殊性在于:一是空间范围大、视野广。二是地形表面细节的复杂性和随机性。可以用在地形模型生成的分形方法有基于中点移位(Midpoint Displacement)的方法、基于断层构造(Fault Formation)的方法,本文选择基于中点移位的方法生成地形模型。

2.1 一维中点移位法

在一维空间中,中点移位方法是用递归的方法进行的。如图1所示,从一条线段AB开始,选择适当的dHeight值,取线段AB的中点C,并用一个在-dHeight/2和dHeight/2之间的随机值置换C的值;减小dHeight的值,并对线段AC和CB进行递归处理,计算AC的中点D并赋随机值,同样计算CB中点E并赋随机值;重复上述步骤直到生成了足够多的细节为止。

如图2所示,递归10次的结果,可以清晰看出一个山丘的2维切面轮廓图。迭代次数可以控制,可以增加,可以删除,直到适合实际的需求为止。

2.2 二维中点移位法

二维中点移位法须计算正方形的中点和构成正方形4条边的中点。

如图3所示,从一个正方形ABCD开始,选择4个顶点的高程值作为初始值。根据公式1,计算A、B、C、D的高程值的平均值,并加上一个-dHeight/2和-dHeight/2之间的随机值作为中点E的高程值;根据公式2计算出F的高程值,同样方法计算出G、H、I的高程值;根据公式3计算出J的高程值,同样的方法计算出O、P、Q的高程值;重复上述步骤直到已经得到了充足的细节层次。

在公式1、2、3中R是随机函数,dH是dHeight。尤其注意的是,在计算F点的高程值时,F点可以看作是正方形AEBE’的中心点,E’是E点关于F的对称点,所以用公式2计算类似F点的高程值。

在每次迭代时,dHeight的值都要乘2-r,r是地形的粗糙度常数(Roughness Constant)。r=1时,每次迭代时,都要除以2,这就是2.1节中一维中点移位法所用的比率;r=1时,所产生的地形十分自相似。r>1时,dHeight减小的快,较早进行的迭代对地形影响较大;r>1时,可以产生平滑的具有突出部分的地形(如山峰或者山谷)。r

中点移位法最主要的特点是合成速度快,时间复杂度仅是n的线性次项,实现非常容易,代码简单,可迭代进行,并且可以合成任意分辨率的地形,甚至可以细分到子象素,降低图像显示的混淆度。

3. 实验数据及其分析

图4a是粗糙度r=0.4时生成的地形高程图,图4b是相应的纹理图,图4c明显的属于混沌地形。

通过控制地形粗糙度,中点移位生成的各种类型的地形,这些地形可以通过拼接构建虚拟星球。如图5所示,利用本文的方法构建的简单星球截图,图5a、图5b是不同视角的截图。

4. 结束语

本文给出了基于中点移位法和过程纹理生成地形的算法,其突出优点是算法效率高,图形渲染速度快,输出的场景真实感强。其中基于地形高程场的过程纹理生成方法不仅仅可以生成与地形高程场相匹配的纹理,而且还可以应用在动态地形[纹理的生成。

进一步研究基于其他方法生成地形,包括基于断层构造(Fault Formation)的方法,基于粒子沉积(Particle Deposition)的方法。

参考文献:

[1] Giger C.Digital Elevation Models and Digital Terrain Models[Z]. Technical Presentation,2002,GeoInformation Technologies Group,Swiss Federal Institute of Technology,Zurich,Switzerland.

[2] P Lindstrom,D Koller,W Ribarsky,L F Hodges,N Faust,G A Turner. Real-Time Continuous Level of Detail Rendering of Height Fields [A]. In Proceedings of SIGGRAPH'96 [C].1996:109-118.

[3] Blinn,J.F.,Simulation of Wrinkle puter Graphics[J].Vol.12,No.3,1978.

[4] Fournier A,Fussell D,Carpenter L C,Computer Rendering of Stochastic Models[J].Comm.ACM,Vol.25,No.6,1982.

[5] 骆岩林,汪国昭. 地形模拟的细分细化方法[J].计算机学报,1999.22(7):746-751.

[6] 李红达,叶正麟,王小平.分形插值曲面[J].计算机辅助设计与图形学报,2002.14(4):316-319.