基于 3D建模技术的迷宫玩具开发

安徽大学本科毕业论文 安徽大学 本科毕业论文（设计、创作） 题 目： 基 于 3D 建模技术的迷宫玩具开发 学生姓名： 吴文明 学号： 院（系）： 文典学院 专业： 统计 学 入学时间： 2011 年 9 月 导师姓 名： 王良龙 职称 /学位： 教 授 /博士 导师所在单位： 安 徽大学 数学科学学院 完成时间： 2015 年 6 月 安徽大学本科毕业论文 i 基于 3 迷宫 玩具 开发 摘 要 31世纪最具发展前景的技术。中国的玩具产业长期面临生产成本高、创新设计不足、洋品牌盛行等问题。 3赋予中国的玩具产业新的活力。本文研究 3对市场上迷宫玩具造型单一的问题，研究开发一款能够设计基于不同造型的迷宫玩具的 3文首先阐述通过深度优先遍历算法生成随机迷宫，然后介绍使用 下来是利用 C+编程语言和 件可以设计基于圆柱造型和球造型的两种迷宫玩具，并最终通过 件的实现为玩具的设计与制造提供经验和思路，同时研究也为 3 关键词 : 迷宫； 3D 打印； 3D 建模 ； 深度优先遍历； 徽大学本科毕业论文 D D in 1st in of of D to D in of To in a 3D on of is to be of by it to a D to D of UI + t. of be by DM in of to of as a D in 3D 3D 徽大学本科毕业论文 录 1 绪论 . 1 研究背景 . 1 研究目的 . 2 开发工具与关键技术概况 . 3 3D 建模 . 3 介 . 4 程 . 4 论文主要工作和章节安排 . 6 2 迷宫算法 . 7 图的遍历算法 . 7 深度优先遍历 . 7 广度优先遍历 . 8 迷宫的相关说明 . 8 迷宫的表示 . 8 迷宫的要求 . 9 迷宫与图的联系 . 10 基于图的深度优先遍历的迷宫算法实现 . 11 随机迷宫生成的算法实现 . 11 迷宫路径搜索的 算法实现 . 13 结果展示 . 15 3 迷宫的 3D 建模 . 16 迷宫分析 . 16 基于圆柱造型的迷宫玩具建模 . 17 建模思路 . 17 通道建模 . 18 模型生成 . 19 基于球造型的迷宫玩具建模 . 19 4 软件设计 . 22 迷宫玩具三维建模软件的整体架构 . 22 软件的设计与实现 . 22 安徽大学本科毕业论文 随机迷宫生成 . 22 功能实现 . 23 用户界面 . 26 软件实例 . 27 5 结果展示 . 29 3D 打印技术 . 29 3D 打印的原理 . 29 3D 打印的特点 . 29 3D 打印的问题 . 30 打印迷宫玩具结果 . 30 6 总结与展望 . 32 工作总结 . 32 在的问题及工作展望 . 32 参考文献 . 34 致 谢 . 35 安徽大学本科毕业论文 1 1 绪论 研究背景 人类刚刚步入的 21世纪，一种绿色制造技术迅速吸引公众的眼球，这就是 3D 打印。 3领 21世纪新一轮数字化制造浪潮 1。美国纽约时报称 3会改变大自然的制造方式 2。英国经济学人杂志专题报道 3 33。 30年代中期，目的是抛弃传统工厂流水线的生产模式，通过 3 图 3D 打印机（图片来源 ： 随着生活水平的提高，越来越多的家长开始关注儿童的早期教育。在儿童的早期教育中，玩具，特别是益智玩具备受家长青睐。玩具融合了娱乐性、艺术性和教育性等特点，有助儿童智力开发，激发儿童探索新奇事物，锻炼儿童肢体和感官协调性，培养积极向上的意志品格 4。据统计，中国 16岁以下的儿童约占总人口的五分之一。庞大的人口基数带来巨大的消费需求，这直接导致了玩具市场的繁荣。中国是名副其实的玩具大国，但是中国却不是玩具强国。一方面，由于原材料和劳动力成本的增加而导致生产企业的利润逐步缩减。另一方面，国内外玩具市场被各种洋品牌主导，而外部贸易壁垒高筑，国内品牌难以 “ 走出去 ”5。 3发、制造提供了新的思路，在玩具的制造和开发设计等方面具有显著优势。 降低成本：传统制造业是通过模具加工得到产品。但是，在加工的过程中，切割、磨削、熔融等加工方式无疑会造成原材料的浪费。而 3幅度节省生产成本，缩短生产周期。 安徽大学本科毕业论文 2 个性化设计：英国金融时报记者、新工业革命作者彼得 马什把人类的制造业分为五个阶段：少量定制、少量标准化阶段、大批量标准化生产、大批量定制化和个性化生产 6。 3改玩具，实现真正意义上的个性化定制。 30年代家庭计算机的普及有着极其相似的历史境遇。两种技术都是从造价高昂、体型笨重的机器开始，最开始的用途都是在一些很有限的领域，比如政府机构 7。但是计算机技术发展到现在，其应用已经深入到人类生活的方方面面，彻底影响人类的生活方式。而 3项技术真正得以应用应该归结于技术上的成熟和 易 接受的成本，无论是技术方面还是成本方面， 3快3利于进一步建设创新型国家，推动我国由 “ 工业大国 ” 向 “ 工业强国 ” 转变 8。 研究目的 作为益智 玩具的经典款式之一，迷宫玩具一直是老少皆宜的一类玩具。玩家通过迷宫玩具可以锻炼判断力和记忆力，培养耐心，同时也要求玩家具备一定的综合分析能力和对时空的感知能力，把握整体与局部的关系 9。但是自从迷宫玩具问世以来，一直都保持经典的玩具形式，市场上的迷宫玩具几乎都是基于平面造型的形态 (见图 图 基于平面造型的迷宫玩具（图片来源： ） 笔者在 淘宝 网 和 亚马逊 等 购物网站检索迷宫玩具，发现大部分迷宫都是基于平面造型，市场上尚未出现基于圆柱体或球体造型的迷宫玩具。平面造型的迷宫不仅限制了迷宫玩具的设计与开发，也使得迷宫玩具的造型大同小异，没有创新。 安徽大学本科毕业论文 3 笔者正是出于这样的思考，选择了 “ 基于 3宫 玩具 开发 ” 这一课题。本课题的最终目标是设计一款迷宫玩具的三维模型软件，这款软件能够自动生成不同造型的迷宫玩具模型。 3本研究课题旨在研究如何将 33此为例阐述 3借此推广 3同时希望能够为中国玩具产业特别是益智 玩具的设计与开发提供创意和思路，从而推动中国的玩具产业进一步发展。 开发工具与关键技术概况 3随着计算机技术的发展以及互联网的普及，数字媒体已经渗入人类生活的各个方面。从声音，图片，到视频，再到如今快速发展的 3字媒体的发展通过影响人们的行为方式和思考方式深刻地影响着社会领域的发展，消费业、制造业等都受到来自数字媒体的强烈冲击 10。 图 数字媒体的发展（图片来源于中国科学技术大学刘利刚教授计算机图形学讲义） 3够更加准确地刻画我们的现实世界。将 2入三维世界，通过三维建模软件在虚拟 的 三维空间构建出具有三维 形态 的模型，这就是 33据 3以将 3 工程设计类 ： 主要包括 软件和 软件 。 建筑设计类 ： 。 影视动画类： 3 。 安徽大学本科毕业论文 4 在本课题中选用的建模软件是一款开源的小软件 它对计算机配置要求很低，安装文件小巧，但功能却 是非常强大 。 与其他建模软件相比 ， 图 件界面（图片来源于 ) （ 1）使用脚本语言描述 3不同于 3户 掌握繁琐复杂的按钮操作，取而代之的是简单的 过 译成功之后呈现 3是 过程序设计语言进行 3户可以更加精确地描述 3 （ 2）操作简单，使用方便 与 3装简单，携带方便。由于 时，门简单。 （ 3）支持命令行处理 可以处理命令行。这一优点可以将 写 与 3用程序。 的是为开发跨平台的图形用户界面应用程序提供一个完整的 C+应用程序开发框架。与同类型产品相比， 安徽大学本科毕业论文 5 （ 1）可移植性 利用 需要重新将其编译一遍即可在其他不同的操作系统平台中重复使用，即所谓的 “ 一次编写，随处编译 ” 11。 得开发跨平台 （ 2） 菜单栏，工具栏，进度条等等，用户可以根据需要将不同的窗口部件组合起来创建出用户需要的窗口样式。窗口部件是定义窗口部件则是通过子类化得到 12。 图 图 （ 3）信号和槽机制 信号和槽机制是 12。这种机制是 有 13。 （ 4）多线程 在单线程情况下，交互界面可能会因为一个耗时操作而出现未响应的 “ 假死 ”情况，而多线程编程则可以很好地解决这个问题。 使得它易于开发具 有 可移植性的多线程 14。 安徽大学本科毕业论文 6 论文主要工作和章节安排 本课题研究的主要内容是设计一款专门用于迷宫玩具 3户利用软件可以设计基于不同造型的迷宫玩具，并且最后得到用于 3论文的各章节安排具体如下： 第一章为绪论。本章叙述本课题的研究背景和研究目的，简要介绍了课题研究中所用到的开发工具与关键技术。 第二章为迷宫算法。本章首先介绍与迷宫算法相关的图的遍历算法，然后叙述了随机迷宫生成算法和迷宫路径搜索算法。 第三章为迷宫的 3章详细介绍了用 型和基于球造型的迷宫玩具模型。 第四章为软件设计。本章详细阐述了迷宫玩具 3件的设计与实现以及软件操作实例。 第五章为结果展示。本章主要是介绍 3 第六章为总结与展望。本章总结在完成毕业设计期间的收获和不足，展望未来 3后期的研究奠定基础。 安徽大学本科毕业论文 7 2 迷宫算法 本章将先从图论中经典的遍历算法入手，研究随机迷宫的生成算法和迷宫路径的搜索算法。然后通过 C+编程语言实现这两种迷宫算法。其中，深度优先和广度优先都是图论中解决问题的主要思想。 图的遍历算法 图的传统遍历算法有两种，深度优先遍历（ 广度优先遍历（ 两种算法都是通过迭代的方式对图中的顶点按照 “ 尽可能广 ” 或 “ 尽可能深 ” 的顺序去遍历。由于两种算法都是一种通过边找邻接点的过程，因此两种算法的时间复杂度相同 15。 图 左图为图的深度优先遍历，右图为图的广度优先遍历 深度优先遍历 深度优先遍历可以概括为 “ 能进则进，不进则退 ” 。算法的具体步骤如下 16： : 假设图 意选择某个顶点 问顶点 v，将此顶点作为当前考察点 。 : 依次考察 果未被访问过，则选择该顶点访问并将此顶点作为当前考察点。按照这种方法继续访问下去，如果某个顶点的所有邻接点都被访问过，则退回上一层，换一个邻接点继续访问，直到图 : 若图 在剩下未被访问的顶点中任意选择一个顶点作为当前考察点，重复上述操作，直到图 安徽大学本科毕业论文 8 深度优先遍历的算法如图 深度优先 遍历点的顺序为 ：2-8-3-7。 广度优先遍历 广度优先遍历可以概括为 “ 逐层扩展 ” 。算法的具体步骤如下 17： : 假设图 意选择某个顶点 问顶点 v。 : 考察 次访问其中未被访问过的邻接点。然后分别从这些邻接点出发依次访问它们的邻接点中未被访问过的顶点。按照逐层扩展的原则继续访问，直到图 : 若图 在剩下未被访问的点中任意选择一个顶点作为新的起点，重复上述操作，直到图 广度优先遍历的算法如图 广度优先 遍历点的顺序为 ： 2-4-6-8。 迷宫的相关说明 迷宫的表示 在讨论迷宫的算法之前，首先要解决的问题是迷宫的表示。迷宫的组成元素包括入 口、出口、墙壁和通道。在本课题中，将迷宫表示为一个二维数组 。mn定义一个 m+1行 n+1列的迷宫。二维数组中的元素只能是 0或 1， 0表示该位置是通道， 1表示该位置是墙壁。例如，用 9表示一个行数为 7，列数为 10的迷宫，假设迷宫的入口坐标为（ 0， 2） ，出口坐标为（ 6， 8）（见图 图 迷宫的表示 安徽大学本科毕业论文 9 迷宫的要求 不是所有的迷宫都能用于迷宫玩具的设计，本课题研究的迷宫玩具要求迷宫的左右两侧是连通的。为了能够成功生成迷宫，并且能够将生成的迷宫用于玩具的开发与设计，需要满足如下要求： （ 1）生成迷宫之前，在迷宫的上下两侧添上用 0表示的通道（见图 但是不在左右两侧添上通道，这是为了让迷宫的左右两侧连通。 图 迷宫的上下两侧添上通道 （ 2） 所生成的迷宫有且仅有一条路径； （ 3） 所生成的迷宫不允许出现两条或两条以上的横向或纵向通道并列在 一起（见图 图 左图中三条横向通道并列在一起，右图中三条纵向通道并列在一起 （ 4） 为了方便生成迷宫，要求迷宫的行数为奇数，列数为偶数。迷宫的入口和出口用户可以自己设定，但是必须位于奇数列上。迷宫的第一行和最后一行只能放置入口和出口。 安徽大学本科毕业论文 10 迷宫与图的联系 建立迷宫与图的联系，能够更好地理解迷宫的生成方式，实现迷宫算法。 二维数组中的元素全都是 1的迷宫可以看作是迷宫的初始化（见图 通过初始化的迷宫可以生成各种类型的迷宫（见图 如果将迷宫的每一个元素表示为一个点，并且相邻的点用线段连接（图 这样就将迷宫转化为图论中的图。这个图有两个特点： 第一， 图中不含圈，也就是说路径不是闭合的。第二，这是一张连通图，也就是说图中任意两点都有路径连接。 在图论里，不含圈的连通图被称为树。图 中黑点标记表示迷宫的左右两侧相通。对应地，迷宫可以看作其初始化状态下迷宫的生成树。这样就建立起迷宫与图之间的对应关系，可以用图的理论来研究迷宫。通过深度优先遍历 (或广度优先遍历 (都可以构建出图的生成树，当然也可以用来生成迷宫。本课题中采用深度优先遍历算法。 图 迷宫的初始化 (左图）及其所对应的图（右图） 图 生成后的迷宫 (左图）及其所对应的图（右图） 安徽大学本科毕业论文 11 基于图的深度优先遍历的迷宫算法实现 随机迷宫生成的算法实现 （ 1） 类的设计 通过深度优先遍历实现随机迷宫生成算法，类必须包含的数据成员是迷宫的行数和列数，函数成员主要是实现迷宫生成的函数，而且这个函数必须是递归函数。类的具体设计如下： #00 ; /迷宫的列数 ; /定义一个迷宫上限，防止用户自定义时迷宫的行数或列数越界 ; /迷宫生成函数 /随机搜索迷宫的通道，被 调用 ; /默认构造函数 x,y); /构造函数，定义 x行 ; /打印随机生成的迷宫。 ; （ 2） 迷宫的初始化 迷宫的初始化在构造函数中实现，迷宫的初始化状态全是墙壁，然后需要设置迷宫的上下两侧为通道，设置迷宫的出口和入口。迷宫入口和出口的设置必须要满足 这里，设置迷宫的入口坐标设为（ 0， 2），出口设为最后一行的倒数第二列。 （ 3） 迷宫生成函数的实现 为了保证迷宫的随机性，需要将随机数用于迷宫的生成。 用来产生随机数种子， 利用随机数种子产生随机数。 x, y)是随机迷宫生成的核心算法 18。这是一个递归函数。算法流程图如图 安徽大学本科毕业论文 12 图 随机迷宫生成算法流程图 安徽大学本科毕业论文 13 迷宫路径搜索的算法实现 （ 1） 类的设计 为了实现迷宫路径搜索算法，需要定义两个类，一个是辅助类，作用是定义一个三元组结构，用来记录当前位置和上一个位置的前进方向。另一个类必须包含的数据成员是迷宫的行数和列数，函数成员主要是实现迷宫路径搜索的函数。两个类的具体设计如下： x; y; c; /c=1 表示方向向右， c=2 表示方向向上， c=3 表示方向向左， c=4 表示方向向下 x=0,y=0,c=1):x(x),y(y),c(c) /初始 化，初始方向都 向 右 ; ; /迷宫的列数 ; /默认构造函数 s); /寻找路径 ; （ 2） 路径搜索函数的实现 函数 s)是迷宫路径搜索的核心算法 19。算法的思想是当沿着某条路径走不通时，就后退一步或者多步，选择其他路径，直到找到出口为止。此过程需要使用一个栈来记录试探过程中所走过的路径信息。这个栈中成员的数据类型就是辅助类所定义的三元组结构。 当某个方向走不通时，就需要从栈中调取信息来改变方向；当所有方向都走不通时，即表示走进死胡同，就需要从栈中调取信息后退到上一个位置。这个函数的实现不是依赖递归，而是通过一个循环算法，循环终止的条件是找到出口，算法流程图如图 安徽大学本科毕业论文 14 图 迷宫路径搜索算法流程图 安徽大学本科毕业论文 15 结果展示 图 行数为 15，列数为 16的迷宫（左图）及其路径（右图） 图 行数为 25，列数为 26的迷宫（左图）及其路径（右图） 安徽大学本科毕业论文 16 3 迷宫的 3D 建模 在绪论部分介绍了 3前，应用比较广泛的 3是这些建模软件都有文件庞大、操作不便、入门困难等缺点，因此，针对本研究课题，选用 章首先进一步分析迷宫的数据结构，然后通过 于圆柱造型的迷宫玩具模型和基于球造型的迷宫玩具模型。 迷宫分析 通过第二章的内容已经知道迷宫实际上可以看成是生成树，可以用图来表示一个迷宫，并且利用随机迷宫生成算法可以生成指定大小的迷宫。 迷宫玩具的 3此需要进一步分析迷宫，从原始的迷宫图中抽象出迷宫的数据结构，首先引入迷宫中点和边两个概念。 （ 1） 顶点：迷宫图中的最小单元，包括通道和墙壁。 顶点有两个属性：顶点的坐标 (m， n）和顶点的索引 标（ m， n）表示该顶点位于第 m+1行第 n+1列。顶点的索引与顶点的坐标是一一对应的，设迷宫图左上角第一个顶点的索引为 0，逐列往下 索引 。顶点的结构类型定义如下： m; /顶点的横坐标 n; /顶点的纵坐标 （ 2） 边：一行或一列上连续的通道组成。 边有三个属性：起点、终点和方向。方向分为横向和纵向。如果边的方向是横向，则起点的左边邻接点是墙壁，终点的右边邻接点是墙壁。如果边的方向是纵向，则起点的上边邻接点是墙壁，终点的下边邻接点是墙壁。 在这里，需要 考虑迷宫的左右两侧相通，也就是说边可以连接迷宫的左右两侧，边的结构类型定义如下： /起点 /终点 /方向 安徽大学本科毕业论文 17 图 行数为 15，列数为 16的迷宫表示 假设有如图 迷宫中的横向边集合可以表示为： 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），方向是横向。 基于圆柱造型的迷宫玩具建模 建模思路 后通过布尔运算生成所需要的几何形体。基于圆柱造型的迷宫玩具建模的总体思路是在圆柱体外表面做布尔差运算，即在圆柱体外表面减去迷宫的通道部分，就可以在圆柱体外表面创建一个迷宫。 安徽大学本科毕业论文 18 建模的主要内容有： （ 1）圆柱体：这是迷宫的载体，圆柱体的高度和半径要和迷宫的行数与列数对应，防止迷宫的通道和墙壁过宽或过窄。 （ 2）通道：这是建模的核心内容。包括横向通道和纵向通道。 通道建模 为了迷宫玩具的美观，规定通道设计的要求如下： （ 1）通道的横截面是梯形； （ 2）横纵通道相交时能够契合； （ 3）横纵通道能够环绕在圆柱体的外表面。 为了保证要求（ 2），横纵通道的宽度设置必须一致。对于要求（ 3），需要将横纵通道根据坐标和长度排布在圆柱体外表面。 轴方向拉伸 挤出为三维模型。对于纵向通道的设计，先对梯形线性挤出，然后对两个挤出后的梯形做布尔交运算。 图 左图为纵向通道生成示意图，右图为长度为 3的纵向通道模型 轴方向旋转一周挤出为三维模型。对于横向通道的设计，先对梯形旋转挤出一个与圆柱体同半径的圆管，然后将这个圆管和扇形做布尔交运算，横向通道的长度由扇形的圆心角决定。 图 左图为横向通道生成示意图，右图为长度为 3的横向通道模型 安徽大学本科毕业论文 19 模型生成 通道建模完成之后，再将生成的横纵通道按照迷宫的形状排布在圆柱体的外表面。排布的代码如下： x,y, 。（ x， y）表示通道所代表的边的起点坐标， 示圆柱体的半径 0,0,y) /绕 Z 轴旋转， 示迷宫每一列所占的角度 ,x* /平移， 示迷宫通道的宽度 ; /子对象，表示横向通道或纵向通道 完成最后的布尔减运算之后，得到最终的基于圆柱造型的迷宫玩具模型，如图 图 基于圆柱造型的迷宫玩具模型 基于球造型的迷宫玩具建模 采用 设计基于圆柱造型的迷宫玩具模型的思路，同样可以设计出基于球造型的迷宫玩具模型，这样做是可行的，理由如下： （ 1）球面是不可展曲面，可以采用近似展开的方法展开球面。球面上的点除了南北极外，与平面上的点是一一对应的； （ 2）本课题研究的迷宫要求第一行和最后一行只能放置入口和出口，因此可以将球的南北极设置为入口和出口，而不改变迷宫的形状结构； （ 3）迷宫的横纵通道可以沿着球的经纬线摆放。 安徽大学本科毕业论文 20 基于球造型的迷宫玩具是以