分形与真实感地形生成研究
摘要
本文主要是关于分形与真实感地形生成算法的研究，用计算机生成的真实感地形一直是计算机图形学中一个富有挑战性且重要的课题，这种挑战性源于场景的多样性和绘制真实感场景的复杂性。它包括对山体，植被，天空以及云的模拟。研究的目的在于这一方向的研究在GIS、计算机动画中场景的合成、驾驶与飞行模拟、游戏和计算机艺术等中有广泛的应用前景。
本文是应用D-S算法来完成整个生成过程的。D-S算法是在“矩形”算法基础上完成的，先介绍一下“矩形”算法：由于这种算法都是在每个矩形中间取一个点，所以称这种算法为“矩形”算法，具体算法思想如下：
从下面这三幅图不难看出，第二幅比前一幅多做了一次细分，也就是分形层数增加了一层，随着分形层数的增加,地形的精确度会不断提高。然后不断对矩形的中点根据已存在数值的对角线上的两端点数值的平均值上下波动一定的随机数值，获得新的中点高度， 这从第三幅图和第二幅的区别可以明显看出来。
图1 矩形算法示意图
从上面几幅连续不断细分的地形网格图，不难看出只要不断细分就可以产生越发逼真的地形。
但是经过研究和实际试验，发现矩形算法有缺陷，因为每次都是一分为四，而且只使用了一个矩形形中的对角线上的两个点。本文应用的是D-S算法来生成地形网格克服了这一缺点，同时利用该算法生成高度图从而形成蓝天白云以及地形的纹理图。
D-S算法的思想如下：
从一个很大的空2D数组开始。维数应该是2的n次方加1（如 33X33、65X65、129X129等）。将四个角设为相同高度。如果你察看所得到东西，它是一个正方形。取个简单的例子，用一个5X5的数组。首先，四个角种上了初始高度值，表示为黑点。
这是递归细分过程的起点，该过程分两步：
diamond步
取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个正方形时有点象钻石。
square步
取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与diamond步相同的随机量，计算出每条边中点值。这又给出一个正方形。
这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该过程得到16个方形，第三次得到64个方形。增长得很快。方形数目等于2(I + 2)，其中I为递归经过细分过程的次数。
对于第一遍经过diamond步时，依据四个角的值在数组中心生成一个值。然后平均四个角的值（如果种子值相等则完全没必要），并加上一个-1.0到1.0之间的随机值。在插图b中，新值显示成黑色，已经存在的点显示为灰色。对于square步，在相同的范围内生成随机值。这一步时有四个棱锥；它们在数组中心相交，这样我们计算四个diamond中心。diamonds的角被平均以找出新值的基数。插图c用黑色显示新值，现存值为灰色。
现在进行第二遍。再次从diamond步开始。第二遍与第一遍有两点不同。首先，我们现在有四个四边形面不是一个，因此我们得计算四个方面的中心。其次，这是关键，生成随机数的范围已经被减小了。这将把我们的随机数取值范围将从(-1.0,1.0)到(-0.5,0.5)。在插图d中，我们这一步计算得到的四个正方形中心值显示为黑色。
最后，我们进行第二遍的square步。有12个棱锥中心，我们现在需要计算12个新值，如图3.11的e中黑色所示。现在数组中全部25个元素都已经生成。
图2 D-S算法注释图
就这样如果经过多次迭带可一生成一组高度值，将邻近的高度值连接起来就会形成地形网格。
现在我们知道如何利用D-S算法生成地形网格。那么，我们怎么生成头上的天空呢？
diamond-square算法拼嵌完成的数组非常适于表示云天的纹理图。与把数组看作一套高度图上的y值相反，把它看成云的不透明度数据。最小数组值代表最蓝。天空中最清晰的部分，最大的值代表最白，天空中云最重的部分。分析数组并生成如下的纹理图是相当琐碎的。
已经限定了高、低值以建立清晰有云的天空。
天空是用一个如上的纹理图做的，沿一个八边金字塔重复排放多次，曲面几何体用一个高分辩率纹理图绘制。这个纹理图是通过从一个平行顶视图着色一个高度拼嵌有光照曲面而生成的。然后，这个图被读出用作纹理图。地形的纹理图也是用类似的方法来完成的。
这样就可以生成我们想要的地形网格以及所需要的纹理。同时注意到应用了OpenGL来生成地形。OpenGL作为一种三位工具软件包，在交互式三维图形建模能力和编程方便具有方面具有无可比拟的优越性。OpenGL灵活方便地实现了高级图形技术。它的应用起到了锦上添花的作用。
在实现算法的同时，最后还应用该算法编制了一个测试程序，通过更改不同的参数可以对算法由进一步的了解。同时，为以后的应用也打下了良好的基础。
分析结果如下：
当生成地形网格时，当粗糙度介于0.6到0.8之间，叠代的次数介于3到5之间时，所生成的图形比较接近于自然场景中的山形；
当生成蓝天白云时，当迭代次数较大时（大于8），粗糙度大于等于0.5时，所生成的蓝天白云图形比较接近于自然场景中的形象；
当生成地形纹理时，当迭代次数为8（或更大?
This thesis is mainly about the study on fractal and realistic terrain synthesis. It is always a challege and important problem that make a realistic terrain with computer in computer graphics area. This challege comes out of the diversity of the secene and the complexity of creatinig realistic terrain. It is composed of the simulation to the mountain ,the sky and the clouds. The goal of the research is that the research in this area have extensive applications in GIS,synthesizing in the computer motivation,driving and flying simulation,computer games and computer arts.
This thesis uses the D-S theory complete the whole prossess of synthesis. D-S theory is completed under the foundation of the retangle theory, so first we’ll talk about the retangle theory: we call this theory the retangle theory because of the fact that this theory get a point in the middle of each retangle. The idea is as following:
This from the following falgs, we knows that the second flag has an additional iteration than the first one . With the increasing of the times of the iteration ,the accuracy will be inceased ,too. Then,change the numerical value of the middle point of the retangle accoding to the average value of the four corner points of the retangle ,thus we get a new hight value of the middle point. It is obvious in the difference between the second and the third flag.
flag 1. retangle theory skech map
From the series flags of the terrain gridding, it is easy to know that the terrain will be inceasingly realistic as long as we gei more details by incease the times of the iteration.
But the retangle theory has the limitation by reasearching and the experiments. Each time the retangle is divided into four parts and only use tow of the four points. This thesis use the D-S theory to overcome the shortcoming of the retangle theory . At the same time use D-S theory to create hight falg. So we get the blue sky and the texture falg of the terrain.
The idea of the D-S theory is as following: It is started by a blank and large 2D array.And the demitation fo it should be 2n +
1 .Texture(such as 33x33,65x65,129x129 etc.). Initial the hight value of the four points of the retangle with the same value.Just like what you have seen it is a square. Give a simple example ,we use an 5x5 array .First, initial the hight value of the four points of the retangle with the same value,express with black point.
This is the jumpping-off point of recursion process,this process has two steps:
diamond step
Get a four points square, generate a radom value in the middle point of the square, the middle point is the corss of the two pair of diagonals. The value of the middle point is equal to the average value of the four value of the corners plus a radomn value. Thus we get a pyramid. It looks like a diamond when there are lots of squars on the gridding.
square step
Get the pyramid that generate by each four points,generate a radomn value in the middle of the pyramid. This gives another square,also.
Like this,if we have generated a seed square and got four squares by a single iteration.We get 16 squares by using this process a second time,third time we get 64 squares. It increases very fast. The figure of the squares is equal to 2(I + 2) , I is the time of iteration.
For the first time in the diamond step,we get a value according as the four value of the corners. Then get the average of the value of the four corner points(if the value of the seed is the same it becomes unnecessary),and it should plus a radomn value which is between –1.0 to 1.0. In the flagb, new value dispalys in black,the old point displays in gray. To the square step, generate radomn value in the same range. In this step there are four pyramid;they are intersect in the middle of the array,so we calculate four diamond center. The corners of diamonds are averaged to find a new base.We use black to display new value ,the old value is displayed in gray in flagc.
Second tme now. Start by the diamond step .there are two differences between the first time and the secon
本文是应用D-S算法来完成整个生成过程的。D-S算法是在“矩形”算法基础上完成的，先介绍一下“矩形”算法：由于这种算法都是在每个矩形中间取一个点，所以称这种算法为“矩形”算法，具体算法思想如下：
从下面这三幅图不难看出，第二幅比前一幅多做了一次细分，也就是分形层数增加了一层，随着分形层数的增加,地形的精确度会不断提高。然后不断对矩形的中点根据已存在数值的对角线上的两端点数值的平均值上下波动一定的随机数值，获得新的中点高度， 这从第三幅图和第二幅的区别可以明显看出来。
图1 矩形算法示意图
从上面几幅连续不断细分的地形网格图，不难看出只要不断细分就可以产生越发逼真的地形。
但是经过研究和实际试验，发现矩形算法有缺陷，因为每次都是一分为四，而且只使用了一个矩形形中的对角线上的两个点。本文应用的是D-S算法来生成地形网格克服了这一缺点，同时利用该算法生成高度图从而形成蓝天白云以及地形的纹理图。
D-S算法的思想如下：
从一个很大的空2D数组开始。维数应该是2的n次方加1（如 33X33、65X65、129X129等）。将四个角设为相同高度。如果你察看所得到东西，它是一个正方形。取个简单的例子，用一个5X5的数组。首先，四个角种上了初始高度值，表示为黑点。
这是递归细分过程的起点，该过程分两步：
diamond步
取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个正方形时有点象钻石。
square步
取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与diamond步相同的随机量，计算出每条边中点值。这又给出一个正方形。
这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该过程得到16个方形，第三次得到64个方形。增长得很快。方形数目等于2(I + 2)，其中I为递归经过细分过程的次数。
对于第一遍经过diamond步时，依据四个角的值在数组中心生成一个值。然后平均四个角的值（如果种子值相等则完全没必要），并加上一个-1.0到1.0之间的随机值。在插图b中，新值显示成黑色，已经存在的点显示为灰色。对于square步，在相同的范围内生成随机值。这一步时有四个棱锥；它们在数组中心相交，这样我们计算四个diamond中心。diamonds的角被平均以找出新值的基数。插图c用黑色显示新值，现存值为灰色。
现在进行第二遍。再次从diamond步开始。第二遍与第一遍有两点不同。首先，我们现在有四个四边形面不是一个，因此我们得计算四个方面的中心。其次，这是关键，生成随机数的范围已经被减小了。这将把我们的随机数取值范围将从(-1.0,1.0)到(-0.5,0.5)。在插图d中，我们这一步计算得到的四个正方形中心值显示为黑色。
最后，我们进行第二遍的square步。有12个棱锥中心，我们现在需要计算12个新值，如图3.11的e中黑色所示。现在数组中全部25个元素都已经生成。
图2 D-S算法注释图
就这样如果经过多次迭带可一生成一组高度值，将邻近的高度值连接起来就会形成地形网格。
现在我们知道如何利用D-S算法生成地形网格。那么，我们怎么生成头上的天空呢？
diamond-square算法拼嵌完成的数组非常适于表示云天的纹理图。与把数组看作一套高度图上的y值相反，把它看成云的不透明度数据。最小数组值代表最蓝。天空中最清晰的部分，最大的值代表最白，天空中云最重的部分。分析数组并生成如下的纹理图是相当琐碎的。
已经限定了高、低值以建立清晰有云的天空。
天空是用一个如上的纹理图做的，沿一个八边金字塔重复排放多次，曲面几何体用一个高分辩率纹理图绘制。这个纹理图是通过从一个平行顶视图着色一个高度拼嵌有光照曲面而生成的。然后，这个图被读出用作纹理图。地形的纹理图也是用类似的方法来完成的。
这样就可以生成我们想要的地形网格以及所需要的纹理。同时注意到应用了OpenGL来生成地形。OpenGL作为一种三位工具软件包，在交互式三维图形建模能力和编程方便具有方面具有无可比拟的优越性。OpenGL灵活方便地实现了高级图形技术。它的应用起到了锦上添花的作用。
在实现算法的同时，最后还应用该算法编制了一个测试程序，通过更改不同的参数可以对算法由进一步的了解。同时，为以后的应用也打下了良好的基础。
分析结果如下：
当生成地形网格时，当粗糙度介于0.6到0.8之间，叠代的次数介于3到5之间时，所生成的图形比较接近于自然场景中的山形；
当生成蓝天白云时，当迭代次数较大时（大于8），粗糙度大于等于0.5时，所生成的蓝天白云图形比较接近于自然场景中的形象；
当生成地形纹理时，当迭代次数为8（或更大?
This thesis is mainly about the study on fractal and realistic terrain synthesis. It is always a challege and important problem that make a realistic terrain with computer in computer graphics area. This challege comes out of the diversity of the secene and the complexity of creatinig realistic terrain. It is composed of the simulation to the mountain ,the sky and the clouds. The goal of the research is that the research in this area have extensive applications in GIS,synthesizing in the computer motivation,driving and flying simulation,computer games and computer arts.
This thesis uses the D-S theory complete the whole prossess of synthesis. D-S theory is completed under the foundation of the retangle theory, so first we’ll talk about the retangle theory: we call this theory the retangle theory because of the fact that this theory get a point in the middle of each retangle. The idea is as following:
This from the following falgs, we knows that the second flag has an additional iteration than the first one . With the increasing of the times of the iteration ,the accuracy will be inceased ,too. Then,change the numerical value of the middle point of the retangle accoding to the average value of the four corner points of the retangle ,thus we get a new hight value of the middle point. It is obvious in the difference between the second and the third flag.
flag 1. retangle theory skech map
From the series flags of the terrain gridding, it is easy to know that the terrain will be inceasingly realistic as long as we gei more details by incease the times of the iteration.
But the retangle theory has the limitation by reasearching and the experiments. Each time the retangle is divided into four parts and only use tow of the four points. This thesis use the D-S theory to overcome the shortcoming of the retangle theory . At the same time use D-S theory to create hight falg. So we get the blue sky and the texture falg of the terrain.
The idea of the D-S theory is as following: It is started by a blank and large 2D array.And the demitation fo it should be 2n +
1 .Texture(such as 33x33,65x65,129x129 etc.). Initial the hight value of the four points of the retangle with the same value.Just like what you have seen it is a square. Give a simple example ,we use an 5x5 array .First, initial the hight value of the four points of the retangle with the same value,express with black point.
This is the jumpping-off point of recursion process,this process has two steps:
diamond step
Get a four points square, generate a radom value in the middle point of the square, the middle point is the corss of the two pair of diagonals. The value of the middle point is equal to the average value of the four value of the corners plus a radomn value. Thus we get a pyramid. It looks like a diamond when there are lots of squars on the gridding.
square step
Get the pyramid that generate by each four points,generate a radomn value in the middle of the pyramid. This gives another square,also.
Like this,if we have generated a seed square and got four squares by a single iteration.We get 16 squares by using this process a second time,third time we get 64 squares. It increases very fast. The figure of the squares is equal to 2(I + 2) , I is the time of iteration.
For the first time in the diamond step,we get a value according as the four value of the corners. Then get the average of the value of the four corner points(if the value of the seed is the same it becomes unnecessary),and it should plus a radomn value which is between –1.0 to 1.0. In the flagb, new value dispalys in black,the old point displays in gray. To the square step, generate radomn value in the same range. In this step there are four pyramid;they are intersect in the middle of the array,so we calculate four diamond center. The corners of diamonds are averaged to find a new base.We use black to display new value ,the old value is displayed in gray in flagc.
Second tme now. Start by the diamond step .there are two differences between the first time and the secon
引文
Miller, Gavin S. P., The Definition and Rendering of Terrain Maps. SIGGRAPH 1986 Conference Proceedings (Computer Graphics, Volume 20, Number 4, August 1986).
Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987 course notes #15.
Peitgen, Jurgens, and Saupe, Chaos and Fractals, New Frontiers of Science. Springer-Verlag, 1992.
Fournier, A., Fussell, D., Carpenter, L., Computer Rendering of Stochastic Models, Communications of the ACM, June 1982.
齐东旭，分形及其计算机生成,科学出版社，1994：68-75
彭群生，鲍虎军，金小刚，计算机真实感图象的算法基础。
齐敏，郝重阳，佟明安基于分形技术的多分辨率三维地景建模方法研究 中国图像图形学报2000 Vol.5 No.7 P.568-572。
张荣华，李凤霞，贺小杨，可扩展的多分辨率三维地形应用框架的研究 计算机应用 2003 Vol.23 No.3 P.82-84。
谭兵，徐青，周杨，大区域地形可视化技术的研究 中国图像图形学报 2003 Vol.8（A） No.5 P.578-584。
胡卓玮，杨国东 地形三维可视化的实现与应用 计算机应用 2003 Vol.23 No.10 P.70-73
费广正，乔林，Visual C++ 6.0高级编程技术——OpenGL篇，中国铁道出版社，2000
Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987 course notes #15.
Peitgen, Jurgens, and Saupe, Chaos and Fractals, New Frontiers of Science. Springer-Verlag, 1992.
Fournier, A., Fussell, D., Carpenter, L., Computer Rendering of Stochastic Models, Communications of the ACM, June 1982.
齐东旭，分形及其计算机生成,科学出版社，1994：68-75
彭群生，鲍虎军，金小刚，计算机真实感图象的算法基础。
齐敏，郝重阳，佟明安基于分形技术的多分辨率三维地景建模方法研究 中国图像图形学报2000 Vol.5 No.7 P.568-572。
张荣华，李凤霞，贺小杨，可扩展的多分辨率三维地形应用框架的研究 计算机应用 2003 Vol.23 No.3 P.82-84。
谭兵，徐青，周杨，大区域地形可视化技术的研究 中国图像图形学报 2003 Vol.8（A） No.5 P.578-584。
胡卓玮，杨国东 地形三维可视化的实现与应用 计算机应用 2003 Vol.23 No.10 P.70-73
费广正，乔林，Visual C++ 6.0高级编程技术——OpenGL篇，中国铁道出版社，2000