[翻譯]以程序性演算法產生3D城市

由本論文產生的3D虛擬城市。大約含有26000幢建築物!

譯者序
這篇文章我斷斷續續翻了將近兩個月才完成 很高興終於發文了. 尖端科技總是由學術界做為先鋒 CG動畫也不例外. ㄧ套軟體的發表先由科學家提出構想 發表論文 再由軟體開發商基於學術論文將演算法轉變成軟體與ㄧ般人可讀的使用介面. 論文永遠走在時代的前端 所以接下來我將萃選出最近一些不錯的論文 將這些原文翻譯成漢字 希望讓台灣的軟體開發上能夠由這些論文中發掘一些題材與靈感. 最近的規劃就是先翻譯關於城市產生器(city generator)的論文集. 城市產生顧名思義就是讓軟體隨機的產生大量建築物與道路 利用軟體產生城市的3D模型. 這樣的軟體再商業上還沒出現但是已經有一些類似的服務在做了(沒有賣軟體但是有客製服務, 例如CityEngine) 相信不久的將來城市產生器會越來越成熟變成一個新興軟體發展重點 就像幾年前渲染外掛蓬勃發展那樣.

這篇論文是由兩位瑞士研究者Yoav I H Parish, Pascal Müller所發明的. Peter Jackson的金剛電影裡面的紐約城市就是基於這篇論文(請參考此連結) 有此可見這篇論文的其重要性. 本文內容含有大量的程式語言 我沒有程式語言背景 所以在翻譯的時候只能翻其概念 如果內容過於艱深則選擇不翻譯以免誤導讀者. 其餘的部份則是以意譯為原則 不採用直譯 盡可能讓文句通順 如果有任何不妥之處歡迎來信指正 謝謝大家.

論文原始連結pdf檔

標題:程序性產生城市的3D模型與材質(Procedural Modeling of Cities)

摘要:
用電腦軟體建立一個城市必須要面對幾個問題。每一個城市地區的交通運輸網絡，人口及環境等影響，往往是疊加的。建築物外表遵循歷史，美學及建築法規。創造一個虛擬城市，必須產生路線，設計和大量的建築物。我們提出一個系統使用程序性的做法，基於L-system，建立城市模型。從各種影像地圖作為輸入，如土地與水的界線和人口密度，我們的系統會產生一個系統的公路和街道，劃分土地變為地段，並創造適當的幾何建築物。為創造一個城市的街道地圖， L-system，考量整體目標和區域特色，並降低複雜的生產規則。以L-system產生的幾何和紋理，以程序方法構成的建築物。


圖1 ：城市產生器的工作流程圖。黑色框框代表每個獨立工具產生的資料與結果。

圖2 ：左欄：具有20英里直徑的虛擬城市其水，海拔和人口密度的貼圖。右欄：從這些輸入的資料產生的可能道路圖。

圖3 ：套用到繼任器的函數。

圖4 ：左：每條公路的末端發射出放射狀的線路, 這些線路會自動找尋最高人口密度的區域（暗區） 。右：連接人口中心的可能公路網。

圖5 ：常見的道路類型。

表1 ：在cityengine系統中使用的道路類型, 簡短描述與舉例。

圖6 ：左：高度圖與由舊金山規則所產生的公路圖。右：街道地圖投射到地形上面。

圖7 ：左：兩種不同的街道佈局控制圖(紐約和巴黎演算規則)。右: 把兩個地圖疊產生的街道圖。

圖8 ：區域限制的例子。上排：由整體目標所產生的參數。下排：經過修正的參數。

圖9 ：街道產生系統套用到曼哈頓。上排：經過28個和142個演算步驟後產生的街道。中排：最終演算出來的路線圖。下排：曼哈頓真正的街道是這樣的。

圖10 ：左：最終道路圖。中：由道路交叉口所產生的街區。右：生成的街區。那些太小的街區或是道路無法到達的街區事後會被移除掉。

圖11 ：5個建築物產生的連續步驟。l系統的基礎(根)是一個box，如此一來便於lod的產生。

圖12 ：左：用一個函數將兩個分隔組定義出一個層（這裏使用的函數是AND） 。

圖13 ：左：用隨機影像地圖產生的一個巢狀圖層。中：圖層的疊合。右：紅色圖層影響綠色圖層中網格的尺寸。

圖14 。左中：使不同的參數渲染出來的磚牆面。右：窗口和門戶周圍不同大小和顏色的磚頭。

圖15 。左：原始的圖片與網格疊合在一起，如藍色框線及紅色網格細胞分別構成巢狀隨機圖層。中右：不同尺寸但相同風格的建築外牆。

圖16 。渲染出來的虛擬城市。

圖17 。運用圖二中的數據產生的虛擬城市 。大約含有26000幢建築物。

1. 引言
建模與視覺化3D大型城市，是計算機圖形學中巨大挑戰。城市系統具有高功能性和視覺的複雜性。它們受到歷史，文化，經濟和社會變革隨著時間的推移，在每一個環節中都會對城市產生影響。觀看真實城市的照片，如紐約，顯示出城市的複雜性，街道模式，建築物，形式和紋理。當今電腦的運算力與記憶體的容量，使得建模與可視化技術的大面積城市已成為可行。應用面呢？從創作、從研究和教育用途，如城市規劃，建立虛擬環境來模擬。特別是娛樂市場，例如電影和遊戲產業，對於快速建立各種複雜環境有很高的需求。 在計算機圖形學中，制作大型、複雜可視化建模的系統，有著悠久的傳統。大部分是用在處理自然現象。製作這些大場景，關鍵在簡單的元素組合出複雜的大系統。 部分這些系統包括：侵蝕模擬， 粒子為基礎的森林, 雲建模。語法為基礎的產生模式（尤其是l系統），在過去的應用主要是創造植物。 l -系統已演變成非常複雜和強大的工具，並已被廣泛地使用在建模的植物生態系統當中。

1.1在城市建模當中過去的研究
其中一個方法模擬城市，是利用航空圖像提取建築物和街道來建構城市模型。有很多不同的研究項目，依靠這種方法。這種方法可以用於重建城市，但不是在沒有影的輸入數據之下，創造新的虛擬城市，如果沒有攝。 現有關於可視化城市的研究工作多側重於技術數據管理，快速，實時的可視化和快取使用優化。 ，亞歷山大等人。描述一個模式語言，其中包括超過250個相關模式，為順利建設的城市，建築物和房屋。他們從很籠統的模式一樣， "環城公路" ，以非常侷限性的功能為應用，例如 "在裂縫之間的石頭鋪路" 。由於這些模式都是非公式化的，他們不能自動產生的方式創造3d城市。 空間句法已經研製成功 。空間句法可以被看作為一套分析複雜的大型空間的理論。它試圖解釋人類行為和活動，從空間的角度來看，並已用在分析城市行人潮或尋路分析。這種方法是必需依靠現有城市地圖。在建築設計互動的研究領域中，有種研究方法：形狀語法。這種方法使用的生產規則，但不是處理strings，形狀文法直接定義形狀。形狀文法已被用來產生兩維模式，並應用在互動設計上。

1.2我們的方法
我們目前的cityengine系統能夠模擬出一個完整的城市，只用了一個比較小統計和地理數據輸入，而且我們的方法還有高度的可控性。據我們所知，過去並沒有人發明類似這樣的系統 。 [ 5 ]但是有個方法，是經由修該現有的幾何來創造城市。然而，這種方法要用手動的方式產生3D model。其他系統[ 4 ， 32 ]依靠航空照片，輸入建築物和公路。我們cityengine創造了城市環境，從無到有，分層次的，易於理解的規則，可以依照用戶需求改變內容。 [ 33 ] ， wegener分裂市區模型到子系統。他說，在產生網絡子系統時，土地使用和住房是最耗電腦運算的步驟。因此，在我們cityengine中 ，創造城市只產生交通網和建築物。土地利用數據，是由用戶提供的圖像地圖而來。當我們學習大城市的航空照片時，很顯然地街道遵循某種模式。道路運輸中會影響城鎮人口分佈。 l型系統已被使用在類似的應用[ 20 ]，且L-system具有資料庫擴張的優勢 [ 30 ] ，這意味著，能產生有說服力的大型道路。我們採用了L-system，創建大中城市，收集了[ 11 ]於四個大的城市：紐約，巴黎，東京和倫敦。 雖然我們已經簡化了基本模型，但主要設計目標是讓該系統很容易擴展。我們希望能夠增加新的子系統，如不同的運輸網絡（在地下，火車）和另類的土地用途。要做到這一點，我們延伸了l系統具有更先進的機制，這使得加入新的規則變的很簡單。

1.3概述
在第2章裡，我們描述cityengine系統的概念和制作流程和使用方法。在第3章介紹了延伸l -系統，使用戶實現整體目標和區域性的限制條件。我們證明了使用這一擴展概念來建立路線圖。第四章作一簡要概述了街區分割和建築物的產生，並解釋我們提出的機制，以簡化變形的外牆。最後，我們展示用cityengine製作出來的效果，並在第5章討論。

2系統架構
cityengine系統由幾個不同的工具，組成工作流程，如圖1所示。在第一個步驟，輸入數據道路產生系統，利用一種擴展l系統。先形成地區之間的道路，然後將建築物放置到其間的空間中。在第三個步驟中，運用另一種l系統，建築物以固體的形狀進行布爾操作，產生3D模型。最後，解析器解釋所有結果。可視化軟件應該能夠處理的多邊形幾何和紋理圖。在這種情況下，為幾乎任何三維渲染都可以。此外，多數掃描線渲染器支持程序紋理，所以產生建築物地墻面可以被納入到生產流程當中。
大部分是藉由輸入二維影像地圖，來建立一個虛擬城市。這些圖片可以很容易產生，可以經由手繪或是掃描進來的地理圖。數據可分為兩大類：
-地理地圖
-海拔地圖
-土地/水/植被圖
-人口密度區域地圖（住宅，商業或混合區）
-街道模式（控制行為的街道）
-高度地圖（最大建物高度）

控制的各種參數的特殊工具，是可以經由用戶以交互方式或提供參數文件來改變，由。舉例來說，統計等測量數據，以此近似面積大小的塊或平均人數交叉口每平方哩，可以用來改變所造成的街道地圖。在圖2頂部的圖片的例子地理圖形圖像顯示，土地與水的界限，另ㄧ張圖又描繪出該地區的人口分佈。
兩種不同l -系統引用為建立完整的城市，一個是用在產生街道，另ㄧ個是用在產生建築物。人口密度是是受到城市街道所影響的。透過街道，人們在各種交通工具中被運送[ 12 ] 。當創建街道時，我們考慮這個情況用類似的方法，以公開l系統模型[ 20 ]產生。該l系統的機制作了修改，以這樣一種方式，各種不同的道路格局，可以使用同一生產規則來產生。
但並非所有的道路，會改變人口密度，例如：連接兩個城市的道路。因此，我們選擇了考慮兩種類型的道路：公路和街道。他們不同於在自己的宗旨和行為：公路連接地區高度集中的人口在全球範圍內，通過掃描，人口密度在地圖上的輸入為流量。街道涵蓋地區之間的公路，根據當地人口密度，讓所有街道交通進入就近的公路。兩者合計，這兩個類型道路，形成虛擬城市的交通網。
ㄧ但路線圖生成了，土地劃分成較小的地區，四周的街道。這些地區可以以幾何級數細分，以界定個別建築物的分割土地。建築物本身所產生的一個隨機，參數l系統。在我們的制度下，建築物是由外框線的擠壓，變形而產生地。 為最終可視化技術在渲染建築物外牆紋理生成採用半程序的做法。每一建築物外牆是拼接成的疊加和嵌套網格結構。分個的單元由此細分而來的，然後再指派紋理或程序紋理。

三，創造街道地圖
3.2道路創造的整體目標
整體目標，主要是考慮設定參數的模塊，其初始值。該系統重量的影響，所有活躍的全球目標，並選擇適當的值為參數。影響某一特定目標，在任何時候，是控制輸入影像地圖。

3.2.1人口密度
如上所述，公路建設的主要方面，高度聚居的城市用高速公路連結，而街道發展成住宅區時，則給予居民使用公路的權利[ 12 ] 。該參數的確定一條公路部分敘述如下： 高速公路連接中心的人口。尋找未來人口中心，每一個公路道端芽數射線輻射狀在一個預設的半徑。沿著這條射線，樣本的人口密度是從人口密度地圖而來。人口在每個取樣點上線，是與加權逆距離到roadend和總結。方向與最大的總結是選擇繼續增長。如圖4所示。

與此相反，街道上不改變其方向將沿著最陡的梯度人口密度地圖。通常，他們的後續主導街道佈局。這是合理的，因為大多數的街道，在市區建成後，會以疊加模式加成上去。在創造街兩端仍低，人口密度在其環境下，通常是在該地區內的集體，根據該機制的建議，為Open L-systems [ 20 ] 。當一個地區的沒有人口時，街道就停止增長。

3.2.2道路格局
其他重要的全球性目標，是公路與佔主導地位的模式在這方面的工作。這適用於兩個公路和街道，雖然在我們的城市模型裡，街道上都是有限的，在可能的模式，他們可以形成。在圖5各種頻繁的道路格局正在上市[ 9 ] 。
最真實的城市展出多項道路模式，歷史的不同階段會產生不一樣的道路模式。 [ 12 ] ， fuesser分類街道分成兩個大類：主要街道和定居為導向的道路。在他的分析，他比較網格狀與放射狀的道路模式。在多中心的城市網格模式佔上風，而在單核心的城市放射狀模式佔據主導地位。高速公路，通常有兩種模型，街道通常出現在網格或類似網格的模式。 [ 11 ]區分不同地區，在城市導致的結論是，中央區人口密度高，它可以被看作是多中心的城市。因此，在高密度區的城市，網格模式是佔主導地位。 我們採用了幾種模式，並訂下下列規則。

-基本規則：這是最簡單可行的規則。有沒有疊加模式和所有道路，遵循人口密度。這也可以被稱為自然增長的交通運輸網絡。主要是年紀較大的部分城市表現出這種模式。所有其他規則是基於限制的規則，縮小選擇的分支夾角和公路段長度。
-紐約（或棋盤）細則如下特定的全球或局部的角度來看，最大的長度和寬度，單座。這是城市地區中最常見的街道佈局，而所有的公路和街道上形成矩形。
-巴黎（或放射）規則：高速公路以放射狀圍繞市中心，它可以是計算出來的數據輸入或設置手動。
-舊金山規則：這種模式可以讓街道和高速公路後續路線的海拔最低限度。道路對不同高度層相連，規模較小的街道上，即遵循陡海拔和很短。這種模式通常是在地形高低起伏較劇烈的地方可觀察到。見圖6。

下表總結了道路產生依照這些規則：如果在某一地點有多種模式，所有的模式都會被評估。建議參數值是總結和加權據該值輸入到圖像灰度地圖裡面。這使得混合不同類型的道路變得很容易，在圖7 。

3.3.1能夠偵測自我的L-系統
現有的軟體裡面還找不到能夠將L-系統分支合併在一起的系統,雖然在程序性血管紋路產生方面有類似的做法。在交通系統中的死胡同道路，是例外。大部分道路不會形成死胡同而是繞一圈迴路[ 9 ] 。迴路的形成，讓道路的拓撲由樹狀變成網狀。由於我們沒有一個交通模擬車流的基本模型，我們忽略了道路車輛負載的影響力。圖9所示的一個例子，利用曼哈頓島的地圖產生的道路。，曼哈頓最古老的一部分是沒有用規則圖案來產生的。而城市較新的部分，是用”紐約規則”所產生的。區域的限制條件讓公路沿著海岸線方現行走。請注意電腦橋產生的位置與真實的橋的位置非常接近。

4. 建築物的建模
ㄧ但路線圖生成，該系統就產生了土地分割，用來安置這些建築。一個隨機l系統，接著生成幾何的建築物。每一幢建築物給予不同紋理。為了使用較少的記憶體，我們用半自動的方式產生材質。
4.1劃分地段
在創造了公路和街道上之後，城市細分為許多小的領域，我們稱之為blocks。我們假設，上述大部產生凸型的區塊。因此，這個系統禁止凹的區塊。塊劃分成較小的單位，用一個簡單的，遞歸算法使邊長接近平行，直到該細分地段達到用戶所指定的值。
在大多數城市，依照建築物法規，控制建築物最高高度，依照地面面積的分配和分區規劃。因此，用戶可以控制最高高度的建築物通過使用一個圖像地圖和制約摩天大廈的產生。經過細分的塊，如果劃分區塊太小，系統會將該區塊丟棄。
4.2幾何
在我們的系統當中所有的建築物都是參數，隨機L-system產生的。每一個的區塊產生一個建築物。遵循不同風格，我們考慮了三種類型的建築物：摩天大廈，商業大廈和住宅。這些都是由分區規則，通過使用影像地圖來控制的。對每一種建築不一樣執行不同的生產規則。 建築物是經由任意地面規劃而產生的。該模塊的l系統構成的轉型模式（規模及動議） ，擠壓模塊，分支和終止單元，和幾何模板，屋頂，天線等，最終規模建設，是由地面圖，這是轉化詮釋輸出的l系統。雖然可以經由這種方式產生大量的各種建築，但系統仍有其侷限，因為建築物的功能，不能由這些簡單的規則產生。不過，也有高度的視覺複雜性，可以達到如下所示，在圖11 。

4.3紋理
複雜的場景細節可以通過在建築物上添加細緻的貼圖來達成。我們用實際建築物的圖片，修改和投影到幾合體上。雖然這種方法提供了最詳盡的貼圖，然而準備貼圖卻要消耗大量時間。此外，由於大樓數目過多，記憶體的限制構成問題。大多數的這些困難是可以解決的，若使用程序紋理[ 10 ] 。不幸的是，並非所有細節能夠以這種方式達成。某些圖案像石頭和磚牆可以用合成的方式取得（ [ 22 ] ， [ 19 ] ） ，但建築物的牆面不能只是用這種方法達到。因此，我們決定設計一種工具，用半自動方式創造外牆，採用分層和簡單的功能性成分技術 [ 10 ] ，我們稱為分層網格。 我們的設計是基於對外牆的觀察。為了簡化我們的模型，下列假設門面紋理已取得：
1 外牆顯示一個或幾個重疊或嵌套網格狀結構，大多數網格細胞，完成相同的功能，即通常窗戶或大門是開啟的。2特別是網格會影響到其他週邊的網格，如在一樓的窗戶會和一樓以上的窗戶有不同的尺寸。3不規則的網格式針對整體，而不是單一的網格細胞。
我們的目標是要營造程序紋理，使用戶能夠捕捉某種風格的建築物貼圖，通過建立一個通用的風格紋理。每一個單一的風格紋理應產生各種不同的紋理，在定義出的風格裡，不論尺寸。由於圖像的門面分子能夠捕捉到細節，本系統仍然能產生磚面，門窗。
分層網格系統是基於區間群體。一個區間群體，是一套不重疊的，有序列的間隔。好處是用一維時間間隔為基礎的紋理是行與列的，且可以改變單間隔。儘管如此，我們還是能夠改變特定的網格細胞。 兩個任意區間群體能夠結合起來，形成雙向層如圖一所示， 12 。
圖層也可以是一個程序紋理，圖像地圖或另一層。舉例來說，當使用一個窗戶的影像地圖時，我們用了一些照片，顯示窗口開放，半開放和關閉。隨機運用不同的窗口，以每一個單元為基礎，很容易建立出複雜的圖案。這套系統的缺點是每一個材質必須要手動建立。如圖一所示， 15 ，這是通過肉眼確定規律及測量門面元素的大小。ㄧ但shader被定義出來，材質就能拉伸成任何的長寬。

五、結果
我們提出幾張利用cityengin產生的城市，渲染出來的圖片。第一張是在即時渲染引擎產生的，而第二個例子是使用raytracer產生的 。 如圖一所示，有16截圖的'虛擬'曼哈頓，用 dvreality 5.0這套軟體呈現出來 。該模型包括曼哈頓島，含有大約13'000棟建築物。建立街道圖前後計算花費不到十秒鐘，分割街區並建立建築物大約花了10分鐘。建築物被拉伸，並自動產生紋理。由於該軟體不支持動態紋理生成，我們使用了一套傳統貼圖方式製作建築材質。橋是用手動的方式添加到場景中。
我們的第二個例子是一個不同的自動生成結果。在這個例子中，紋理是用程式自動疊合產生的。最後張圖片，是用Maya 3.0渲染出來的 。

6. 今後的工作
我們提出了一套系統，能夠由二維輸入數據產生一個大型城市。我們的做法並不取決於空中攝影的街道和建築物，是能夠產生無限多的城市，且產生的速度非常快。該系統生成的街道地圖，通過延伸的l -系統，處理許多不同的要求，就整體或是區域性地，且不會增加核心系統的複雜性，並創造了建築形狀對後來產生的分配。我們也發明了一個簡單的建築物紋理產生技術，能夠以程序性的方法產生。

這樣一個複雜的系統---城市產生器，引申出很多有趣的問題，可能會導致更為切合實際的結果。整體的道路產生：更多規則可以被添加到讓道路建立機制，讓道路的形成更加的真實。把這些因子加到道路產生器當中，可以利用抑制或是利益來決策道路路線的產生 。 模擬與分析增長：把城市的演進顯示出來又帶來新的問題。交通流可以添加到系統當中，並可能引發路線的成長過程。 建築物的產生：我們可以將房子分成幾個功能單元，這些單元再組合成為新的建築物，可能會是一個更好的建築物產生方式。可視化：創建程序紋理樣式，可能經由自動的方法找到有其盤狀的建築物材質，然後自動產生風格不同的貼圖。

[更多評論]
免費城市製造外掛CT Gen (Citygen)

拍幾張照片就可以轉換成3D模型的軟體--STRATA Foto 3D

電腦動畫世界裡的角色行為behavior