基于3D建模技术的迷宫玩具开发毕业论文.pdf 40页

'安徽大学本科毕业论文安徽大学本科毕业论文（设计、创作）题目：基于3D建模技术的迷宫玩具开发学生姓名：吴文明学号：V21114008院（系）：文典学院专业：统计学入学时间：2011年9月导师姓名：王良龙职称/学位：教授/博士导师所在单位：安徽大学数学科学学院完成时间：2015年6月 安徽大学本科毕业论文基于3D建模技术的迷宫玩具开发摘要3D打印是21世纪最具发展前景的技术。中国的玩具产业长期面临生产成本高、创新设计不足、洋品牌盛行等问题。3D打印技术的应用，将赋予中国的玩具产业新的活力。本文研究3D打印技术在玩具开发设计以及制造上的实际应用。针对市场上迷宫玩具造型单一的问题，研究开发一款能够设计基于不同造型的迷宫玩具的3D建模软件。本文首先阐述通过深度优先遍历算法生成随机迷宫，然后介绍使用OpenSCAD建模软件建立迷宫玩具模型，接下来是利用C++编程语言和Qt库编写图形界面应用程序。软件可以设计基于圆柱造型和球造型的两种迷宫玩具，并最终通过FDM3D打印机打印迷宫玩具实物。软件的实现为玩具的设计与制造提供经验和思路，同时研究也为3D打印技术在玩具产业乃至整个制造业的应用提供借鉴。关键词:迷宫；3D打印；3D建模；深度优先遍历；OpenSCAD；Qti 安徽大学本科毕业论文DevelopmentofMazeToysBasedon3DModelingTechnologyAbstract3Dprintinghasbeenthemostprospectivetechnologyinthe21stcentury.ThetoyindustryinChinahasbeenintroublewithhighcost,lackofinnovation,anddominationofthetoysaboard.Theapplicationof3DprintingtechnologywillhelptoinvigoratethetoyindustryinChina.Thisdissertationstudiesthepracticalapplicationof3Dprintinginthedesignandproductionoftoys.Tosolvetheproblemthatthemazetoysinthemarketmostlyhavethesinglestructure,a3Dmodelingsoftwarewhichcandesignmazetoysbasedondifferentkindsofstructureissupposedtobedeveloped.Firstly,thedissertationelaboratesthegenerationofrandommazesbydepth-firstsearchalgorithm,andthenitintroduceshowtouseOpenSCAD,akindof3Dmodelingsoftware,tobuild3Dmodelsofthemazetoys.ThefollowingareabouttheGUIwhichwasprogrammedbyC++andQt.Twokindsofmazetoy,cylinderandsphere,canbedesignedbythissoftware.Finally,somesolidmazetoysprintedbyFDMarepresentedinthedissertation.Theimplementofthissoftwareprovidesexperienceandideastothedesignandproductionoftoys,andtheresearchalsoservesasareferencefortheapplicationsof3Dprintinginthetoyindustryandeventheentiremanufacturingindustry.Keywords:maze;3Dprinting;3Dmodeling;Depth-firstsearch;OpenSCAD;Qtii 安徽大学本科毕业论文目录1绪论............................................................................................................................................11.1研究背景..........................................................................................................................11.2研究目的..........................................................................................................................21.3开发工具与关键技术概况..............................................................................................31.3.13D建模.................................................................................................................31.3.2OpenSCAD简介....................................................................................................41.3.3Qt编程..................................................................................................................41.4论文主要工作和章节安排..............................................................................................62迷宫算法.....................................................................................................................................72.1图的遍历算法..................................................................................................................72.1.1深度优先遍历.......................................................................................................72.1.2广度优先遍历.......................................................................................................82.2迷宫的相关说明..............................................................................................................82.2.1迷宫的表示...........................................................................................................82.2.2迷宫的要求...........................................................................................................92.2.3迷宫与图的联系.................................................................................................102.3基于图的深度优先遍历的迷宫算法实现....................................................................112.3.1随机迷宫生成的算法实现.................................................................................112.3.2迷宫路径搜索的算法实现.................................................................................132.4结果展示........................................................................................................................153迷宫的3D建模.......................................................................................................................163.1迷宫分析........................................................................................................................163.2基于圆柱造型的迷宫玩具建模....................................................................................173.2.1建模思路.............................................................................................................173.2.2通道建模.............................................................................................................183.2.3模型生成.............................................................................................................193.3基于球造型的迷宫玩具建模........................................................................................194软件设计...................................................................................................................................224.1迷宫玩具三维建模软件的整体架构............................................................................224.2软件的设计与实现........................................................................................................22iii 安徽大学本科毕业论文4.2.1随机迷宫生成.....................................................................................................224.2.2功能实现.............................................................................................................234.2.3用户界面.............................................................................................................264.3软件实例........................................................................................................................275结果展示...................................................................................................................................295.13D打印技术..................................................................................................................295.1.13D打印的原理...................................................................................................295.1.23D打印的特点...................................................................................................295.1.33D打印的问题...................................................................................................305.2打印迷宫玩具结果........................................................................................................306总结与展望...............................................................................................................................326.1工作总结........................................................................................................................326.2存在的问题及工作展望..................................................................................................32参考文献.........................................................................................................................................34致谢..............................................................................................................................................35iv 安徽大学本科毕业论文1绪论1.1研究背景人类刚刚步入的21世纪，一种绿色制造技术迅速吸引公众的眼球，这就是3D打印。3D打印技术的崛起，引领21世纪新一轮数字化制造浪潮[1]。美国纽约时报称3D打印是工业革命的升级版，将会改变大自然的制造方式[2]。英国经济学人杂志专题报道3D打印，称3D打印将引领第三次工业革命[3]。3D打印起源于上个世纪90年代中期，目的是抛弃传统工厂流水线的生产模式，通过3D打印机打印出三维立体实物。图1.1：3D打印机（图片来源：ucrobotics)随着生活水平的提高，越来越多的家长开始关注儿童的早期教育。在儿童的早期教育中，玩具，特别是益智玩具备受家长青睐。玩具融合了娱乐性、艺术性和教育性等特点，有助儿童智力开发，激发儿童探索新奇事物，锻炼儿童肢体和感官协调性，培养积极向上的意志品格[4]。据统计，中国16岁以下的儿童约占总人口的五分之一。庞大的人口基数带来巨大的消费需求，这直接导致了玩具市场的繁荣。中国是名副其实的玩具大国，但是中国却不是玩具强国。一方面，由于原材料和劳动力成本的增加而导致生产企业的利润逐步缩减。另一方面，国内外玩具市场被各种洋品牌主导，而外部贸易壁垒高筑，国内品牌难以“走出去”[5]。3D打印技术为玩具的设计、开发、制造提供了新的思路，在玩具的制造和开发设计等方面具有显著优势。降低成本：传统制造业是通过模具加工得到产品。但是，在加工的过程中，切割、磨削、熔融等加工方式无疑会造成原材料的浪费。而3D打印技术彻底颠覆这种生产套路，大幅度节省生产成本，缩短生产周期。1 安徽大学本科毕业论文个性化设计：英国《金融时报》记者、《新工业革命》作者彼得·马什把人类的制造业分为五个阶段：少量定制、少量标准化阶段、大批量标准化生产、大批量定制化和个性化生产[6]。3D打印允许消费者自己设计、修改玩具，实现真正意义上的个性化定制。3D打印技术的发展和上个世纪70年代家庭计算机的普及有着极其相似的历史境遇。两种技术都是从造价高昂、体型笨重的机器开始，最开始的用途都是在一些很有限的领域，比如政府机构[7]。但是计算机技术发展到现在，其应用已经深入到人类生活的方方面面，彻底影响人类的生活方式。而3D打印技术也正在朝着这个趋势发展。一项技术真正得以应用应该归结于技术上的成熟和易接受的成本，无论是技术方面还是成本方面，3D打印技术还有待进一步发展。加快3D打印产业发展和3D打印技术人才培养，有利于进一步建设创新型国家，推动我国由“工业大国”向“工业强国”转变[8]。1.2研究目的作为益智玩具的经典款式之一，迷宫玩具一直是老少皆宜的一类玩具。玩家通过迷宫玩具可以锻炼判断力和记忆力，培养耐心，同时也要求玩家具备一定的综合分析能力和对时空的感知能力，把握整体与局部的关系[9]。但是自从迷宫玩具问世以来，一直都保持经典的玩具形式，市场上的迷宫玩具几乎都是基于平面造型的形态(见图1.2)。图1.2：基于平面造型的迷宫玩具（图片来源：http://www.amazon.cn/）笔者在淘宝网和亚马逊等购物网站检索迷宫玩具，发现大部分迷宫都是基于平面造型，市场上尚未出现基于圆柱体或球体造型的迷宫玩具。平面造型的迷宫不仅限制了迷宫玩具的设计与开发，也使得迷宫玩具的造型大同小异，没有创新。2 安徽大学本科毕业论文笔者正是出于这样的思考，选择了“基于3D建模技术的迷宫玩具开发”这一课题。本课题的最终目标是设计一款迷宫玩具的三维模型软件，这款软件能够自动生成不同造型的迷宫玩具模型。3D打印技术具有非常广阔的应用前景，而本研究课题旨在研究如何将3D打印、3D建模等相关技术应用到玩具的设计制造，以此为例阐述3D打印技术在实际制造中的具体应用流程，并借此推广3D打印，同时希望能够为中国玩具产业特别是益智玩具的设计与开发提供创意和思路，从而推动中国的玩具产业进一步发展。1.3开发工具与关键技术概况1.3.13D建模随着计算机技术的发展以及互联网的普及，数字媒体已经渗入人类生活的各个方面。从声音，图片，到视频，再到如今快速发展的3D技术，数字媒体的发展通过影响人们的行为方式和思考方式深刻地影响着社会领域的发展，消费业、制造业等都受到来自数字媒体的强烈冲击[10]。图1.3：数字媒体的发展（图片来源于中国科学技术大学刘利刚教授计算机图形学讲义）3D数字媒体作为更高级的数字媒体，能够更加准确地刻画我们的现实世界。将2D图形从二维平面中解放，进入三维世界，通过三维建模软件在虚拟的三维空间构建出具有三维形态的模型，这就是3D建模。3D建模是获取三维模型的主要手段。根据3D建模的不同用途，可以将3D建模软件分为三类：工程设计类：主要包括CAD类软件和CAID类软件。建筑设计类：SketchUp、PKPM等。影视动画类：3DSMax、Maya、Rhino、Softimage等。3 安徽大学本科毕业论文1.3.2OpenSCAD简介在本课题中选用的建模软件是一款开源的小软件OpenSCAD。OpenSCAD是一款用于构建实体CAD模型的建模软件，它对计算机配置要求很低，安装文件小巧，但功能却是非常强大。与其他建模软件相比，OpenSCAD有如下显著特点：图1.4：OpenSCAD软件界面（图片来源于http://www.openscad.org/index.html)（1）使用脚本语言描述3D模型不同于3DSMax和Maya等软件，OpenSCAD不要求用户掌握繁琐复杂的按钮操作，取而代之的是简单的OpenSCAD语言。通过OpenSCAD的脚本语言描述对象，编译成功之后呈现3D模型，这是OpenSCAD区别其他建模软件的最大特点。通过程序设计语言进行3D建模，用户可以更加精确地描述3D模型。（2）操作简单，使用方便与3DSMax和Maya相比，OpenSCAD是一款非常小的软件，安装简单，携带方便。由于OpenSCAD的非交互性，OpenSCAD没有复杂的交互界面。同时，OpenSCAD所使用的脚本语言非常精简，入门简单。（3）支持命令行处理OpenSCAD不仅可以用作一个图形用户界面，还可以处理命令行。这一优点可以将OpenSCAD用于3D建模技术的开发，编写与3D模型有关的图形用户界面（GUI）应用程序。1.3.3Qt编程Qt是由美国奇趣科技公司开发，目的是为开发跨平台的图形用户界面应用程序提供一个完整的C++应用程序开发框架。与同类型产品相比，Qt有如下特点：4 安徽大学本科毕业论文（1）可移植性利用Qt编写过一次的代码，只需要重新将其编译一遍即可在其他不同的操作系统平台中重复使用，即所谓的“一次编写，随处编译”[11]。Qt的可移植性提高了代码的利用率，使得开发跨平台GUI应用程序变得简单。（2）QWidget类Qt提供了完整的窗口部件，如菜单栏，工具栏，进度条等等，用户可以根据需要将不同的窗口部件组合起来创建出用户需要的窗口样式。窗口部件是QWidget或其子类的实例，自定义窗口部件则是通过子类化得到[12]。QWidget继承自QObject，QObject类是所有Qt对象的基类（见图1.5）。图1.5：QObject类的继承关系（3）信号和槽机制信号和槽机制是Qt编程的基础。Qt中的信号和槽可以在程序中两个互不了解的对象之间建立联系[12]。这种机制是Qt中最引以为豪的机制。所有GUI应用程序最关心的问题是实现部件和用户之间的交互，而Qt正是通过这种信号和槽的机制来实现[13]。（4）多线程在单线程情况下，交互界面可能会因为一个耗时操作而出现未响应的“假死”情况，而多线程编程则可以很好地解决这个问题。Qt的线程支持是独立于平台的线程类型，这使得它易于开发具有可移植性的多线程Qt应用程序[14]。5 安徽大学本科毕业论文1.4论文主要工作和章节安排本课题研究的主要内容是设计一款专门用于迷宫玩具3D建模的软件。用户利用软件可以设计基于不同造型的迷宫玩具，并且最后得到用于3D打印的网格数据文件。本论文的各章节安排具体如下：第一章为绪论。本章叙述本课题的研究背景和研究目的，简要介绍了课题研究中所用到的开发工具与关键技术。第二章为迷宫算法。本章首先介绍与迷宫算法相关的图的遍历算法，然后叙述了随机迷宫生成算法和迷宫路径搜索算法。第三章为迷宫的3D建模。本章详细介绍了用OpenSCAD建模软件设计基于圆柱造型和基于球造型的迷宫玩具模型。第四章为软件设计。本章详细阐述了迷宫玩具3D建模软件的整体构架、软件的设计与实现以及软件操作实例。第五章为结果展示。本章主要是介绍3D打印的原理以及展示利用3D打印机打印的迷宫玩具。第六章为总结与展望。本章总结在完成毕业设计期间的收获和不足，展望未来3D打印的发展趋势，为后期的研究奠定基础。6 安徽大学本科毕业论文2迷宫算法本章将先从图论中经典的遍历算法入手，研究随机迷宫的生成算法和迷宫路径的搜索算法。然后通过C++编程语言实现这两种迷宫算法。其中，深度优先和广度优先都是图论中解决问题的主要思想。2.1图的遍历算法图的传统遍历算法有两种，深度优先遍历（DFS）和广度优先遍历（BFS）。两种算法都是通过迭代的方式对图中的顶点按照“尽可能广”或“尽可能深”的顺序去遍历。由于两种算法都是一种通过边找邻接点的过程，因此两种算法的时间复杂度相同[15]。图2.1：左图为图的深度优先遍历，右图为图的广度优先遍历2.1.1深度优先遍历深度优先遍历可以概括为“能进则进，不进则退”。算法的具体步骤如下[16]：step1:假设图G中所有的顶点都未曾被访问，任意选择某个顶点v作为遍历的起点，访问顶点v，将此顶点作为当前考察点。step2:依次考察v的所有邻接点，如果未被访问过，则选择该顶点访问并将此顶点作为当前考察点。按照这种方法继续访问下去，如果某个顶点的所有邻接点都被访问过，则退回上一层，换一个邻接点继续访问，直到图G中和顶点v有路径连接的顶点都被访问到。step3:若图G中还有顶点没有被访问，则在剩下未被访问的顶点中任意选择一个顶点作为当前考察点，重复上述操作，直到图G的所有顶点都被访问到。7 安徽大学本科毕业论文深度优先遍历的算法如图2.1左图所示，其深度优先遍历点的顺序为：V1->V2->V4->V8->V5->V3->V6->V7。2.1.2广度优先遍历广度优先遍历可以概括为“逐层扩展”。算法的具体步骤如下[17]：step1:假设图G中所有的顶点都未曾被访问，任意选择某个顶点v作为遍历的起点，访问顶点v。step2:考察v的所有邻接点，依次访问其中未被访问过的邻接点。然后分别从这些邻接点出发依次访问它们的邻接点中未被访问过的顶点。按照逐层扩展的原则继续访问，直到图G中和v有路径连接的顶点都被访问到。step3:若图G中还有顶点没有被访问，则在剩下未被访问的点中任意选择一个顶点作为新的起点，重复上述操作，直到图G的所有顶点都被访问到。广度优先遍历的算法如图2.1右图所示，其广度优先遍历点的顺序为：V1->V2->V3->V4->V5->V6->V7->V8。2.2迷宫的相关说明2.2.1迷宫的表示在讨论迷宫的算法之前，首先要解决的问题是迷宫的表示。迷宫的组成元素包括入口、出口、墙壁和通道。在本课题中，将迷宫表示为一个二维数组。maze[m][n]定义一个m+1行n+1列的迷宫。二维数组中的元素只能是0或1，0表示该位置是通道，1表示该位置是墙壁。例如，用maze[6][9]表示一个行数为7，列数为10的迷宫，假设迷宫的入口坐标为（0，2），出口坐标为（6，8）（见图2.2)。图2.2：迷宫的表示8 安徽大学本科毕业论文2.2.2迷宫的要求不是所有的迷宫都能用于迷宫玩具的设计，本课题研究的迷宫玩具要求迷宫的左右两侧是连通的。为了能够成功生成迷宫，并且能够将生成的迷宫用于玩具的开发与设计，需要满足如下要求：（1）生成迷宫之前，在迷宫的上下两侧添上用0表示的通道（见图2.3)，但是不在左右两侧添上通道，这是为了让迷宫的左右两侧连通。图2.3：迷宫的上下两侧添上通道（2）所生成的迷宫有且仅有一条路径；（3）所生成的迷宫不允许出现两条或两条以上的横向或纵向通道并列在一起（见图2.4）；图2.4：左图中三条横向通道并列在一起，右图中三条纵向通道并列在一起（4）为了方便生成迷宫，要求迷宫的行数为奇数，列数为偶数。迷宫的入口和出口用户可以自己设定，但是必须位于奇数列上。迷宫的第一行和最后一行只能放置入口和出口。9 安徽大学本科毕业论文2.2.3迷宫与图的联系建立迷宫与图的联系，能够更好地理解迷宫的生成方式，实现迷宫算法。二维数组中的元素全都是1的迷宫可以看作是迷宫的初始化（见图2.5左图），通过初始化的迷宫可以生成各种类型的迷宫（见图2.6左图）。如果将迷宫的每一个元素表示为一个点，并且相邻的点用线段连接（图2.6右图）。这样就将迷宫转化为图论中的图。这个图有两个特点：第一，图中不含圈，也就是说路径不是闭合的。第二，这是一张连通图，也就是说图中任意两点都有路径连接。在图论里，不含圈的连通图被称为树。图2.6右图是图2.5右图的生成树，其中黑点标记表示迷宫的左右两侧相通。对应地，迷宫可以看作其初始化状态下迷宫的生成树。这样就建立起迷宫与图之间的对应关系，可以用图的理论来研究迷宫。通过深度优先遍历(DFS)或广度优先遍历(BFS)，都可以构建出图的生成树，当然也可以用来生成迷宫。本课题中采用深度优先遍历算法。图2.5：迷宫的初始化(左图）及其所对应的图（右图）图2.6：生成后的迷宫(左图）及其所对应的图（右图）10 安徽大学本科毕业论文2.3基于图的深度优先遍历的迷宫算法实现2.3.1随机迷宫生成的算法实现（1）类的设计通过深度优先遍历实现随机迷宫生成算法，类必须包含的数据成员是迷宫的行数和列数，函数成员主要是实现迷宫生成的函数，而且这个函数必须是递归函数。类的具体设计如下：#defineMAZE_MAX100classMaze{private:introws_;//迷宫的行数intcols_;//迷宫的列数charmap[MAZE_MAX+5][MAZE_MAX+5];//定义一个迷宫上限，防止用户自定义时迷宫的行数或列数越界voidmakeMaze();//迷宫生成函数intsearch(int,int);//随机搜索迷宫的通道，被makeMaze()调用public:Maze();//默认构造函数Maze(intx,inty);//构造函数，定义x行y列的迷宫vectorprintMaze();//打印随机生成的迷宫。};（2）迷宫的初始化迷宫的初始化在构造函数中实现，迷宫的初始化状态全是墙壁，然后需要设置迷宫的上下两侧为通道，设置迷宫的出口和入口。迷宫入口和出口的设置必须要满足2.2.2中迷宫的要求。在这里，设置迷宫的入口坐标设为（0，2），出口设为最后一行的倒数第二列。（3）迷宫生成函数的实现为了保证迷宫的随机性，需要将随机数用于迷宫的生成。srand((unsigned)time(NULL))用来产生随机数种子，rand()利用随机数种子产生随机数。search(intx,inty)是随机迷宫生成的核心算法[18]。这是一个递归函数。算法流程图如图2.7所示：11 安徽大学本科毕业论文图2.7：随机迷宫生成算法流程图12 安徽大学本科毕业论文2.3.2迷宫路径搜索的算法实现（1）类的设计为了实现迷宫路径搜索算法，需要定义两个类，一个是辅助类，作用是定义一个三元组结构，用来记录当前位置和上一个位置的前进方向。另一个类必须包含的数据成员是迷宫的行数和列数，函数成员主要是实现迷宫路径搜索的函数。两个类的具体设计如下：classnode//辅助类{public:intx;inty;intc;//c=1表示方向向右，c=2表示方向向上，c=3表示方向向左，c=4表示方向向下node(intx=0,inty=0,intc=1):x(x),y(y),c(c){}//初始化，初始方向都向右};classPath{private:introws;//迷宫的行数intcols;//迷宫的列数public:Path();//默认构造函数vectorfindpath(constvector&s);//寻找路径};（2）路径搜索函数的实现函数vectorPath::findpath(constvector&s)是迷宫路径搜索的核心算法[19]。算法的思想是当沿着某条路径走不通时，就后退一步或者多步，选择其他路径，直到找到出口为止。此过程需要使用一个栈来记录试探过程中所走过的路径信息。这个栈中成员的数据类型就是辅助类所定义的三元组结构。当某个方向走不通时，就需要从栈中调取信息来改变方向；当所有方向都走不通时，即表示走进死胡同，就需要从栈中调取信息后退到上一个位置。这个函数的实现不是依赖递归，而是通过一个循环算法，循环终止的条件是找到出口，算法流程图如图2.8所示：13 安徽大学本科毕业论文图2.8：迷宫路径搜索算法流程图14 安徽大学本科毕业论文2.4结果展示图2.9：行数为15，列数为16的迷宫（左图）及其路径（右图）图2.10：行数为25，列数为26的迷宫（左图）及其路径（右图）15 安徽大学本科毕业论文3迷宫的3D建模在绪论部分介绍了3D建模的概念，目前，应用比较广泛的3D建模软件主要是Autodesk公司旗下的3DSMax、Maya以及zBrush。但是这些建模软件都有文件庞大、操作不便、入门困难等缺点，因此，针对本研究课题，选用OpenSCAD这款小巧实用的建模软件用于迷宫玩具的3D建模技术开发。本章首先进一步分析迷宫的数据结构，然后通过OpenSCAD建模软件建立两种迷宫玩具的模型：基于圆柱造型的迷宫玩具模型和基于球造型的迷宫玩具模型。3.1迷宫分析通过第二章的内容已经知道迷宫实际上可以看成是生成树，可以用图来表示一个迷宫，并且利用随机迷宫生成算法可以生成指定大小的迷宫。迷宫玩具的3D建模需要用到能够刻画迷宫的相关数据，因此需要进一步分析迷宫，从原始的迷宫图中抽象出迷宫的数据结构，首先引入迷宫中点和边两个概念。（1）顶点：迷宫图中的最小单元，包括通道和墙壁。顶点有两个属性：顶点的坐标(m，n）和顶点的索引index。坐标（m，n）表示该顶点位于第m+1行第n+1列。顶点的索引与顶点的坐标是一一对应的，设迷宫图左上角第一个顶点的索引为0，逐列往下索引。顶点的结构类型定义如下：typedefstruct{intm;//顶点的横坐标intn;//顶点的纵坐标intindex;//顶点的索引}point；（2）边：一行或一列上连续的通道组成。边有三个属性：起点、终点和方向。方向分为横向和纵向。如果边的方向是横向，则起点的左边邻接点是墙壁，终点的右边邻接点是墙壁。如果边的方向是纵向，则起点的上边邻接点是墙壁，终点的下边邻接点是墙壁。在这里，需要考虑迷宫的左右两侧相通，也就是说边可以连接迷宫的左右两侧，边的结构类型定义如下：typedefstruct{typedefenum{col,row}DIR；pointstart；//起点pointend；//终点DIRdir；//方向}edge；16 安徽大学本科毕业论文图3.1：行数为15，列数为16的迷宫表示假设有如图3.1形式的迷宫，则迷宫中的横向边集合可以表示为：[1,2,1,8],[1,10,1,0],[3,4,3,6],[3,12,3,0],[5,6,5,8],[5,10,5,12],[7,0,7,2],[7,4,7,6],[7,8,7,14],[9,6,9,8],[9,10,9,12],[9,14,9,0],[11,0,11,2],[11,4,11,6],[11,8,11,10],[11,12,11,14],[13,0,13,14]纵向边集合可以表示为：[0,2,5,2],[1,8,5,8],[1,10,5,10],[1,12,3,12],[3,0,7,0],[3,4,11,4],[5,6,7,6],[5,12,7,12],[5,14,9,14],[7,2,11,2],[9,6,11,6],[9,8,11,8],[9,10,11,10],[9,12,11,12],[11,0,13,0],[11,14,14,14]例如[1,2,1,8]表示一条边，起点是（1，2），终点是（1，8），方向是横向。[1,10,1,0]表示一条连接迷宫左右两侧的边，起点是位于最后一列的（1，10），终点是位于第一列的（1，0），方向是横向。3.2基于圆柱造型的迷宫玩具建模3.2.1建模思路OpenSCAD的建模方式主要是以基本几何体为操作单位，然后通过布尔运算生成所需要的几何形体。基于圆柱造型的迷宫玩具建模的总体思路是在圆柱体外表面做布尔差运算，即在圆柱体外表面减去迷宫的通道部分，就可以在圆柱体外表面创建一个迷宫。17 安徽大学本科毕业论文建模的主要内容有：（1）圆柱体：这是迷宫的载体，圆柱体的高度和半径要和迷宫的行数与列数对应，防止迷宫的通道和墙壁过宽或过窄。（2）通道：这是建模的核心内容。包括横向通道和纵向通道。3.2.2通道建模为了迷宫玩具的美观，规定通道设计的要求如下：（1）通道的横截面是梯形；（2）横纵通道相交时能够契合；（3）横纵通道能够环绕在圆柱体的外表面。为了保证要求（2），横纵通道的宽度设置必须一致。对于要求（3），需要将横纵通道根据坐标和长度排布在圆柱体外表面。OpenSCAD中的线性挤出操作可以将平面图形沿Z轴方向拉伸挤出为三维模型。对于纵向通道的设计，先对梯形线性挤出，然后对两个挤出后的梯形做布尔交运算。图3.2：左图为纵向通道生成示意图，右图为长度为3的纵向通道模型OpenSCAD中的旋转挤出操作可以将平面图形绕Z轴方向旋转一周挤出为三维模型。对于横向通道的设计，先对梯形旋转挤出一个与圆柱体同半径的圆管，然后将这个圆管和扇形做布尔交运算，横向通道的长度由扇形的圆心角决定。图3.3：左图为横向通道生成示意图，右图为长度为3的横向通道模型18 安徽大学本科毕业论文3.2.3模型生成通道建模完成之后，再将生成的横纵通道按照迷宫的形状排布在圆柱体的外表面。排布的代码如下：modulepolar(x,y,off=bolt_r)//OpenSCAD中的封装。（x，y）表示通道所代表的边的起点坐标，off表示圆柱体的半径{rotate([0,0,arcw]*y)//绕Z轴旋转，arcw表示迷宫每一列所占的角度translate([off,0,x*channel])//平移，channel表示迷宫通道的宽度children();//子对象，表示横向通道或纵向通道}完成最后的布尔减运算之后，得到最终的基于圆柱造型的迷宫玩具模型，如图3.4所示：图3.4：基于圆柱造型的迷宫玩具模型3.3基于球造型的迷宫玩具建模采用3.2中设计基于圆柱造型的迷宫玩具模型的思路，同样可以设计出基于球造型的迷宫玩具模型，这样做是可行的，理由如下：（1）球面是不可展曲面，可以采用近似展开的方法展开球面。球面上的点除了南北极外，与平面上的点是一一对应的；（2）本课题研究的迷宫要求第一行和最后一行只能放置入口和出口，因此可以将球的南北极设置为入口和出口，而不改变迷宫的形状结构；（3）迷宫的横纵通道可以沿着球的经纬线摆放。19 安徽大学本科毕业论文基于球造型的迷宫玩具是以球体作为迷宫载体，对于通道的设计有如下要求：（I）通道的形状是圆管状，因此同样采用线性挤出操作；（II）由于球的特殊结构，迷宫的横纵通道的几何形状应当是一样（图3.5）；（III）为了使横纵通道在相交处能够契合，在横向通道的两侧添上和圆管横截面的半径同样大小的球（图3.5右图)；图3.5：左图为纵向通道，右图为横向通道（IV）摆放通道时，球的外表面应该适当高于通道圆管横截面的圆心，这样设计的原因是防止迷宫内的游戏滚珠掉落（图3.6）；图3.6：左图为球的外表面经过球心，右图为球的外表面高于球心图3.7：在横向通道两侧添加小球使横纵通道在相交处契合（V）迷宫的中间一行放置在球的赤道处。20 安徽大学本科毕业论文完成最后的布尔减运算之后，得到最终的基于球造型的迷宫玩具模型，如图3.8所示：图3.8：基于球造型的迷宫玩具模型21 安徽大学本科毕业论文4软件设计前面两章分别介绍了迷宫算法和迷宫玩具的3D建模，本章阐述在C++和Qt库编程的基础上迷宫玩具三维建模软件的设计与实现。4.1迷宫玩具三维建模软件的整体架构本套迷宫玩具三维建模软件是基于随机生成的迷宫实现软件的几个主要功能：二维迷宫显示，迷宫游戏，迷宫玩具的三角网格数据文件生成及三维显示，因此软件相应地分为三个层次(图4.1)：（1）随机迷宫生成：这是软件的底层，整个软件的功能是以底层的随机迷宫为基础，底层主要为上层提供数据。软件的底层应该封装良好，但是需要从用户界面获取迷宫的相关信息，如行数和列数。（2）功能实现：这是软件的核心层次，这一层次将会对底层数据进行处理，实现软件的主体功能。为了实现程序良好的封装，应该将功能实现与用户界面分离开来。用户界面只是用来获取数据。而功能实现只实现和用户界面之间的消息传递。（3）用户界面：这是软件的人机交互接口。通过该接口，用户向系统发送命令或输入数据，系统相应地将执行结果反馈给用户。交互功能是用户界面的核心，主要是通过Qt的信号和槽机制实现的。图4.1：迷宫玩具3D建模软件的整体架构示意图4.2软件的设计与实现4.2.1随机迷宫生成用户在交互界面输入迷宫的尺寸，然后生成适合设计迷宫玩具的迷宫图。这里使用的生成算法是第二章介绍的随机迷宫生成算法。22 安徽大学本科毕业论文4.2.2功能实现（1）2D迷宫绘制2D迷宫绘制要实现的功能是将随机生成的迷宫在Qt主窗口显示出来，用灰色正方形表示一个墙壁单元，空格表示通道单元，如图4.2所示：图4.2：2D迷宫绘制Qt绘图要用到QPainter类，利用QPainter类绘制时首先要定义一个QPainter类的对象，然后设置Qpen(画笔)或QBrush(画刷)的颜色、大小等属性。绘图时，只要实现QWidget类的paintEvent(QPaintEvent*)方法即可。主要代码为：voidimagewidget::paintEvent(QPaintEvent*paintevent){QPainterpainter;painter.begin(this);painter.setBrush(Qt::gray);//设置笔刷颜色为灰色if(draw_status_){vectorptr;ptr=maze->printMaze();//获取迷宫信息intm=ptr.size();intn=ptr[0].size();for(inti=0;i