三維迷宮的設(shè)計與制造

1、University of Science and Technology of ChinaA disserion for masters degreeDesign and Fabrication of 3D MazeAuthor :Kang WangSpelity :Compuional MathematicsSupervisor :Finished Time :Prof. Ligang LiuMay, 2016中國科學(xué)技術(shù)大學(xué)性本人所呈交的, 是本人在導(dǎo)師指導(dǎo)下進行工作所取得的成果。除已特別加以標注和致謝的地方外，中不包含任何他人已經(jīng)做的貢獻均已在或撰中作了寫過的成果。與我一同工作的對本明確

2、的說明。作者簽名：簽字日期：中國科學(xué)技術(shù)大學(xué)使用作為申請學(xué)位的條件之一，著作權(quán)擁有者中國科學(xué)技術(shù)大學(xué)擁有送交中國描等的部分使用權(quán)，即：學(xué)校按有關(guān)規(guī)定向國家有關(guān)部門或機構(gòu)的復(fù)印件和，允許被查閱和借閱，可以將編入全文數(shù)據(jù)庫等有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃保存、匯編。本人提交的電子文檔的內(nèi)容和紙質(zhì)的內(nèi)容相一致。的在后也遵守此規(guī)定。 公開 年作者簽名：導(dǎo)師簽名：簽字日期：簽字日期：摘 要摘要三維打印作為一種新興的制造技術(shù)，由于其突破傳統(tǒng)制造方式的局限，受到了越來越多的關(guān)注，并且有了越來越廣泛的應(yīng)用。在三維打印中，三維模型是基礎(chǔ)，在打印過起著決定性的作用；切片計算是三維打印中對模型處理的步驟

3、，直接影響打印結(jié)果的精度和效果。本文就三維模型和計算切片等三維打印中的基本問題展開。本文首先提出了一種基于二維迷宮和三維結(jié)構(gòu) (三維曲面) 的三維迷宮生成算法，主要通過 CSG 建模技術(shù)實現(xiàn)。傳統(tǒng)基于網(wǎng)格模型的切片算法存在效率低、誤差大等問題，而三維模型的隱式表達能夠顯著改善這些不足。在基于隱式函數(shù)的 3D 打印切片算法的基礎(chǔ)上，本文提出了一種面向 CSG 建模系統(tǒng)的 3D 打印切片算法。通過本文算法，可以在大幅減少處理時間的同時，模型精度也有所第一部分是三維迷宮的生成算法。迷宮是一類經(jīng)典且廣泛的益智玩具，迷宮的和設(shè)計在實際生活中有著廣泛的應(yīng)用前景。相對于二維迷宮，三維迷宮在難度和趣味性上達到

4、了一個更高的水平。本文主要是通過改進二維迷宮的隨機算法，提出了循環(huán)迷宮的概念和迷宮復(fù)雜度公式，進而提出了一種基于四邊形網(wǎng)格曲面的三維迷宮設(shè)計算法。該算法主要包括三個過程：首先將給定的三維曲面四邊形網(wǎng)格化；然后確定迷宮的起點和終點，通過基于最小生成樹的二維迷宮生成算法在網(wǎng)格表面生成迷宮路徑；最后，將迷宮實體化為三維結(jié)構(gòu)，并與原始三維模型做運算，得到三維迷宮。運算，是一種 CSG 建了是面向 CSG 建模系由于生成的迷宮是由大量的基本集合體通過模表達。為了避免進行三角化，生成三角網(wǎng)格，統(tǒng)的 3D 打印切片算法。隱式表達的三維模型有著三角網(wǎng)格不可替代的優(yōu)點，如表達能力強，運算簡便，沒有拓撲上的不正確

5、，如自交或等。這些優(yōu)點正是三維打印所需要的，并且是網(wǎng)格表達所不具備的。CSG 建模技術(shù)通過簡單體素的拼合構(gòu)造復(fù)雜幾何體。在計算機圖形學(xué)和 CAD 建模領(lǐng)域，CSG 建模技術(shù)經(jīng)常被用于實體建模。為了解決制造問題，基于隱式函數(shù)的 3D 打印切片算法，提出了面向 CSG 建模系統(tǒng)的 3D 打印切片算法，可以在大幅減少處理時間的同時，模型精度也有所。最后通過 3D，用算法生成的迷宮制造出個性化的三維迷宮玩具，大大增強了迷宮的趣味性和用戶體驗。： 三維打印，迷宮，實體建模，隱式函數(shù)，切片算法IABSTRACTABSTRACTAs a new kind of manufacturing technolog

6、y, 3D Pring hase more andhe limiion ofmore popular and been used in various fields due to its exceedingtraditional manufacturing method. 3D m, the foundation of 3D Pring, plays adecisive rolesing of 3D Prhe pring pros; slice calculation is the core step for mpro-ing re-ing, and directly affects the

7、preciand effect of the prsult.heof all, this pr proes a 3D maze generation algorithm based on thegiven 2D maze map and 3D structure(3D surface), mainly achieved by CSG mingtechnology. There are some problemslicing algorithm based on mesh expresch low efficiency and great error, and the implicit expr

8、esraditionalof 3D mcan significantly improves these weaknesses。In combination with the 3D Pring s-licing algorithm based on implicit expres, this pr presents a 3D pring slicingalgorithm for CSG mcan reduce the proing system based on slicing algorithm of implicit function. Its time dramatically and i

9、ncrease the preciwith our algorithm.Thepart is about the 3D maze generation algorithm research. Maze is a clas-sic and widespread educational toy, and the research and design of maze has a broadapplication prospect in real life. Compared to the 2D maze, 3D maze achieves a higherlevelerms of complexi

10、ty anderesting. By improving the random By improvingthe random generation algorithm of 2D maze, the concept of loop maze and the formulaof complexity of the maze are proedhis pr. Then the pr presents a 3Dmaze design algorithm based on the quadrilateral mesh surfa. This approaainlyconsist of three pr

11、ocedures:surface; second, the start po, the quadrilateral mesh is generated on the given 3Dand end poof the maze are chose alternatively, and themaze on the quadrilateral mesh surface is obtained by teration algorithm of 2Dmaze based on a minimum spanning tree algorithm; last, turn the mazeo 3D stru

12、c-ture, and 3D maze is generated by usingoperation betn the 3D structureand the original 3D m.Because the maze is generated by a large number of basic assembly constitutedwithoperations, it is an expresof CSG ming. In order to avoid tri-ing slicing algorithm forangulation which costs plenty of time,

13、 we studied a 3D prCSG ming system. The advantages of implicit expresof 3D ms, such as thestrong ability of expresare the key pos in 3D Pr, the simplicity of operation and the correctness of topology,ing which the mesh expreslacks. CSG ming sys-operatorstem allows a mer to create a complex surface o

14、r object by usingto combine objects.In computer graphics and CAD, CSG is often used in solid mIII-ABSTRACTing. In order to solve the problem of production,ut forward for 3D pring slicingalgorithm for CSG mcan reduce the proing system based on slicing algorithm of implicit function, Its time dramatic

15、ally and increase the preciwith our algorithm.Using this algorithm, severalalized 3D maze toys are made by 3D prer withconsumedly enhancederesting and user experience.Keywords:3D pring, maze, solid ming, implicit function, slicing algorithmIV目 錄目錄摘要 I III V 11122ABSTRACT 目錄 第一章 緒論 1.11.21.3引言 課題的背景及

16、意義 相關(guān)工作 1.3.1迷宮的相關(guān) 1.3.2二維迷宮的生成31.3.34三維迷宮的生成1.3.43D 打印技術(shù) 51.3.53D的工作流程 71.3.63D 打印的切片算法 89101.41.5本文的工作 本文的結(jié)構(gòu) 11111111第二章 三維迷宮的生成算法 2.1 三維迷宮的提出 2.2 二維迷宮的設(shè)計 2.2.1迷宮的表示及約束 基于最小生成樹的迷宮生成 循環(huán)迷宮 復(fù)雜度量化的迷宮 結(jié)果 2.2.2122.2.3142.2.4162.2.51718182.3 三維迷宮的設(shè)計 2.3.1算法概述 四邊形網(wǎng)格化 基于四邊形網(wǎng)格的迷宮設(shè)計 2.3.2182.3.320212.4 小結(jié) V目

17、 錄第三章 面向CSG 建模系統(tǒng)的 3D 打印切片算法 3.1 CSG 建模技術(shù) 23232425252627272931333435363737373840404042444545454749513.2 OpenSCAD介紹 3.2.1 基本幾何元素 3.2.2 基本變換 3.3 基于隱式函數(shù)的 3D 打印切片算法 3.3.1 Marching Sqaure 算法 填充結(jié)構(gòu)的生成支撐結(jié)構(gòu)的生成 3.4 基本幾何元素和基本變換的隱式函數(shù)表達 3.4.1 基本幾何體的隱式函數(shù)表達 3.4.2 基本幾何變換與隱式函數(shù) 3.5 基于CSG-Tree 的 3D 打印切片算法 3.6 小結(jié) 第四章 三維

18、迷宮的制造 4.1 用 OpenSCAD 表達三維迷宮 4.1.1 基于圓柱造型的迷宮玩具建模 4.1.2 基于球造型的迷宮玩具建模 4.1.3 基于任意曲面的迷宮玩具建模 4.2 實驗結(jié)果 4.2.1設(shè)計 4.2.2 打印結(jié)果展示 4.3 小結(jié) 第五章 總結(jié)與展望 5.1內(nèi)容的總結(jié) 5.2 未來工作的展望 參考文獻 致 謝 在讀期間的學(xué)術(shù)與取得的成果 VI第一章緒論第一章緒論1.1引言在所有的新興技術(shù)中，3D 打印被稱為是第四次工業(yè)的快速成型技術(shù)，3D 打印號稱將會引領(lǐng)“第四次工業(yè) 個世紀 90 年代中期，歷經(jīng)三十年的發(fā)展。第一代 3D 年代中后期，主要是以能夠打印模型為主。第二代 3D快速

19、成型發(fā)展到能夠打印高精度的功能性產(chǎn)品。的起點。作為新興”。3D 打印于上誕生于 20 世紀 80是在最近幾年由3D 打印技術(shù)是對傳統(tǒng)制造業(yè)的一次。與傳統(tǒng)制造業(yè)相比，3D 打印技術(shù)突破了設(shè)計與制造的局限性，讓一切設(shè)計都成為制造上的可能。傳統(tǒng)制造技術(shù)通過切割、拋光等減材技術(shù)制造模具，然后再利用模具實現(xiàn)批量生產(chǎn)。而 3D打印是一種增材制造技術(shù)，整個過程無需生產(chǎn)昂貴的模具，通過“一次成型”，大大降低了生產(chǎn)成本。在個性化定制等傳統(tǒng)制造的軟肋領(lǐng)域，3D 打印也有廣泛的應(yīng)用。1.2課題的背景及意義隨著計算機技術(shù)的發(fā)展以及互聯(lián)網(wǎng)的普及，數(shù)字滲入人類生活的各個，到，再到如今快速發(fā)展的 3D 技術(shù)，數(shù)字方面。從聲

20、音、通過影響人們的行為方式和思考方式深刻地影響著社會領(lǐng)域的發(fā)展，消費業(yè)和制造業(yè)都受到來自數(shù)字的強烈沖擊。伴隨著國際競爭的加劇，高新技術(shù)背景下的新型制造技術(shù)正在影響傳統(tǒng)的制造業(yè)。21 世紀是 3D 打展與崛起的時代，將 3D 打印應(yīng)用到現(xiàn)代制造業(yè)，促進產(chǎn)業(yè)升級和調(diào)整，創(chuàng)造巨大的利潤空間。而 3D 打印也將是未來制造業(yè)乃至其他行業(yè)的大勢所趨。面對大量的中國制造而非中國創(chuàng)造，中國需要全面提升創(chuàng)新能力。在此背景下，本文選擇了制造業(yè)中迷宮玩具的設(shè)計與制造。迷宮的和設(shè)計，在實際生活中有著廣泛的應(yīng)用前景。利用迷宮的復(fù)雜結(jié)構(gòu)設(shè)計防偽標識能夠極大提高標識防偽的能力；利用迷宮的結(jié)構(gòu)，在建筑和景觀設(shè)計中融入迷宮的風(fēng)

21、格，能夠產(chǎn)生別具一格的設(shè)計效果；在設(shè)計和二維流形的參數(shù)化中迷宮也有重要應(yīng)用。本文正是立足于此并且結(jié)合了個人。利用 CSG 建模技功生成三維迷宮模型。然后又結(jié)合 3D術(shù)，本文結(jié)合二維迷宮和三維結(jié)打印考慮模型的實際制造問題。切片計算是三維打印中對模型處理的步驟，是打印效果的重要影響之一。針對具體的三維迷宮模型的打印，考慮到 CSG 建模系統(tǒng)，本文提出了一種面向 CSG 建模系統(tǒng)的 3D 打印切片算法。通過本文算法，可以在大幅減少處理時間的同時，模型精度也有所。1第一章緒論1.3相關(guān)工作1.3.1迷宮的相關(guān)古今中外，不論神話還是現(xiàn)實世界，都能見到迷宮的身影。迷宮不僅擁有悠久的歷史也有深厚的文化內(nèi)涵。

22、迷宮建筑因為其中充斥的神秘主義令無數(shù)人著迷；迷宮因為廣泛性和趣味性深受各個層次的人喜愛，一直長久不衰；作為兒童學(xué)前教育的益智玩具，迷宮玩具更是備受家長青睞。因此，關(guān)于迷宮的與設(shè)計具有廣闊的應(yīng)用前景和實用價值，不少學(xué)者在迷宮的研究與設(shè)計領(lǐng)域做出過貢獻13。Phillips4了羅馬馬賽克式迷宮的拓撲，提出了一種迷宮重建理論，指出這個理論可以用于破損的迷宮重建和保存。McClendon5 提出了一種計算迷宮復(fù)雜度的方法，但是 McClendon 所的迷宮是一類更加廣泛的由曲線的迷宮。在迷宮的路徑曲線上定義連續(xù)函數(shù)，考慮路徑長度、極值點等復(fù)雜度的影響，利用連續(xù)化方法提出了計算曲線迷宮復(fù)雜度的公式。對在

23、迷宮設(shè)計方面，Xu 和 Kaplan 提出了一種生成帶有漩渦結(jié)構(gòu) (圖 1.1左圖)的復(fù)雜迷宮算法6，并設(shè)計基于圖像的迷宮算法7。系統(tǒng)通過擴展傳統(tǒng)的迷宮生成算法建立適應(yīng)圖像風(fēng)格的迷宮，并且遵從用戶指定的迷宮路徑。當然，用戶只能指定路徑的大致方向，不能具體設(shè)計路徑。由于沒有考慮生成迷宮的質(zhì)量，因此也沒有給出計算迷宮復(fù)雜度的方法。Hans 和 Karan 8 將圓形迷宮（labyrhine）和矩形迷宮（maze）這兩種類型的迷宮結(jié)構(gòu)綜合在一起，表示為二維流形上的曲線，提出了一種類迷宮結(jié)構(gòu)的自動生成算法 (圖 1.1右圖)。圖 1.1漩渦結(jié)構(gòu)的迷宮6（左圖）和帶有邊界的類迷宮組織8（右圖）迷宮的和設(shè)

24、計，在實際生活中有著廣泛的應(yīng)用前景。利用迷宮的復(fù)雜結(jié)構(gòu)設(shè)計防偽標識能夠極大提高標識防偽的能力；利用迷宮的結(jié)構(gòu)，在建筑和景觀設(shè)計中融入迷宮的風(fēng)格，能夠產(chǎn)生別具一格的設(shè)計效果；在維流形的參數(shù)化中迷宮也有重要應(yīng)用。設(shè)計和二2第一章緒論1.3.2二維迷宮的生成傳統(tǒng)隨機迷宮的生成是通過圖的遍歷算法實現(xiàn)的9。圖的傳統(tǒng)遍歷算法有兩種，深度優(yōu)先遍歷（DFS）和廣度優(yōu)先遍歷（BFS）。兩種算法都是通過迭代的方式對圖中的頂點按照“盡可能廣”或“盡可能深”的順序去遍歷。由于兩種算法都是一種通過邊找鄰接點的過程，因此兩種算法的時間復(fù)雜度相同。深度優(yōu)先遍歷可以概括為“能進則進，不進則退”。算法的具體步驟如下(圖 1.2

25、左圖)：step 1: 假設(shè)圖 G 中所有的頂點都未曾被，任意選擇某個頂點 v 作為遍點；歷的起點，頂點 v，將此頂點作為當前step 2: 依次將此頂點作為當前v 的所有鄰接點，如果未被點。按照這種方法繼續(xù)過，則選擇該頂點并下去，如果某個頂點的所有鄰接點都被過，則退回上一層，換一個鄰接點繼續(xù)，直到圖 G 中和頂點 v 有路徑連接的頂點都被到；step 3: 若圖 G 中還有頂點沒有被，則在剩下未被的頂點中任意選擇一個頂點作為當前點，重復(fù)上述操作，直到圖G 的所有頂點都被到。圖 1.2深度優(yōu)先遍歷（左圖），遍歷點的順序為：V1-V2-V4-V8-V5-V3-V6-V7；廣度優(yōu)先遍歷（右圖），遍

26、歷點的順序為：V1-V2-V3-V4-V5-V6-V7-V8。廣度優(yōu)先遍歷可以概括為“逐層擴展”。算法的具體步驟如下 (圖 1.2右圖)：step 1: 假設(shè)圖 G 中所有的頂點都未曾被，任意選擇某個頂點 v 作為遍歷的起點，step 2:頂點 v；v 的所有鄰接點，依次其中未被過的鄰接點。然后分過的頂點。按照逐層擴別從這些鄰接點出發(fā)依次它們的鄰接點中未被展的原則繼續(xù)，直到圖 G 中和 v 有路徑連接的頂點都被到；的點中任意選擇step 3: 若圖 G 中還有頂點沒有被，則在剩下未被一個頂點作為新的起點，重復(fù)上述操作，直到圖 G 的所有頂點都被到。3第一章緒論在圖論里，不含圈的連通圖被稱為樹。

27、二維迷宮可以看作初始狀態(tài)迷宮的生成樹。這樣就建立起迷宮與圖之間的對應(yīng)關(guān)系，可以用圖的理論來迷宮。通過深度優(yōu)先遍歷 (DFS) 或廣度優(yōu)先遍歷 (BFS)，都可以構(gòu)建出圖的生成樹，當然也可以用來生成迷宮。本課題中采用深度優(yōu)先遍歷算法 (圖 1.3)。圖 1.3利用深度優(yōu)先遍歷算法生成的迷宮1.3.3三維迷宮的生成作為益智玩具的經(jīng)典款式之一，迷宮玩具一直是老少皆宜的一類玩具。玩家通過迷宮玩具可以鍛煉判斷力和力，培養(yǎng)耐心和對時空的感知能力，把握整體與局部的關(guān)系。但是自從迷宮玩具問世以來，一直都保持經(jīng)典的玩具形式，市場上的迷宮玩具幾乎都是基于平面造型的形態(tài) (圖 1.4)。圖 1.4基于平面造型的迷宮

28、玩具（來源：htt/）隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，三維數(shù)據(jù)成為繼聲音、圖像和視頻之后更高級的數(shù)字類型，能夠準確地刻畫現(xiàn)實世界。將迷宮由二推廣到三，無疑增加了迷宮的難度，同時也增加迷宮的性，提4第一章緒論高了迷宮的趣味性與可玩性，對玩家空間想象能力的培養(yǎng)大有裨益。然而對于三維迷宮，鮮有學(xué)者做過深入的和。一些玩具設(shè)計者通過在多面體上設(shè)立擋板，擋板之間迷宮的通道，而多面體的各個面之間通過迷宮的通道相互連通，形成如圖 1.5圖所示的迷宮。雖然出現(xiàn)過不少三維迷宮的設(shè)計方案，但是在制造領(lǐng)域，鮮有三維迷宮實現(xiàn)批量生產(chǎn)，也尚未出現(xiàn)專門的三維迷宮設(shè)計。因為大部分三維迷宮的設(shè)計方案與生產(chǎn)實際之間存在差距。

29、一方面，三維迷宮的設(shè)計難度遠遠高于二維迷宮，設(shè)計者需要在三中構(gòu)思迷宮的三維結(jié)構(gòu)；另一方面，三維迷宮的設(shè)計難度也決定了迷宮的難度，復(fù)雜的三維結(jié)構(gòu)超過玩家的理解能力范圍。圖 1.5兩種迷宮的設(shè)計方案? 本文結(jié)合二維迷宮生成和 3D 建模技術(shù)，將二維迷宮嵌入到三維模型表面，得到三維迷宮。利用 3D 打印，用算法生成的迷宮制造出個性化的三維迷宮玩具，大大增強了迷宮的趣味性和體驗性。1.3.43D 打印技術(shù)人類剛剛步入的 21 世紀，一種綠色制造技術(shù)迅速吸引公眾的眼球，這就是3D 打印。3D 打印的崛起，引領(lǐng) 21 世紀新一輪數(shù)字化制造浪潮。稱 3D 打印是工業(yè)的升級版，將會改變大自然的制造方式12。英

30、國經(jīng)濟學(xué)3D 打印，稱 3D 打印將引領(lǐng)第三次工業(yè)13。3D 打印人雜志專題于上個世紀 90 年代中期，目的是拋棄傳統(tǒng)工廠流水線的生產(chǎn)模式，通過 3D 打印機打印出三維3D 打印（3D pr實物 (圖 1.6)。ing），又稱增材制造技術(shù)（Additive Manufacturing, AM），快速成型（RaPrototy）、分層制造（Layered Manufacturing）。普通的 2D，如噴墨的打印原理是利用噴嘴噴出的細小墨滴組成圖像中的像5第一章緒論圖 1.6Makerbot 公司制造的 3D(來源：./)素，不同噴嘴噴出的墨滴顏色不同，因此可以組成色彩多樣的圖像。與 2D 打印原理

31、類似，3D 打印是以三維數(shù)字模型文件為藍本，將特定的打印材料，如塑料、粉末、絲、片、板等逐層推積，或再黏合疊加，形成最終產(chǎn)品。傳統(tǒng)制造技術(shù)是采用切、削、鉆孔等去除多余材料得到最終產(chǎn)品，是一種“減材”制造方式。相比傳統(tǒng)制造技術(shù)，3D 打印是將模型一層層打印出來的，是一種典型的“經(jīng)濟節(jié)約型技術(shù)”，主要有下列特點：（1）縮短研制周期3D 打印只需要數(shù)字模型文件就能打印實物，舍棄傳統(tǒng)制造業(yè)中模具制作的工序，從而極大地縮短了產(chǎn)品的研制周期，能夠大幅度提高生產(chǎn)率。（2）降低制造成本與傳統(tǒng)制造業(yè)相比，3D 打印能夠有效地降低制造成本。第一，生產(chǎn)產(chǎn)品不需要在工廠進行，節(jié)約了廠房的成本。第二，由于摒棄傳統(tǒng)的加工

32、方式而減少原材料的浪費，從而降低材料成本。（3）實現(xiàn)個性化定制3D依賴的是數(shù)字模型文件，因此打印之前需要用戶設(shè)計出 3D 模型，用戶可以根據(jù)個人需要，設(shè)計出個性化的產(chǎn)品，同時又可以根據(jù)既有的 3D 模型實現(xiàn)批量生產(chǎn)，這是傳統(tǒng)制造業(yè)難以實現(xiàn)的。（4）應(yīng)用領(lǐng)域廣泛更短的生產(chǎn)周期、制造更為復(fù)雜幾何形狀以及降低制造成本的能力，使得 3D 打印可應(yīng)用的行業(yè)逐步擴大，涉及經(jīng)濟，文化，軍事，教育等諸多領(lǐng)域。只要這些行業(yè)需要模型和原型，3D 打印技術(shù)就可以得以應(yīng)用。6第一章緒論1.3.53D的工作流程目前 3D是熔融沉積成型中技術(shù)最為成熟應(yīng)用最廣的是 FDM。FDM的簡稱。FDM工作時，先將各種熱熔型的絲材，

33、ABS、聚碳酸酯 PC 等加熱融化，同時由三維噴頭噴出，逐層堆積如工程成三維實體模型。整個過程在計算機的控制之下，以數(shù)字模型文件為基礎(chǔ)。從設(shè)計模型到打印模型，3D的工作流程主要分為以下幾步 (圖 1.7)：的工作流程14圖 1.73D（1）三維模型設(shè)計。三維模型的獲取主要通過兩個途徑：建模和掃描建模是指通過三維建模如 Maya、SolidWorks 等，用戶根據(jù)需求重建。自行構(gòu)建三維模型。掃描重建是指通過三維掃描設(shè)備，如結(jié)構(gòu)光掃描儀、激光掃描儀等獲取點云數(shù)據(jù)，然后通過算法重建出三維模型。（2）格式轉(zhuǎn)換為 STL 文件。STL 文件格式（stereo lithography，光立體造型術(shù)的縮寫）

34、是一種為快速原型制造技術(shù)服務(wù)的三維圖形文件格式。STL文件由多個三角形面片的定義組成，每個三角形面片的定義包括三角形各個定點的三維坐標及三角形面片的法矢量。STL 是 3D 打印業(yè)內(nèi)的標準文件類型，因此需要將三維模型文件轉(zhuǎn)化為 STL 格式文件，才能用 3D進行打印。（3）計算切片。3D 打印實際上是逐層進行的，這就需要事先對三維模型進行數(shù)字切片。將模型沿高度方向 (三維坐標中的 z 方向) 離散化，分為若干層，每一層用以切面為底面、本層厚度為高度的柱體近似表示。切片是三維打印中對模型處理的步驟，切片算法將在下一小節(jié)介紹。目前主要的切片有Cura、makerwat、slic3r。（4）規(guī)劃打印

35、路徑。切片所得到薄層反映著打印物體的一個橫截面。所謂路徑是打印噴頭在不同的組件中的運動軌跡。路徑按大類來分，有輪廓和填充兩種。同樣的一組切片，不同的打印路徑得到的打印效果也不一樣。因此，需要規(guī)劃出具體的打印路徑，并對其進行合理的優(yōu)化，以得到更快更好的切片打印效果。7第一章緒論（5）打印三維模型。根據(jù)上述計算的切片及規(guī)劃的打印路徑逐層進行打印，將所打印的切片薄層累計疊加，最終形成三維實體。1.3.63D 打印的切片算法由上節(jié)可知，3D 打印實質(zhì)上是打印材料逐層累加的過程，切片是三維打印中對模型處理的步驟。切片過薄會導(dǎo)致大量的時間消耗，甚至?xí)?dǎo)致打印機無法正常打印；切片過厚則會產(chǎn)生較大誤差，導(dǎo)致打

36、印的模型表面呈現(xiàn)鋸齒狀，打印效果差。如何在保證打印效率的同時得到更好的打印效果，這就導(dǎo)致了 20 世紀九十年代切片算法的飛速發(fā)展。目前的切面算法主要分成兩大類：網(wǎng)格切片算法和直接切片算法。在自適應(yīng)的切片過，切片的厚度是由網(wǎng)格模型的幾何形狀和用戶指定的最大可允許的尖頂高度確定的。1994 年，Dolenc 和 Makela 15 提出了最大可允許的尖頂高度的概念，隨后這一概念被廣泛應(yīng)用于切片的計算。切片的厚度由尖頂高度 c 和邊界處頂點的法向決定，尖頂高度是通過用戶指定的最大可允許的尖頂高度Cmax 確定。設(shè)法向為N(Nx, Ny, Nz)切片的厚度CmaxNzt0Nz如果t tmax, ttm

37、ax 主要算法如下：（1）逐步一致細化16逐步一致細化的切片算法是首先將網(wǎng)格模型劃分成一致的水平切片，且厚度等于用戶指定的最大可允許的薄層厚度tmax 然后對那些不滿足尖頂高度要求：c 1 時，表示支還存在多階支路，此時計算多階支路的復(fù)雜度會多一個權(quán)重 i，這表明隨著支路階數(shù)的增大，對整個迷宮的復(fù)雜度影響不僅僅是簡單的復(fù)雜度疊加，而是影響越來越大?？紤]圖 2.10中擁有二階支路的支路，其一階支路的長度為 6，拐點為C1,1 C1,2 C1,3 C1,4 間距分別為 2，2，2，二階支路長度為 4，拐點為C2,1 C2,2 C2,3 間距分別為 2，2，因此6662 42 4+Branch(B

38、)17222222設(shè) S 是迷宮 M 的主路徑，B1 B2 B3, . Bn 分別是 S 上的 n 條支路，定義迷宮 M 的復(fù)雜度為所有支路的復(fù)雜度之和，因此，定義整個迷宮的復(fù)雜度函16第二章三維迷宮的生成算法數(shù)為：nComplexity(M)Branch()Bii=1計算圖 2.10中的迷宮復(fù)雜度：2217Branch(B1)Branch(B2) Branch(B3)Branch(B1)16 + 6 + 6 + 611.71542313因此，迷宮的復(fù)雜度為：Complexity(M)1 + 17 + 11.7 + 130.7圖 2.10影響迷宮復(fù)雜度的相關(guān)（圖中迷宮為非循環(huán)迷宮）2.2.5結(jié)

39、果圖圖 2.11顯示了三種設(shè)計風(fēng)格的二維迷宮：隨機迷宮、循環(huán)迷宮及定制迷宮，紅色表示由迷宮起點到迷宮終點的主路徑。隨機迷宮是傳統(tǒng)迷宮生成算法實現(xiàn)的，循環(huán)迷宮和定制迷宮是通過迷宮生成算法實現(xiàn)的。通過對比，可以看出，定制迷宮能夠產(chǎn)生較好的路徑形狀，循環(huán)迷宮的左右兩側(cè)可相互連通。圖圖 2.12展示了三種復(fù)雜度的平面迷宮，根據(jù)復(fù)雜度公式，圖的迷宮復(fù)雜度是 0，圖的迷宮復(fù)雜度是 24，圖的迷宮復(fù)雜度是 33。17第二章三維迷宮的生成算法圖 2.11(a) 是基于傳統(tǒng)迷宮生成算法實現(xiàn)的隨機迷宮；(b) 是本文循環(huán)迷宮算法生成的循環(huán)迷宮，左右兩側(cè)是連通的；(c) 是交互系統(tǒng)結(jié)合用戶交互生成的迷宮，用戶可以自

40、行設(shè)計迷宮的主路徑，支路部分由系統(tǒng)隨機生成。圖 2.12復(fù)雜度分別為 0,24,33 的迷宮圖2.3三維迷宮的設(shè)計2.3.1算法概述三維模型最常見的表示方式是網(wǎng)格，不論是三角網(wǎng)格、四邊形網(wǎng)格，還是六邊形網(wǎng)格，網(wǎng)格所表達的三維模型都具有點、線、面等基本的數(shù)據(jù)結(jié)構(gòu)。三維模型的網(wǎng)格具有圖的特征，是一張三中的圖。因此，通過圖導(dǎo)出其最小生成樹，就能在三維模型的網(wǎng)格上生成迷宮。三維迷宮的設(shè)計在理論上是可行的。對于給定的三維模型，設(shè)計三維迷宮算法流程如圖 2.13所示。二維迷宮實體化是將迷宮由二維結(jié)構(gòu)轉(zhuǎn)化為三維結(jié)構(gòu)，這樣做的目的是為了用二維迷宮與三維模型三維迷宮。三維迷宮的方法是通過迷宮與三維模型之間的差運

41、算實現(xiàn)的。如圖 2.14所示，差運算實際上就是從原始三維模型中減去二維迷宮得到三維迷宮。2.3.2四邊形網(wǎng)格化網(wǎng)格是表示三維模型最簡單有效的方式 (圖 2.15)，三維模型網(wǎng)格化也是研究三維模型基礎(chǔ)性的一步，三維模型網(wǎng)格化的好壞會直接影響后續(xù)工作的結(jié)果。18第二章三維迷宮的生成算法圖 2.13三維迷宮設(shè)計流程圖圖 2.14三維迷宮設(shè)計示意圖: (a) 中的圓柱模型與 (b) 中的實體化二維迷宮做到 (c) 中的三維迷宮。差運算得因此，需要針對不同的問題選擇不同的網(wǎng)格化方式。在本文中，模型的四邊形網(wǎng)格化，主要是基于以下考慮：選擇三維高質(zhì)量的四邊形網(wǎng)格相對于和較好的收斂性27；四邊形網(wǎng)格更符合二維

42、迷宮的特征，因此生成的二維迷宮也具有較好的外觀。度相同的三角形網(wǎng)格，具有更精確的解圖 2.15三維模型的四邊形網(wǎng)格化: (a) 為三維網(wǎng)格曲面；(b) 為生成的四邊形網(wǎng)格。四邊形網(wǎng)格化自上個世紀八十年代成為的熱點，算法雖不及三角網(wǎng)格化成熟，但是也涌現(xiàn)出許多算法。根據(jù)生成原理，四邊形網(wǎng)格化大致可以分為19第二章三維迷宮的生成算法直接方法和間接方法。直接方法就是在給定的幾何區(qū)域上直接生成四邊形網(wǎng)格，間接方法就是通過三角網(wǎng)格轉(zhuǎn)化為四邊形網(wǎng)格。四邊形網(wǎng)格可以看成是特殊的三角網(wǎng)格，因為可以將一個四邊形沿對角線分成兩個三角形。但是，反過來卻不一定成立。Lo? 提出了通過移除三角網(wǎng)格之間的對角線，將兩個三角

43、形變成一個四邊形的方法。這是一個相對簡單的合并方法，但是由于相鄰的兩個三角網(wǎng)格之間不一定能夠四邊形，也可能同一個三角形能與多個相鄰三角形網(wǎng)格又有四邊形網(wǎng)格的混合網(wǎng)格。四邊形，因此最終得到了一個既有三角形2.3.3基于四邊形網(wǎng)格的迷宮設(shè)計四邊形網(wǎng)格的結(jié)構(gòu)為隨機迷宮的生成提供了便利。在使用二維迷宮生成算法之前，首先要獲取四邊形網(wǎng)格中的所有頂點的領(lǐng)域信息。除邊界外，四邊形網(wǎng)格頂點的鄰接點個數(shù)都為 4。為了避免麻煩，本文僅考慮在四邊形網(wǎng)格內(nèi)部生成迷宮。然后需要指定迷宮的起點和終點，通過基于最小生成樹的二維迷宮生成算法，在四邊形網(wǎng)格表面生成二維迷宮，如圖 2.16所示。算法具體過程已詳述，這里不再重復(fù)。

44、文為了建立三維迷宮，需要將二維迷宮實體化。本文采用的二維迷宮實體化方式是用圓柱代替迷宮中相鄰兩點之間的路徑。圓柱滿足條件如下：圓柱的高度等于兩頂點之間的距離；圓柱的上下兩個底面分別以相鄰兩頂點為圓心；圓柱之間按照頂點順序依次連接。圖 2.16基于四邊形網(wǎng)格的迷宮設(shè)計: (a) 在四邊形網(wǎng)格上選取兩點作為起點和終點；(b) 隨機生成連接起點和終點的一條主路徑；(c) 在主路徑基礎(chǔ)上生成迷宮的其他支路面；(d) 不斷重復(fù)面 (c) 最終得到完整的迷宮。20第二章三維迷宮的生成算法2.4小結(jié)了三維迷宮的生成算法。結(jié)合二維迷宮生成和 3D 建模技術(shù)，迷宮的設(shè)計，本章提出一種新的三維迷宮設(shè)計思路：即將二

45、維本章主要借鑒已有的迷宮嵌入到在三維模型表面，得到三維迷宮。不同于二維迷宮，三維迷宮對迷宮的設(shè)計具有的約束，如循環(huán)迷宮；出于用戶交互系統(tǒng)的需求，應(yīng)該為用戶提供迷宮路徑可控的生成算法，即定制迷宮；考慮如何評估生成迷宮的有效性，需要對迷宮的復(fù)雜度量化。本章首先了二維迷宮的生成算法。通過對傳統(tǒng)的二維迷宮生成算法進行改進，生成能夠設(shè)計出三維迷宮的平面迷宮；然后通過二維迷宮嵌入到在三維模型表面，提出三維迷宮的生成算法，同時也給出了循環(huán)迷宮和路徑可控迷宮的設(shè)計方法。21第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法3.1CSG 建模技術(shù)CSG（Co

46、nstructive solid geometry）建模技術(shù)，即實體幾何構(gòu)造技術(shù)，是實體建模的一種。所謂實體建模，是指通過簡單體素的拼合構(gòu)造復(fù)雜幾何體。CSG 建模技術(shù)利用一些基本體素，如長方體、圓柱體、球體、錐體、圓環(huán)體以及掃描體、放樣體、旋轉(zhuǎn)體、拉伸體等，通過集合運算（拼合或運算，如求和、求差、求交）生成復(fù)雜形體。CSG 建模技術(shù)往往能夠創(chuàng)造非常復(fù)雜的曲面和幾何體，實際上都是通過基本幾何體之間的巧妙組合。如圖 3.1 所示。與其他建模技術(shù)相比，實體模型存在許多不同的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)不僅了全部的幾何信息，而且還了所有的點、線、面、體的拓撲信息，它能完整地表示物體的所有形狀信息，可以無歧

47、義地確定一個點是在物體外部、內(nèi)部或表面上，能夠進一步滿足物性計算、有限元分析等應(yīng)用的要求。圖 3.1CSG-Tree 表示復(fù)雜幾何體的建模過程（來源：）在計算機圖形學(xué)和 CAD 建模領(lǐng)域，CSG 建模技術(shù)通常被用于過程建模（procedural ming），主要應(yīng)用于多邊形網(wǎng)格。它是目前最常見、最重要的方法之一。CSG 建模技術(shù)中最重要的兩個概念是基本幾何體和運算。用來表示復(fù)雜幾何體的最簡單幾何體被稱為基本幾何體，常見的有：長方體、圓柱體、球體、錐體、圓環(huán)體以及旋轉(zhuǎn)體；基本幾何體和多個基本幾何體之間可以通過運算得到新的幾何體，這些運算主要有：單個基本幾何體的平移、旋轉(zhuǎn)、縮放等或多個基本幾何體幾

48、何體之間的運算，如求和、求差、求交。23面向 CSG 建模系統(tǒng)的 3D 打印切片算法第三章用 CSG 表示一個物體可用二叉樹的形式加以表達， 稱為 CSG Tree。 CSG-Tree 的葉子分為兩種，就是上文提到的基本幾何體和運算。CSG 表示的優(yōu)點有：數(shù)據(jù)量小，數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)管理容易；可以方便地轉(zhuǎn)換成邊界表示；形狀比較容易修改。CSG 表示的缺點有：表示形體的覆蓋域有較大的局限性，受基本幾何體和運算限制；局部操作不蓉易實現(xiàn)；顯示與繪制 CSG 表示的形體需要較長的時間。3.2OpenSCAD介紹OpenSCAD(圖 3.2)。Open-在本課題中選用的建模是一款開源的小SCAD 是一款

49、用于構(gòu)建實體 CAD 模型的建模。OpenSCAD 不是一個交互建模。相反，它是在文件中描述對象，并呈現(xiàn)文件中描述的 3D 模型，因此整個建模過程，用戶完全掌握著控制權(quán)，可以輕松地更改任何步驟在建模過，甚至設(shè)計所定義的配置參數(shù)。OpenSCAD 對計算機配置要求很低，安裝文件小巧，但功能卻是非常強大。與其他建模著特點：相比，OpenSCAD 有如下顯圖 3.2OpenSCAD界面（來源：）（1）使用語言描述 3D 模型不同于 3DS Max 和 Maya 等，OpenSCAD 不要求用戶掌握繁瑣復(fù)雜的作，取而代之的是簡單的 OpenSCAD 語言。通過 OpenSCAD 的 言描述對象，編譯成

50、功之后呈現(xiàn) 3D 模型，這是 OpenSCAD 區(qū)別其他建模24語第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法的最大特點。通過程序設(shè)計語言進行 3D 建模，用戶可以更加精確地描述 3D模型。（2）操作簡單，使用方便與 3DS Max 和 Maya 相比，OpenSCAD 是一款非常小的，安裝簡單，攜帶方便。由于 OpenSCAD 的非交互性，OpenSCAD 沒有復(fù)雜的交互界面。同時，OpenSCAD 所使用的（3）支持命令行處理OpenSCAD 不僅可以用作一個圖形用戶界面，還可以處理命令行。這一優(yōu)語言非常精簡，入門簡單。點可以將 OpenSCAD 用于 3D 建模界面（GUI）應(yīng)用

51、程序。的開發(fā)，編寫與 3D 模型有關(guān)的圖形用戶3.2.1基本幾何元素二本幾何體 (圖 3.3) 主要有：圓：circle(r=radius)正方形 square(size,center)長方形 square(width,height,center)多邊形 polygon(pos,paths)三本幾何體主要有：正方體 cube(size, center)長方體 cube(width,depth,height, center)球 sphere(r=radius)橢球 resize(x,y,z) sphere(r=radius)；圓柱 cylinder(h,r,center)圓臺 cylinder(

52、h,r1,r2,center) r2=0 表示圓錐多面體 polyhedron(pos, triangles, convexity)3.2.2基本變換單個幾何體的基本變換 (圖 3.4) 主要有：平移：translate(x,y,z)旋轉(zhuǎn)：roe(x,y,z)比例縮放：scale(x,y,z)更改大?。簉esize(x,y,z,auto)鏡面：mirror(x,y,z)多個幾何體之間的基本變換主要是聯(lián)合：union()求差：difference()求交： ersection()運算：25第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法圖 3.3OpenSCAD 中的基本幾何體：二維幾何體（

53、左圖）和三維幾何體（右圖）圖 3.4OpenSCAD 中的基本變換：鏡面變換（左圖）和運算（右圖）3.3基于隱式函數(shù)的 3D 打印切片算法三維模型有多種表達方式，如網(wǎng)格表達、參數(shù)表達、隱式表達等。網(wǎng)格表達是通過點、線、面等來描述模型與曲面，是一種離散的表達方式。常用的有三角網(wǎng)格、四邊形網(wǎng)格等。參數(shù)表達是指用一系列以參數(shù)為自變量的函數(shù)來計算曲面上點的位置的方法，如 NURBS 等。隱式表達是指通過一系列的隱函數(shù)fi(x, y, z) 6 0 以及交、并、補等運算所確定的曲面。在上述三種表達方式中，隱式表達是最適合三維打印的。一方面，隱式表達的能力強，運算簡便，沒有拓撲上的不正確。其次，隱式曲面可

54、以計算法向并十分簡單地區(qū)分模型內(nèi)外，便于 模型的處理。最后，在 FDM 型的三維打印中，打印噴頭所走的路徑主要是切面的輪廓，也就是說移動方向與曲線切線方向相同，而這則是隱式曲面比起其它表示方式所具有的優(yōu)勢之一。其他兩種表達方式都會導(dǎo)致處理時間增長，產(chǎn)生較大的誤差。本節(jié)主要介紹基于隱式函數(shù)的 3D 打印切片算法中最主要的三個算法：切片26第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法輪廓查找算法、填充結(jié)構(gòu)的生成算法和支撐結(jié)構(gòu)的生成算法。Marching Sqaure算法是最目前使用最廣泛的切片輪廓查找算法。3.3.1Marching Sqaure 算法隱式表達模型f(x, y, z) 6

55、0在高度 z0 處與平面 z=z0 的交線為f(x, y, z0)0 將其視為 (x, y) 的二維函數(shù)，即為模型在此高度的輪廓。輪廓的查找算法可以使用 Marching Square 算法(圖 3.5)。圖 3.5Marching Squire 算法示例Lorensen 和 Cline 提出過三維模型的 Marching Cube 算法29。與之類似，二維平面也有 Marching Square 算法。算法的是用相互正交的兩組等距直線 (稱為網(wǎng)格線) 將平面均勻的分為若干網(wǎng)格，對每個小方格的四個頂點處的函數(shù)值進行計算來曲線在此方格中的形態(tài)。例如在小方格內(nèi)使用直線或折線來近似表示曲線在小方格內(nèi)

56、的形態(tài) (圖 3.6).3.3.2填充結(jié)構(gòu)的生成為保證所打印出的模型有足夠的強度，內(nèi)部填充是必不可少的。填充的生成與輪廓的查找算法類似，均是將某一切片所在平面離散為網(wǎng)格進行計算。現(xiàn)階段，成 切片引擎所生成的填充方式大同小異：一是以 Makerware 為代表27第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法圖 3.6使用 Marching Squire 算法近似表示曲線的六邊形 (圖 3.7左圖) 填充；二是以 Cura 為代表正方形 (圖 3.7 左圖) 填充?？紤]到填充的具體方式并不會過多地影響到模型的強度，而六邊形填充則會要求更復(fù)雜的算法，更長的處理時間，因此正方形填充。選擇采用與

57、 Cura 相同的填充模式 圖 3.7兩種填充模式正方形填充模式是指各層切片交替單向填充，即奇數(shù)層打印 x 方向上的等距直線作為填充，偶數(shù)層打印 y 方向上的等距直線填充 (反之亦可)，為填充線。這樣，整體就會以正方形的模式進行填充。稱之在某一切片所在平面上，希望能夠生成對應(yīng)的填充。與查找輪廓線算法相似，(亦稱為網(wǎng)格線) 分為若干方格。對于固定的切片，填充線的方向是固定的。不妨設(shè)填充線的方向為 y 方向，即與 y 軸平行。這樣，此層上的填充線一定在 y 方向的網(wǎng)格線上。而填充線決定了模型的填充率，因此網(wǎng)格線可以由填充率決定。顯然，當網(wǎng)格線間的距離為 L 時，填充率大概為 。L確定好兩條網(wǎng)格線之

58、間的距離，也就是填充線之間的距離后，則需要確定每條填充線的起止點。顯然，填充線應(yīng)該在模型內(nèi)部，且與外殼相接，因此起止點應(yīng)由外殼的位置與層數(shù) (也就是厚度) 共同決定。對于每一條 y 方向的網(wǎng)格線，首先計算網(wǎng)格線上的格點是否在模型內(nèi)部且不在外殼的范圍內(nèi)。這樣就可以確定出網(wǎng)格線上的格點是否屬于填充線，同時28第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法也就確定出了填充線起止點大致的位置。確定出起止點大致范圍后，可以采用二分法精細化起止點位置。也可以用隱函數(shù) y 方向上的一階偏導(dǎo)與 Sampson 距離來估計。這樣，填充線就可以完全確定下來了 (圖 3.8)。圖 3.8生成填充的算法3.3.

59、3支撐結(jié)構(gòu)的生成支撐算法包括內(nèi)部支撐和外部支撐算法。內(nèi)部支撐當模型在某層切片處過于平坦時，如球形的頂部，會導(dǎo)致相鄰的切片形狀與本層切片形狀相差較大，從而會導(dǎo)致外表并不連續(xù)，漏出模型的內(nèi)部等瑕疵 (圖 3.9)。一般來說，切片引擎會采取內(nèi)部關(guān)鍵部分全填充的方法來避免這種情況。大部分切片引擎所采取的填充方式是用直線填充 (圖 3.10)。外部支撐許多模型都會有懸空部分，而三維打印的順序是從低到高，打印懸空部分時則必須有一個支點。模型的外部支撐所起到的作用便是如此。因此，判斷一個點是否需要支撐，其標準就是模型表面某點處的法向是否與 z 軸負方向接近 (圖 3.11)。在圖中，P = (x,y,z)，

60、則有29面向 CSG 建模系統(tǒng)的 3D 打印切片算法第三章圖 3.9無內(nèi)部支撐導(dǎo)致的瑕疵圖 3.10生成多層外殼f(P)0nf(P)nz 0n (0,0,1)nzn cos cos n 若min 為需要支撐的臨界值，則有nzcos min cos n如果判斷出某點需要支撐，則顯然有此點以下，或模型表面某點以上全部需要打印。最后，在切片過，給定一個切片，通過和預(yù)處理結(jié)果求交，確定出平面上的那些點需要打印支撐。與內(nèi)部填充的模式相似，采用的也是正方形網(wǎng)格式的支撐。通過分層打印相互正交的直線來外部支撐。30第三章 面向 CSG 建模系統(tǒng)的 3D 打印切片算法圖 3.11支撐的判定與生成支撐的預(yù)處理同樣