等值線、帶、立方演算

在繪圖運算的演算法當中，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，從中能從圖片生成可列印的三維線稿模型，是個頗為有趣的應用。