Marching squares(一)


你應該有看過等高線之類的圖形,這類圖形以線段將等值的點連接起來,結果就好比有個平面,在某個高度橫切過某個地形,留下一個地形輪廓,若多幾個不同高度的平面,就可以產生如下的圖形:

Marching squares(一)

上圖是使用〈Perlin 雜訊〉產生類似地圖高度的資料,然後使用在不同高度下畫出的圖案。

想尋找等值點並加以連接,可以使用的演算之一是 Marching squares,其實它的出發點很簡單,維基百科 Marching squares 的圖很清楚,就使用其中的圖吧!先從簡單的資料來看:

Marching squares(一)

如果選擇 1.5 作為目標值,等值點有可能就是上圖中的藍點(因為資料之間的值只能估算),連接成直線就可以了:

Marching squares(一)

問題在於若有更多資料,每一格資料都要估算等值點就會耗費大量運算,這時可以簡化對角資料:

Marching squares(一)

另外就是事先過濾掉不需要計算等值點的資料,簡單來說,就是將資料分為大於指定值與小於指定值的部份,例如,若有以下資料:

Marching squares(一)

將小於 1.5 的設為 0,大於等於 1.5 的設為 1:

Marching squares(一)

顯然地,正中間被 1 圍繞的 1 不用計算其周圍資料的等值點,問題在於怎麼知道它被 1 圍繞著?這時可以將 0 看成是黑點,1 看成是白點,將點與點連接起來:

Marching squares(一)

現在每四個點可以看成一個細胞,細胞的四個角落,黑點與白點的組合可能性會有 16 個,為了將這 16 個可能性編碼,可以像〈哈密頓路徑〉中談過的,給予每個角落一個值:

Marching squares(一)

然後這些細胞的角落若是黑點,就可以獲得角落值,角落值的加總就會有 16 個值,代表 16 個可能性,若將這 16 個可能性下,會產生的線段連結也畫上去,就會如下圖:

Marching squares(一)

因此就方才的資料來看,將線逐一對照畫上,就會產生以下的圖形:

Marching squares(一)

不過,注意到 Case 5,為什麼不畫成這樣呢?

Marching squares(一)

類似地,Case 10,為什麼不畫成這樣呢?

Marching squares(一)

顯然地,Case 5 與 Case 10 需要進一步考量,可以使用細胞四個頂點求得中點,看看中點的值是否小於指定值來做進一步判斷。例如 Case 5 可以進一步劃分為:

Marching squares(一)

Case 5 可以進一步劃分為:

Marching squares(一)

方才提到,為了避免耗費過多運算,有些等值點可以不用計算,相對地,如果你想要更細緻的等值線,也可以增加等值點的計算,例如,維基百科 Marching squares 中有張藍色的圖,其中 Case 5 與 Case 10,增加了與中點間的等值點,要不要計算這個點取決於你想要的等值線細緻度,下圖是以角落總值順序重新排列該圖的結果:

Marching squares(一)

瞭解以上之後,應該要實作為程式就不難了,下一篇文件再來看看怎麼寫…