在繪圖運算的演算法當中,Marching squares主要用於將二維資料轉換為彼此連接的等值線(isoline),線與線之間相連、構成輪廓線,可進一步擴展為等值帶(isoband),或是處理三維資料的Marching cubes演算。

Marching squares演算

一般而言,我們應該都看過地形等高線或播報氣象時等壓線之類的圖形!這類圖形將與指定值相等的點以線段連接,以地形為例,若有個平面,在某個高度橫切過某個地形,就會留下一個地形輪廓,若有多個不同高度的平面橫切地形,將取得的輪廓線疊在一起,就是熟悉的等高線了。

實際上,我們不可能拿到關於平面橫切地形的完整資訊,所擁有的資料可能只是某個經緯度處的海拔高度,因此,如果想畫出某個高度等高線,可採用的直覺作法是:將每個點與鄰近八個點進行計算,看看是否有內插值等於指定的海拔高度,不過,如果每點都要與鄰近八個點進行計算的話,將會過於耗費運算資源。

然而,若能事先過濾掉不需要計算內插值的點,就可以改進運算效率。方法是先為每一點的資料,標示它是小於或大於指定值。

例如,以0與1標示,這就有了與海拔高度對應的二維資料,當中包含0或1,若有一整群的0或一整群的1,其中被圍繞的部份,就不用計算其周圍資料的等值點,我們只要針對0與1交界處,來計算等值點就可以了。

問題在於怎麼知道某點同樣是0或1圍繞著?我們可以將0看成是黑點,1看成是白點,將點與點連接起來,將每四個點看成一個細胞,而細胞四個角落的黑點與白點組合,可能性會有16個,接著,可以為這16個可能性編碼,例如,賦予細胞頂點各有1、2、4、8的值,若是黑點,就可以獲得角落值,四個角落獲得的值,加總後就會有16個值,代表16個可能性。

不過,若黑點與白點正好都位於對角,實際上會形成鞍部,此時,就必須考慮這是個往上的鞍部(山的凸起),還是往下的鞍部(谷的下凹),隨後,我們可以使用細胞四個頂點來求得中點,看看中點的高度來判定,在去除鞍部的模擬兩可之後,最後的可能性會有18個。

接下來,就是建立這18個可能性下,每個細胞產生的等值線連結,等值線要繪製到多細緻,主要是看需求。

根據維基百科Marching squares條目的說明,我們從歷史記錄中可以看到,過去只有簡單的等值線直線版本,不過,從2020年12月之後,針對鞍部的部份,已經修改為具有曲線的版本了,組合出來的輪廓線會更為細緻。

在掃描完每個細胞後,將每個細胞建立的線段彼此連接起來,就是輪廓線了,若想看看以圖片表示的繪製過程,我們可以參考〈Marching squares(一)〉

擴展為等值帶

因為演算過程就像從一個方塊行進至另一個方塊,於是,才有了Marching squares這個名稱的由來,視覺化程式庫d3.js的d3-contour擴充可產生等高線之類的輪廓線,就是基於Marching squares,不過,我們看看d3-contour說明中的範例圖,會發現這不單只是輪廓線,而是一個輪廓面?

實際上,輪廓面是由每個方塊生成的等值帶組合而成,為了生成等值帶,必須指定這個帶狀的上界與下界。

而這就像在山坡上建築梯田,會在指定的上下界之間切出平面作為田地。就程式演算而言,這類似等值線的作法,只不過此次並不是標示每格資料為0與1,而是標示其為小於下界、介於上下界或大於上界,例如,可分別標示為0、1、2。

接下來,我們將每四個點組織為細胞,並為它們進行編碼,例如,若細胞的四個角落是小於下界(0)、小於下界(0)、大於上界(2)、介於上下界(1),就編碼為0021。

若根據目前維基百科〈Marching squares〉條目中的說明圖片來看,會有82種可能性,而我們需要的是,這82種可能性當中的藍色的帶狀部份(非淺藍或紫色部份)。

若要為82種可能性建立多邊形頂點,會是個繁雜的任務,不過,實際上頂點可以旋轉,而在非鞍部的情況中,每四個頂點在旋轉後是相同的,在鞍部的情況,則有三組每兩個頂點旋轉後相同、兩組每四個頂點旋轉後相同,加上0000、1111與2222,最後可以歸納為34種頂點組合。

其實,在建立等值線時,因為只是線段,部份頂點的計算方式相同,若要再考慮頂點旋轉方式,案例還可以再減少,只不過程式實作上,16種案例並不難撰寫,如果我們直接為每種情況建立頂點,程式閱讀上反而容易理解一些。

等值立方演算

既然可以基於二維資料,轉換為彼此連接的等值線或等值帶,如果資料是三維,例如人體電腦斷層掃描後轉換成的三維資料,可否用類似算法,建立具有相同值的三維平面,由這些平面組合為三維立體模型呢?

因為平面可以切為三角形的組合,而有了三角形,就可以計算面的法向量,從而決定哪一面是物體的裡部或外部,此時,這些就是三維建模時必需的資訊了。

是的!這樣的演算,一般而言,會稱為Marching cubes,就像Marching squares是由一個二維方塊行進至另一個二維方塊,而Marching cubes是由一個三維方塊行進至另一個三維方塊,每個三維方塊標示為大於或小於等值面(isosurface),然後,我們再將每個三維方塊作為一個點,以八個頂點組合為一個細胞。

接著,我們就可以為細胞編碼了。由於有八個頂點,總共會有256種可能的情況,然而,在考慮三維方塊可以旋轉、具有對稱特性之下,歸納後的等值面會有15種基本模式,因而可以製作一個查找表──我們可基於八個頂點作為索引,以15種基本模式來查找出256種可能的等值面座標。

網路上,也有現成的Marching cubes查找表,可以拿來使用,如果你想看看程式實作的方式,可以參考〈Polygonising a scalar field〉

或許你會覺得奇怪,為何二維版本的Marching squares的等值帶案例歸納後,會比Marching cubes多?這是為前者考慮了上、下界的閥值,而後者只有一個閥值,就像等值線只有一個閥值,而Marching cubes,實際上,是Marching squares的等值線擴充而來。

有趣的等值線、帶應用

有興趣的話,你可以試著實現Marching squares的等值線或等值面,其實,這麼做並不難,我們也可以參考〈Marching squares(二)〉〈Marching squares(三)〉,其中,就有p5.js實現的版本。

在實現等值線、帶的過程中,對Marching squares有更深入認識之後,我們就能知道,等值線、帶並不單只是用於等高線、等壓線之類的場合,我曾經以此實現了OpenSCAD版本的Marching squares,並寫了個簡單的切片程式Image slicer,從中能從圖片生成可列印的三維線稿模型,是個頗為有趣的應用。

作者簡介


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


熱門新聞

Advertisement