三维迷宫的设计与制造

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中国科学技术大学性本人所呈交的, 是本人在导师指导下进行工作所取得的成果。除已特别加以标注和致谢的地方外，中不包含任何他人已经做的贡献均已在或撰中作了写过的成果。与我一同工作的对本明确

2、的说明。作者签名：签字日期：中国科学技术大学使用作为申请学位的条件之一，著作权拥有者中国科学技术大学拥有送交中国描等的部分使用权，即：学校按有关规定向国家有关部门或机构的复印件和，允许被查阅和借阅，可以将编入全文数据库等有关数据库进行检索，可以采用影印、缩印或扫保存、汇编。本人提交的电子文档的内容和纸质的内容相一致。的在后也遵守此规定。 公开 年作者签名：导师签名：签字日期：签字日期：摘 要摘要三维打印作为一种新兴的制造技术，由于其突破传统制造方式的局限，受到了越来越多的关注，并且有了越来越广泛的应用。在三维打印中，三维模型是基础，在打印过起着决定性的作用；切片计算是三维打印中对模型处理的步骤

3、，直接影响打印结果的精度和效果。本文就三维模型和计算切片等三维打印中的基本问题展开。本文首先提出了一种基于二维迷宫和三维结构 (三维曲面) 的三维迷宫生成算法，主要通过 CSG 建模技术实现。传统基于网格模型的切片算法存在效率低、误差大等问题，而三维模型的隐式表达能够显著改善这些不足。在基于隐式函数的 3D 打印切片算法的基础上，本文提出了一种面向 CSG 建模系统的 3D 打印切片算法。通过本文算法，可以在大幅减少处理时间的同时，模型精度也有所第一部分是三维迷宫的生成算法。迷宫是一类经典且广泛的益智玩具，迷宫的和设计在实际生活中有着广泛的应用前景。相对于二维迷宫，三维迷宫在难度和趣味性上达到

4、了一个更高的水平。本文主要是通过改进二维迷宫的随机算法，提出了循环迷宫的概念和迷宫复杂度公式，进而提出了一种基于四边形网格曲面的三维迷宫设计算法。该算法主要包括三个过程：首先将给定的三维曲面四边形网格化；然后确定迷宫的起点和终点，通过基于最小生成树的二维迷宫生成算法在网格表面生成迷宫路径；最后，将迷宫实体化为三维结构，并与原始三维模型做运算，得到三维迷宫。运算，是一种 CSG 建了是面向 CSG 建模系由于生成的迷宫是由大量的基本集合体通过模表达。为了避免进行三角化，生成三角网格，统的 3D 打印切片算法。隐式表达的三维模型有着三角网格不可替代的优点，如表达能力强，运算简便，没有拓扑上的不正确

5、，如自交或等。这些优点正是三维打印所需要的，并且是网格表达所不具备的。CSG 建模技术通过简单体素的拼合构造复杂几何体。在计算机图形学和 CAD 建模领域，CSG 建模技术经常被用于实体建模。为了解决制造问题，基于隐式函数的 3D 打印切片算法，提出了面向 CSG 建模系统的 3D 打印切片算法，可以在大幅减少处理时间的同时，模型精度也有所。最后通过 3D，用算法生成的迷宫制造出个性化的三维迷宫玩具，大大增强了迷宫的趣味性和用户体验。： 三维打印，迷宫，实体建模，隐式函数，切片算法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、意义 相关工作 1.3.1迷宫的相关 1.3.2二维迷宫的生成31.3.34三维迷宫的生成1.3.43D 打印技术 51.3.53D的工作流程 71.3.63D 打印的切片算法 89101.41.5本文的工作 本文的结构 11111111第二章 三维迷宫的生成算法 2.1 三维迷宫的提出 2.2 二维迷宫的设计 2.2.1迷宫的表示及约束 基于最小生成树的迷宫生成 循环迷宫 复杂度量化的迷宫 结果 2.2.2122.2.3142.2.4162.2.51718182.3 三维迷宫的设计 2.3.1算法概述 四边形网格化 基于四边形网格的迷宫设计 2.3.2182.3.320212.4 小结 V目

17、 录第三章 面向CSG 建模系统的 3D 打印切片算法 3.1 CSG 建模技术 23232425252627272931333435363737373840404042444545454749513.2 OpenSCAD介绍 3.2.1 基本几何元素 3.2.2 基本变换 3.3 基于隐式函数的 3D 打印切片算法 3.3.1 Marching Sqaure 算法 填充结构的生成支撑结构的生成 3.4 基本几何元素和基本变换的隐式函数表达 3.4.1 基本几何体的隐式函数表达 3.4.2 基本几何变换与隐式函数 3.5 基于CSG-Tree 的 3D 打印切片算法 3.6 小结 第四章 三维

18、迷宫的制造 4.1 用 OpenSCAD 表达三维迷宫 4.1.1 基于圆柱造型的迷宫玩具建模 4.1.2 基于球造型的迷宫玩具建模 4.1.3 基于任意曲面的迷宫玩具建模 4.2 实验结果 4.2.1设计 4.2.2 打印结果展示 4.3 小结 第五章 总结与展望 5.1内容的总结 5.2 未来工作的展望 参考文献 致 谢 在读期间的学术与取得的成果 VI第一章绪论第一章绪论1.1引言在所有的新兴技术中，3D 打印被称为是第四次工业的快速成型技术，3D 打印号称将会引领“第四次工业 个世纪 90 年代中期，历经三十年的发展。第一代 3D 年代中后期，主要是以能够打印模型为主。第二代 3D快速

19、成型发展到能够打印高精度的功能性产品。的起点。作为新兴”。3D 打印于上诞生于 20 世纪 80是在最近几年由3D 打印技术是对传统制造业的一次。与传统制造业相比，3D 打印技术突破了设计与制造的局限性，让一切设计都成为制造上的可能。传统制造技术通过切割、抛光等减材技术制造模具，然后再利用模具实现批量生产。而 3D打印是一种增材制造技术，整个过程无需生产昂贵的模具，通过“一次成型”，大大降低了生产成本。在个性化定制等传统制造的软肋领域，3D 打印也有广泛的应用。1.2课题的背景及意义随着计算机技术的发展以及互联网的普及，数字渗入人类生活的各个，到，再到如今快速发展的 3D 技术，数字方面。从声

20、音、通过影响人们的行为方式和思考方式深刻地影响着社会领域的发展，消费业和制造业都受到来自数字的强烈冲击。伴随着国际竞争的加剧，高新技术背景下的新型制造技术正在影响传统的制造业。21 世纪是 3D 打展与崛起的时代，将 3D 打印应用到现代制造业，促进产业升级和调整，创造巨大的利润空间。而 3D 打印也将是未来制造业乃至其他行业的大势所趋。面对大量的中国制造而非中国创造，中国需要全面提升创新能力。在此背景下，本文选择了制造业中迷宫玩具的设计与制造。迷宫的和设计，在实际生活中有着广泛的应用前景。利用迷宫的复杂结构设计防伪标识能够极大提高标识防伪的能力；利用迷宫的结构，在建筑和景观设计中融入迷宫的风

21、格，能够产生别具一格的设计效果；在设计和二维流形的参数化中迷宫也有重要应用。本文正是立足于此并且结合了个人。利用 CSG 建模技功生成三维迷宫模型。然后又结合 3D术，本文结合二维迷宫和三维结打印考虑模型的实际制造问题。切片计算是三维打印中对模型处理的步骤，是打印效果的重要影响之一。针对具体的三维迷宫模型的打印，考虑到 CSG 建模系统，本文提出了一种面向 CSG 建模系统的 3D 打印切片算法。通过本文算法，可以在大幅减少处理时间的同时，模型精度也有所。1第一章绪论1.3相关工作1.3.1迷宫的相关古今中外，不论神话还是现实世界，都能见到迷宫的身影。迷宫不仅拥有悠久的历史也有深厚的文化内涵。

22、迷宫建筑因为其中充斥的神秘主义令无数人着迷；迷宫因为广泛性和趣味性深受各个层次的人喜爱，一直长久不衰；作为儿童学前教育的益智玩具，迷宫玩具更是备受家长青睐。因此，关于迷宫的与设计具有广阔的应用前景和实用价值，不少学者在迷宫的研究与设计领域做出过贡献13。Phillips4了罗马马赛克式迷宫的拓扑，提出了一种迷宫重建理论，指出这个理论可以用于破损的迷宫重建和保存。McClendon5 提出了一种计算迷宫复杂度的方法，但是 McClendon 所的迷宫是一类更加广泛的由曲线的迷宫。在迷宫的路径曲线上定义连续函数，考虑路径长度、极值点等复杂度的影响，利用连续化方法提出了计算曲线迷宫复杂度的公式。对在

23、迷宫设计方面，Xu 和 Kaplan 提出了一种生成带有漩涡结构 (图 1.1左图)的复杂迷宫算法6，并设计基于图像的迷宫算法7。系统通过扩展传统的迷宫生成算法建立适应图像风格的迷宫，并且遵从用户指定的迷宫路径。当然，用户只能指定路径的大致方向，不能具体设计路径。由于没有考虑生成迷宫的质量，因此也没有给出计算迷宫复杂度的方法。Hans 和 Karan 8 将圆形迷宫（labyrhine）和矩形迷宫（maze）这两种类型的迷宫结构综合在一起，表示为二维流形上的曲线，提出了一种类迷宫结构的自动生成算法 (图 1.1右图)。图 1.1漩涡结构的迷宫6（左图）和带有边界的类迷宫组织8（右图）迷宫的和设

24、计，在实际生活中有着广泛的应用前景。利用迷宫的复杂结构设计防伪标识能够极大提高标识防伪的能力；利用迷宫的结构，在建筑和景观设计中融入迷宫的风格，能够产生别具一格的设计效果；在维流形的参数化中迷宫也有重要应用。设计和二2第一章绪论1.3.2二维迷宫的生成传统随机迷宫的生成是通过图的遍历算法实现的9。图的传统遍历算法有两种，深度优先遍历（DFS）和广度优先遍历（BFS）。两种算法都是通过迭代的方式对图中的顶点按照“尽可能广”或“尽可能深”的顺序去遍历。由于两种算法都是一种通过边找邻接点的过程，因此两种算法的时间复杂度相同。深度优先遍历可以概括为“能进则进，不进则退”。算法的具体步骤如下(图 1.2

25、左图)：step 1: 假设图 G 中所有的顶点都未曾被，任意选择某个顶点 v 作为遍点；历的起点，顶点 v，将此顶点作为当前step 2: 依次将此顶点作为当前v 的所有邻接点，如果未被点。按照这种方法继续过，则选择该顶点并下去，如果某个顶点的所有邻接点都被过，则退回上一层，换一个邻接点继续，直到图 G 中和顶点 v 有路径连接的顶点都被到；step 3: 若图 G 中还有顶点没有被，则在剩下未被的顶点中任意选择一个顶点作为当前点，重复上述操作，直到图G 的所有顶点都被到。图 1.2深度优先遍历（左图），遍历点的顺序为：V1-V2-V4-V8-V5-V3-V6-V7；广度优先遍历（右图），遍

26、历点的顺序为：V1-V2-V3-V4-V5-V6-V7-V8。广度优先遍历可以概括为“逐层扩展”。算法的具体步骤如下 (图 1.2右图)：step 1: 假设图 G 中所有的顶点都未曾被，任意选择某个顶点 v 作为遍历的起点，step 2:顶点 v；v 的所有邻接点，依次其中未被过的邻接点。然后分过的顶点。按照逐层扩别从这些邻接点出发依次它们的邻接点中未被展的原则继续，直到图 G 中和 v 有路径连接的顶点都被到；的点中任意选择step 3: 若图 G 中还有顶点没有被，则在剩下未被一个顶点作为新的起点，重复上述操作，直到图 G 的所有顶点都被到。3第一章绪论在图论里，不含圈的连通图被称为树。

27、二维迷宫可以看作初始状态迷宫的生成树。这样就建立起迷宫与图之间的对应关系，可以用图的理论来迷宫。通过深度优先遍历 (DFS) 或广度优先遍历 (BFS)，都可以构建出图的生成树，当然也可以用来生成迷宫。本课题中采用深度优先遍历算法 (图 1.3)。图 1.3利用深度优先遍历算法生成的迷宫1.3.3三维迷宫的生成作为益智玩具的经典款式之一，迷宫玩具一直是老少皆宜的一类玩具。玩家通过迷宫玩具可以锻炼判断力和力，培养耐心和对时空的感知能力，把握整体与局部的关系。但是自从迷宫玩具问世以来，一直都保持经典的玩具形式，市场上的迷宫玩具几乎都是基于平面造型的形态 (图 1.4)。图 1.4基于平面造型的迷宫

28、玩具（来源：htt/）随着计算机技术和网络技术的飞速发展，三维数据成为继声音、图像和视频之后更高级的数字类型，能够准确地刻画现实世界。将迷宫由二推广到三，无疑增加了迷宫的难度，同时也增加迷宫的性，提4第一章绪论高了迷宫的趣味性与可玩性，对玩家空间想象能力的培养大有裨益。然而对于三维迷宫，鲜有学者做过深入的和。一些玩具设计者通过在多面体上设立挡板，挡板之间迷宫的通道，而多面体的各个面之间通过迷宫的通道相互连通，形成如图 1.5图所示的迷宫。虽然出现过不少三维迷宫的设计方案，但是在制造领域，鲜有三维迷宫实现批量生产，也尚未出现专门的三维迷宫设计。因为大部分三维迷宫的设计方案与生产实际之间存在差距。

29、一方面，三维迷宫的设计难度远远高于二维迷宫，设计者需要在三中构思迷宫的三维结构；另一方面，三维迷宫的设计难度也决定了迷宫的难度，复杂的三维结构超过玩家的理解能力范围。图 1.5两种迷宫的设计方案? 本文结合二维迷宫生成和 3D 建模技术，将二维迷宫嵌入到三维模型表面，得到三维迷宫。利用 3D 打印，用算法生成的迷宫制造出个性化的三维迷宫玩具，大大增强了迷宫的趣味性和体验性。1.3.43D 打印技术人类刚刚步入的 21 世纪，一种绿色制造技术迅速吸引公众的眼球，这就是3D 打印。3D 打印的崛起，引领 21 世纪新一轮数字化制造浪潮。称 3D 打印是工业的升级版，将会改变大自然的制造方式12。英

30、国经济学3D 打印，称 3D 打印将引领第三次工业13。3D 打印人杂志专题于上个世纪 90 年代中期，目的是抛弃传统工厂流水线的生产模式，通过 3D 打印机打印出三维3D 打印（3D pr实物 (图 1.6)。ing），又称增材制造技术（Additive Manufacturing, AM），快速成型（RaPrototy）、分层制造（Layered Manufacturing）。普通的 2D，如喷墨的打印原理是利用喷嘴喷出的细小墨滴组成图像中的像5第一章绪论图 1.6Makerbot 公司制造的 3D(来源：./)素，不同喷嘴喷出的墨滴颜色不同，因此可以组成色彩多样的图像。与 2D 打印原理

31、类似，3D 打印是以三维数字模型文件为蓝本，将特定的打印材料，如塑料、粉末、丝、片、板等逐层推积，或再黏合叠加，形成最终产品。传统制造技术是采用切、削、钻孔等去除多余材料得到最终产品，是一种“减材”制造方式。相比传统制造技术，3D 打印是将模型一层层打印出来的，是一种典型的“经济节约型技术”，主要有下列特点：（1）缩短研制周期3D 打印只需要数字模型文件就能打印实物，舍弃传统制造业中模具制作的工序，从而极大地缩短了产品的研制周期，能够大幅度提高生产率。（2）降低制造成本与传统制造业相比，3D 打印能够有效地降低制造成本。第一，生产产品不需要在工厂进行，节约了厂房的成本。第二，由于摒弃传统的加工

32、方式而减少原材料的浪费，从而降低材料成本。（3）实现个性化定制3D依赖的是数字模型文件，因此打印之前需要用户设计出 3D 模型，用户可以根据个人需要，设计出个性化的产品，同时又可以根据既有的 3D 模型实现批量生产，这是传统制造业难以实现的。（4）应用领域广泛更短的生产周期、制造更为复杂几何形状以及降低制造成本的能力，使得 3D 打印可应用的行业逐步扩大，涉及经济，文化，军事，教育等诸多领域。只要这些行业需要模型和原型，3D 打印技术就可以得以应用。6第一章绪论1.3.53D的工作流程目前 3D是熔融沉积成型中技术最为成熟应用最广的是 FDM。FDM的简称。FDM工作时，先将各种热熔型的丝材，

33、ABS、聚碳酸酯 PC 等加热融化，同时由三维喷头喷出，逐层堆积如工程成三维实体模型。整个过程在计算机的控制之下，以数字模型文件为基础。从设计模型到打印模型，3D的工作流程主要分为以下几步 (图 1.7)：的工作流程14图 1.73D（1）三维模型设计。三维模型的获取主要通过两个途径：建模和扫描建模是指通过三维建模如 Maya、SolidWorks 等，用户根据需求重建。自行构建三维模型。扫描重建是指通过三维扫描设备，如结构光扫描仪、激光扫描仪等获取点云数据，然后通过算法重建出三维模型。（2）格式转换为 STL 文件。STL 文件格式（stereo lithography，光立体造型术的缩写）

34、是一种为快速原型制造技术服务的三维图形文件格式。STL文件由多个三角形面片的定义组成，每个三角形面片的定义包括三角形各个定点的三维坐标及三角形面片的法矢量。STL 是 3D 打印业内的标准文件类型，因此需要将三维模型文件转化为 STL 格式文件，才能用 3D进行打印。（3）计算切片。3D 打印实际上是逐层进行的，这就需要事先对三维模型进行数字切片。将模型沿高度方向 (三维坐标中的 z 方向) 离散化，分为若干层，每一层用以切面为底面、本层厚度为高度的柱体近似表示。切片是三维打印中对模型处理的步骤，切片算法将在下一小节介绍。目前主要的切片有Cura、makerwat、slic3r。（4）规划打印

35、路径。切片所得到薄层反映着打印物体的一个横截面。所谓路径是打印喷头在不同的组件中的运动轨迹。路径按大类来分，有轮廓和填充两种。同样的一组切片，不同的打印路径得到的打印效果也不一样。因此，需要规划出具体的打印路径，并对其进行合理的优化，以得到更快更好的切片打印效果。7第一章绪论（5）打印三维模型。根据上述计算的切片及规划的打印路径逐层进行打印，将所打印的切片薄层累计叠加，最终形成三维实体。1.3.63D 打印的切片算法由上节可知，3D 打印实质上是打印材料逐层累加的过程，切片是三维打印中对模型处理的步骤。切片过薄会导致大量的时间消耗，甚至会导致打印机无法正常打印；切片过厚则会产生较大误差，导致打

36、印的模型表面呈现锯齿状，打印效果差。如何在保证打印效率的同时得到更好的打印效果，这就导致了 20 世纪九十年代切片算法的飞速发展。目前的切面算法主要分成两大类：网格切片算法和直接切片算法。在自适应的切片过，切片的厚度是由网格模型的几何形状和用户指定的最大可允许的尖顶高度确定的。1994 年，Dolenc 和 Makela 15 提出了最大可允许的尖顶高度的概念，随后这一概念被广泛应用于切片的计算。切片的厚度由尖顶高度 c 和边界处顶点的法向决定，尖顶高度是通过用户指定的最大可允许的尖顶高度Cmax 确定。设法向为N(Nx, Ny, Nz)切片的厚度CmaxNzt0Nz如果t tmax, ttm

37、ax 主要算法如下：（1）逐步一致细化16逐步一致细化的切片算法是首先将网格模型划分成一致的水平切片，且厚度等于用户指定的最大可允许的薄层厚度tmax 然后对那些不满足尖顶高度要求：c 1 时，表示支还存在多阶支路，此时计算多阶支路的复杂度会多一个权重 i，这表明随着支路阶数的增大，对整个迷宫的复杂度影响不仅仅是简单的复杂度叠加，而是影响越来越大。考虑图 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设 S 是迷宫 M 的主路径，B1 B2 B3, . Bn 分别是 S 上的 n 条支路，定义迷宫 M 的复杂度为所有支路的复杂度之和，因此，定义整个迷宫的复杂度函16第二章三维迷宫的生成算法数为：nComplexity(M)Branch()Bii=1计算图 2.10中的迷宫复杂度：2217Branch(B1)Branch(B2) Branch(B3)Branch(B1)16 + 6 + 6 + 611.71542313因此，迷宫的复杂度为：Complexity(M)1 + 17 + 11.7 + 130.7图 2.10影响迷宫复杂度的相关（图中迷宫为非循环迷宫）2.2.5结

39、果图图 2.11显示了三种设计风格的二维迷宫：随机迷宫、循环迷宫及定制迷宫，红色表示由迷宫起点到迷宫终点的主路径。随机迷宫是传统迷宫生成算法实现的，循环迷宫和定制迷宫是通过迷宫生成算法实现的。通过对比，可以看出，定制迷宫能够产生较好的路径形状，循环迷宫的左右两侧可相互连通。图图 2.12展示了三种复杂度的平面迷宫，根据复杂度公式，图的迷宫复杂度是 0，图的迷宫复杂度是 24，图的迷宫复杂度是 33。17第二章三维迷宫的生成算法图 2.11(a) 是基于传统迷宫生成算法实现的随机迷宫；(b) 是本文循环迷宫算法生成的循环迷宫，左右两侧是连通的；(c) 是交互系统结合用户交互生成的迷宫，用户可以自

40、行设计迷宫的主路径，支路部分由系统随机生成。图 2.12复杂度分别为 0,24,33 的迷宫图2.3三维迷宫的设计2.3.1算法概述三维模型最常见的表示方式是网格，不论是三角网格、四边形网格，还是六边形网格，网格所表达的三维模型都具有点、线、面等基本的数据结构。三维模型的网格具有图的特征，是一张三中的图。因此，通过图导出其最小生成树，就能在三维模型的网格上生成迷宫。三维迷宫的设计在理论上是可行的。对于给定的三维模型，设计三维迷宫算法流程如图 2.13所示。二维迷宫实体化是将迷宫由二维结构转化为三维结构，这样做的目的是为了用二维迷宫与三维模型三维迷宫。三维迷宫的方法是通过迷宫与三维模型之间的差运

41、算实现的。如图 2.14所示，差运算实际上就是从原始三维模型中减去二维迷宫得到三维迷宫。2.3.2四边形网格化网格是表示三维模型最简单有效的方式 (图 2.15)，三维模型网格化也是研究三维模型基础性的一步，三维模型网格化的好坏会直接影响后续工作的结果。18第二章三维迷宫的生成算法图 2.13三维迷宫设计流程图图 2.14三维迷宫设计示意图: (a) 中的圆柱模型与 (b) 中的实体化二维迷宫做到 (c) 中的三维迷宫。差运算得因此，需要针对不同的问题选择不同的网格化方式。在本文中，模型的四边形网格化，主要是基于以下考虑：选择三维高质量的四边形网格相对于和较好的收敛性27；四边形网格更符合二维

42、迷宫的特征，因此生成的二维迷宫也具有较好的外观。度相同的三角形网格，具有更精确的解图 2.15三维模型的四边形网格化: (a) 为三维网格曲面；(b) 为生成的四边形网格。四边形网格化自上个世纪八十年代成为的热点，算法虽不及三角网格化成熟，但是也涌现出许多算法。根据生成原理，四边形网格化大致可以分为19第二章三维迷宫的生成算法直接方法和间接方法。直接方法就是在给定的几何区域上直接生成四边形网格，间接方法就是通过三角网格转化为四边形网格。四边形网格可以看成是特殊的三角网格，因为可以将一个四边形沿对角线分成两个三角形。但是，反过来却不一定成立。Lo? 提出了通过移除三角网格之间的对角线，将两个三角

43、形变成一个四边形的方法。这是一个相对简单的合并方法，但是由于相邻的两个三角网格之间不一定能够四边形，也可能同一个三角形能与多个相邻三角形网格又有四边形网格的混合网格。四边形，因此最终得到了一个既有三角形2.3.3基于四边形网格的迷宫设计四边形网格的结构为随机迷宫的生成提供了便利。在使用二维迷宫生成算法之前，首先要获取四边形网格中的所有顶点的领域信息。除边界外，四边形网格顶点的邻接点个数都为 4。为了避免麻烦，本文仅考虑在四边形网格内部生成迷宫。然后需要指定迷宫的起点和终点，通过基于最小生成树的二维迷宫生成算法，在四边形网格表面生成二维迷宫，如图 2.16所示。算法具体过程已详述，这里不再重复。

44、文为了建立三维迷宫，需要将二维迷宫实体化。本文采用的二维迷宫实体化方式是用圆柱代替迷宫中相邻两点之间的路径。圆柱满足条件如下：圆柱的高度等于两顶点之间的距离；圆柱的上下两个底面分别以相邻两顶点为圆心；圆柱之间按照顶点顺序依次连接。图 2.16基于四边形网格的迷宫设计: (a) 在四边形网格上选取两点作为起点和终点；(b) 随机生成连接起点和终点的一条主路径；(c) 在主路径基础上生成迷宫的其他支路面；(d) 不断重复面 (c) 最终得到完整的迷宫。20第二章三维迷宫的生成算法2.4小结了三维迷宫的生成算法。结合二维迷宫生成和 3D 建模技术，迷宫的设计，本章提出一种新的三维迷宫设计思路：即将二

45、维本章主要借鉴已有的迷宫嵌入到在三维模型表面，得到三维迷宫。不同于二维迷宫，三维迷宫对迷宫的设计具有的约束，如循环迷宫；出于用户交互系统的需求，应该为用户提供迷宫路径可控的生成算法，即定制迷宫；考虑如何评估生成迷宫的有效性，需要对迷宫的复杂度量化。本章首先了二维迷宫的生成算法。通过对传统的二维迷宫生成算法进行改进，生成能够设计出三维迷宫的平面迷宫；然后通过二维迷宫嵌入到在三维模型表面，提出三维迷宫的生成算法，同时也给出了循环迷宫和路径可控迷宫的设计方法。21第三章 面向 CSG 建模系统的 3D 打印切片算法第三章 面向 CSG 建模系统的 3D 打印切片算法3.1CSG 建模技术CSG（Co

46、nstructive solid geometry）建模技术，即实体几何构造技术，是实体建模的一种。所谓实体建模，是指通过简单体素的拼合构造复杂几何体。CSG 建模技术利用一些基本体素，如长方体、圆柱体、球体、锥体、圆环体以及扫描体、放样体、旋转体、拉伸体等，通过集合运算（拼合或运算，如求和、求差、求交）生成复杂形体。CSG 建模技术往往能够创造非常复杂的曲面和几何体，实际上都是通过基本几何体之间的巧妙组合。如图 3.1 所示。与其他建模技术相比，实体模型存在许多不同的数据结构，这些数据结构不仅了全部的几何信息，而且还了所有的点、线、面、体的拓扑信息，它能完整地表示物体的所有形状信息，可以无歧

47、义地确定一个点是在物体外部、内部或表面上，能够进一步满足物性计算、有限元分析等应用的要求。图 3.1CSG-Tree 表示复杂几何体的建模过程（来源：）在计算机图形学和 CAD 建模领域，CSG 建模技术通常被用于过程建模（procedural ming），主要应用于多边形网格。它是目前最常见、最重要的方法之一。CSG 建模技术中最重要的两个概念是基本几何体和运算。用来表示复杂几何体的最简单几何体被称为基本几何体，常见的有：长方体、圆柱体、球体、锥体、圆环体以及旋转体；基本几何体和多个基本几何体之间可以通过运算得到新的几何体，这些运算主要有：单个基本几何体的平移、旋转、缩放等或多个基本几何体几

48、何体之间的运算，如求和、求差、求交。23面向 CSG 建模系统的 3D 打印切片算法第三章用 CSG 表示一个物体可用二叉树的形式加以表达， 称为 CSG Tree。 CSG-Tree 的叶子分为两种，就是上文提到的基本几何体和运算。CSG 表示的优点有：数据量小，数据结构简单，数据管理容易；可以方便地转换成边界表示；形状比较容易修改。CSG 表示的缺点有：表示形体的覆盖域有较大的局限性，受基本几何体和运算限制；局部操作不蓉易实现；显示与绘制 CSG 表示的形体需要较长的时间。3.2OpenSCAD介绍OpenSCAD(图 3.2)。Open-在本课题中选用的建模是一款开源的小SCAD 是一款

49、用于构建实体 CAD 模型的建模。OpenSCAD 不是一个交互建模。相反，它是在文件中描述对象，并呈现文件中描述的 3D 模型，因此整个建模过程，用户完全掌握着控制权，可以轻松地更改任何步骤在建模过，甚至设计所定义的配置参数。OpenSCAD 对计算机配置要求很低，安装文件小巧，但功能却是非常强大。与其他建模著特点：相比，OpenSCAD 有如下显图 3.2OpenSCAD界面（来源：）（1）使用语言描述 3D 模型不同于 3DS Max 和 Maya 等，OpenSCAD 不要求用户掌握繁琐复杂的作，取而代之的是简单的 OpenSCAD 语言。通过 OpenSCAD 的 言描述对象，编译成

50、功之后呈现 3D 模型，这是 OpenSCAD 区别其他建模24语第三章 面向 CSG 建模系统的 3D 打印切片算法的最大特点。通过程序设计语言进行 3D 建模，用户可以更加精确地描述 3D模型。（2）操作简单，使用方便与 3DS Max 和 Maya 相比，OpenSCAD 是一款非常小的，安装简单，携带方便。由于 OpenSCAD 的非交互性，OpenSCAD 没有复杂的交互界面。同时，OpenSCAD 所使用的（3）支持命令行处理OpenSCAD 不仅可以用作一个图形用户界面，还可以处理命令行。这一优语言非常精简，入门简单。点可以将 OpenSCAD 用于 3D 建模界面（GUI）应用

51、程序。的开发，编写与 3D 模型有关的图形用户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)旋转：roe(x,y,z)比例缩放：scale(x,y,z)更改大小：resize(x,y,z,auto)镜面：mirror(x,y,z)多个几何体之间的基本变换主要是联合：union()求差：difference()求交： ersection()运算：25第三章 面向 CSG 建模系统的 3D 打印切片算法图 3.3OpenSCAD 中的基本几何体：二维几何体（

53、左图）和三维几何体（右图）图 3.4OpenSCAD 中的基本变换：镜面变换（左图）和运算（右图）3.3基于隐式函数的 3D 打印切片算法三维模型有多种表达方式，如网格表达、参数表达、隐式表达等。网格表达是通过点、线、面等来描述模型与曲面，是一种离散的表达方式。常用的有三角网格、四边形网格等。参数表达是指用一系列以参数为自变量的函数来计算曲面上点的位置的方法，如 NURBS 等。隐式表达是指通过一系列的隐函数fi(x, y, z) 6 0 以及交、并、补等运算所确定的曲面。在上述三种表达方式中，隐式表达是最适合三维打印的。一方面，隐式表达的能力强，运算简便，没有拓扑上的不正确。其次，隐式曲面可

54、以计算法向并十分简单地区分模型内外，便于 模型的处理。最后，在 FDM 型的三维打印中，打印喷头所走的路径主要是切面的轮廓，也就是说移动方向与曲线切线方向相同，而这则是隐式曲面比起其它表示方式所具有的优势之一。其他两种表达方式都会导致处理时间增长，产生较大的误差。本节主要介绍基于隐式函数的 3D 打印切片算法中最主要的三个算法：切片26第三章 面向 CSG 建模系统的 3D 打印切片算法轮廓查找算法、填充结构的生成算法和支撑结构的生成算法。Marching Sqaure算法是最目前使用最广泛的切片轮廓查找算法。3.3.1Marching Sqaure 算法隐式表达模型f(x, y, z) 6

55、0在高度 z0 处与平面 z=z0 的交线为f(x, y, z0)0 将其视为 (x, y) 的二维函数，即为模型在此高度的轮廓。轮廓的查找算法可以使用 Marching Square 算法(图 3.5)。图 3.5Marching Squire 算法示例Lorensen 和 Cline 提出过三维模型的 Marching Cube 算法29。与之类似，二维平面也有 Marching Square 算法。算法的是用相互正交的两组等距直线 (称为网格线) 将平面均匀的分为若干网格，对每个小方格的四个顶点处的函数值进行计算来曲线在此方格中的形态。例如在小方格内使用直线或折线来近似表示曲线在小方格内

56、的形态 (图 3.6).3.3.2填充结构的生成为保证所打印出的模型有足够的强度，内部填充是必不可少的。填充的生成与轮廓的查找算法类似，均是将某一切片所在平面离散为网格进行计算。现阶段，成 切片引擎所生成的填充方式大同小异：一是以 Makerware 为代表27第三章 面向 CSG 建模系统的 3D 打印切片算法图 3.6使用 Marching Squire 算法近似表示曲线的六边形 (图 3.7左图) 填充；二是以 Cura 为代表正方形 (图 3.7 左图) 填充。考虑到填充的具体方式并不会过多地影响到模型的强度，而六边形填充则会要求更复杂的算法，更长的处理时间，因此正方形填充。选择采用与

57、 Cura 相同的填充模式 图 3.7两种填充模式正方形填充模式是指各层切片交替单向填充，即奇数层打印 x 方向上的等距直线作为填充，偶数层打印 y 方向上的等距直线填充 (反之亦可)，为填充线。这样，整体就会以正方形的模式进行填充。称之在某一切片所在平面上，希望能够生成对应的填充。与查找轮廓线算法相似，(亦称为网格线) 分为若干方格。对于固定的切片，填充线的方向是固定的。不妨设填充线的方向为 y 方向，即与 y 轴平行。这样，此层上的填充线一定在 y 方向的网格线上。而填充线决定了模型的填充率，因此网格线可以由填充率决定。显然，当网格线间的距离为 L 时，填充率大概为 。L确定好两条网格线之

58、间的距离，也就是填充线之间的距离后，则需要确定每条填充线的起止点。显然，填充线应该在模型内部，且与外壳相接，因此起止点应由外壳的位置与层数 (也就是厚度) 共同决定。对于每一条 y 方向的网格线，首先计算网格线上的格点是否在模型内部且不在外壳的范围内。这样就可以确定出网格线上的格点是否属于填充线，同时28第三章 面向 CSG 建模系统的 3D 打印切片算法也就确定出了填充线起止点大致的位置。确定出起止点大致范围后，可以采用二分法精细化起止点位置。也可以用隐函数 y 方向上的一阶偏导与 Sampson 距离来估计。这样，填充线就可以完全确定下来了 (图 3.8)。图 3.8生成填充的算法3.3.

59、3支撑结构的生成支撑算法包括内部支撑和外部支撑算法。内部支撑当模型在某层切片处过于平坦时，如球形的顶部，会导致相邻的切片形状与本层切片形状相差较大，从而会导致外表并不连续，漏出模型的内部等瑕疵 (图 3.9)。一般来说，切片引擎会采取内部关键部分全填充的方法来避免这种情况。大部分切片引擎所采取的填充方式是用直线填充 (图 3.10)。外部支撑许多模型都会有悬空部分，而三维打印的顺序是从低到高，打印悬空部分时则必须有一个支点。模型的外部支撑所起到的作用便是如此。因此，判断一个点是否需要支撑，其标准就是模型表面某点处的法向是否与 z 轴负方向接近 (图 3.11)。在图中，P = (x,y,z)，

60、则有29面向 CSG 建模系统的 3D 打印切片算法第三章图 3.9无内部支撑导致的瑕疵图 3.10生成多层外壳f(P)0nf(P)nz 0n (0,0,1)nzn cos cos n 若min 为需要支撑的临界值，则有nzcos min cos n如果判断出某点需要支撑，则显然有此点以下，或模型表面某点以上全部需要打印。最后，在切片过，给定一个切片，通过和预处理结果求交，确定出平面上的那些点需要打印支撑。与内部填充的模式相似，采用的也是正方形网格式的支撑。通过分层打印相互正交的直线来外部支撑。30第三章 面向 CSG 建模系统的 3D 打印切片算法图 3.11支撑的判定与生成支撑的预处理同样