年初開始進入3D打印行業，受命以Cura為基礎，研發一款自主的3D打印切片軟件。
自主研發要取其長處，補其不足，首先自然是要搞清楚Cura到底做了什麼，讀Cura的代碼是必需的。我一向都覺得比起自己寫代碼來，讀別人的代碼是一個漫又而痛苦的過程，讀者的思想與寫者總有偏差，往往又無法驗證自己的猜想是否正確，只歎人腦不是電腦，無法把眼前的代碼從頭到尾執行一遍。不知道各位資深程序會有什麼辦法，我的辦法是“翻譯”，看著別人寫的代碼，加上自己的理解之後，按自己的喜好重新寫出來，看一段翻譯一段，等全部翻譯完成，理論上作者的思路也明白了，同時還有了一份功能一模一樣的代碼，自己的理解是否正確，也可以通過執行“翻譯”出來的代碼驗證。
計劃總是美好的，中間的工程卻是充滿變數，之間的曲折折疊不說。經過若干次推倒重寫，勉強算是有了一份自己的切片軟件，又經過了半年的推敲摸索以及打印經驗積累，一個還算另自己滿意的切片軟件最終誕生。起名Pango，先觀大略。
Cura的架構
Cura是一個python語言實現，使用wxpython圖形界面框架的3D打印切片界面軟件，說它是界面軟件是因為Cura本身並不會進行實際的切片操作。實際的切片工作是由另外一個C++語言實現的CuraEngine命令行軟件來具體負責的，用戶在Cura界面上的絕大多數操作，如加載模型、平穩旋轉縮放、參數設置等最終會轉換成並執行一條CuraEngine命令；CuraEngine把輸入的STL、DAE或OBJ模型文件切片輸出成gcode字符串返回給Cura；Cura再把gcode在3D界面上可視化成路徑展現給用戶。
我主要參考的代碼是CuraEngine，本文主要篇幅也會放在CuraEngine上。而Pango的界面代碼就主要靠我自己發揮了。
Cura和CuraEngine都可以Github上找到，地址：
https://github.com/daid/Cura
https://github.com/Ultimaker/CuraEngine
我所參考的版本是15.04，15.06之後Cura和CuraEngine都有較大的改動，但核心流程沒變。所以本文分析的版本也到15.04為止。
言歸正傳，下面我們將開始一步一步揭開CuraEngine把一個模型文件轉換成為gcode的過程。
從總體上講，CuraEngine的切片分為五個步驟：
步驟一：模型載入
有一點3D編程經驗的人都知道，計算機中的3D模型大多是以三角形面組合成的表面所包裹的空間來表示的。三角形作為3D模型的基本單元，有結構簡單，通用性強，可組合成任意面的特點；空間坐標中只要三個點就可以表示一個唯一的三角形，兩點只能表示一條直線，而再多的直線也無法組成一個平面；空間中的任意三個不共線的點都可以組成一個三角形，而四個點所組成的四邊形就必需要求四點共面；任意的表面都可以拆解成三角形，一個四邊形可以拆解成兩個三角形，但一個三角形卻沒有辦法用四邊形組合而成。計算機所擅長的事情就是把簡單的事情不斷重復，而三角形正是因為這些特性，成為了計算機3D世界的基石。
CuraEngine內部也是用三角形組合來表示模型的，不過同樣一個三角形組合，卻有無窮多種數據結構來進行存儲。CuraEngine切片的第一步，就是從外部讀入模型數據，轉換成以CuraEngine內部的數據結構所表示的三角形組合。
有了三角形組合還不夠，CuraEngine在載入模型階段還要對三角形進行關聯。兩個三角形共有一條邊的，就可以判斷它們為相鄰三角形。一個三角形有三條邊，所以最多可以有三個相鄰三角形。一般而言，如果模型是封閉的，那它的每一個三角形都會有三個相鄰三角形。
有了三角形的相鄰關系，可以大幅提高下一個步驟分層過程的處理速度。Cura之所以成為當前市場上切片速度最快的軟件，這是其中最顯著的優化之一。
如果把模型放在XY平面上，Z軸對應的就是模型高度。我們把XY平面抬高一定高度再與模型的表面相交，就可以得到模型在這個高度上的切片。所謂的分層就是每隔一定高度就用一個XY平面去和模型相交作切片，層與層之間的距離稱為層高。全部層高切完後就可以得到模型在每一個層上的輪廓線。就像是切土豆片一樣，把一個圓的或不圓的異或不管什麼奇形怪狀的土豆用菜刀一刀一刀切開，最後就能得到一盤薄如紙片的土豆片，當然那還得你的刀功要足夠好才行。
分層本質上就是一個把3D模型轉化為一系列2D平面的過程，自此之後的所有操作就都是在2D圖形的基礎上進行了。
在前面模型載入階段我說到了CuraEngine埋了一個三角形關聯的伏筆，作用是什麼，現在可以揭曉答案了。我們知道，兩個平面相交，得到的是一條直線，一個平面和一個三角形相交，就得到一條線段。當然也有可能什麼也得不到，平台平行啦，三角形的三個點都在平面的同一面之類。這些我們可以不管，我們現在只關心和平面有交集的那些三角形即可。我們把一個平面和所有的三角形都相交了一遍，得到了許許多多的線段。但是我們需要的是2D圖形，三角形是2D圖形，四邊形，任意多邊形都是2D圖形，而線段不是。所以我們就要把這些線段試著連成一個多邊形，那麼問題來了，要把這些線段連起來，只能兩個兩個地去試，看看它們是不是共端點。粗算一下，每一層都是平方級的復雜度，再算上層數，那就是三次方級。但現在，我們知道了三角形的關聯關系。兩個關聯的三角形，如果都與一個平面相交，那它們的交線一定也是關聯的。如此一來，每一條線段只需要判斷三個與它相鄰三角形，看看與這個平面有沒有交線即可，一下子就把問題的復雜度降了一個次元。速度自然可以有質的提升。
經過分層之後，我們得到了一疊2D平面圖形。接下來需要做的事情就是對每一層的平面圖形進行跑馬圈地，標記出哪裡是外牆、內牆、填充、上下表面、支撐等等。
圖形相交
二元圖形操作，最終結果為兩個圖形共同包含的區域。記作：A * B
二元圖形操作，最終結果為兩個圖形其中之一或兩者所包含的區域。記作：A + B
二元圖形操作，最終結果為屬於前者但不屬於後者的區域。記作：A - B
一元圖形操作，最終結果為圖形區域的邊界向外擴展指定的距離。
一元圖形操作，最終結果為圖形區域的邊界向內收縮指定的距離。內縮與外擴互為逆運算。
這些就是CuraEngine所用到的2D圖形操作。運算不多，卻可以做許許多多的事情。比如上面所說的上下表面計算，就可以用數學公式來表示：
表面(i) = [填充(i) - 層(i + n)] + [填充(i) - 層(i - n)]
填充(i) = 填充(i) - 表面(i)
其中，i為當前層號，n為上下表面層數（可以不一樣）。多簡單，數學就是這麼任性！
同樣的，組件裡面內外牆，填充怎麼劃分，只用一個內縮運算就可以搞定：
外牆 = 組件.offset(-線寬)
內牆1 = 組件.offset(-線寬 * 2)
...
內牆n = 組件.offset(-線寬 * (n + 1))
填充 = 組件.offset(-線寬 * (n + 2))
如果模型無需支撐，那組件劃分到這裡就可以收工了。否則，接下就是計算支撐的時間。
我用CuraEngine半年下來覺得它最大的不足就是在支撐上，這也是我在Pango投入最大精力要改進的地方，這裡就先簡單介紹一下CuraEngine所用的支撐算法。
CuraEngine首先把整個打印空間在XY平台上劃分成為200um*200um的網格。每個網格的中心點再延Z軸向上作一條直線，這條直線可能會與組成3D模型的三角形相交。三角形與直線的交點以及這個三角形的傾斜度會被記錄到網格裡面。
步驟四：路徑生成
步驟五：gcode生成
路徑都生成好了，還需要翻譯對打印機可以實別的gcode代碼才行。這一步花樣不多，按部就班即可。
先讓打印機做一些准備工作：歸零、加熱噴頭和平台、抬高噴頭、擠一小段絲、風扇設置。
從下到上一層一層打印，每層打印之前先用G0抬高Z坐標到相應位置。
按照路徑，每個點生成一條gcode。其中空走G0；邊擠邊走用G1，Cura的設置裡有絲材的直徑、線寬，可以算出走這些距離需要擠出多少材料；G0和G1的速度也都在設置裡可以調整。
若需回抽，用G1生成一條E軸倒退的代碼。在下一條G1執行之前，再用G1生成一條相應的E軸前進的代碼。
所有層都打完後讓打印機做一些收尾工作：關閉加熱、XY歸零、電機釋放。
生成gcode的過程中，CuraEngine也會模擬一遍打印過程，用來計算出打印所需要的時間和材料長度，這些也會寫在gcode的注釋裡供用戶參考。
待續
寫了這麼多，Cura的切片流程也只能講個大概，也算是個提綱，希望對大家有所幫助。我計劃對於上面的第一個步驟再專文分析。除此之外，還有Cura界面部分以及Cura與CuraEngine的通訊也可以講講。之後就是我半年創作，自我感覺良好到覺得可以超越Cura的Pango，也是不說不快的。
未完待續，敬請期待。
