1 动漫产业被视为21世纪创意经济中最有希望的朝阳产业,其中3D动漫是动漫产业的发展方向.3D动漫造型作为3D动漫的核心元素,需要具有足够的创意才能吸引大众的眼球,然而设计师往往受到现有造型和设计观念的影响而很难设计出具有足够创意的造型.因此,如何自动生成新颖奇特的3D动漫造型,辅助设计人员完成造型设计,实现3D动漫制作的自动化和智能化,是一个亟待解决的问题. 目前,3D动漫造型的生成通常利用3D建模软件Maya,3DMax等直接绘制,这种方法获得的3D动漫造型美观、精确,但是速度较慢、成本较高,无法自动生成大量的富有创意的动漫造型.近年来,利用进化计算方法进行产品设计、建筑设计等得到了广泛的关注,并取得了大量的研究成果[1-6].悉尼大学的JohnGero教授进行了利用遗传算法生成建筑平面图的研究[1],展示了如何通过对著名建筑风格的学习进化生成新的建筑物.剑桥大学的制造研究所副研究员AlexandraMelikeBrintrup进行了如何根据定义的评价标准和使用者的身材进化生成各种椅子造型的研究[2].潘云鹤院士及其博士生在创新过程、创新原理的描述和计算模型方面做了很多探索性工作[3],由潘云鹤院士负责的“支持产品创新设计的计算机辅助技术与系统”项目,成功开发了支持产品创新设计的7个计算机辅助软件平台.山东师范大学与香港理工大学在支持创新设计的多Agent协同设计环境方面展开了一系列的研究,做了很多有意义的探索,开发的原型系统通过利用遗传算法及机器学习技术,可以生成形态各异的手机、台灯及建筑外观等造型[4,5].从国内外的研究现状来看,基于进化计算的3D制作已经成为当前研究的热点问题,但是利用进化计算方法制作3D动漫造型的研究还较少. 因此,本文提出一种支持协同设计的3D动漫造型进化计算方法,该方法利用HSF协同技术和C/S模式,以较低的成本、较高的工作效率有效地利用专家知识,实现协同设计;同时利用ACIS规则,通过选择、交叉、变异和精英保留操作产生新的创意新颖的3D动漫造型.实验结果表明,本文提出的方法可以有效地实现3D动漫造型的自动进化,并且可以有效地支持多专家协同设计. 2 基于HSF协同和ACIS规则的交互式遗传算法———HAIGAHAIGA在已有3D动漫造型的基础上,借助专家知识,利用遗传算法实现动漫造型的自动进化,一方面保持了原始初始化种群:采用三种方式生成可以使3D动漫造型变形的ACIS规则表达式.一种是随机生成与种群数等量的ACIS规则表达式;另一种是从数据库中提取出与种群数等量的高质量造型对应的ACIS规则表达式;第三种是随机生成一半,从数据库中提取一半. 专家评分:以处理图像能力强大的图形工作站作为服务器,以一般PC机作为客户端,通过HSF协同将服务器端进化生成的3D动漫造型实时传输到客户端并显示在屏幕上,专家们各自进行评分并提交评分结果,客户端及时将结果反馈给服务器. 适应度值计算:根据各专家的评分及其权威度,计算出加权平均满意度和共识度,然后按比例求和得到适应度值. 新种群产生:根据适应度值,对种群中3D动漫造型对应的ACIS规则表达式执行选择、交叉和变异操作产生新的规则表达式,进而产生新的种群.精英保留:新一代与上一代种群加和后,保留适应度值排在前30%的优良个体. 2.2 HSF协同与ACIS规则 2.2.1 HSF协同 HOOPS/Stream是平台和GUI均独立的C++类的集合,它能够使应用程序通过各种网络有效地传输高度压缩的文件,这个功能使它成为开发工程软件、CAD/CAM/CAE、数字模仿、仿真、可流动的3D造型应用和科学可视化应用的理想组件.它也允许开发者创建仅有的真正开放的可视化标准(HSF),这对于工程和网络用途都是最优的. HSF格式是为数不多的支持2D和3D数据的流格式类型中的一种.HSF被紧密地集成到HOOPS/3dAF和造型工具中,HSF文件被创建时就被压缩、安排好并且随时准备流动这就减少了对3D模型数据耗时的预处理操作.数据被创建时就可以流动,这对于基于C/S模式的应用和通过Web传递是非常重要的.由于其数据是高度压缩的,因此可以大大缩短传输时间,从而实现大模型的实时显示. 传统的造型设计主要依赖于一位设计专家的主观感觉,但因个人能力有限,设计专家往往只是趋于做出局部最优选择;如果由多专家参与评价,在一般的3D设计环境下,专家们只能依次在同一台图形工作站上对同一个造型进行评分,这样既浪费时间又大大降低了工作效率;而若多专家各自拥有一台图形工作站通过传参协同进化、渲染出造型后再评分,则会大大提高设计成本. 鉴于以上不足,本文采用HSF协同技术作为多专家同步参与3D动漫造型进化设计的环境支持,以图像处理能力强大的图形工作站作为服务器,以一般的PC机作为客户端. HAIGA通过HSF协同将服务器端新进化生成的3D动漫造型实时发送到各个客户端并显示在客户端屏幕上;设计专家在客户端评分,评分结果将被及时反馈给服务器;服务器端收集完专家组的评分后进行下一代的进化.通过利用HSF协同技术,大大降低了设计成本、提高了设计效率. 2.2.2 ACIS规则 ACIS(三维几何造型引擎)规则是对ACIS规则表达式的符号化表示,内部用一棵称为规则树的C++类树表示,通过这些类可以进行求导、微分、积分、求解方程以及确定规则的维数等操作. 规则不仅可以用来定义各种曲线、曲面,还可以对几何体执行变形操作,其中最有用的变形就是非均匀缩放.利用三个含有多个规则符号的字符串构成用于非均匀缩放的规则表达式,其中使用的规则符号与计算机采用的数学符号类似,语法也与数学符号基本一致.表示规则表达式的字符串一经产生就可以转换成一棵ACIS规则树使3D实体变形.非均匀缩放是指在x轴、y轴和z轴方向上按照不同的缩放比例改变模型中的每个点.一个球体(如图3(a))经均匀缩放只能是一个球体,而经过非均匀缩放后可以变为复杂的模型.例如,假设缩放前模型上点的坐标为(x,y,z),缩放后新模型上对应的点坐标为(X,Y,Z),则球体的非均匀缩放可表示为:X=0.3*xY=0.05*y+0.4*cos(0.5*x)Z=0.1*z.#p#分页标题#e# 由此可见,要实现对初始造型方法和初始造型软件未知的3D动漫造型进行创新设计,可以通过ACIS规则表达式执行非均匀缩放实现.针对ACIS规则表达式的特点,相比标准的采用定长二进制编码的交互式遗传算法,采用二叉树结构的表示方法更有利于ACIS规则表达式的生成和进化.因此,在本文中,将利用二叉树表示ACIS规则. 2.2.3 ACIS规则表示二叉树 定义1.一棵ACIS规则表示二叉树是一个由操作数、一元及二元操作符组成的结点集,此结点集由根结点及其左、右子树或空集组成.树的结点可以是操作符或者是操作数.对二叉树执行中序遍历即可得到一个合法的规则表达式. 其中,操作数可以是常量也可以是变量,变量包括x、y、z;二元操作符包括基本运算符+,-,*,/,^;一元操作符包括基本数学函数sqrt()、exp()、log(),三角函数sin()、cos()、tan()、asin()、acos()、atan(),以及双曲函数sinh()、cosh()、tanh()、asinh()、acosh()、atanh()等.所有的数学函数都具有求导数、求值运算等公共特性.本文采用ACIS规则中数学函数的表示方法,由三棵ACIS规则表示二叉树构成一个ACIS规则表达式.有关树的更详细特性见文献[8].本文采用的ACIS规则表示二叉树与一般的二叉树定义和操作相同. 2.3 交互式遗传操作 作为一种智能全局优化算法,遗传算法在工程设计优化和规划管理领域得到了广泛应用.对于一般的采用遗传算法解决设计问题的应用,可以确定相应的目标函数,然后依据计算得到的目标函数值来选择进化的个体.但是,对于创新设计,一般没有形成目标函数的客观评价标准,通常的解决办法是与设计专家进行交互,利用设计专家已有的知识来产生目标函数值,此方法把创新设计的选择权交给了专家[9],充分考虑到了设计者的喜好,是以人为中心的,对难以定义目标函数的创新性设计是一种非常有效的方法.交互式遗传操作包括选择、交叉、变异和精英保留,所有的操作都以二叉树作为操作对象. 2.3.1 适应度函数的建立 本文采用Ohsaki[10]提出的多专家共同评价作为建立适应度函数的依据,以较少的评价选项减轻专家的评价负担、提高参与的积极性.共有五个评价选项供专家选择,专家仅需从“很好”、“比较好”、“一般”、“比较差”、“很差”五个等级中选择一项,而不需要给出具体的分值.“很差”、“比较差”、“一般”、“比较好”和“很好”依次对应评分为0分、2分、4分、6分和8分.若有n位专家参与评分,则分值区间为[0,7n],这种区间跨度不会因较少的评价选项而影响HAIGA的收敛性. 引入多专家同步评价机制后,采用“加权平均满意度”与“共识度”共同作为建立适应度函数的指标.满意度是指设计专家在设计产品过程中所感受到的主观满意和接受程度,主要通过五个评价选项体现,各专家表现出的满意度的加权期望值即为专家组的加权平均满意度;共识度的概念由西班牙格林纳达大学的软计算与智能信息系统研究团队提出[11],用来描述设计专家们对于某种设计产品达成共识和偏好的程度.使用双指标的原因如下:第一,由于专家们具有不同的设计风格和设计经验,这意味着专家个体的设计偏好各不相同;第二,单凭加权平均满意度也不能完全真实反映产品的优劣情况,以表1为例,假设专家的权重相同,虽然三种解决方案A、B、C对应的专家的加权平均满意度均为5,但相对于方案B和C,专家对方案A未表现出“比较差”的态度,共识性程度较高,故较符合专家组的共同需求. 2.3.1.1 加权平均满意度的计算 由于不同专家的设计水平、个人声誉等各不相同,其评分的权威性也各不相同,因此拥有不同的设计权重.设专家d对通过规则表达式a进化产生的新造型的加权评分值为sd′=w(d)•sd(a) (1)则设计专家组对通过规则表达式a进化产生的新造型的最终加权评分值可用如下公式表示:s′(a)=∑d∈Dsd′(a)=∑d∈Dw(d)•sd(a) (2)式(1)、(2)中,D代表设计专家集,w(d)是设计专家d∈D的设计权重,sd(a)表示设计专家d对通过ACIS规则表达式a进化产生的新造型的评分值.则加权平均满意度可表示为s′(a)=s′(a)∑i∈Dw(i)=∑d∈Dw′(d)•sd(a) (3)式(3)中,d、n均为正整数,1≤d≤n,且对于每一位专家d∈Dw′(d)=w(d)∑i∈Dw(i),即∑nd=1w′(d)=1,d∈D2.3.1.2 共识度的计算令s′max(a)={sj′(a);sj′(a)≥si′(a),i=1,2,…,n},s′min(a)={sk′(a);sk′(a)≤si′(a),i=1,2,…,n},则s′(a)和sd′(a)分别经[0,1]标准化后的值为S(s′(a))=s′(a)-s′min(a)s′max(a)-s′min(a),S(sd′(a))=sd′(a)-s′min(a)s′max(a)-s′min(a)采用标准差计算共识度R=1-∑nd=1(S(sd′(a))-S(s′(a)))2/n2.3.1.3 适应度函数的定义假设加权平均满意度S(s′(a))和共识度R所占适应度值比例分别为α和β(α+β=1,通过试验可以得到α和β之间较优的比例关系),则适应度函数可定义为:f(a)=αS(s′(a))+βR获得最大适应度值的造型对应的ACIS规则表达式即是专家组最终选择的变形表达式a*,可用反函数的形式表示为:a*=argmaxa∈Af(a) (4)若有多个AICS规则表达式满足(4)式,则设计专家组可以根据具体需求综合考虑从这些表达式中选择一个或多个使用2.3.2 选 择遗传算法中的选择操作存在遗传漂移问题,文献[12]对这种问题做了大量的分析,指出在进化过程中由于受选择压等因素的影响,种群有均匀收敛于单一个体的趋势,虽然遗传漂移问题不能从根本上消除,但是采用恰当的选择方法可以减轻遗传漂移问题的影响.文献中提到赌等按比例选择的方法要劣于联赛选择方法,所以本文中采用两个体联赛选择机制[12],即从当前种群中随机选取两个个体进行比较,适应度值高的个体被选中,采用此方法可以在一定程度上防止遗传算法的过早收敛.#p#分页标题#e# 2.3.3 交 叉 交叉是遗传算法中最主要的一种操作.在交叉操作前,先由选择操作选出待交叉的父个体,然后再将父辈的优良基因进行交叉组合,产生新的优秀个体,使得原来种群中优良个体Fig.4 Executingcrossoverandmutationonbinarytrees的特性能够在一定程度上得以保留.常用的交叉方法有单点交叉、两点交叉和多点交叉,本文的交叉操作是在两棵高质量的父辈树上分别随机地选择一个交叉结点,然后交换以选中的结点为根结点的两棵子树,得到两个后代.交叉操作如图4(a)-(d)所示. 2.3.4 变 异 变异,虽然发生的概率很低,但它在遗传算法中却起着双重作用,一方面扩展解空间,增强后代的多样性,以使选择和交叉可以继续起作用;另一方面它自身也可以起到搜索算子的作用.在二叉树结构编码的遗传算法中,是在单棵父辈树上随机选择一个结点为变异点进行变异.为了增强变异的效果,本文将如下三种变异策略结合起来使用:1)将个体的m结点用另一个元素替代;2)交换m结点的左右子树;3)用一棵新的子树替代父辈树上以m结点为根结点的子树. 2.3.5 精英保留策略 一般的精英保留策略有:1)将前一代最好的个体加入到下一代的进化中,此方法由于保留的优良个体数量较小,容易丢失部分比较好的造型;2)将前一代和基于前一代进化产生的种群合并,然后排序,取前一半作为下一代新产生的种群,这种策略虽然可以保留尽可能多的优良个体,但是容易导致种群过早收敛,不利于生成造型的多样化. 鉴于以上策略的不足,本文采取以下方法执行精英保留策略:设种群数为n,把每次遗传操作后,按产生的新种群B的适应度值排序,取出前30%n个个体与上一代种群合并,记为种群A.将A的适应度值排序,取前30%n个个体,如果前30%n个个体中有k(k≤30%n)个个体属于上一代,就随机淘汰新一代中k个个体,把上一代的前k个个体加入到新一代中.精英保留策略可保证当前的优秀个体不会被交叉变异等遗传操作破坏. 3 HAIGA用于3D动漫造型进化 为了验证HAIGA算法的性能,以ACIS、HOOPS、VS2003作为平台,开发了一个3D动漫造型自动进化原型系统.下面介绍利用该系统进化一个3D动漫造型的详细步骤:Step1.初始化种群.种群通过在常量、变量、一元及二元运算符集中随机选择来生成多棵字符二叉树.本文利用一元及二元运算符本身的数学特点和二叉树的特性,判断产生的数学表达式是否是一个有效的ACIS规则表达式(例如,若二叉树结点中有运算符“+”,则以该结点为根结点的子树必须同时具有左子树和右子树;若结点中有数学函数“sin”,则以Fig.5 Originalmodelingandgeneratedmodelingsbyevolving该结点为根结点的子树只能且必须具有右子树).用堆栈及数据结构中二叉树的中序遍历算法,将生成的二叉树转换成符合ACIS规则的表达式.为了保留成功设计的特征,本文将高质量造型及其对应的ACIS规则表达式存储在数据库中,可以从数据库中提取一些ACIS规则表达式作为初始种群的一部分.例如,随机生成两个ACIS规则表达式1和2,对用Maya制作的3D动漫造型进行变形,初始化种群,如上页图5(a)-(c)所示. 规则表达式1:vec(((0.9+0.6)*x),((((0.1+0.2)+(0.4+0.9))*y)+((y*sin(y*0.8))*sin(y*0.8))),((0.3+0.9)*z))规则表达式2:vec(((0.4+0.8)*x),((((0.4+0.8)+(0.8+0.4))*y)+y),((PI+0.8)*z))Step2.服务器端系统根据生成的ACIS规则表达式生成新造型,并将新造型通过HSF协同显示到各个客户端,参与设计的多专家共同为各个造型评分,然后系统根据公式f(a)=αS(s′(a))+βR计算种群中个体的适应度值.如图6和图7所示,图6为已经建立的协同设计环境下的服务器端,图7为协同设计环境下的客户端,其中的造型为服务器端通过HSF协同发送的. Fig.6 Server-sideFig.7 Client-side Step3.对种群执行选择操作和精英保留策略. Step4.对种群执行交叉操作.以规则表达式1和2中y方向为例,将表达式1对应的y方向上的二叉树中以A为根结点的子树,与表达式2对应的y方向上的二叉树中以B为根结点的子树交叉,可得规则表达式3和4对应的y方向上的二叉树,如图7(a)-(d)所示. 规则表达式3:vec(((0.9+0.6)*x),((((0.1+0.2)+(0.4+0.9))*y)+(y*sin(y*0.8))),((0.3+0.9)*z))规则表达式4:vec(((0.4+0.8)*x),((((0.4+0.8)+(0.8+0.4))*y)+(y*sin(y*0.8))),((PI+0.8)*z))Step5.对种群执行变异操作.以规则表达式4中y方向上的二叉树为例,将表达式4对应的y方向上的二叉树中的叶子结点C变异,可得规则表达式5,如图4(d)(e)所示.规则表达式3、4、5对应的进化效果如图5(d)-(f)所示. 规则表达式5:vec(((0.4+0.8)*x),((((0.4+0.8)+(0.8+0.4))*y)+(y*sin(y*PI))),((PI+0.8)*z))Step6.如果用户不终止,转Step2;否则结束. 4 结 论 本文针对3D动漫造型的自动生成问题,提出一种支持协同设计的3D动漫造型进化计算方法,通过利用HSF协同技术和ACIS规则,在充分利用设计专家知识的基础上,进化生成新颖的3D动漫造型.通过一系列3D动漫造型的设计表明,该方法能够有效支持协同设计,并进化生成一些创意新颖的3D动漫造型. 下一步的工作将主要针对如何减少人机交互的次数,以及如何增强变形结果的可控性展开进一步的研究.