地形生成的细分随机移位方法

张润花，刘树群，赵付青

（1.甘肃建筑职业技术学院 基础课部，兰州 730050；2.兰州理工大学 计算机与通信学院，兰州 730050）

地形生成的细分随机移位方法

张润花1，2＊，刘树群2，赵付青2

（1.甘肃建筑职业技术学院 基础课部，兰州 730050；2.兰州理工大学 计算机与通信学院，兰州 730050）

将4点细分格式推广到三维表面，提出一种基于四边形栅格4点细分格式的随机移位地形生成方法.实验结果表明提出的算法可以方便生成具有真实感、基本可控性的山脉地形，较好地解决了传统随机中点移位方法对生成地形的形状无法预测和控制、裂缝和不真实的问题.

分形；地形；随机中点位移法；细分；边界

基于分形的自然景物模拟现已成为计算机图形学研究的前沿课题，山体、地形是自然界最复杂的景物之一.三维地形可视化［1-2］在虚拟战场环境、游戏、地形漫游、地理信息系统等众多领域有着广泛的应用［3-4］.更具真实感［5］、可控性的山脉地形模拟，逐渐得到人们的重视.

目前，国内外学者已经对三维地形真实感及细分方法做了大量的研究.最常见的随机中点位移算法［6-8］有三角形细分法和正方形细分法；其中又以正方形细分法最为灵活，并避免了随机中点位移方法中可能出现的折痕问题.由于传统随机中点移位方法存在对生成地形形状无法预测和控制、裂缝和不真实的问题.本文将四点细分格式推广到三维表面，提出了一种基于分形的地形生成细分的随机移位方法.

1 地形生成的基本方法

基于细分［9］的地形生成的基本过程是在初始高度网格的基础上递归地进行细分和改变顶点高度，直到满意的细分尺寸.初始网格的产生有多种方法，如给定或交互编辑产生或通过随机方法、IFS［10］、分形生长等.初始高度网格决定着地形的大尺度形态.依据表面构网方式的不同，可分为三角形网格和四边形网格.细分就是将高度网格加细，三角网格加细一般是在三角形每条边的中点附近增加一个顶点，这样可以将原三角形细为4个三角形（如图1）.

图1 三角形网格细分Fig.1 Triangle mesh subdivision

然后在各中点上增加一个高斯随机偏移量，其标准偏差由式s＝α·2－kH给出，其中k为迭代次数，α是一个比例因子，H是Hurst指数.为计算方便也可以使用f（k）＝αβk，其中α为初始范围缩放因子，β为递归下降因子，β∈（0，1），α的作用是调节缩放递归过程范围因子的比例.由于实际上只使用离散的值，因子可以用数值表设定每层递归的随机范围因子.

细分算法的最大优点是它能够从任意的初始网格出发产生光滑的曲面.目前的细分格式大体上分为两类：逼近型细分和插值型细分.逼近型细分技术是一种割顶点方法，直观效果稍差.而插值型细分技术保持初始网格顶点不变.相比较而言，插值型细分比逼近型细分更直观，计算量更小，交互性更好，更具优势.

2 细分方法

细分方法的实质是通过对初始控制点或者初始网格进行一系列的细化过程，细化的极限生成所需要的曲线或者曲面.细分是生成任意拓扑曲面强有力的方法.细分算法的最大优点是它能够从任意的初始网格出发产生光滑的曲面.

曲线的插值型四点格式按照下面的规则进行细分：

图2 曲线细分的四点格式Fig.2 Four－point method of curve subdivision

可以将其用于曲面细分.记

图3 曲面细分的四点格式Fig.3 Four－point method of surface subdivision

面上的细分点（面点）fij可以用水平和垂直方向的四点格式均值来表示：

水平和垂直方向的细分点可以使用边线四点公式与垂直方向面点四点格式的加权平均值，λ∈（0，1），

实际上，可以有多种细分方案，而在每种方案下可以有多种分点计算方法.

3 边界处理

在边界处，如果简单地使用线性插值，就会出现与随机中点移位方法类似的问题.因此，一般选用与内部网格细分次数相当的细分方法，本文选用局部三次插值.如果当前细分层的栅格为M×N，则每个边界栅格最外层边点的细分点要用到相邻的4个点，其组合系数为

其中的“·”表示边点的位置，如

其它三个角面点的组合系数是对上述矩阵旋转90°、180°和270°的结果.

左侧边界面点的组合系数为（其它边界面点的组合系数也要对下列矩阵进行旋转）

非边界面点的组合系数为

当然可以用三次格式进行细分来生成地形.

4 规范网格上的地形生成

规范栅格是指网格的尺寸为（2n＋1）×（2n＋1），如果当前栅格间隔为d＝2k（1＜k＜n），进一步细分的间距为2k－1，即x和y的值很容易获得，细分过程只针对z进行，则新面点fi，j为

5 实验

参数ω和λ的正常取值范围为ω∈（0，1／8），λ∈ ［0，1］.随机数使用rk＋1＝3.96 rk（1－rk）.范围因子f（k）＝αβk中的α＝0.25，β＝0.5，图4～图5使用相同的初始网格.参数相同情况下的随机中点移位方法（见图4）的山峰凸尖，坡面平坦与双线性曲面相对应，且会出现明显的棱脊.使用本文方法生成的地形（见图5）的山峰较厚重，坡面过度自然，没有棱脊现象发生.参数在正常范围取值时生成的地形都较自然，且ω和λ取值较大时山体陡峭，较小时平缓（见图5）.ω＝0时退化为随机中点移位方法.参数可以适当超出范围，生成的地形一般会保持大尺度样式，但小尺度会产生剧烈变化的表面，一般需要进行整体平滑处理.

6 结论与展望

图4 随机中点移位方法生成的地形Fig.4 Terrain generation based on the method of random mid－point displacement

图5 细分随机移位方法生成的地形（取ω＝0.0625，λ＝0.75）Fig.5 Terrain generation based on the method of random subdivision displacement（letω＝0.0625，λ＝0.75）

使用随机中点移位方法生成地形时，当随机范围参数较大时，地形陡峭；一般需进行不同尺度的平滑处理，并因此造成生成的地表的大体形态与初始栅格之间形成较大差异.当随机范围参数较小时，会出现山峰过于尖凸、山体平整和缺少厚重感的缺陷（见图4），也需要进行平滑处理.本文提出的细分随机移位方法有效解决了这些问题，且生成的地形自然，从图5可以看出，随机范围因子为0.75时仍能反应出最初栅格的形貌，当范围因子缩小时与初始栅格的关联更明显（实际应用中多采用0.5），当使用相同的随机条件进行交互控制时，初始栅格的变化与最终生成地形之间形成良好的预见关系.且因为省去了三次平滑处理而使总体计算复杂度有所下降.

需要进一步研究的内容包括：对地形的形态、表面粗糙度、不同尺度的地形特征及连续过渡等具有更好控制能力的细分方法，以及各种方法的结合，研究适合地形拼接的细分方法，超大地形的局部及层次控制，不同需求的特征控制，交互式编辑等.

［1］李耀辉，周丽莉.虚拟现实中三维仿真地形的生成［J］.微计算机信息，2006，22（10）：280－282.

［2］韩 飞.面向虚拟环境的三维地形生成方法［J］.计算机工程，2010，36（19）：261－262，265.

［3］张剑飞，王艳涛，程 杰.大规模三维地形的生成和漫游［J］.哈尔滨理工大学学报，2010，15（2）：28－30，34.

［4］林乔木，张永刚.三维动态地形视景仿真技术［J］.海洋技术，2010，29（2）：101－103.

［5］李庆忠，高秀荣.三维可控真实感地形生成方法研究［J］.系统仿真学报，2008，20（11）：2938－2941.

［6］林 岚.基于分形理论的高精度地形绘制算法研究［D］.武汉：华中科技大学，2006.

［7］Li J，Teng H Z.3Dvisualization technology and application of seabed terrain［J］.Ocean Surveying and Mapping，2004，24（4）：44－47.

［8］梁 俊，王 琪，刘坤良，等.基于随机中点位移法的三维地形模拟［J］.计算机仿真，2005，22（1）：213－215，223.

［9］王占东.细分曲面关键技术研究［D］.南京：南京航空航天大学，2003.

［10］刘树群，任到飞.迭代函数系统吸引子逼近的一个标记算法［J］.兰州理工大学学报，2010，36（2）：83－87.

Terrain generation based on the method of random subdivision displacement

ZHANG Runhua1，2，LIU Shuqun2，ZHAO Fuqing2
（1.Department of Fundamental Courses，Gansu Construction Vocational Technical College，Lanzhou 730050；2.School of Computer and Communication，Lanzhou University of Technology，Lanzhou 730050）

In this paper，4－point subdivision scheme is extended to 3Dsurface，and a method of random subdivision displacement terrain generation based on quadrilateral grid 4－point subdivision scheme is proposed.The experimental results indicate that the algorithm is capable of creating the terrain of reality and fundamental controllability，which solves the unpredictable，unmanageable，crannied and untrue problems in terrain generation based on traditional random mid－point displacement method（RMD）.

terrain；topography；random mid－point displacement method；subdivision；boundary

TP391

A

1000－1190（2012）05－0533－04

2012－01－03.

国家自然科学基金项目（61064011）.

＊E－mail：zhangrh2010＠qq.com.