计算机毕设外文翻译

1、County continuation records has examined and approved the draft, spirit, believe, comprehensive Yearbook of zhuanglang already prepared draft, entered the phase of evaluation. Civil air defense workPAGE County continuation records has examined and approved the draft, spirit, believe, comprehensive Y

2、earbook of zhuanglang already prepared draft, entered the phase of evaluation. Civil air defense workPAGE 6County continuation records has examined and approved the draft, spirit, believe, comprehensive Yearbook of zhuanglang already prepared draft, entered the phase of evaluation. Civil air defense

3、 workGenerating Random Fractal TerrainPart I: Generating Random Fractal TerrainIntroduction Ten years ago, I stumbled across the 1986 SIGGRAPH Proceedings and was awestruck by one paper in particular, entitled The Definition and Rendering of Terrain Maps by Gavin S. P. Miller 1 . It described a hand

4、ful of algorithms for generating fractal terrain, and the authors also introduce a new method which they considered to be an improvement.Initially I was impressed that these algorithms (even the algorithms considered flawed by the authors) could create such incredible landscape images! Then, upon re

5、ading the paper, I was floored by the simplicity of these algorithms.Ive been a fractal terrain addict ever since.The math behind the algorithm can get quite complex. However, completely understanding the math is not a prerequisite for grasping the algorithm. And thats good. Because if I had to expl

6、ain all the math to you before explaining the algorithm, wed never get to the algorithm. Besides, there is literally tons of material out there on the mathematical concepts involved in fractals. See the references at the end of this article for a good start.For the same reasons that I wont go into t

7、he math details, I cant include a broad overview of fractals and everything they can be used for. Instead, Im going describe the concepts behind fractal terrain generation, and give a focused and detailed description of my personal favorite algorithm: the diamond-square algorithm. Ill demonstrate ho

8、w to use this algorithm to statically tessellate an array of height data that can be used for geometric terrain data, terrain texture maps, and cloud texture maps.What can you do with a fractal terrain? I assume you already know that; thats why youre reading this. Random terrain maps are great for f

9、light simulators or making texture maps to use as a background (showing a distant mountain range, for example). The same algorithm that makes terrain can also be used to generate texture maps for partly cloudy skies.Before I go further, a disclaimer: I am not a game programmer. If you are reading th

10、is because you want algorithms for rendering terrain quickly, youve come to the wrong place. Ill only describe the process of generating the terrain model. How you render it is up to you.Self-Similarity The key concept behind any fractal is self-similarity. An object is said to be self-similar when

11、magnified subsets of the object look like (or identical to) the whole and to each other.2 Consider the human circulatory system. This is a fine example of self-similarity in nature. The same branching pattern is exhibited from the largest arteries and veins all the way down to the smallest capillari

12、es. If you didnt know you were using a microscope, you wouldnt be able to tell the difference between capillaries and arteries.Now consider a simple sphere. Is it self-similar? No. At significantly large magnification, it stops looking like a sphere altogether and starts looking like a flat plane. I

13、f you dont believe me, just take a look outside. Unless you happen to be in orbit while reading this, youll see no indication that the Earth is a sphere. A sphere is not self-similar. It is best described using traditional Euclidean geometry, rather than a fractal algorithm.Terrain falls into the se

14、lf-similar category. The jagged edge of a broken rock in the palm of your hand has the same irregularities as a ridgeline on a distant horizon. This allows us to use fractals to generate terrain which still looks like terrain, regardless of the scale in which it is displayed.A side note on self-simi

15、larity: In its strictest sense, it means self-identical, that is, exact miniature copies of itself are visible at increasingly small or large scales. I actually dont know of any self-identical fractals that exist in nature. But the Mandelbrot set is self-identical. I wont even go into describing the

16、 Mandelbrot set. Go dig up any of the references for more info.Midpoint Displacement in One Dimension The diamond-square algorithm, which I will describe later, uses a kind of midpoint-displacement algorithm in two dimensions. To help you get a grip on it, well look at it first in one dimension. One

17、-dimensional midpoint displacement is a great algorithm for drawing a ridgeline, as mountains might appear on a distant horizon. Heres how it works:Start with a single horizontal line segment.Repeat for a sufficiently large number of times Repeat over each line segment in the scene Find the midpoint

18、 of the line segment. Displace the midpoint in Y by a random amount. Reduce the range for random numbers. How much do you reduce the random number range? That depends on how rough you want your fractal. The more you reduce it each pass through the loop, the smoother the resulting ridgeline will be.

19、If you dont reduce the range very much, the resulting ridgeline will be very jagged. It turns out you can tie roughness to a constant; Ill explain how to do this later on.Lets look at an example. Here, we start with a line from -1.0 to 1.0 in X, with the Y value at each endpoint being zero. Initiall

20、y well set the random number range to be from -1.0 to 1.0 (arbitrary). So we generate a random number in that range, and displace the midpoint by that amount. After doing this, we have: Now the second time through the outer loop, we have two segments, each half the length of the original segment. Ou

21、r random number range is reduced by half, so it is now -0.5 to 0.5. We generate a random number in this range for each of the two midpoints. Heres the result:We shrink the range again; it is now -0.25 to 0.25. After displacing the four midpoints with random numbers in this range, we have:Two things

22、you should note about this.First, its recursive. Actually, it can be implemented quite naturally as an iterative routine. For this case, either recursive or iterative would do. It turns out that for the surface generation code, there are some advantages to using an iterative implementation over a re

23、cursive one. So for consistency, the accompanying sample code implements both the line and surface code as iterative.Second, its a very simple algorithm, yet it creates a very complex result. That is the beauty of fractal algorithms. A few simple instructions can create a very rich and detailed imag

24、e.Here I go off on a tangent: The realization that a small, simple set of instructions can create a complex image has lead to research in a new field known as fractal image compression. The idea is to store the simple, recursive instructions for creating the image rather than storing the image itsel

25、f. This works great for images which are truly fractal in nature, since the instructions take up much less space than the image itself. Chaos and Fractals, New Frontiers of Science 3 has a chapter and an appendix devoted to this topic and is a great read for any fractal nut in general.Back to realit

26、y.Without much effort, you can read the output of this function into a paint program and come up with something like this:This could be used as scenery outside a window, for example. The nice thing about it is that it wraps, so you can keep around one relatively small image and completely wrap a sce

27、ne with it. That is, if you dont mind seeing the same mountain in every direction.OK, before we go into 2D fractal surfaces, you need to know about the roughness constant. This is the value which will determine how much the random number range is reduced each time through the loop and, therefore, wi

28、ll determine the roughness of the resulting fractal. The sample code uses a floating-point number in the range 0.0 to 1.0 and calls it H. 2(-H) is therefore a number in the range 1.0 (for small H) to 0.5 (for large H). The random number range can be multiplied by this amount each time through the lo

29、op. With H set to 1.0, the random number range will be halved each time through the loop, resulting in a very smooth fractal. With H set to 0.0, the range will not be reduced at all, resulting in something quite jagged.Here are three ridgelines, each rendered with varying H valuesHeight MapsThe midp

30、oint displacement algorithm described above can be implemented using a one-dimensional array of height values which indicate the vertical location of each line segment vertex. This array is a one-dimensional height map. It maps its indices (X values) to height values (Y values).To simulate random te

31、rrain, we want to extrapolate this algorithm into 3D space, and to do so we need a two-dimensional array of height values which will map indices (X and Z values) into height values (Y values). Note that although our end goal here is to generate three-dimensional coordinates, the array only needs to

32、store the height (Y) values; the horizontal (X and Z) values can be generated on the fly as we parse through the array.By assigning a color to each height value, you could display a height map as an image. Here, high points in the terrain (large values) are represented by white, and low points (smal

33、l values) are represented by black:Rendering a height map this way is useful for generating cloud texture maps, which Ill discuss later. Such a representation could also be used to seed a height map.中文译文：随机分形地形的生成第一部分：生成随机分形地形介绍十年前，我参加 1986 年 SIGGRAPH 活动， Gavin S. P. Miller 那篇题为 Definition and Rende

34、ring of Terrain Maps 的论文让我充满敬畏。该文描述了少数生成分形地形的算法，作者还介绍了一个他们认为更先进的新方法。开始我被这些算法能够生成难以置信的风景图所震惊！（尽管这些算法被作者认为“漏洞百出”）后来，读过论文，这些算法之简单将我完全打败了。我从此成为一个分形地形迷。算法背后的数学可能相当复杂。然而，完全理解这些数学并不是掌握这些算法的必要条件。很好，否则我得在解释算法之前讲解所有的数，也许永远也讲不到算法。此外，关于分形数学的文字材料数以吨计，参见本文本的参考部分会有所帮助。同样的原因，我不会深入到数学细节，也不包括对分形的广泛总览及它们可被用来做的每样东西。相反，

35、我将描述分形地形生成背后的概念，并集中仔细讲解我个人最喜欢的 ”diamond-square” 算法。我将演示如何使用这个算法静态拼嵌高度数据数组，这些数据可用于几何地形数据、地形纹理数据及云纹理映射。分形有什么用呢？假定你已经知道，那正是你读本文的原因。随机地形图对飞行模拟或制作背景纹理图（如显示一带远山）十分有用。生成地形的算法也可用于生成部分云天的纹理图。在继续之前，申明一下：我不是游戏程序员。如果你为找到一个快速绘制地形的算法而读此文，那你来错了地方。我只描述生成地形模型的过程。着色绘制是你自己的事。自相似任何分形最关键的概念是自相似。当一个物体的一部分放大后看起来仍与整个物体一样，那

36、这个物体就是自相似。考虑一下人体的循环系统。这是自然界中自相似的好例子。从最大的动脉和静脉分支直到最小的微血管，整个过程都显现相同的分支模式。如果你不知道正在使用显微镜，将无法分辨微血管和大动脉。现在再考虑一个简单的球。它是自相似的吗？不！大幅度放大后，它看起来不再象一个球，而象块平板。如果你不相信，看看户外。除非恰好你在太空轨道上看本文，否则将完全没法看出地球是个球体。球体不是自相似的。它适用传统的欧几里德几何描述而不是分形。地形属于自相似范畴。手掌上的碎岩锯齿状边缘与远处地平线边的山脊有相同的不规则形状。这使我们可以用分形来生成地形，不管显示时怎么放大，它看起来仍然象地面。有关自相似请注意

37、：严格意义下，它意味着自分辨 (self-identical) ，即，自身精确的缩略拷贝在逐渐放大缩小时可见。我并不知道自然界存在任何自分辨分形。但 mandelbrot 集是自分辨的。我不会进一步讨论 Mandelbrot 集。到参考里找进一步的信息。一维中点变换后边要讲的 diamond-square 算法，在两维上使用一种中点变换算法。为帮助你了解个大概，我们先看一维情况。当山脉出现在远处地平线处时，一维中点变换是绘制山脊的好算法。看看它是怎么工作的：以一条水平地平线段开始重复足够多次对场景中的每条线段做找到线段的中点在 Y 方向上随机移动中点一段距离减小随机数取值范围将随机数值域减速小多少呢？那取决于你想要分形的陡峭程度。每次循环减少的越多，所得山脊线就越平滑。但如果减得太多，则会有明显的锯齿感。可以粗糙度存在一个常量里。后面会解释如何做。来