基于元胞遗传算法的3D动漫造型设计研究.pdf

学号：2010021161 姓名：杨晓鹏 联系电话email： 所在学院：信息科学与工程学院 单 位 代 码单 位 代 码 10445 学学 号号 2010021161 分分 类类 号号 tp391.72 研 究 生 类 别研 究 生 类 别 全 日 制全 日 制 硕硕 士士 学学 位位 论论 文文 （学学 术术 学学 位位） 论 文 题 目：基于元胞遗传算法的 3d 动漫 造型设计研究 学科专业名称：学科专业名称：计算机软件与理论计算机软件与理论 申申 请人姓请人姓 名：名：杨晓鹏杨晓鹏 指指 导导 教教 师：师：刘刘 弘弘 教授教授 论文提交时间：论文提交时间：2012 年年 06 月月 15 日日 独独 创创 声声 明明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果， 也不包含为获得 （注： 如没有其他需要特别声明的， 本栏可空） 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解 学校学校 有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。 本人授权 学校学校 可 以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、 缩印或扫描等 复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本授权书） 学位论文作者签名： 导师签字： 签字日期：20 年 月 日 签字日期：20 年 月 日 山东师范大学硕士学位论文 目目 录录 摘要摘要 i abstractabstract iii 第一章第一章 绪论绪论 1 1.1 研究背景及意义 1 1.2 3d 动漫造型设计面临的问题 . 2 1.3 论文的主要工作及创新点 . 2 1.4 组织结构 3 第二章第二章 相关工作相关工作 . 5 2.1 引言 5 2.2 3d 动漫造型设计研究现状 5 2.2.1 3d 动漫发展简述 . 5 2.2.2 计算机辅助 3d 动漫造型设计研究现状 . 6 2.3 进化计算在创新设计中的研究现状 7 2.4 元胞遗传算法研究现状 9 2.5 本章小结 10 第三章第三章 元胞遗传算法的基础理论元胞遗传算法的基础理论 . 11 3.1 引言 11 3.2 遗传算法 11 3.2.1 遗传算法概述 11 3.2.2 标准遗传算法的描述 . 12 3.2.3 标准遗传算法的基本流程 . 12 3.2.4 遗传算法的特点 14 3.3 元胞自动机 15 3.3.1 元胞自动机概述 15 3.3.2 元胞自动机的构成 15 3.4 元胞遗传算法 . 19 3.4.1 元胞遗传算法概述 19 3.4.2 元胞遗传算法的主要操作 . 19 3.4.3 元胞遗传算法的基本流程 . 20 3.5 本章小结 21 第四章第四章 改进的元胞遗传算法改进的元胞遗传算法 . 22 4.1 引言 22 4.2 基于树结构的元胞遗传算法 22 4.2.1 acis 研究 22 4.2.2 树结构编码 24 4.2.3 基于树结构的元胞操作 25 4.3 交互式元胞遗传算法 27 4.3.1 隐性指标设置 . 27 4.3.2 显性指标设置 . 28 山东师范大学硕士学位论文 4.4 引入演化规则的元胞遗传算法 . 28 4.4.1 演化规则概述 . 29 4.4.2 基于专家知识的演化规则 . 29 4.5 本章小结 31 第五章第五章 基于改进元胞遗传算法基于改进元胞遗传算法 eticgaeticga 的的 3d3d 动漫造型创新设计方法动漫造型创新设计方法 . 32 5.1 引言 . 32 5.2 基于 eticga 的 3d 动漫造型创新设计方法 . 33 5.2.1 eticga 概述 33 5.2.2 m-eticga 方法概述 34 5.3 3d 动漫造型创新设计方法比较实验 37 5.3.1 与基于 tiga 的方法比较 . 37 5.3.2 与基于 ticga 的方法比较 . 37 5.4 3d 动漫造型创新设计实例 . 38 5.4.1 小博士造型的创新设计过程 38 5.4.2 小博士创意造型展示 . 41 5.5 本章小结 42 第六章第六章 3d3d 动漫造型设计系统模块动漫造型设计系统模块 . 43 6.1 引言 . 43 6.2 3d 动漫造型设计模块介绍 . 43 6.2.1 造型数据管理 . 44 6.2.2 造型进化设计 . 44 6.3 3d 动漫造型展示 45 6.3.1 游泳男孩 46 6.3.2 稻草人 . 47 6.3.3 红发小姑娘 47 6.3.4 卡通小猪 48 6.3.5 卡通女精灵 48 6.3.6 卡通男精灵 48 6.4 动画作品展示 48 6.5 本章小结 49 第七章第七章 总结与展望总结与展望 . 50 7.1 总结 . 50 7.2 展望 . 51 参考文献参考文献 . 52 攻读硕士学位期间的主要成果攻读硕士学位期间的主要成果 56 致谢致谢 57 山东师范大学硕士学位论文 i 基于元胞基于元胞遗传算法遗传算法的的3d动漫造型设计研究动漫造型设计研究 摘要摘要 作为造型艺术的分支之一， 动漫一直深受世界各地人们的喜爱。 在动漫产业飞速发展 的今天，随着动漫与 3d 技术的紧密结合，3d 动漫已然成为了推动动漫及其衍生产品发 展的重要力量。从现有的优秀 3d 动漫作品不难发现，无论是玩具总动员中那些精灵 古怪的卡通玩具，还是功夫熊猫中那些身怀绝技的武林高手，创意新颖的 3d 动漫造 型是决定一部动漫作品成功与否的关键要素。 成功设计的动漫造型不但能得到观众的喜爱 和推崇， 提升动漫作品的票房号召力， 而且对于整个动漫产业及其衍生产品的发展起着至 关重要的作用。 传统的 3d 动漫造型设计大多是通过三维动画软件，如 maya、3d max 等完成的，虽 然这种方法绘制出的造型精致美观，但是却面临着造型创意性不足、设计周期长、制作成 本高等诸多问题。 就造型创意性不足来说， 原因是由于造型设计师在设计过程中往往会受 到已有造型和设计观念的限制，无法设计出足够吸引人眼球、让人过目不忘的创新造型； 就造型设计周期长、制作成本高来说，虽然 maya 等三维动画软件功能强大，但是熟练掌 握它不仅需要用户兼具计算机和美术的相关知识， 还需要一个长期的学习过程， 不仅如此， 每一个造型从设计、 绘制到完成都需要耗费设计师大量的时间精力， 这无疑在一定程度上 延长了设计周期、提高了制作成本。因此，如何快速且自动地生成创意新颖的 3d 动漫造 型成为当下计算机辅助创新设计的研究热点。 本文以激发造型设计师创作灵感、辅助其高效完成造型制作为目标，针对传统 3d 动 漫造型设计面临的以上问题开展研究。本文的主要工作及创新点概括如下： 1. 将元胞遗传算法引入计算机辅助 3d 动漫造型设计中。 元胞遗传算法(cellular genetic algorithm, cga)具有收敛速度快、寻优性能好和能够 丰富种群多样性的优点，结合计算机辅助设计思想和进化计算技术，本文将 cga 应用于 3d 动漫造型设计中，以期借助其独特的优势快速高效地生成大量创意新颖的 3d 动漫造 型。为了较好地将 cga 应用到计算机辅助 3d 动漫造型设计中，对 cga 进行了改进，提 出了基于树结构的元胞遗传算法(cellular genetic algorithm based on tree-structure coding, tcga)、交互式元胞遗传算法(interactive cellular genetic algorithm, icga)和引入演化规 则的元胞遗传算法(cellular genetic algorithm with evolutionary rules, ercga)， 分别有效 地解决了直接应用 cga 到 3d 动漫造型设计时所遇到的编码困难、适应度函数难以确定 以及加入人机交互后，人机交互次数过多的问题。 2. 提出了一种基于改进元胞遗传算法 eticga 的 3d 动漫造型创新设计方法。 结合 tcga、icga 和 ercga，提出了一种综合的改进元胞遗传算法引入演化 规则的树结构交互式元胞遗传算法(interactive cellular genetic algorithm based on tree-structure coding with evolutionary rules, eticga)， 该算法使用树结构编码方式对规则 山东师范大学硕士学位论文 ii 表达式进行编码， 利用专家打分的方式对造型进行评价， 同时采用基于专家知识的演化规 则对造型状态进行动态改变。由于 eticga 继承了 tcga、icga 和 ercga 各自在三维 造型设计上的优势，能够全面符合 3d 动漫造型创新设计的要求，故本文在其基础上提出 了基于 eticga 的 3d 动漫造型创新设计方法(m-eticga)， 有效地解决了传统造型设计 方法中造型创意性不足、设计周期长且制作成本高的问题。 3. 在山东省科技攻关项目“基于进化计算的协同三维动漫创作系统”的基础上，将 本文研究内容加入了原型系统中，实现了基于 eticga 的 3d 动漫造型设计模块。通过一 系列 3d 动漫造型的设计实验表明，本文提出的 m-eticga 方法不仅能够在一定程度上 提高造型的变形进化效率， 还可以快速高效地设计出数量众多且创意新颖的3d动漫造型， 激发设计师的创作灵感，降低动画制作成本，提高工作效率。 关键词关键词 创新设计；3d 动漫造型；元胞遗传算法；树结构编码；人机交互；演化规则 中图法分类号中图法分类号 tp391.72 山东师范大学硕士学位论文 iii research on 3d animation modeling design based on cellular genetic algorithm abstract as a branch of modeling art, animation has been appreciated by people all over the world. in the rapid development of todays animation industry, animation and 3d technology integrate with each other more closely, and 3d animation has already become an important force to promote the development of animation and its derivative product. it is not difficult to find the existing outstanding 3d animations, such as the funny cartoon toys of toy story and the martial arts masters of kung fu panda, that creative 3d animation modelings are the core elements of the excellent animations. successful design of animation modelings can not only get loved and respected by audience, enhance the box-office appeal of the animation itself, but also play a vital role for the development of the entire animation industry and its derivative industry. the traditional design method of 3d animation modelings, by which can obtain attractive and precise 3d animation modelings, is to use three-dimensional modeling software such as maya or 3d max to draw directly. however, this method is faced with many problems, for instance, the lack of creativity, long design circle, high production costs, etc. for the problem of the lack of creativity, the reason is that animation designers are often subject to the limitation of the existing modelings and design concepts in the design process, therefore, they can not design creative modelings which are attractive and unforgettable enough. for the problem of long design circle and high production costs, the reason is that although the 3d animation software are powerful, to skillfully master them not only requires users to have knowledge of computer technology and aesthetics at the same time, but also need a long learning process of modeling. moreover, it takes the designers a lot of time and energy to design, draw and complete each modeling, and this will undoubtedly extend the design circle and increase the costs to some extent. therefore, how to quickly and automatically generate creative 3d animation modelings has become a research focus of the present computer-aided creative design. aiming at inspiring designers and assisting them to make modelings more efficiently, a research is carried out in this paper to solve the problems that traditional 3d animation modeling design is faced with. the main work and innovation of this paper are summarized as follows: 1. cellular genetic algorithm is introduced to the computer-aided 3d animation modeling design. cellular genetic algorithm (cga) has great advantages that are fast speed of convergence, good performance of optimization, and the ability of enriching the diversity of populations. combined with computer-aided design ideas and evolutionary computation techniques, cga is 山东师范大学硕士学位论文 iv introduced to the computer-aided 3d animation modeling design, in order to quickly and efficiently generate diverse and innovative 3d animation modelings with its unique advantages. to apply cga to creative design of 3d animation modelings better, this paper firstly improves cga and proposes cellular genetic algorithm based on tree-structure coding (tcga), interactive cellular genetic algorithm (icga) and cellular genetic algorithm with evolutionary rules (ercga), which are effectively solve the problems of coding, the difficulty of determining fitness functions and the problem of a large number of human-computer interactions respectively. 2. a creative design method of 3d animation modelings based on improved cellular genetic algorithm (eticga) is proposed. combined with tcga, icga and ercga, an integrated improved cellular genetic algorithm is proposed, which is interactive cellular genetic algorithm based on tree-structure coding with evolutionary rules (eticga), and this algorithm uses tree-structure coding to encode acis rule expressions, utilizes the way of experts grading to evaluate the modelings, and adopts evolutionary rules based on experts knowledge to change the state of modelings dynamically. due to the fact that eticga inherits all advantages of tcga, icga and ercga in three-dimensional modeling design so that it can fully meet the requirements of the creative design of 3d animation modelings, a creative design method of 3d animation modelings based on eticga (m-eticga) is introduced, which can effectively solve the problem of the lack of creativity, long design circle, high production costs, etc. 3. based on shandong province science and technology research project of the cooperative creation system of 3d animation models based on evolutionary computation, above researches are inserted into the prototype system, and a 3d animation modeling design module based on eticga is developed. experimental results show that the efficiency of deformation and evolution of 3d animation modelings based on m-eticga has been improved to some extent, moreover, this method can quickly and efficiently generate a large number of creative 3d animation modelings, inspire designers, help reduce production costs, and improve work efficiency. keywords: creative design; 3d animation modeling; cellular genetic algorithm; tree-structure coding; human-computer interaction; evolutionary rules 山东师范大学硕士学位论文 1 第第一一章章 绪绪论论 1.1 研究背景及研究背景及意义意义 “动漫”一词，实际上是动画和漫画的合成与缩写。随着现代传媒技术的发展，动画 和漫画之间联系日趋紧密，两者常被合称为动漫。作为造型艺术的一门分支，动漫一直深 受世界各地人们的喜爱。 随着近些年我国对动漫产业的扶持和推动， 中国已经进入从动漫大国向动漫强国跨越 的攻坚期，动漫产业随即成为了人们关注的焦点。所谓动漫产业，它是指以“创意”为核 心，以动漫为表现形式，包含动漫图书、报刊、电影、电视、音像制品、舞台剧和基于现 代信息传播技术手段的动漫新品种等动漫直接产品的开发、生产、出版、播出、演出和销 售，以及与动漫形象有关的服装、玩具、电子游戏等衍生产品的生产和经营的产业。作为 一个新兴产业，因其有着广泛的发展前景，动漫产业被称为 21 世纪“新兴的朝阳产业” 和“无烟产业” 。对于美国、日本、韩国等动漫大国，其动漫产业每年的产值在全国生产 总值中占据重要比例。拿日本来说，日本动漫产业俨然已成为日本的第三大产业，规模已 突破 2000 亿日元，动画产品出口值远远高于钢铁出口值。相对于美日韩等动漫强国，我 国现阶段依然处于动漫产业发展的探索阶段。据统计，我国 2004 年动漫产业总产值高达 117 亿元人民币， 2005 年动漫产业总产值达到了 180 亿元人民币， 并且中国动漫市场还有 1000 亿元人民币的产值空间等待开发。面对如此巨大的市场商机和文化影响力，为了推 动民族动画产业奋起直追，国家相继制定出台了一系列扶持动画产业振兴发展的政策措 施，大力发展动漫产业。除了注意到动漫产业迅猛发展的势头，我们还需要重视我国动漫 产业发展中的诸多问题和困难。 振兴中国动漫产业必须摈弃一味的模仿美国和日本等动漫 强国，关键在于要不断地挖掘和探索如何制作高品质且创意优秀的动漫作品。 对于一部成功的动漫作品， 动漫造型起到了核心且至关重要的作用。 在世界上许多获 得过巨大成功的动漫作品中，如迪斯尼早起的米老鼠与唐老鸭 、 猫和老鼠 、 白雪公 主与七个小矮人 、 狮子王 ，再到现如今风靡全球的怪物史瑞克 、 功夫熊猫 ，还有 在日本动漫作品中，深受世界各地人们喜爱的 hellokitty、樱桃小丸子、机器猫，这些造 型独特、创意新颖的动漫形象以其独特的艺术魅力征服了世界各地的观众。可见，一个独 特新颖的动漫造型不仅能够吸引观众眼球，同时也是一个动漫作品成功与否的关键。 在动漫产业飞速发展的今天，动漫与 3d 技术结合更加紧密，更多 3d 动漫受到了人 们的喜爱和追捧。 造型作为衡量一部动漫作品成败与否以及受欢迎程度的重要指标， 已经 越来越受到人们的关注与重视。作为 3d 动漫的核心问题，如何快速高效地生产出创意新 颖且吸引人眼球的 3d 动漫造型已经成为了当下的研究热点。 山东师范大学硕士学位论文 2 1.2 3d 动漫造型设计面临的问题动漫造型设计面临的问题 目前，3d 动漫造型主要是通过三维动画软件，如 maya、3d max 等绘制生成，虽然 通过该方法绘制的 3d 动漫造型精致美观，但是却面临着造型创意性不足、设计周期长、 制作成本高等诸多问题。 就造型创意性不足来说， 由于人类的设计灵感有限， 造型设计师在设计过程中往往会 受到已有造型和设计观念的限制， 因此无法设计出足够吸引人眼球、 让人过目不忘的创新 造型，而且容易生成雷同的设计作品，这对于设计要在动画作品中担任主角的 3d 动漫造 型(简称为 3d 动漫角色造型)来说无疑是一个致命伤。 就造型设计周期长、制作成本高来说，虽然 maya、3d max 等三维动画软件功能强 大， 但是熟练掌握它不仅需要用户兼具计算机和美术的相关知识， 还需要一个长期的学习 过程。不仅如此，每一个造型从设计、绘制到完成都需要耗费设计师大量的时间精力，特 别是在群体动画制作中，由于制作群体造型的工作量巨大，利用传统的设计方法，设计师 需要花费相当多的时间和精力在造型的设计和绘制中，速度过慢、成本过高、且无法自动 生成大量的造型。 因此，无论对于 3d 动漫角色造型还是对于 3d 动漫群体造型的制作，都迫切需要一 种计算机辅助设计环境， 能够激发动漫设计师的创作灵感， 辅助其快速且高效地生成新颖 独特的 3d 动漫造型。 1.3 论论文文的的主要工作及主要工作及创新点创新点 本文在研究元胞遗传算法和 3d 动漫造型技术的基础上，结合可视化技术，以解决传 统 3d 动漫造型设计所面临的问题、设计支持 3d 动漫造型创新设计的方法、提高造型的 新颖程度和生成效率为目标开展研究工作，本文的主要工作与创新点概括如下： 1. 将元胞遗传算法引入计算机辅助 3d 动漫造型设计中。 元胞遗传算法1是元胞自动机与遗传算法的结合体， 该算法使用元胞自动机的演化规 则来代替遗传算法中传统的交叉机制。 在算法执行过程中， 将进化个体映射到拓扑分布中， 个体间的遗传操作限制在其相应邻域内， 依据一定的更新策略， 通过局部个体间的相互作 用实现全局最优解的搜索。 该算法不仅具有良好的收敛性和寻优性， 还为优秀个体提供了 一种高效的迁移方法，由于最优解在整个种群当中逐渐传播，种群的个体出现多元化、多 样性的可能性就会加大。可见，运用元胞遗传算法利于快速生成 3d 动漫造型，且易于生 成丰富多样的创新造型。 然而，在直接结合标准元胞遗传算法和 3d 动漫造型设计时，我们遇到了以下几个困 难： 1) 元胞遗传算法在编码方式上一般采用与标准遗传算法相同的定长二进制编码。然 而，在 acis 造型平台上对 3d 动漫造型实行非均匀缩放变形时，使用了由数学表达式组 成的 acis 规则表达式。由于我们无法预知随机产生的 acis 规则表达式的长度和内容， 山东师范大学硕士学位论文 3 使用定长二进制编码对其进行编码是不合理的。 2) 由于在创新设计中没有统一的评价标准， 3d 动漫造型的适应度值难以用统一的适 应度函数计算。如何对生成的造型进行评价，成为使用元胞遗传算法对 3d 动漫造型进行 变形进化的一大难点。 为了将元胞遗传算法较好地应用到 3d 动漫造型创新设计中， 利用元胞遗传算法的优 良特性，快速高效地生成创意新颖且数量众多的 3d 动漫造型。针对以上困难，本文在标 准元胞遗传算法的基础上进行了以下的改进，提出了相应的改进元胞遗传算法： 1) 为了更好地发挥 acis 在造型设计中的作用，方便数学表达式的生成，本文采用 一种更为灵活的基于树结构的编码方式，提出了基于树结构的元胞遗传算法(cellular genetic algorithm based on tree-structure coding, tcga)； 2) 本文在元胞遗传算法的基础上引入人机交互方式，利用专家知识确定造型的适应 度值从而解决了造型的适应度值难以用统一的适应度函数计算的难题， 由此通过融入更多 专家的主观因素以生成更多符合大众审美标准的造型，提出了交互式元胞遗传算法 (interactive cellular genetic algorithm, icga)； 3) 由于人的工作能力有限，为了减少人机交互过程中专家的打分次数，本文引入了 一种基于专家知识的演化规则，提出了引入演化规则的元胞遗传算法(cellular genetic algorithm with evolutionary rules, ercga)。 2. 提出了一种基于改进元胞遗传算法 eticga 的 3d 动漫造型设计方法。 基于 tcga、icga 和 ercga，提出了一种综合的改进元胞遗传算法引入演化 规则的树结构交互式元胞遗传算法(interactive cellular genetic algorithm based on tree-structure coding with evolutionary rules, eticga)， 该算法使用树结构编码方式对规则 表达式进行编码， 利用专家打分的方式对造型进行评价， 同时采用基于专家知识的演化规 则对造型状态进行动态改变。由于 eticga 继承了 tcga、icga 和 ercga 各自在三维 造型设计上的优势，能够全面符合 3d 动漫造型创新设计的要求，故本文在其基础上提出 了基于 eticga 的 3d 动漫造型创新设计方法(m-eticga)，有效地解决了传统造型设计 方法中造型创意性不足、设计周期长且制作成本高的问题。 3. 在山东省科技攻关项目“基于进化计算的协同三维动漫创作系统”的基础上，结 合以上研究内容，将改进元胞遗传算法 eticga 加入到了原型系统中，实现了基于 eticga 的 3d 动漫造型设计模块。通过一系列 3d 动漫造型的设计实验表明，本文提出 的方法不仅能够在一定程度上提高造型的变形进化效率， 还可以快速高效地设计出创意新 颖且数量众多的 3d 动漫造型，激发设计师的创作灵感，降低动画制作成本，提高工作效 率。 1.4 组织结构组织结构 本论文共分为七章论述了基于元胞遗传算法的 3d 动漫造型设计， 其组织结构图如图 1-1 所示： 山东师范大学硕士学位论文 4 将元胞遗传算法进行改进， 使之适用于三维造型创新设计 提出问题 分析问题 第二章 相关工作 综合改进的元胞遗传算法，并在其基础 上提出支持3d动漫造型创新设计的方法 第五章 基于改进元胞遗传算法 eticga的3d动漫造型创新设计方法 第六章 3d动漫造型设计系统模块 第七章 总结与展望 第一章 绪论 解决问题 结 论 第四章 改进的元胞遗传算法 第三章 元胞遗传算法的 基础理论 图图 1-1 论文组织结构图论文组织结构图 第一章介绍了本文的研究背景及研究意义， 分析了3d动漫造型设计当前存在的问题。 随后，对本文的主要工作及创新点加以概述。最后，给出了本文的整体组织结构。 第二章讨论了3d动漫造型设计的研究现状、 进化计算在创新设计中的相关研究工作， 以及元胞遗传算法的研究现状。 第三章阐述了元胞遗传算法的基本理论， 对遗传算法、 元胞自动机和元胞遗传算法进 行了概要性的描述，为将元胞遗传算法应用于 3d 动漫造型设计奠定了理论基础。 第四章分别针对将元胞遗传算法应用于 3d 动漫造型所遇到的问题， 提出了三种改进 的元胞遗传算法。 第五章提出了一种综合的改进元胞遗传算法 eticga， 并介绍了基于改进元胞遗传算 法 eticga 的 3d 动漫造型创新设计方法。通过方法比较实验和具体的设计实例，验证了 该方法的高效性和有效性，能够自动生成数量众多且创意新颖的动漫造型。 第六章介绍了在山东省科技攻关项目 “基于进化计算的协同三维动漫创作系统” 的基 础上， 加入本文的研究成果所开发的基于改进元胞遗传算法 eticga 的 3d 动漫造型创新 设计系统模块。最后给出了更多的造型设计实例，验证了本文研究的有效性。 第七章总结了本文的主要工作及创新点， 并提出了今后需要进一步研究的工作和一些 待解决的问题。 山东师范大学硕士学位论文 5 第第二二章章 相关工作相关工作 2.1 引言引言 本章主要介绍了 3d 动漫造型设计的研究现状、 进化计算在创新设计领域的相关研究 工作以及元胞遗传算法的研究现状， 为本文基于元胞遗传算法的 3d 动漫造型设计研究奠 定了基础。 2.2 3d 动漫动漫造型造型设计研究现状设计研究现状 2.2.1 3d 动漫动漫发展简述发展简述 伴随着计算机技术以及软件技术的迅速发展， 动漫设计逐步从传统的人工绘制向现代 的计算机辅助设计转变。 计算机辅助动漫制作时代开始于1963年， bell 实验室的 e.zajac， ken knowlton 等人在 1963 年到 1967 年四年间开始使用了计算机制作动画片2,3。在这一 时期， 研究工作主要是集中在用计算机产生的动态图形来阐明科学理论。 真正将计算机应 用于传统计算机动画制作的研究开始于七十年代初期。著名艺术家 peter folded 利用论文 computer generated key-frame animation4中研制出的辅助动画制作系统 msgen，成功 地制作出一系列的动画影片，其中 hunger 在 1974 年斩获多项国际性电影节大奖。进入 八十年代， 则进入了对计算机动画系统的研究高潮。 随着计算机辅助设计技术和计算机图 形学的发展，1995 年玩具总动员的问世，这是一部完全使用电脑制作、全部使用计 算机 3d 动漫技术创作的动画电影，标志着动漫进入了 3d 时代。 在 3d 动漫飞速发展的今天，3d 动漫的发展并不是一帆风顺的。一方面，虽然现阶 段各种动漫造型层出不穷， 但是人们发现越来越多的造型出现了雷同的情形。 由于人类创 新思维受到各方面因素的影响和制约， 设计并绘制一个足够吸引大众眼球、 让人过目不忘 的造型变得越来越困难。另一方面，对于 3d 动漫来说，由于动漫造型师不能简单地在平 面图上画出三维造型或场景， 所以这时候他们必须借助于一些三维动画制作软件， 如 maya 和 3d max 等。虽然说 maya 和 3d max 功能强大，但是面对如此复杂的系统，使用者需 要同时具备计算机专家和艺术家的相关知识。 对于两个知识结构完全不同的学科， 要求一 个用户同时兼具是非常困难的， 而一个用户能够熟练的运用这类三维动画制作软件还需要 一个相当长的学习过程。不仅如此，每一个造型从设计、绘制到完成都需要耗费设计师大 量的时间和精力。以上的情况无疑在很大程度上延长了 3d 动漫造型的设计周期，增加了 3d 动漫造型的制作成本。近些年来，找到一种自动化、智能化的 3d 动漫造型设计制作 技术成为了广大 cad 专家学者和工程师奋斗的目标。 山东师范大学硕士学位论文 6 2.2.2 计算机辅助计算机辅助 3d 动漫动漫造型设计造型设计研究现状研究现状 为了促进动漫造型设计的初学者能够在短期间内快速完成造型设计， 也为了促进动漫 造型专业设计人员能够设计出更为创新的作品， 开发行之有效的计算机辅助设计系统一直 以来都是 cad 科研人员所面临的难题。经过了长期的钻研和努力，计算机辅助 3d 动漫 造型设计的研究主要集中在交互编辑建模、相片提取建模和数据驱动对象建模三种方法 上。 交互编辑建模交互编辑建模 美国纽约大学的 olga sorkine 和美国比勒菲尔德大学 mario botsch 在 interactive shape modeling and deformation5一文中概括性的介绍了有关交互式3d造型建模和变形的 最新研究成果。 东京大学的 takeo igarashi、satoshi matsuoka 等开发了一种简单且能够快速绘制 3d 造型的素描界面， 用户只需要在二维交互屏幕上画出三维造型的平面图， 系统则会通过提 取平面图的线条自动地构造出相应的 3d 多边形造型。通过该交互技术，系统可以在 10 分钟内自动生成用户画出的一些有趣的造型，如 teddy 小熊、小鸭子等等6。 与之类似的交互式绘制方法还有很多， 大部分都是通过二维交互式界面让用户创新地 画出一些精确且平滑的二维轮廓图形， 使用多种变形技术7,8和一些其他的造型操纵工具9 生成相应的 3d 造型。除了绘制二维轮廓图形10,11制作三维造型外，另外一种方法是画出 造型的内部骨架12。 通过交互编辑建模的方式， 用户能够将自己绘制的平面图形较为快速地转换为三维造 型，如果想要制作精良的动漫作品依然需要有美术专业基础的人员完成设计13。 相片提取建模相片提取建模 现实生活中， 我们可以利用相机随时拍下喜欢的事物， 如果能够通过相片中的平面信 息制作出相应的三维造型一定是一件非常有意义的事情， 而相片提取建模法即是在相片中 提取相应的信息建立三维造型的建模方法。 研究发现， 当输入的是一幅单一图像， 利用相片提取建模方法可能会产生一些与照片 不符的线条或是一些必要的额外绘制线条，如对称性线条14或用户提示线条15等。那么， 在照片完成输入后， 用户可以在单一的图像基础上绘制其自定义的图形和对象， 这就为再 创造提供了一定的条件。鉴于此，kai xu, hanlin zheng 等研究人员提出了一种三维建模 方法，用户可以通过一张拍摄的照片获取灵感并设计 3d 造型16，例如可以从一张普通椅 子的照片出发，绘制出造型各异的椅子造型。 数据驱动对象建模数据驱动对象建模 数据驱动对象建模是指利用现有的三维造型库， 拼装、 组合或变形为其他独特的三维 造型的建模方法。 山东师范大学硕士学位论文 7 布朗大学的 takeo igarashi 和 john f. hughes 提出了一个 3d 造型界面，在该界面里 使用了一些规则来分析用户的行为以便建议系统接下来的自动操作17。举例来说，如果 用户从一个点出发绘制了两个正交线段，那么系统会建议选择生成矩形。 加拿大的justin matejka等科研人员运用数据驱动技术向autocad的用户提供一些未 利用的菜单命令18。 普林斯顿大学的 thomas funkhouser 在文献19中提出了实例建模方法允许用户搜索 模型库并组装所需的模型， 这种方法要求用户搜索他们要添加的特定部分， 由于开放式建 模阶段的最终目标是不确定的，因此在开放式建模阶段使用该方法是不合适的。 英国的 kreavoy vladislav, julius dan 和 sheffer alla 三位学者提出了一种允许用户手 动挑选常用组件，通过交换现有造型间的部分组件生成创新造型的系统20，但是该系统 依赖于现有的造型组件，不能自动生成意想不到的创意新组件。 斯坦福大学的 mark pauly 教授在 2005 年提出了一种创新方法，基于数据驱动技术的 基础上，利用造型库获取并补充不完整造型的信息21，他们的工作重点集中在补充已知 造型的完整性，但没有涉及造型的创新性。 特拉维夫大学的 ran gal 等研究人员提出了一个能够生成 3d 拼贴画的数据驱动界面 22。 为了支持开放性的 3d 造型建模，2009 年斯坦福大学的 talton 运用数据驱动技术开 发了一个实验性的造型生成系统23，但是该系统受限于必须要从绘制模型空间中得到一 个参数空间； 带着相同的目的， 2010年斯坦福大学的siddhartha chaudhuri和vladlen koltun 亦开发了一个基于数据驱动的造型生成系统24，与 talton 相比，该系统的优势是与现有 的几何造型工具兼容。 小结小结 从交互编辑建模和相片提取建模的 3d 动漫造型设计方法可以看出， 两方法虽然直接 明了，但所需设备昂贵，不利于降低动画制作成本，而且无法实现创意造型的自动生成； 而有关数据驱动对象建模的 3d 造型动漫设计方法在创新设计方面的研究也相对较少。 然 而，3d 动漫造型的创新度对于一部动漫作品来说起着至关重要的作用，所以如何利用计 算机辅助设计技术快速高效地生成创意新颖的 3d 动漫造型成为当下亟待解决的问题。 2.3 进化计算进化计算在创新设计中的在创新设计中的研究现状研究现状 进化计算25(evolutionary computation, 简称 ec)是一类基于生物界的自然选择和自 然遗传机制的计算方法，具有高度并行、随机、自适应等特点。进化计算使用群体搜索技 术，将当前种群作为问题解的代表，通过模拟生物进化过程的选择、交叉和变异等一系列 遗传操作，产生新一代种群，并模拟“代代相传”的思想对每一代的种群实施遗传操作， 以达到使种群进化到近似最优的状态。大自然通过“优胜劣汰”进行的过程，蕴含着大量 的丰富信息， 不仅创造了世界万物， 还创造了变幻莫测的秀丽景色。 这给了我们一个启示， 山东师范大学硕士学位论文 8 那就是通过研究自然创造生物的规律，利用进化计算来辅助 3d 动漫造型的创新设计。 创新设计作为计算机辅助设计(computer-aided design, 简