原文： http://www.gameprogrammer.com/fractal.html
目 錄
說明：本頁所有圖像均經過優化以減小尺寸，所以與實際圖像會有細微差別。
- 第一部分：生成隨機分形地形
- 介紹
- 自相似
- 一維中點變換
- 高度圖
- Diamond-Square 算法
- 藍天白云
- 其它算法
- 第二部分 關于例子源碼
- 安裝
- 快速起步
- 使用程序
- 代碼結構
- 下載源碼[Visual C++工程，使用SGI實現的OpenGL]（單擊標題下載）
- 參考
終于找到這個SGI OpenGl地址了：
http://www.vckbase.com/tools/ocx/ocx_image/opengl2.exe
介紹
十年前，我參加 1986 年 SIGGRAPH 活動， Gavin S. P. Miller 那篇題為 Definition and Rendering of Terrain Maps 的論文讓我充滿敬畏。該文描述了少數生成分形地形的算法，作者還介紹了一個他們認為更先進的新方法。
開始我被這些算法能夠生成難以置信的風景圖所震驚！（盡管這些算法被作者認為“漏洞百出”）后來，讀過論文，這些算法之簡單將我完全打敗了。
我從此成為一個分形地形迷。
算法背后的數學可能相當復雜。然而，完全理解這些數學并不是掌握這些算法的必要條件。很好，否則我得在解釋算法之前講解所有的數，也許永遠也講不到算法。此外，關于分形數學的文字材料數以噸計，參見本文本的參考部分會有所幫助。
同樣的原因，我不會深入到數學細節，也不包括對分形的廣泛總覽及它們可被用來做的每樣東西。相反，我將描述分形地形生成背后的概念，并集中仔細講解我個人最喜歡的 ”diamond-square” 算法。我將演示如何使用這個算法靜態拼嵌高度數據數組，這些數據可用于幾何地形數據、地形紋理數據及云紋理映射。
分形有什么用呢？假定你已經知道，那正是你讀本文的原因。隨機地形圖對飛行模擬或制作背景紋理圖（如顯示一帶遠山）十分有用。生成地形的算法也可用于生成部分云天的紋理圖。
在繼續之前，申明一下：我不是游戲程序員。如果你為找到一個快速繪制地形的算法而讀此文，那你來錯了地方。我只描述生成地形模型的過程。著色繪制是你自己的事。
自相似
任何分形最關鍵的概念是自相似。當一個物體的一部分放大后看起來仍與整個物體一樣，那這個物體就是自相似。
考慮一下人體的循環系統。這是自然界中自相似的好例子。從最大的動脈和靜脈分支直到最小的微血管，整個過程都顯現相同的分支模式。如果你不知道正在使用顯微鏡，將無法分辨微血管和大動脈。
現在再考慮一個簡單的球。它是自相似的嗎？不！大幅度放大后，它看起來不再象一個球，而象塊平板。如果你不相信，看看戶外。除非恰好你在太空軌道上看本文，否則將完全沒法看出球是個球體。球體不是自相似的。它最用傳統的歐幾里德幾何描述而不是分開。
地形屬于自相似范疇。手掌上的碎巖鋸齒狀邊緣與遠處地平線邊的山脊有相同的不規則形狀。這使我們可以用分形來生成地形，不管顯示時怎么放大，它看起來仍然象地面。
關自相似請注意：嚴格意義下，它意味著自分辨 (self-identical) ，即，自身精確的縮略拷貝在逐漸放大縮小時可見。我并不知道自然界存在任何自分辨分形。但 mandelbrot 集是自分辨的。我不會進一步討論 Mandelbrot 集。到參考里找進一步的信息。
一維中點變換
后邊要講的 diamond-square 算法，在兩維上使用一種中點變換算法。為幫助你了解個大概，我們先看一維情況。
當山脈出現在遠處地平線處時，一維中點變換是繪制山脊的好算法。看看它是怎么工作的：
以一條水平地平線段開始
重復足夠多次{
對場景中的每條線段做{
找到線段的中點
在 Y 方向上隨機移動中點一段距離
減小隨機數取值范圍
}
}
將隨機數值域減速小多泊呢？那取決于你想要分形的陡峭程度。每次循環減少的越多，所得山脊線就越平滑。但如果減得太多，則會有明顯的鋸齒感。可以粗糙度存在一個常量里。后面會解釋如何做。
來看個例子。我們以一條 x 從 -1.0 到 1.0 ， y 均為 0 的線段開始。開始，我們將隨機值范圍設為 -1.0 到 1.0 （可任意取）。這樣我們在此范圍里生成一個數字，并將中點移動這么多。這之后，我們就得到了：
現在第二次經過外圈循環，我們有兩段，長度均原來的一半。我們的隨機值也減半，即 -0.5 到 0.5 。我們為兩個中點都生成一個這個范圍內的隨機點，結果為：
再次縮減范圍，現在是 -0.25 到 0.25 。再以該范圍內的數變換四個中點后，我們得到了：
有兩件事你可能已經注意到了。
首先，它是遞歸的。實際上，它可以用一個迭代過程相當自然的實現。對于這種情況，遞歸或迭代都成。對于表面生成代碼，使用迭代實現比遞歸會有一些好處。所以為保持一致，線和面相應的代碼都使用迭代實現。
其次，它是個非常簡單的算法，然而你能創建非常復雜的結果。這正是分形算法的美妙之處。一些簡單的指令可以建立一個具有豐富細節的圖像。
再跑一下題：少量簡單的指令集能夠生成復雜圖像的事實已經成為一個新的研究領域稱為分形圖像壓縮。其思想是保存建立圖像的遞歸指令而不是保存圖像本身。這對于自然界的分形圖像是極有用的，因為指令相對圖像占用的空間要少得多。 Choas （混沌）與 Fractals （分形） new Frontiers of Science 有一章及一個附錄涉及本主題，是一般學習分形的好讀物。
回到現實。
不用太費勁，你可以讀取本函數的輸出到一個繪制程序而得到類似如下的東西：
這可作為窗口景色使用。相關的好東西是它是約束的，所以你可以保留一個相當的小圖像并用它拼出整個場景。如果你不介意在每個方向都看見相同的山，那就這么干。
好的，在進入 2D 分形表面之前，你得了解粗糙度常量。這個值決定每次循環隨機數值域的減少量，也就是說，決定分形結果的粗糙程度。例子代碼使用一個 0.0 到 1.0 之間的浮點數并稱之為 H 。因此 2(-h) 是 1.0( 對于小 H) 到 0.5 （對大 H ）范圍內的數。隨機數范圍在每次循環時乘上這個值。如果 H 設為 1.0 ，則隨機數范圍將每次循環減半，從而得到一個非常平滑的分形。將 H 設為 0.0 ，則范圍根本不減小，結果有明顯的鋸齒感。
下邊是三個山脊，每個用不同的 H 的值繪制：
高度圖
上邊所說的中點變換算法可以用一個一維數組實現，數組成員是表明線段端點垂直位置的高度值。這數組是就是一個一維高度圖。它將索引（ x 值）映射為高度值（ y 值）。
為模擬隨機地形，我們想將該算法推廣到 3D 空間。為做到這一點，我們需要一個兩維高度值數組，它將索引 (x,z) 映射為高度 (y) 。數組只需保存高度值 (y) 。水平面值 (x 和 z) 可以在分析數組時即時生成。
通過對每個高度指定一個顏色，可以將一幅高度圖顯示為一幅圖像。如下，高點為白色，低處為黑色。
繪制高度圖的方法對于生成云彩紋理圖是很有用的，后邊還會討論。這種表達也可以用于播種一個高度圖。
現在我要講講如何拼嵌我們的二維高度圖數組。
Diamond-Square 算法
正如本文開頭提到過的，我先介紹 Gavin S.P.Miller 的論文中隨機地形生成的概念。具有諷刺意義的是， Miller 在論文中說 diamond-square 算法是有缺陷的，然后描述了一種完全不同的基于重量平均和控制點的算法。
Miller 對 diamond-square 算法的抱怨阻止他嘗試迫使該算法建立一座山，也就是，帶有一個山峰，人為增加網格中心點的高度。他讓數組中所有的點都隨機生成。如果 Miller 簡單的只隨機生成中心點，那么即使是他也會同意該算法是個經典的地形生成器。 Diamond-Square 算法可以通過給數組播種值來用一個山峰推出一坐山。比數組中心點更多的點得先播種以構造可接受的結果。他也抱怨一些固有皺折問題。但你得自己判斷。算法最初是由 Fourniew ， Fussell 和 Carpenter 提出的。
思想如下：你從一個很大的空 2D 數組開始。多大呢？為簡化起見，他應該是方的，維數應該是 2 的 n 次方加 1 （如 33X33,65X65,129X129 等）。將四個角設為相同高度。如果你察看所得到東西，它是一個正方形。
取個簡單的例子，用一個 5X5 的數組。（本文后面還要參考這圖，別忘記了）。圖中，圖 a 的四個角種上了初始高度值，表示為黑點。
這是遞歸細分過程的起點，該過程分兩步：
diamond 步：取四個點的正方形，在正方形中點生成一個隨機值，中點為兩對角線交點。中點值是平均四個角值再加上一個隨機量計算得到的。這樣就得到了一個棱錐。當網格上分布著多個正方形時有點象鉆石。
square 步：取每個四點形成的棱錐，在棱錐的中心生成一個隨機值。平均角值再加上與 diamond 步相同的隨機量，計算出每條邊中點值。這又給你一個正方形。
這樣，如果已經生成了一個種子正方形并經過單獨一次細分過程將得到四個方形。第二次經過該過程得到 16 個方形，第三次得到 64 個方形。增長得很快。方形數目等于 2( 2 + I ) ，其中 I 為遞歸經過細分過程的次數。
參考前五幅插圖，下圖示意了使用我們的 diamond-square 算法兩次經過數組時發生的情況。
對于第一遍經過 diamond 步時，我們依據四個角的值在數組中心生成一個值。我們平均四個角的值（如果種子值相等則完全沒必要），并加上一個 -1.0 到 1.0 之間的隨機值。在插圖 b 中，新值顯示成黑色，已經存在的點顯示為灰色。
對于 square 步，我們在相同的范圍內生成隨機值。這一步時有四個棱錐；他們在數組中心相交，這樣我們計算四個 diamond 中心。 diamonds 的角被平均以找出新值的基數。插圖 C 用黑色顯示新值，現存值為灰色。
以上是第一遍，如果用線將這 9 個點邊起來，就可以得到一個線框的表面，看起來就象：
現在進行第二遍。再次從 diamond 步開始。第二遍與第一遍有兩點不同。首先，我們現在有四人四邊形面不是一個，因此我們得計算四個方面的中心。其次，這是關鍵，生成隨機數的范圍已經被減小了。因為例子的緣故，讓我們認為正在使用一個 H=1.0 的值。這將把我們的隨機數取值范圍將從 (-1.0,1.0) 到 (-0.5,0.5) 。在插圖 D 中，我們這一步計算得到的四個正方形中心值顯示為黑色。
最后，我們進行第二遍的 square 步。有 12 個棱錐中心，我們現在需要計算 12 個新值，如圖 e 中黑色所示。
現在數組中全部 25 個元素都已經生成。我們可以得到如下的線框曲面。
如果分配更大的數組，我們可以進行更多遍，每一遍加入更多細節。例如， 5 遍之后表面看起來如下所示：
前面提到過，數組維數需要為 2 的整數次方加 1 。這是因為 2D 數組中的浮點數必須等于 (2n+1)2 。 8 次迭代將需要一個 257X257 的浮點數組，對于標準的 32 位 IEEE 浮點數來說超過 256K 內存。
好了，它就是這么大。用 char 取代 floats 會有所幫助。例子程序使用 floats ，但你要真的關注內存使用那么使用 char 。修改例子使用之使用 -128 到 128 的范圍是很容易的，但別忘了將你生成的值限定在 -128 到 128 范圍里，子序列通過時會生成該范圍以外的值，這會導致溢出。這在使用較小的 H 時尤其可能。
例子程序演示了處理尺寸的另外一種方法。用一個大數組依據 diamond-square 算法進行定位及拼嵌。然后從平行投影體頂視圖進行繪制。這個圖像被讀回來并用作已經拼嵌成較小范圍的第二個數組上的紋理圖。然而，例子程序并沒有這樣做，一但圖像從幀緩沖讀回，第一個數組就被釋放了。
這有個紋理圖的例子：
該圖經過人工著色，山峰為白色，山谷為綠色，兩者之間為灰色。盡管利用例子程序源碼試試自己的配色方案。
早先還到過用迭代實現這個例程比遞歸好。原因是：一個遞歸實現可能翻采用如下形式：
執行 diamond 步；
執行 square 步；
減小隨機數范圍
調用自己四次。
這是個很簡潔的實現，而且毫無疑問它能工作。但它要求用不充足的數據生成某些點。為什么呢？經過第一遍之后，你將再次調用以執行 square 步，但這時并沒有一個棱錐四個角的全部數據。
與之相反，我用個迭代實現，偽碼如下：
當 square 邊長度大于 0 時{
遍歷數組，對每個正方形表達執行 diamond 步
遍歷數組，對每個棱錐表達執行 diamond 步
減小隨機數范圍
}
這樣就消除了遞歸實現中出現的棱錐角丟失問題。但在生成數組邊界的點時還是會碰到這個問題。下圖中，數組中構成棱錐角的位置用亮灰色表示。它們應該被平均以找出新的基本值，即圖中黑色的點。
注意用黑色標記的兩個值。它們實際上是相同的值。每次你在 square 步計算一個邊界上的值時，記得同時把它保存在數組對面邊上。
這意味著前面插圖 e 中，我們實際上不必計算 12 個單獨的值，因為其中的四個在數組相對的兩條邊上重復。實際上只有 8 個值需要計算。
感興趣的讀都可以練習一下：取出源代碼并使用它在邊界的值不重復時也能工作。這對算法正常工作是沒有必要的，按我寫的方式去做就成。
如果你還沒運行過例子程序，現在或許是時候打開看看了。它從兩次迭代生成的曲面開始。曲面是用線框繪制的，只是簡單的將數組中的值用線段邊接起來。數組中的值被當作 Y 值，而 X 和 Z 坐標是在數組分析時即時生成的。通過將一個方形分成兩個三角形可以輕易的使用三角形繪制出這個曲面。三角形通常都是很好的圖元，因為它總是凸性的平面。
用 View Opeions 對話框調節 RAndom seed 值。這會導致生成不同的曲面。調高 iterations 值給曲面增加細節。代碼限制這個值到 10 ，這對于我 32M 內存的 PentiumPro 系統有點多，看起來是黑的（或許五年以后，人們會在新的處理器和更高分辨率的顯示器上運行這個程序，會對我為什么將它限制到 10 十分奇怪的……）。
第一個 H 值控制表面粗糙度，默認值為 0.7 。試著設得更高或更低看看結果如何。
是的這個算法偶爾會產生局部尖刺或皺折。但我偏愛尖或皺折不明顯依賴于觀察角度或飛過它的速度這種超自然的效果
藍天白云
現在我們知道如何生成表面。我們可以生成并著色大量的三角形，也可以生成一個高分辨率的紋理圖并將它應用到低分辯率的表面。不管怎樣，效果相當好。那么，我們怎么生成頭上的天空呢？它比你想象得要簡單。
diamond-square算法拼嵌完成的數組非常適于表示云天的紋理圖。與把數組看作一套高度圖上的y值相反，把它看成云的不透明度數據。最小數組值代表最藍。天空中最晰的部分，最大的值代表最白，天空中云最重的部分。分析數組并生成如下的紋理圖是相當瑣碎的:
這與前面的高度圖很象，但我已經限定了高、低值以建立清晰有云的天空。
也可以用例子程序生成一幅類似的圖像。設置 Select rendering type 下拉菜單為 2D mesh/clouds
。（默認時看起來有像素感，試試把 Cloud iterations 值設為 8 以上修正之）。試試給這 H 賦不同的值（就是前面剛說過的
Cloud iterations 值），以取得不同的云的效果。
如果回到本文開頭，第一幅圖結合了許多我在這做的討論。天空是用一個如上的紋理圖作的，沿一個八邊金字塔重復排放多次曲面幾何體用一個高分辯率紋理圖繪制。這個紋理圖是通過從一個平行頂視圖著色一個高度拼嵌有光照曲面而生成的。然后，這個圖被讀出用作紋理圖。
跟隨本文的例子程序被用于生成本文中出現的幾乎所有圖像。
其它算法
可能會想對曲面生成有比樣本代碼更多的控制。例如，可能想用自己的值給數組的前幾遍初始化種子值，這樣，山、谷……可以基本位于你設計的位置。然后用 diamon-square 算法填寫其它細節。
修改代碼，使之在賦值時略過已有值的數組成員是易于完成的。初始化數組為，例如， -10.0
，給前幾遍指定自己的值作為種子，再增強分形生成代碼只給當前值為 -10.0
的賦值。簡幾遍將不會生成任何值，因為你的種子值已經在那兒了。后續幾遍將在種子值在基礎上生成新值。
如何取得種子值呢？如果想要的形狀遵循某個已知的數學公式，如正弦曲線，就用這個函數生成值。否則，你得找出創造性的方法完成。我見過的一種算法是用灰度值繪制自己的高度圖。將灰度映射成高度值并存入數組。再用 diamond-square 算法增加更多細節。
除了 diamond-square 算法，還有許多拼嵌表面的方法。
用連續隨機增加， 2D 數組的一個隨機部分增高一個很少的量。反復多次，對所選中的數組區域加上一個很小的隨機值。這可以生成相當不錯的結果，但不是線性計算的。如果計算時間無所謂，那么建議試試這個算法。
一另一個相似的方法，制造一個穿過數組的“折斷”，并增加其中的一邊，就象地震出現一樣。再重復多次。這也不是一個線性算法，要多遍才能取得可以接受的結果。
參考參考文獻以了解更多其它途徑。
第二部分 關于例子源碼
安裝
這個例子源碼放在一個 zip 文件中，用你慣用的解壓縮軟件打開。如果你沒有 zip 工具，試試 www.pkware.com 。
源碼使用 OpenGL API 繪制。如果你的機器上沒有則請下載一個。注意本程序認 SGI 實現的 OpenGL ，注意文件名。
快速起步
啟動 Fractal 例子程序
打開 View Options 對話框
從 Select render type 下拉菜單選 2D mesh/renderd
將 Interations 值改為 4
將 Tile 值改為 3 。
使用程序
自己試試就知道了。
參 考
- 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