土砲 CNC：G code 轉換軟體

接續前篇：土砲 CNC：控制界面軟體

本實驗室在使用 pycam 以後感到十分困擾, 於是就自己拼了一個 G code 轉換器
如同 pycam 一樣, 其功能是輸入模型, 輸入參數, 然後我這軟體會分析
最後做出一組 G code 讓機器能切出和模型一樣外型的實體出來
做了以後終於了解這個問題有多機車XD
經過許多的妥協終於完工, 耗時兩個月半
當看到 "妥協" 兩字就要知道和 CNC 的機構一樣, 絕對不是完美的, 都是有漏洞的XD
做過這軟體以後對於 CAD 類軟體收取高額費用就比較能接受
不過我還是不會買, 要買也是公司去買, 不干我的事！XD
所以如同前面自製 CNC 機器, 如果你期望我這自製軟體能有商業軟體等級的轉換能力
我會建議你放棄吧, 乖乖去 Windows 上用商業軟體 (不管如何取得！XD)
這軟體適合給堅持蹲在 Linux 系統上開發的用戶, 以及對於 G code 轉換器有興趣的用戶
一般用戶請迴避, 感謝XD



G code 轉換器所要解決的問題全都是 Computational Geometry 的問題 (以下簡稱 CG)
CG 的多邊形問題, 以及點和線的問題, 我並沒有看過別的 CAD 軟體原始碼
所以解法肯定不是最佳解, 但是是 "可行的" 解法 (基於某些限制下可行！XD)
主要參考軟體是 3D 印表機在用的 Slic3r, 一開始本來是想改那套來用
結果一拆開來看, 居然是用該死的 perl 寫的, 是那個懶人專用極度精簡難以閱讀的 perl !
很痛苦的半猜半看的研究其內容, 抽出關鍵片段, 然後打掉重練
我用 C 和 Python 寫的, 其實剛看到 Python 時我也不是很滿意
尤其當看到 "簡潔" 我就想到 perl, 後來 Python 3.0 大翻修以後
看起來就比較有秩序, 而不是有些詞有特權 (像 print), 那會看起來很不一致
C 的部份是不希望重走 pycam 的路, 我雖然沒有看完它的源碼
但若要猜我會認為那記憶體爆增的問題應該是來自 garbage collection
以及 Python 的精神：“用一種方法，最好是只有一種方法來做一件事” (來自wiki)
整數就都是 long, 浮點都是 double, 哪怕程式中只是一個累加變數, 一律是 long, 一種解法
這會讓記憶體使用量爆增, 尤其存大量陣列時, 然後如果對 Python 直譯器不夠熟悉
這些大量記憶體就很可能沒有釋放, 造成記憶體爆炸
所以我的軟體對於未知長度陣列會用類似 vector 的方法做, 有需要才擴展, 不要時一定要釋放
座標只用 float, 然後遇到 id 時一律 int, 沒有 long 和 double, 而且都是 C 做的
然後 C 部份算完, 把結果透過轉接層換成 Python 可以看的 long 和 double
我只用 Python 來做 UI, 用 C 寫 UI 搬去別的平台常常會有相容性問題
而且編譯困難, 要下一堆參數, 還容易失敗, 這部份 Python 就有優勢
只要 Python 有安裝模組提供相同界面, 我們就不用去知道別人電腦上是 GTK 幾點幾
可以用字串呼叫產生圖形界面, 而不是二進位函式庫對接
所以這套軟體雖然是以 Python 執行, 但是所有的多邊形運算都用 C / C++ 編寫
Python 只是用來設定參數和顯示結果, 用的是 Python GTK 模組 (以下簡稱 PyGtk)
我寫的程式是 C, 引用兩套外部開源軟體：admesh 以及 clipper
源碼都是從 Slic3r 裡複製出來的, 分別是 C 和 C++ 寫成
用 admesh 來讀取 STL 模型, 用 clipper 進行多邊形與多邊形的運算

整個運算流程是這樣的：

1. 讀取 STL 檔, 把模型結構化的存放在記憶體中
2. 依據使用者設定的切割層高度將模型切割成多層
3. 切割後會產生大量線段, 嘗試刪除多餘的線段並連接成多邊形
4. 建立多邊形階層, 了解誰在外面誰在裡面, 哪些區域要切削哪些要保留
5. 對於所有需要切削掉的區域將其多邊形收縮, 收縮距離為使用者設定的銑刀的半徑
6. 收縮後產生輪廓線, 線內區域用水平線填滿, 線的間距為使用者設定的填充直徑
7. 將所有填充的水平線想辦法接起來, 完成後就可以得到可以削掉這區域的路徑
8. 輸出 G code, 將輪廓線依序做出 G code, 然後再把各區域切削路徑全部接起來輸出

步驟 1 即是用 admesh, 步驟 5 則是 clipper, 剩下的就是我寫的, 也就是充滿風險的部份XD
其中又以 3, 4 風險最高, 6 以後的都有常用演算法, 只要照著實作即可, 理論上應該是不會出錯, 應該...XD
我們就一步一步的來說明運作方式, 原始碼在文末發放

讀取 STL 部份完全參考自 Slic3r, 而我的程式放在 modelslicer.c 中的三個函數：
mslic_load_stl mslic_load_stl_2 mslic_load_stl_3
這三段是可以做在一起的, 原先是為了讓讀取大模型時可以讓 PyGtk 顯示讀取狀態才拆開
不過目前在多執行緒方面有些問題所以暫時還是先把它們做在一起
admesh 有一些修復模型的功能, 不過那對於我們切割模型有些時候並沒有幫助, 要看損壞情形
但是即使是良好的模型, 用 admesh 讀取後還是要執行修復
修復對 admesh 來說似乎不單只是修復, 而是包含檢查與紀錄, 所以每次讀取都要執行
同時建立共享頂點, 也就是有一個巨大的陣列存下所有頂點, 接著表示邊和面時就只用頂點的代號表示
例：vertex[20] = { 1.000, 2.000, 3.000 } vertex[21] = { 1.000, 2.000, 4.000 }
陣列中第 20 個頂點位在 X,Y,Z = 1,2,3 第 21 個頂點在 1,2,4
那麼紀錄一條由這兩頂點組成的邊就只用 (20, 21) 表示, 查找頂點也是用這代號
而不是 X,Y,Z 三個浮點數去找, 畢竟一個整數檢查相等比三個浮點數檢查簡單太多了
表示面時也是如此, 一個面有三個邊, 每個邊也都是代號, 指向一個存有兩個頂點代號的結構
在我的程式裡就是 Edge2, 存放兩個頂點代號以及鍵結串列用的指標

讀完模型後接著就是分割, 以水平切割將模型沿 Z 軸切割, 就如同 Slic3r 那樣
取得分割面的形狀目的是要控制銑刀沿著模型邊緣移動, 以切出模型的樣子
像這樣：

如果目標模型是一個實心物體, 那很簡單, 就是對每個多邊形判斷
對每個面執行檢查, 看 Z 的範圍是否在當前切面上, 若是, 就進行切割
三角形只會有直線, 所以直接線性內插, 大概會像這樣

對上圖左的六角柱切割, 會得到上圖右的切面圖, 這段程式在函數 mslic_slice_layer
由於是三角形的面構成, 所以切出的形狀雖然是六邊形但實際上會有 12 個邊
接著只要將這 12 個邊連接起來就完成了
這是從中間切的情況, 那如果切到頂呢?

如上圖左, 如果從頂面切過去, 線段就會變得複雜多了
不過這還算簡單的, 作法是檢查面的 Z 座標, 如果和切面的 Z 座標相等
我們就知道這切面剛好切在三角形上, 接著檢查有幾個頂點在切面上
若有兩個表示有條邊在切面上, 若有三個表示這個面是水平的面
若有一個邊同時是兩個水平的面的邊, 它就一定是上圖右畫紅色的那種邊
拿掉這種邊不會對多邊形的外型構成影響, 所以就把它標記為忽略
全部的面都檢查完以後我們就會留下上圖右黑色部份的邊, 接著一樣是每個邊對接就任務完成

簡單吧～ 可惜現實中不會只有這種模型XD
接著我們考慮有洞的多邊形, 如果把前面六角柱的模型中間挖一個矩形的洞, 像這樣：

根據前面規則, 把水平的面上共用的邊全部忽略, 我們可以得到上圖黑色部份的線
上圖灰色部份代表洞, 需要控制銑刀去把它剃掉
不過這是我們看圖說故事, 容易, 但是在電腦程式中它就只是一堆座標
除非參考原始模型, 並且知道如何計算 3D 多邊形之間的關聯, 像是法向量方向等
那會讓事情變得很複雜, 所以我偷懶了一下, 用一個簡單的方法判斷
就是只用二維空間判斷, 上圖兩組黑線各形成一個迴圈 (或稱封閉的多邊形)
做好的多邊形會和當前已做好的多邊形進行比較, 假設我已經將六邊形儲存
接著做好矩形的多邊形, 我就把矩形每個點去和六邊形測試, 如果所有點都在六邊形內
我就認為矩形是在六邊形內, 把它放到六邊形的 child 節點, 最後會建成一顆 tree
如果矩形都在六邊形之外, 就當成 siblings 節點, 放在同階層
如果有些點在外有些點在內, 表示多邊形互相交叉, 存起來標記為 error, 圖形界面上畫紅線標記
接著, 我們就把整個模型的外框 (bounded box) 和第一層多邊形之間的區域當成要剃掉的區域
第一層和第二層之間的區域 (即上圖兩組黑線之間的區域) 當成要保留的區域
然後第二層和第三層之間的區域 (若無第三層就是第二層全區域) 當成要剃掉的區域
把偶數層到奇數層之間的區域剃掉, 奇數層到偶數層的區域保留
這就是運算流程 1-4 做的事情, 目前已測出某些情況下會出錯XD

以下是已知的現象：

還是一樣六角柱, 只是中間挖了個三角形, 而且正好挖到頂點上
做出來的切面是一個有洞的多邊形, 而且兩個多邊形還有共用頂點
目前我還沒有辦法正確的處理這類多邊形, 所以還是全部剃掉XD
算法是先將所有邊排序, 起點的 XY 座標越小的放串列的越前面
然後從最小的頂點開始, 以上圖來說就是頂點 0 和 1 組成的邊
接著尋找和邊 0,1 連接的邊, 我們可以找到 1,2 1,3 1,4 三條邊
求出 0,1 與這三個邊的外積與 cosine 值用來找出與哪個邊的角度最大
然後選角度最大的進行連接, 剩下的標記為忽略, 等到全部邊連接完
還會再把和這些標記為忽略的邊有連接的邊全部標記為忽略, 這樣會得到一樣只剩六邊形的多邊形
在 CG 裡有標準演算法處理連接問題, 但是那並不符合我們的應用
常見的是解 Convex Hull (凸包) 的問題, 中譯讓我想到gg的蛋包(?)
Slic3r 裡面有留這種程式, 但我不知道它想拿去做啥
不合用的理由是凸包問題是解將頂點圈起來的問題, 我們雖然也有一堆頂點
但我們不可以任意連接, 這樣就和原本的模型不一樣了, 我們只能在既有的邊上做文章
許多 CG 類的函式庫大多假設你知道你要拿什麼去算, 例如許多已知點組成的多邊形
而我們在這階段要解的問題是找出正確的邊線, 問題不同
或許 3D 的 CG 函式庫可能有解決方案, 但那種工具很難找, 找了也不知道怎麼測
2D 用軟體畫線就可以看到結果, 3D 的要搞畫面視點問題就沒完沒了了
所以還是先跳過用 2D 來解

如果模型三角形部份是洞其實不會有問題, 因為那裡本來就是要剃掉的
但如果中間是實體我們又會有麻煩了, 像這樣：

如果我們從上圖左紅色部份水平面切下去, 正常情況應該是得到上圖下方的結果
灰色部份當成洞把它剃掉, 留下中間白色部份
但是這裡切下去我們會看到兩個矩形, 一個在裡面, 一個在外面
基於我們前面寫的規則：把偶數層到奇數層之間的區域剃掉, 奇數層到偶數層的區域保留
我們會算出上圖右側的結果, 把白色保留, 中間的模型實體當成洞給剃掉XD
接著我們改一下模型, 變這樣：

故意讓中間的多邊形去碰到外面多邊形的邊, 結果是中間接線全部被移除
只剩下一層當實體, 全部會被保留, 這不會損壞模型, 但會少剃一層
也就是上圖下方正常情況中灰色部份沒有剃掉, 那裡會比正常情況多出一層的厚度
這個問題最後我的解法是偷改 Z 切割值, 可參考程式中有 SLICE_HIGHER 的地方
假設切割層 Z = 10, 那我就紀錄 Z = 10, 但是下命令切割時卻是下 Z = 10.001
以上面的範例, 軟體切出來的不是紅色面下的矩形就是中間上方的多邊形, 不會剛好在紅色面上
這就是鴕鳥解決法XD 如果使用者做了模型兩個平面剛好差 0.001 應該就會出包了XD
但我相信沒有人會這麼做, 而且我們的土砲 CNC 雕刻機也沒有這種精確度, 沒關係的！
就先當作沒看到吧！XD

程式運作到這裡若都沒有問題, 那剩下的就不太會出錯了
到這裡, 我們應該已經建立出多邊形的階層, 誰該剃掉誰該保留都已經確定
接著就是產生銑刀路徑, 一共分兩部份：輪廓和面積填滿
輪廓部份是用來建立模型的外型, 如果有用過 3D 印表機的用戶應該會注意到
當列印每一層時第一個畫出來的一定是模型的外型, 然後才會將內部填滿
如果不這麼做的話就會像這樣：

上圖左是直接填滿不畫輪廓的, 由於銑刀和 3D 列印頭都是圓的
所以填滿時就會產生上圖黑圈區域的縫隙, 用銑刀這樣切出來的東西就刺刺的
用 3D 列印的話就是滿面坑洞像蜂窩一樣, 看起來肯定很噁心XD
所以要先用上圖右的方法做過一次, 然後再用上圖左的方法填滿
這樣切出來的模型才會有漂亮的邊緣
不過這運算就很複雜了, 要把既有的多邊形向內縮, 標示為洞的多邊形外擴
像這樣

上圖上側是個有洞的多邊形, 如果要產生填滿它的輪廓, 得要外面的邊內縮
裡面的邊外擴, 而且還要考慮紅線的寬度, 像中間太細的不可以劃線
紅線的寬度就等於是銑刀直徑, 當遇到過小的縫不可以硬督進去, 會壞掉的(?)
這樣的內縮問題有個名字, 叫做 straight skeletons
取自 Wiki 的圖：

當中間越縮越小時多邊形會再次被分割, 而不只是將多邊形的外型縮小
這個我就不想花時間去解了, 太難了, 我把這問題交給專家處理：Clipper
這套函式庫專門解多邊形運算, 其中有一個功能叫 offset, 就是解這問題
裡面有運算速度比較, 它的速度很快, 不過蠻賊的, 因為它是用整數座標, 別人是浮點數XD
所以我們的座標轉換去給 Clipper 時會削減精確度, 用類似 fixed point 方法
不過沒有複雜的逼近法, 就是直接乘 1000, 丟進去算完出來後除 1000, 如此而已
0.001 對我這土砲機來說已經精確的過份了, 差一點沒關係XD
詳細轉換過程可參考 clipper_glue.cpp 算出來會像這樣：
淡黃色線是多邊形的外層, 暗黃色線是多邊形的洞
深藍色線是銑刀路徑, 這是銑刀直徑設定為 2 時


這是銑刀直徑設定為 8 時：

下方六邊形的洞本來有線, 直徑增加後就消失了, 因為這樣粗的銑刀若督進去模型就壞了

我們完成了銑刀路徑規劃, 接著就要把規劃好的區域進行填滿
把所有模型以外區域的材料全部剃掉, 這樣模型才會顯露出來
填滿的方式在 3D 印表機中有多種選擇, 什麼蜂巢式方格式交叉式...等
我們這裡只做一種最簡單的, 那就是水平線填滿
有些商業軟體會做 straight skeletons 填滿, 也就是前面 Wiki 的圖
就真的是那樣一圈一圈填起來, 這算法很複雜, 我們還是做簡單的就好
作法就是從輪廓多邊形的最小 y 值處開始, 依據使用者設定的填滿寬度
每隔這寬度就畫一條 X 軸水平線, 一直畫到輪廓多邊形的最大 y 值為止
畫的時候會像這樣

我們就對輪廓多邊形每個邊去比較, 有抓到交叉處就存起來, 然後依 X 值排序
排好後如上圖, 可以得到 X 由小到大四個點, 接著就和算階層時一樣
編號奇數到偶數的點就是在輪廓多邊形內, 把每條這樣的邊都存起來
這算法出自：Polygon-Filling Algorithm
這樣可以得到一個串列, 接著用一個迴圈, 每次找一個可以接起來的邊
找到後就從串列中移除並接起來, 找不到的話就把當前已經連好的線段儲存成填滿區域
接著再從串列抓最前面的開始接, 直到整個串列的線段都被拿光為止
這段程式在 polygon.c 的 mslic_layer_fpolygon_fill 和 mslic_layer_connect_segments
連接時呈 S 型, 先從線段左邊開始, 線段右邊就往 Y 方向找
找 y 值大且右邊也接在同一多邊形上的線段, 然後連接時沿著多邊形的邊去接
如下圖：

淡黃色線是多邊形的外層, 暗黃色線是多邊形的洞
深藍色線是銑刀的輪廓路徑, 淡藍色線是輪廓路徑的填充路徑
注意上圖兩紅色箭頭處, 當兩條水平線段跨在不同邊上時, 要沿著邊緣接起來
如果直接走直線會有問題, 像下方那個紅色箭頭, 如果那裡直接接起來
線段就跨出輪廓路徑, 就會把原本該留下的邊給剃掉

到這裡我們就產生出所有區域的輪廓線和填滿線段, 接著就可以輸出了
輸出 G code 就是把所有線段都 dump 出來而已, 由於是絕對座標
直接把 XY 座標值輸出就可以了, 要特別去注意的大概就是 Z 軸了
我的程式需要指定從哪一層當 Z = 0, 然後所有這層上面的切割層都會輸出
所有這層以下的切割層都忽略, 這用意是避免底座干擾, 這不太好解釋, 自己試試就知XD
設定好 Z = 0 的切割層以後, 我們就從最上層開始輸出, 和 3D 印表機從最下層開始疊加相反
這裡需要處理的有兩項, 一是線段間的連接, 二是 Z 軸跨高
首先線段連接, 如果直接依序輸出, 那結果會像這樣：

暗紫色線是區塊連接線, 也就是銑刀處理完一區後移動到下一區的路線
可以看到它非常的亂, 這樣還是可以切得出來, 但是會花很多時間在區塊間移動
解法就是找最短路徑, 從記憶體中放的第一個區域開始, 做完後找第二區時
搜尋全部區域, 找起始點離自己最近的, 然後連過去, 並標示為已處理
直到所有區域都處理完, 做這修改後會變這樣：

差很大！不會再來回亂跑
接著是 Z 軸跨高, 如果為了安全起見, 我們可以每次要跨區時都把銑刀移到模型最高處
這樣就不會在跨區時不小心把別的要保留區域給剃掉, 但是這樣會多耗時間
有些時候明明在同一區域內, 應該把銑刀稍微抬高跨過去即可, 這樣可以節省加工時間
我的作法是跨區時判斷, 先判斷是否與模型交叉 (即淡黃色和深黃色線)
若有, 表示這線會跨越輪廓, 要把 Z 拉到最高
若無, 接著判斷線段是否全部在當前的輪廓線內
先把跨區線縮短 0.001 (嘿～又偷懶了！XD) 這縮短是迴避線段與輪廓線共用頂點的問題
若都在輪廓線內, 就只提高兩倍切割層高度, 低空跨越
第二個判斷是為了迴避這問題：

這個現象是多虧了有這個模型才不小心發現的, 注意紅色箭頭指的暗紫色線
如果沒有這判斷, 像這種不會和黃線交叉可是又剛好在深藍色輪廓線外的跨接線
要是讓它低空跨越就會把旁邊黃線給剃掉, 所以像這種跨接線在輪廓線外的也要 Z 拉到最高

到這裡所有運算就都完成了, 發放源碼：

modelslicer.tar.gz

上面常測的模型可以到這裡下載：SnowFlake by keving0527

系統裡需有 python3 以及 gtk module, 印象中預設就有
然後要有 C++ 編譯器：sudo apt-get install -y g++
執行 build.sh 即可編譯, 執行 run 即可啟動, run.eng 是英文版
執行畫面：

操作方法就是左邊按鈕由上一路按到下XD
按 "開啟 STL 檔案" 後會呼叫 STL 相關函數, 只建立結構資料
接著設定切割層厚度, 即每層的高度, 接著按 "產生切割層"
如果 console 丟出一些像是 cannot close loop 的訊息就是我失敗了, テヘペロ (・ω<)　(被巴XD)
印象中有些 3D 列印在用的模型還會導致 segment fault, 印象中, 不確定
雖然如果有我也不意外就是了XD 這時請回去修模型, 或是修這軟體XD
完成後可以切換圖層看有沒有問題 (不過就算有問題也不能怎樣就是了, 請修模型或修軟體XD)
用滑鼠按住右側繪圖區可以移動畫面, 滑鼠滾輪可縮放
像這種：

console 會有類似 Poly: intersected! in=... 的訊息
這就是模型個別建好以後就直接放在一起互相交叉, 這我可以算
只不過畫紅線處會因為錯誤而沒有放進多邊形的 tree, 計算時會被忽略, 算出來就像這樣

紅線部份被當成空氣, 如此而已

接著視點控制是用滑鼠拖移畫面時在用的, 拉到某個視點按儲存
接著在拉到別處, 按一下還原就會移回去, 如此而已

接著設定路徑參數, 工具直徑就是銑刀直徑, 填充直徑則是填滿的線寬
它必須小於工具直徑, 這用途是如果要路徑重疊, 例如設 2.5
我會用 2.5 的寬度去算填充路徑, 可是用戶銑刀是裝 3 的, 那它就會產生 1 的重疊
這裡我都不會去寫單位, 不管是 mm 還是 in, 我就是都和 STL 一樣
STL 是用 mm 做單位, 這裡就是 mm, 同理 in 就是 in, 要切換請回去模型切換, 不干我的事XD
填充路徑如果設 0 就是不填充, 如果只是想修邊就設這樣
讓刀具剃邊, 適合粗削後使用, 如果沒粗削就直接上就等著斷刀唄！

邊緣外推就是外框, 目前建議只加大不要縮小, 因為算出來的結果會失效
它只會和第一層黃線去計算, 第二層以後只和前一層算, 所以若外框小於二層以後的多邊形
計算後都不會受外框影響, 不會被裁切, 這樣設沒有意義, 除非要搞怪(?)
完成後按下 "產生路徑" 就會開始畫輪廓線和填充線

接著設定 G code 參數, 銑刀移動速度就只是 F 指令
像這裡設 300 就是加一行 F300 在開頭而已
銑刀跨越增高則是設定銑刀跨區時移動到模型最高的 Z 值後再加上多少
預設 1 就是移到模型高 + 1 的地方
"當前圖層為最底層" 則是設定 Z = 0 的層數, 所謂當前圖層就是前面切換切割層那裡的層數
從那裡改層數改到想當 Z = 0 的地方再來這裡按一下 "當前圖層為最底層" 就完成設定
最後按下輸出 G code, 完成後畫面上會多出許多線, 最後這裡說明各種顏色的線的意義：

灰色：外框線, 按下產生路徑後才會更新
淡黃色：模型外層
暗黃色：模型內層, 即 "洞" 的部份
淡藍色：填充路徑
深藍色：輪廓路徑
暗紫色：跨區路徑, Z 會拉到最高
粉紅色：跨區路徑, Z 會低空掠過, 注意是否有這種線條和黃線交叉, 理論上應該不會有...XD
紅色：錯誤的多邊形


最後 demo：

做一個模型


產生 G code

在 pycam 算了半小時吃光記憶體才算完, 這裡閃一下就算完

丟到平板上


然後開工！

右邊是人體 CNC 切的, 左邊是這次切的, 圓滿了！

這軟體規劃時刻意讓每層可以獨立運算, 用意是多執行緒
應用現代多核心技術平行運算讓速度加快
不過我對 PyGtk 還不是很熟悉, 搞不太定, 所以目前都是單執行緒
但是以我的第四代低電壓 i5 主機來算每個操作都沒有超過五秒過, 大多閃一下就完成
所以這層最佳化有沒有做似乎也不是那麼重要了, 就先放著吧



下篇： 土砲 CNC 雕刻機完成驗收