三维地形交互式编辑.doc

三维地形交互式编辑
1中点移位细分
1.1细分方法
海拔栅格数据是具有细节特征和统计自相似特性的分形曲面。细节特征通过随机来获得，而表面属性控制由细分方法和递归插值算法来把握。海拔栅格一般用于地表网格、云彩和岩石等纹理图像生成，凹凸纹理计算和几何纹理生成等多个用途。
随机表面的细分方法可以用于任意网格，但一般主要以三角网和四边形网为主，四边形网在很多应用中较为方便。

三角高度网格和四边形高度网格
1三角网的随机中点移位方法
对正常三角形（三条边的比值位于一定范围内）和狭长三角形，或者对于较长边或边上细分方法和三角形中心点分割算法。使用边遍历算法，先处理所有边的细分，之后按照三角形遍历并根据该三角形的细分点确定连线方式。

基于边的细分方法

基于内点的细分方法
只使用内点的细分会产生狭长三角形。

2四边形网的随机中点移位方法
对于狭长四边形，可以使用边分割方法将其分成两个四边形。也可以使用先用 square 数据生成 diamond 数据，之后再用 diamond 数据生成 square 数据。

Ø 建立在等距四边形网格上的随机中点移位海拔栅格。
Ø 建立在任意尺寸上的四边形网格的随机非中点移位海拔栅格。
非中点移位是使用目标网格间距控制细分的自适应递归控制算法。原则上可以按单步或两步进行任意中间位置的分割，并按照双线性插值求取平均高度和随机数范围。

3任意网格的随机中点移位方法
凹多边形和带有空洞的多边形依据顶点划分为凸多边形或三角形。
对凸多边形的几何中心点按照平均法向进行限定随机移位。接着在多边形边界上选择边创建分点，此时要相应地处理邻接的另一个多边形并使用该点为边上分点。或使用多边形的现有顶点，则不需要考虑相邻多边形。使用最多的是任意三角剖分或四边形剖分表面或实体，被划分的边必须双侧翼（无向前或向后翼）和长边，中点位于边的中点，平局高程是线的平均法向上含两翼各点的均值，并在该向量上进行随机位移处理。不规则石头可以用此方法建模。

4具备自拼接特性的规范四边形网的随机中点移位方法
规范四边形网是具有形如的四边形网格。
考虑到计算速度和非重复的表面规模，一般可选用256×256栅格。为了能较好的进行自拼贴，右侧和下侧边界的坐标分量为256整数倍的坐标分量值将回绕到0坐标分量值。
1.2种子网格的产生
1由跨距span构造M0×N0阵列初值，可选用行列序或层序安排随机数使用的顺序格局，并且一般要求span是和的公因子。随机种子网格各点的随机值大小和式样受随机数种子srand以及随机数范围lrand和hrand限定。由于计算机所使用的随机数都是伪随机数，因此可以使用不同的随机数模型，如：
随机数种子
模型1：
模型2：，此时使用的参数和随机值均为整数。
模型3：混沌映射模型。。。
假设随机数范围为（0,1），则每点的高程。
2由任意图像的小尺寸灰度图（可经采样、马赛克或变换处理）转换为高度栅格。该方法的好处是可以选择性使用图像的某种特征作为高度网格的基本式样。
3由重叠IFS或可加入某种随机性所产生的低分辨率分形集作为初始种子网格。
4由随机生长方法获取（在0平面上由一个或多个种子点，按指定的生长法则产生）。此时为任意网格（低分辨率或高分辨率），为了能进行自适应细分，需要建立光栅格式。
5由经颜色表转义的混沌图形的灰度图像转化为高程图给出。
6由随机几何图形与颜色叠加方法合成。
7用连续随机叠加的方法。
8用数学曲面法（包括样条曲面）。
种子网格可以与目标网格具有相同的尺寸。
可以对种子栅格数据进行编辑，也可以对目标栅格数据进行编辑。通过对种子栅格的编辑，可以把握地形数据的基本式样。
1.3细分模型
细分一般是在种子网格的基础上进行，也可以回退到高层（废弃部分数据）。
1随机中点移位方法
将随机数范围与粗糙度因子相结合：
，
其中k是细分层次。
对细分的结果按照将目标网格数据调整到～之间。
可选择平滑处理，使表面接近常规的丘陵地形式样。也可选择增加目标网格最低限制，可形成大面积平整区域的地形特征。
2表面插值或光滑细分方法
使用三线性、三立方插值，切角等方法在种子网格的基础上形成平滑表面。
1.4高度变换
1高程映射方法：
„区间（-128, 127）上的连续映射
上的自映射：
上的自映射
上的自映射
„三角函数
上的自映射：
上的自映射：
上的自映射：
2离散自映射（即上的一个置换，也可以映射到的一个子集上）
3颜色表转换（即将高程值作为颜色索引，并通过颜色表将对应的颜色转换为灰度值，即高度）
4其它方法（如油画处理、矩阵变换等）
2海拔栅格的编辑方法
移位面编辑（细化后的曲面）：按粗网格、均衡曲线、随机表格数据、细分算法和插值方法控制的曲面。移位面的作用是为表面构造细致的几何纹理。
基础面编辑（0～32767）：使用不同大小的指数面顶曲面按微量堆积和挖掘的方法进行编辑（初值为0）。基础面的作用是构造任意形状地形（如岩洞等）的粗网格面。
将移位面和基础面进行叠加而得到最终的栅格。
图形编辑工具：顶点编辑、点模式、点大小、均衡曲线、清空基础面、重新生成移位面（重建随机表格，可选择保留粗网格）、改变目标栅格尺寸（用插值保留编辑数据）、改变显示类型（山、云、石纹…）、推拉工具等。上下阀值限定、上下阀值翻转、中间定向翻转，多边形区域上的参数修改、光顺、锐化，提升和沉降多边形（开或闭的直线或曲线），含力学模型的堆积（如喷砂）和挖掘，风蚀和水洗方法，打磨石、侵蚀刷（依据尺寸和强度），对于纹理解释可修改伴随的颜色表对栅格的理解做进一步调整，多边形区域上的连续随机增加，两个地形数据的非对称个性化插值，通过非规则几何的运动扫略方式进行的增减操作等。
可对任意的空间三角和四边形混合网（可封闭为体）进行随机中点移位处理。网格的控制点为粗网格点，网格的平面看成基础面，随机表位于纹理坐标对应的表面点（要求具有自拼贴属性）的合成效果。随机表面总是依据顶点法向进行几何贴图，顶点法向也可以让平面真正地鼓起来。
为海拔栅格及空间表面预定义了多种细分算法。细分这种曲化算法可以用于海拔栅格的基础面编辑。多种随机移位细分方法来构造移位面，可用路径划分出不同的区域并各自使用独有的细化参数和模型，来构造多种表面的组合面。
粗网格点以及细分一次、二次等的点，对最终栅格的贡献依赖于均衡曲线。正常情况下，粗网格的随机值要重要得多，其变化要影响周边的四个粗网格区域，而最抹一层细分产生的网格点的变化只影响本身一个点。用不同颜色区分粗网格、一阶网格、二阶网格及其它层细分网格（用灰色），即网格的顶点编辑允许任意点（关于层和均衡曲线）的受限修改。
2.1整体编辑和局部编辑
基于256×256自拼接海拔栅格的整体编辑是按照坐标回绕方式同等地处理每一个顶点。
局部编辑一般有层次点修改和区块（2×2、4×4等等）修改，并且一般要按照作用强度模式进行改变（与整体编辑相比，方法相同，强度控制方式不同）：

局部编辑首先通过选择模式把鼠标光标位置的拾取矩形（2×2或5×5等）获取几何图形的坐标确定编辑区域（圆或矩形，用二维数组）：
typedef struct __collect {
int x:10; // x坐标
int z:10; // z坐标
int w:8; // 四叉树的半宽（半径）
int dir:4; // 四个方位占2位，每个方向的两片各占1位（01，10，11）
} COLLECT;
先获取光标所拾取的三角形，再根据相机位置与鼠标点的射线方程与三角形的交点在三角面上反算出最近的坐标点。
2.2编辑算法
1光顺：矩阵、卷积矩阵、切角、一次（一阶）和三次（三阶）。
2锐化（粗糙化）：在局部均值上确定理解的随机值，并将此随机按一定限定进行长幅修改。
3提升与沉降：主要针对局部均值进行修改，非均值部分只做少量缩小。
4上下翻转：通过指定平面对低于或高于该平面的部分进行对称到另一侧。
5图像编辑方法：如油画效果等。
6高程变换
3高程相关的纹理合成
地形使用的纹理可以是使用4片或多片按照高程进行纹理合成（称为高程纹理），亦可以将海拔栅格转换为高度图并用颜色表控制生成纹理。
可自拼接纹理是按照N×N回绕一线的方式构成的。在拼接时与海拔栅格的处理一样，先将图像扩展为(N+1)×(N+1)，多出的一线是读取的回绕数据。这样，拼接时就可以将边框线重叠，形成可缩放的无缝连接。
一般使用可自拼接细节图（通常是小尺寸，如64×64）拼接为大尺寸如1025×1025，再与由高程数据处理过的257×257纹理图像进行合成，产生1025×1025的大纹理（当然，可以将高程纹理固定在地表网格上，渲染时再与细节纹理进行合成）。
3.1按照高程数据合成大纹理

小纹理按高程数据合成大纹理

将高程分成四段，使用低位置编号段进行两两插值，最后一段不插值

区间重叠线性插值

将高程分成三段，使用低位置编号段进行两两插值

五等分区间的三次样条插值

四等分区间的区间中点三次插值，或边界重复的三次样条插值

非等分区间的区间线性插值样条（当然可以使用三次样条）最常用
3.2纹理细节
有多种方式。将自拼接几何块固定纹理是较方便的方法。
3.3与几何颜色混合
几何高程一般有固定的颜色渐变序列，与表面纹理混合形成自然的纹理。
4四叉树LOD算法
4.1底层网格的三角划分

关于中心区域的展开4×4网格权值分配矩阵是一个三次高程曲面围成的“体积”，与其后的两种表面三角化方法形成的“体积”较近者为所选三角划分。
＝＋++
4.2自适应层次划分方法
会打乱原始的四叉树层次，数据结构和算法较复杂。
4.3层次四叉树方法
1多块拼合
粗虚线为实际计算的N×N栅格数据，细实线为渲染的(N+1) ×(N+1)栅格数据，其中的右侧和下边均使用了回绕数据（即自拼贴的后续栅格的左侧和上边的数据，右下角=左上角像素）。

2具有自拼贴属性的几何或纹理与环的特征连接表面同构
用表示几何或纹理数据，将其转换为环面上的分割角，。

将绕y轴旋转角：

再加上平移，即为所求映射到环面的三维坐标。而该坐标点的纹理坐标为，顶点法向是上式中的=1时的三维向量。
3预处理
void setup_quadtree(int x, int z, int width)
{ int width2, m, n;

n = width * lod_level;
m = (x - location[0]) * (x - location[0]) + (z - location[2]) * (z - location[2]);
width2 = width >> 1;

if((width > 1) && m < n * n) // 此处添加平整度测试和相机裁剪
{ int i, j;
m = (((z - width2) & MASK2) << SHIFT2);
n = (((z + width2) & MASK2) << SHIFT2);
i = ((x - width2) & MASK2);
j = ((x + width2) & MASK2);

quadtree[(z << SHIFT2) + x] = NODE_POINT;
quadtree[m+i] = EDGE_POINT;
quadtree[m+j] = EDGE_POINT;
quadtree[n+i] = EDGE_POINT;
quadtree[n+j] = EDGE_POINT;

setup_quadtree(x - width2, z - width2, width2);
setup_quadtree(x + width2, z - width2, width2);
setup_quadtree(x - width2, z + width2, width2);
setup_quadtree(x + width2, z + width2, width2);
} else {
quadtree[(z << SHIFT2) + x] = EDGE_POINT;
}
}
5编辑与浏览流程
5.1参数
生成目标类型（0-地形、1-纹理）：DWORD product = 0;
表面贴图数据：Texture tex[] = {w, h, image}[];
地图子块编码和子块个数：
DWORD idImg, numImg; // 图像纹理
DWORD idGeo, numGeo; // 几何纹理
一般情况下，地表栅格控制大尺寸地表轮廓（山脉、丘陵或平地），几何纹理控制地表的细节特征，图像纹理进一步细化地表形成真实的地表形体。三种数据均可以用单个或多个同类（也许允许异类）数据进行拼接。
天空盒数据用内置的模型自动生成和扩展。天空盒也是地表栅格的生成目标之一。

地形参数设置对话框：INITPARAM
种子网格规模SEEDS（1,2,4,8,16,32,64,128,256）
高程范围因子heightScale（0,1）
表面粗糙度模型：float coarse[] = 0.7F;（使用数组具有更好的效果控制。使用时，先生成数值的乘积序列，如果是非中点可按最小加速度曲线计算该序列的插值）。
海平面高度：float elevation = 0.0;（用来确定天空盒的底面高度）。
高程最低限lowLimit = -128.0F;（-1,1）
随机数种子randStart = 0.5F; （0,1）
随机数参数： randscale, randShift
随机数模型：0-Logistic，1-素数线性映射，…

编辑控制参数设置对话框：EDITPARAM
操作域尺寸（1，32，64）
作用区模式：指数、余弦、样条等
作用方式：层次方法、邻接点
选项：使用随机（＋随机因子）
表明：表面细分、平滑矩阵、卷积矩阵
强度：一次滤波、三次滤波
高程映射：[-128～127]上的自映射（Logistic映射、三角函数等），置换，颜色表转换等。

浏览模式参数设置对话框：VIEWPARAM
地形数据显示模式：线框、表面纹理
选项：波浪，天空盒，雾
纹理：（纹理文件名，插值的位置）[ 4 ]
显示因子：y因子、(x, z )因子
细节层次（1,2,3,4,全）
视锥角（0, 90）

颜色表设置对话框：COLORTABLEPARAM
编辑连续彩色曲线（编辑RGB样条曲线）
修改256色颜色表（编辑16×16颜色块表）

5.2命令和工具
文件：
新建、打开、保存、另存为、合成（按比例与当前数据合并）、保存位图、退出
初始化种子（随机粗网格、读入图像、生长、点随机叠加）
编辑：
场景状态（编辑、浏览）
数据类型（地形、纹理、颜色表（在256*511上背景竖线条表示为颜色的RGB分形曲线））
操作形式（点的徒手画类型、连续折线类型、多边形区域类型）
整体编辑：比例、高程变换、最低限、提取种子
公共编辑：提升、沉降、光顺、折皱、上翻、下翻；
其它编辑：路、桥；布局（房、车、树、草…）；贴图（堆放图片的地表设计）
查看：
更换天空盒、更换基础纹理（一般用四层）、更换细节纹理
读入和保存颜色表、设置连续颜色表控制、修改单个颜色
经颜色表转换数据
显示（面、线框）
背景模式（背景色、天空盒）
细节层次（8,16,32,64）
浏览模式（步行、飞行）
帮助：
地形编辑操作、地形原理、关于地形编辑器。

工具栏：新建、打开、保存、保存图像；地形、纹理、颜色表；撤消、重做；提升、沉降、光顺、折皱、上翻、下翻、浏览；背景色、表面/线框、细节层次（8,16,32,64）、步行/飞行。
5.3渲染
一般，观察点与水平面形成固定夹角（15～45度），编辑时要根据观察点及高程线的观察效果调整综合高程（主要是粗网格点的）数值。
主要的浏览方式有两种：约束在表面上的步行方式和保持绝对海拔高度的飞行方式。改变倾角（即改变了高度）、调整观察高度、绕观察中心的y轴矢量旋转、保持高度的飞行控制（左右旋转和进退，无侧旋）
天空盒：用类似于地表拼接的方法生成天空盒纹理，并用移动天空盒的方式进行浏览处理。天空盒所使用的纹理可以用海拔栅格产生与编辑。
波浪：通过为每个网格顶点增加一个偏移产生波浪。
1将257×257的海拔栅格数据块拼合为4×4块
2将观察者置于（1,1）块的中央，并以该点的（x,z）及y = elevation为中心，按棱长3N+1构造天空盒。当观察者的（x,z）坐标发生改变时，天空盒中心也随之移动（但不跟随旋转）。
3由于高程数据和纹理数据均按照N×N尺寸进行的自拼接，即观察者位于不同的区块的对应位置应看到相同的场景地表。所以，观察者总是位于（1,1）块之内在越过边界时进行回绕。
4如果场景摆放了任何东西，则该东西依照N×N边界进行回绕分割，应用于所有的子块上。

5.4流程

地形浏览
生成海拔栅格：
y [N][N]
编辑 y 数组
地形数据：
几何、纹理、拓扑
管理
RGB分层纹理数据
Texture tex[4]
管理
RGBA颜色表数据
colortable[256]
模式 = 纹理
模式 = 地形
模式
管理
层次四叉树矩阵
quadtree[4N][4N]
图像浏览
RGB目标纹理数据
quadtree[N][N]
设置
初始化（种子）参数
风格控制参数

地形和纹理数据编辑：
比例、高程变换、
最低限、提取种子
整体编辑
海拔栅格数据：
y_old [N][N]
局
部
编
辑
提升、沉降、光顺、
折皱、上翻、下翻
海拔栅格数据：
y_new [N][N]

海拔栅格数据：y [N][N]
高度相关纹理：tex [N][N]
细节等级（1,2,4,8,16,32,64,128）
当前颜色
合成纹理数据
texImage(1025×1025)
读入纹理 /
纹理参数控制
LOD四叉树或纹理数据：
quadTree [N][N]
地形浏览（步行/飞行）
线
面
线/面
设置线材质
面材质
纹理
式样
模式
分层纹理数据
/ 颜色表数据
高程、颜色表、
分层纹理选项
图像浏览
（平移/缩放）