在電腦運算的世界中,三維模型是由諸多頂點、索引定義的網格(mesh)構成,然而,如何自動從頂點建立索引,以及從二維形狀建立三維模型等需求,則是網格生成(mesh generation)演算的範疇。

網格的建構

許多三維建模軟體或繪圖程式庫,多半提供了立方體、球、環等基本三維物件,初學者可透過交集、減集、聯集等操作來處理這些基本物件,組合出想要的模型,然而,這種方式能建立的模型,在外型上終究有其限制。

進階的建模軟體會提供佈線之類的編輯模式,在此模式下,多半會看到物件呈現許多點與線,點與線構成許多面,這些面構成網格,若是增加點就會增加佈線,從而增加許多面,相對地,刪除點就會減少面,拖曳點可以改變這些面的外形,從而改變物件的外觀。

網格是由大量的平坦多邊形,也就是共面的頂點組成,而面的最小單位是三角形,因為只要三個頂點不共線,就必定共面。

在手動建模軟體中進行佈線時,通常會建議用四邊形佈線,這是因為,若要對既有網格做後續處理,例如細分(Subdividing)、平滑(Smoothing)等,四邊形會比較容易,然而,對於不共面的四個頂點,其實可以看出有兩個三角形,只是僅顯示四個邊線罷了。

在決定哪些頂點構成面時,必須留意頂點的順序,每個面的頂點必須全部順時針或者都是逆時針,這是因為頂點順序可用來決定面的法向量,而法向量是光線、陰影等計算的重要基礎;三維的頂點會有x、y、z三個值,直接使用頂點會耗費許多記憶空間,因而會對頂點編造索引,然後用一組索引,也就是頂點索引陣列,來代表哪個面是由哪些頂點依哪種順序構成。

不過,有些形狀的頂點,在順序上有規則可循,例如扇形、帶形等,以帶形為例,帶子可以從左邊逐一剪下三角形,這些三角形在帶子上其實是共用頂點,將這些頂點依序編索引,實作時只要依序且循環地走訪這些索引就可以了,也就是說,如果模形本身可以分解為帶狀,就不用特別建立頂點索引陣列。

自動建立索引陣列

一般而言,扇形、圓、帶形在順序上,有規則可循,因此,像WebGL就提供了gl.TRIANGLE_FAN、gl.TRIANGLE_STRIP等常數,只要排好頂點座標並指定常數,就不用提供索引陣列,通常我們也稱這類頂點為無索引頂點。

三維程式庫可能封裝了OpenGL/WebGL,然後通常提供了polyhedron之類的功能,我們可以指定頂點與索引陣列來自訂模型,不過,寫程式時,並沒有滑鼠可以讓你佈線,總不能手動來填入頂點與索引陣列吧!

其實換個角度來想,無索引頂點只是因為提供的頂點順序有規則可循,而OpenGL/WebGL可以自動處理索引陣列罷了,因此,只要有規則可循,安排好對應的頂點順序,接下來,就可以實作程式來生成索引陣列。

例如,若頂點代表一個數學函式z=f(x,y)構成的曲面,且這些頂點是y為0到10,x為0到10的順序安排好,某個頂點(x,y),就可以與上、右、右上的頂點,構成兩個三角形,處理全部座標後,就可以構成一個曲面,程式實作可參考〈繪製曲面〉

甚至有些模型連頂點順序都不必安排好,例如,曲面頂點若是隨意散布,我們只要將頂點排序就可以了;類似地,任意數量頂點若構成了凸面體,我們可以先進行排序,再透過三維的凸包(hull)來演算出索引陣列,而三維凸包演算的方法之一是遞增法,若對程式實作有興趣,可參考〈自訂3D物件〉

從二維生成三維

有時候,會希望給一個二維的形狀,以及一個路徑,然後自動依路徑生成三維物件,這就像擠牙膏,從牙膏管的出口面擠出一條牙膏,因而這個動作稱為擠出(extrude),建模軟體基本上都會提供這類功能。

想要實作擠出,在這之前,我們必須要實現掃掠(sweep)。

首先,若三維空間當中,有多個面,代表將模型用刀橫切時所得到的平面,接著,如果我們將這些切面的頂點,依序連接起來,之後就可以重組成模型,而這個動作稱為放樣成形(loft),若構成切面的頂點數都相同,就會是放樣成形的一個特例,稱為掃掠。

掃掠其實很容易實作,因為構成切面的頂點數都相同,代表著只要目前切面上取兩個頂點、下個切面取兩個頂點,就可以構成四邊形,將之切為兩個三角形就可以了;若是切面的頂點數不同,可以求兩個切面的最小公倍數,然後看看各自切面上,要在哪些邊上增加頂點,最後兩個切面的頂點數都相同下,就可以用掃掠了。

如果給個二維形狀,能自動生成路徑上的切面,掃掠這些切面,不就是擠出了嗎?

最簡單的作法,就是在z方向生成切面,我們只要為二維形狀的頂點加上z分量,就可以了,而這就是線性擠出(linear extrude);進一步地,我們還可以在線性路徑上,多生成幾個切面,而且,每個切面可以各自縮放、旋轉,促使線性擠出能產生更大的變化。

如果想要讓二維形狀擠出時有點曲線變化,而不只是線性,那麼,可以從旋轉擠出(rotate extrude)的實作開始嘗試,相對而言,這是最簡單的曲線擠出,以xy平面上的形狀為例,只要在x軸將之移至指定的半徑處,然後,對每個頂點繞y軸旋轉,就可以得到新的切面,而掃掠這些切面,就會得到一個環狀模型。

至於對於任意點構成的路徑,可以用兩個點求得向量,這個向量可作為切面的法向量,有了法向量,就可以知道二維形狀該如何旋轉,才能讓面與法向量方向一致,轉動二維形狀後,將面移至其中一個點,全部的點處理完後,掃掠這些面,就是路徑擠出(path extrude)。

不過,實現路徑擠出時,必須留意的是,在只提供形狀與路徑的情況下,其實在切面的相關資訊上是不足的。

而用兩個點去求得法向量,只是猜測這個切面可能是該法向量,實際上,還有其他的猜測方式,對此有興趣的人,可以參考先前專欄〈別對問題存在幻想〉

自動調整網格的點邊面

以上談到自動調整網格的點邊面,屬於網格生成演算的範疇,我在先前專欄〈Voronoi與Delaunay〉談過的Delaunay三角分割也是,而且,還有其他的分割法,像是耳切法(ear clipping),而方才提及的細分、平滑,都有相關的演算法可以處理。

因為網格處理通常要面對大量的頂點,而且,相關的演算往往結合了巧妙的資料結構處理,以及有效率的演算流程,因此,若能充分地認識這些網格生成演算,無論在資料結構與演算法上,我們都會有極大的收穫,同時,這樣的過程經常令人驚嘆且趣味十足!

作者簡介


報名台灣唯一超規格資安盛會


熱門新聞

Advertisement