基于形状文法的伊斯兰图案生成研究*

李　园　王化雨,2　崔　嘉,2

(1.山东师范大学信息科学与工程学院　济南　250014) (2.山东省分布式计算机软件新技术重点实验室　济南　250014)



基于形状文法的伊斯兰图案生成研究*

李园1王化雨1,2崔嘉1,2

(1.山东师范大学信息科学与工程学院济南250014) (2.山东省分布式计算机软件新技术重点实验室济南250014)

为了解决二维参数化生成方法对图案风格难以表示的问题,论文以伊斯兰几何图案设计为例,对伊斯兰几何图案的生成规则进行了研究,提出了一种基于形状文法的二维图案生成算法。根据对伊斯兰几何图案的分析结果,得到大量组成伊斯兰图案的基本图元,并将其作为初始形状结合形状文法规则和仿射变换操作,实现具有伊斯兰风格的几何图案的绘制。该算法能快速灵活地生成大量伊斯兰几何图案,为下一步进行智能配色填充设计奠定了基础。

图元; 几何图案; 形状文法; 仿射变换

Class NumberTP391

1　引言

图案在人类生活中无处不在,因其简单、易懂、富于装饰性的特征,从古至今一直深受人们喜爱。应用点、线、面形成的图案变化丰富,不同时代、地域和民族的人们赋予图案不同的内涵：直线分割的图案刚毅俊逸；弧线作为构架的图案柔和优雅；装饰性的图案层次丰富,变化多样。在艺术领域,图案的绘制能表现出艺术家独特的设计思路和灵感,是一种无限制的情感表达方式。除此之外,图案在工程、自然科学、雕塑、平面设计、影视、服装设计等各个方面也有广泛的应用。

当前,图案的表现形式、创作方法越来越丰富。大量图案的产生方式逐渐由纯手工模式向计算机辅助创作模式进行转变。利用计算机辅助图案设计的方法主要分为参数化自动生成方式[1]和手工绘制方式。参数化自动生成方式是利用一组参数约束生成的图形,当赋予不同的参数值时,就会生成不同的目标图形；而手工绘制方式则是需要用户进行手工操作完成绘制过程。在图案生成时,自动生成方式大部分是[2～4]由逐个像素赋色得到的,这种方法虽然可以绘制出绚丽多彩的图案,但速度相对较慢。手工绘制方式[5～7]对用户的要求较高,用户必须具备足够的领域知识[8]、美术功底[9]、图案创作经验[10]并能熟练使用这些工具,才能设计出具有艺术性[11]、观赏性和实用性[12]的好作品。

本文方法将生成图案最小的单位作为基本图元。基本图元作为初始形状,根据形状文法规则[13～14]生成最小图元,然后进行仿射变换操作实现伊斯兰几何图案设计。该方法对图案进行参数化生成,更加方便快捷地对图案进行修改,结合形状文法,可以保持图案的风格不变。

2　形状文法

形状文法是Stiny等[15]在1980年提出的。形状文法可以定义为一个四元组,记作：SG(S,L,R,I),其中：

1)S是一个有限的形状集合；

2)L是一个有限的标记集合；

3)R是有限的形状规则集合,当α∈(S,L)+,β∈(S,L)*时,其形式为α→β；

4)I是初始标记形状且I∈(S,L)+。

形状文法由一系列的形状和文法规则组成,以带标记的形状作为基本要素,通过文法分析产生新的形状[16],当设计师预先设定了明确的初始形状和文法规则,所有可能的设计方案都将包含在形状文法所定义的规则范围之内,如将这一方法与衍生设计相结合,并由计算机实现文法规则的应用,可大大拓展设计的可能性,生成更加丰富多彩的图案。

目前,形状文法在国际CAD(Computer Aided Design)领域中已成为一个重要研究方向,在国内研究发展中,形状文法的研究也受到了很多研究人员的重视,如黄琦等[17]将其应用在产品风格方面的研究,但由于影响产品风格的因素比较多,单一特征的实验只能反映产品风格认知的部分信息,很难满足消费者对产品的需求；崔嘉等[18]通过形状文法进行了建模,并产生大量的刺绣设计图案,然而在生成图案的过程中,特征矩阵是由系统设计人员指定的,进一步研究交互过程动态地决定特征矩阵的数值,以便更好地获取用户的主观设计特征；王伟伟等[19]提出一种基于形状文法的产品形态创新设计模型,以辅助实现品牌基因、参考形态元素与流行设计元素之间的融合和推演,但是,形状文法的推演机制在智能设计技术方面还有待进一步研究。

3　二维图案设计

本文方法将生成图案最小的单位作为基本图元。基本图元作为初始形状,根据形状文法规则生成最小图元,然后进行仿射变换操作实现伊斯兰几何图案设计。

3.1基本图元

本文以Joules Bourgoin设计的Les éléments de l’art arabe图集作为实验样本,伊斯兰图案是一种自相似性图案,图案在不同尺度上保持一致性,也就是同样的形状和图样在以不同的规格重复,而且图案的重复可以无限的进行下去。不过在实际应用中伊斯兰图案通常会被裁成矩形并以主要图案的中心作为矩形的四角,这样处理不仅保持了优美的几何形状,同时也清晰地表明这种图案的边缘可以无限的延伸下去。部分图集如表1所示。分析样本图案得到大量组成伊斯兰图案的基本图元,根据几何图形的基本特征,通过几何图形的外接圆半径和圆心计算出图形的各个顶点坐标,然后调用图形库AGG(Anti-Grain Geometry)中的函数,生成基本图元。

图1　Les éléments de l’art arabe部分图集

为了能够更好地实现基本图元的表示,通过三角函数公式对基本的几何图形的各顶点坐标进行计算。基本图元及其表达公式如图2所示。

图2　硬件平台结构

以正六角星为例,其中心点为外接圆的圆心(x0,y0),半径为r,通过三角函数公式计算出正六角星个顶点坐标,并通过圆心(x0,y0)和半径r表示,表达公式如图3所示。

图3　正六角星表达公式

3.2图案生成算法

图案生成算法的思想是把生成的基本图元作为初始形状,然后根据形状文法的规则进行操作, 得到几何图案中的最小图元,再通过仿射变换操作, 生成伊斯兰几何图案。算法流程图如图4所示。

图4　算法流程图

算法步骤如下：

Step 1：输入基本图元作为初始形状I并对其做标记L,同时输入形状语法规则rule 1, …, rulen；

Step 2：判断I是否满足rule 1,如果不满足则结束,否则输出变化后的形状F1,判断F1是否满足rule 2,如果不满足则结束,否则输出变化后的形状F2,判断F2是否满足rule3,如果不满足则结束,否则输出变化后的形状F3,即图案的最小图元；

Step 3：对F3进行仿射变换操作；

Step 4：输出伊斯兰几何图案。

以一幅伊斯兰几何图案为例,根据形状文法规则对伊斯兰几何图案的生成过程进行规则的设置,图5(a)为伊斯兰几何图案样本图,图5(b)为伊斯兰几何图案生成规则,分析过程：首先把正六角星作为初始形状,执行rule 1操作,对初始形状做标记,检测到标记则执行rule2操作,然后判断生成的图形是否有三个标记,如果有则执行rule 3操作,最后则执行rule 4操作去掉标记,实现图案的生成,效果图如图5(c)所示。

图5　伊斯兰几何图案设计

根据用户需求对图案的生成规则进行修改,实验效果图如图6所示。

图6伊斯兰几何图案效果图

4　结语

通过对伊斯兰几何图案进行实验探索其内部结构及其现实意义,总结为以下几点：

1) 通过应用简单的几何关系相互组合的方法,将一个正方形网格衍生成一系列迥然不同的正方形组合图样。

2) 五次对称和十次对称的几何图案体现了优雅的黄金分割：一条线段上某点将整个线段分为两部分,其中较短部分与较长部分之比等于较长部分与整个线段长度之比。

3) 星形图案的各角上经常表现为上下交叠的两个线段,这是一种常见的表现形式。

本文主要对伊斯兰几何图案进行了分析,将形状文法与图案生成相结合,进行二维图案的生成研究,通过算法控制,提高图案生成效率和美观度,实现了图案的可视化操作。本文只是对二维图案设计过程进行了分析,对于二维图案配色设计方面尚未涉及,下一步主要针对二维图案进行智能配色填充设计,对新的色彩方案进行风格等方面的评价。

[1] 张宝云,黄敏.一种新的分形树递归算法的研究[J]. 微计算机信息,2010,15:216-228.

ZHANG Baoyun, HUANG Min. Research on A New Recursive Algorithm of Fractal-Tree[J]. Microcomputer Information,2010,15:216-228.

[2] Xing, J., H.-T. Chen, and L.-Y. Wei, Autocomplete painting repetitions[J]. ACM Transactions on Graphics(TOG),2014, 33:172-194.

[3] 赵海英,惠雯,徐光美.一种新的图案纹样生成方法[J].计算机系统应用,2011(3):85-89.

ZHAO Haiying, HUI Wen, XU Guangmei. A New Method for Pattern Generation[J]. Computer Systems & Applications,2011(3):85-89.

[4] 赵海英,徐正光,张彩明.一类新疆民族风格的织物图案生成方法[J].图学学报,2012(2):1-8.

ZHAO Haiying, XU Zhengguang, Zhang Caiming. A Method for Style Generation Based on Xin jiang Ethnic Fabric Pattern[J].Journal of Graphics,2012(2):1-8.

[5] 赵海英,张俊慧.新疆民间艺术图案数字化技术[J].计算机系统应用,2011,12:167-172.

ZHAO Haiying,ZHANG Junhui. Xinjiang Folk Art Patterns Digital Techonlogy[J]. Computer Systems & Applications,2011,12:167-172.

[6] 赵海英,潘志庚,徐正光.基于构型风格的新疆民族织物图案自动生成[J].图学学报,2013(1):17-21.

ZHAO Haiying,PAN Zhigeng,XU Zhengguang. Automatic Generation of Xinjiang Ethnic Fabric Patterns Based on Configuration Style[J].Journal of Graphics,2013(1):17-21.

[7] 汪浩.基于多媒体技术的图案设计研究[D].武汉:武汉理工学,2003.

WANG Hao.The Researeh on Pattern Design Based on Multimedia Technology[D]. Wuhan:Wuhan University of Technology,2003.

[8] T Weissman Knight. Transformations of languages of designs: part 1[C]//Environment and Planning B: Planning and Design,1983,10:125-128.

[9] McCormack J, Dorin A, Innocent T, Generative design: a paradigm for design research[OL]. 2012.

[10] C.Soddu. Logics of Imagination.Generative Art performs the Artist Style as ExecutableProcess[C]//In proceedings of XV Generative Art Conference, GA2012, Domus Argenia Pub,2012:78-94.

[11] C.Soddu. Generative Art Geometry.Logical interpretations for Generative Algorithms[C]//proceedings of XVII Generative Art Conference - GA2014,2014:11-23.

[12] 鲁力,李欣.基于AGG算法库的通用图形接口设计[J].微计算机信息,2009(6):266-267.

LU Li,LI Xin. AGG(Anti-Grain Geometry) based PiatformIndependent Graphics Interface Design[J]. Microcomputer Information,2009(6):266-267.

[13] 崔嘉,唐明晰,刘弘.形状动态表示在产品概念设计中的应用[J].计算机辅助设计与图形学学报,2014,10:1879-1885.

CUI Jia,TANG Mingxi,KIU Hong. Dynamic Shape Representation for Product Modeling in CoNceptual Design[J]. Journal of Computer-Aided Design & Computer Graphics,2014,10:1879-1885.

[14]黄翔,周栋.简述形状语法及其应用[J].华中建筑,2004,2:45-48.

HUANG Xiang,ZHOU Dong. Intruction of Shape Grammar and Its Application[J]. Huazhong Architecture,2004,2:45-48.

[15] Stiny G, Gips J, et al. shape grammars and the generative specification of painting angsculpt- ure[J]. Information Processing,1972,71:1460-1465.

[16] 王仁华,赵宪忠.形状语法驱动空间杆系结构的构型合成[J].计算机辅助设计与图形学学报,2011,11:1924-1930.

WANG Renhua, ZHAO Xianzhong. Shape Grammars Driven Configuration Synthesis of Spatial Truss Structures[J]. Journal of Computer-Aided Design & Computer Graphics,2011,11:1924-1930.

[17] 黄琦,孙守迁.产品风格计算研究进展[J].计算机辅助设计与图形学学报,2006,11:1629-1636.

HUANG Qi,SUN Shouqian. State-of-the-art of Research on Product Style Computation[J]. Journal of Computer-Aided Design & Computer Graphics,2006,11:1629-1636.

[18] 崔嘉,唐明晰,陆宏菊.主观评估模型在计算机衍生设计中的应用[J].计算机辅助设计与图形学学报,2013,7:931-936.

CUI Jia, TANG Mingxi, Lu Hongju. Application of Subjective Evaluation Model in the Generative Design[J]. Journal of Computer-Aided Design & Computer Graphics,2013,7:931-936.

[19] 王伟伟,杨延璞,杨晓燕,等.基于形状文法的产品形态创新设计研究与实践[J].图学学报,2014,1:68-73.

WANG Weiwei,YANG Yanpu, Yang Xiaoyan, et al. Method of Product Form Design Based on Shape Grammar[J]. JOURNAL OF GRAPHICS,2014,1:68-73.

附录

以正六角星为例,代码实现过程如下所示：

class?hexagon{

public:

hexagon(double?cx,?double?cy,?double?r)

{

m_step = 0;

m_pt[0].x = cx; m_pt[0].y = cy-r;

m_pt[1].x = cx-cos(M_PI/6)*r/3; m_pt[1].y = cy-r/2;

m_pt[2].x = cx- cos(M_PI/6)*r; m_pt[2].y = cy-r/2;

m_pt[3].x = cx-tan(M_PI/6)*r; m_pt[3].y = cy;

m_pt[4].x = cx+ cos(M_PI/6)*r; m_pt[4].y = cy+ r/2;

m_pt[5].x = cx-cos(M_PI/6)*r/3; m_pt[5].y=cy+r/2;

m_pt[6].x = cx; m_pt[6].y = cy+r;

m_pt[7].x = cx+ cos(M_PI/6)*r/3; m_pt[7].y=cy+r/2;

m_pt[8].x = cx+cos(M_PI/6)*r; m_pt[8].y = cy+r/2;

m_pt[9].x = cx+ tan(M_PI/6)*r; m_pt[9].y = cy;

m_pt[10].x = cx+ cos(M_PI/6)*r; m_pt[10].y = cy-r/2;

m_pt[11].x = cx+ cos(M_PI/6)*r/3; m_pt[11].y=cy+r/2;

}

void rewind(unsigned)

{

m_step = 0;

}

unsigned vertex(double* x,?double* y)

{

switch(m_step++)

{

case 0:

*x = m_pt[0].x;

*y = m_pt[0].y;

return agg::path_cmd_move_to;

case 1:

case 2:

case 3:

case 4:

case 5:

case 6:

case 7:

case 8:

case 9:

case 10:

case 11:

*x = m_pt[m_step-1].x;

*y = m_pt[m_step-1].y;

return agg::path_cmd_line_to;

case 12:

return agg::path_cmd_end_poly

|agg::path_flags_close;

default:

return agg::path_cmd_stop;

}

}

private:

agg::point_d m_pt[12];

unsigned m_step;

};

Islamic Pattern Generate Based on Shape Grammar

LI Yuan1WANG Huayu1,2CUI Jia1,2

(1.School of Information Science & Engineering, Shandong Normal University, Ji’nan250014) (2.Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology, Ji’nan250014)

In order to solve the problem that 2D parametric generative methods can hardly demonstrate the pattern style, this paper puts forward 2D generative algorithm based on shape grammar, which is gained through researching on the generative rules of Islamic geometric by case study on Islamic geometric design. According to the analysis on Islamic geometric patterns, large numbers of elements of Islamic patterns are obtained, which are taken as initial shape combined with shape grammar rules and affine transform operation to achieve geometric patterns with the Islamic style. This algorithm can quickly and flexibly generate a large number of Islamic geometric patterns, and lay the foundation for the design of intelligent color matching filled.

element, geometric pattern, shape grammar, affine transformation

2016年3月8日,

2016年4月24日

李园,女,硕士,研究方向:计算机图形图像处理。王化雨,男,副教授,硕士生导师,研究方向：计算机图形图像处理。崔嘉,男,讲师,硕士生导师,研究方向：计算机辅助设计、形状语法、遗传算法、计算机视觉、人机交互。

TP391DOI:10.3969/j.issn.1672-9722.2016.09.038