李　園　王化雨,2　崔　嘉,2

(1.山東師范大學(xué)信息科學(xué)與工程學(xué)院　濟(jì)南　250014) (2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室　濟(jì)南　250014)

?

基于形狀文法的伊斯蘭圖案生成研究*

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

(1.山東師范大學(xué)信息科學(xué)與工程學(xué)院濟(jì)南250014) (2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室濟(jì)南250014)

為了解決二維參數(shù)化生成方法對(duì)圖案風(fēng)格難以表示的問題,論文以伊斯蘭幾何圖案設(shè)計(jì)為例,對(duì)伊斯蘭幾何圖案的生成規(guī)則進(jìn)行了研究,提出了一種基于形狀文法的二維圖案生成算法。根據(jù)對(duì)伊斯蘭幾何圖案的分析結(jié)果,得到大量組成伊斯蘭圖案的基本圖元,并將其作為初始形狀結(jié)合形狀文法規(guī)則和仿射變換操作,實(shí)現(xiàn)具有伊斯蘭風(fēng)格的幾何圖案的繪制。該算法能快速靈活地生成大量伊斯蘭幾何圖案,為下一步進(jìn)行智能配色填充設(shè)計(jì)奠定了基礎(chǔ)。

圖元; 幾何圖案; 形狀文法; 仿射變換

Class NumberTP391

1　引言

圖案在人類生活中無處不在,因其簡單、易懂、富于裝飾性的特征,從古至今一直深受人們喜愛。應(yīng)用點(diǎn)、線、面形成的圖案變化豐富,不同時(shí)代、地域和民族的人們賦予圖案不同的內(nèi)涵：直線分割的圖案剛毅俊逸；弧線作為構(gòu)架的圖案柔和優(yōu)雅；裝飾性的圖案層次豐富,變化多樣。在藝術(shù)領(lǐng)域,圖案的繪制能表現(xiàn)出藝術(shù)家獨(dú)特的設(shè)計(jì)思路和靈感,是一種無限制的情感表達(dá)方式。除此之外,圖案在工程、自然科學(xué)、雕塑、平面設(shè)計(jì)、影視、服裝設(shè)計(jì)等各個(gè)方面也有廣泛的應(yīng)用。

當(dāng)前,圖案的表現(xiàn)形式、創(chuàng)作方法越來越豐富。大量圖案的產(chǎn)生方式逐漸由純手工模式向計(jì)算機(jī)輔助創(chuàng)作模式進(jìn)行轉(zhuǎn)變。利用計(jì)算機(jī)輔助圖案設(shè)計(jì)的方法主要分為參數(shù)化自動(dòng)生成方式[1]和手工繪制方式。參數(shù)化自動(dòng)生成方式是利用一組參數(shù)約束生成的圖形,當(dāng)賦予不同的參數(shù)值時(shí),就會(huì)生成不同的目標(biāo)圖形；而手工繪制方式則是需要用戶進(jìn)行手工操作完成繪制過程。在圖案生成時(shí),自動(dòng)生成方式大部分是[2～4]由逐個(gè)像素賦色得到的,這種方法雖然可以繪制出絢麗多彩的圖案,但速度相對(duì)較慢。手工繪制方式[5～7]對(duì)用戶的要求較高,用戶必須具備足夠的領(lǐng)域知識(shí)[8]、美術(shù)功底[9]、圖案創(chuàng)作經(jīng)驗(yàn)[10]并能熟練使用這些工具,才能設(shè)計(jì)出具有藝術(shù)性[11]、觀賞性和實(shí)用性[12]的好作品。

本文方法將生成圖案最小的單位作為基本圖元。基本圖元作為初始形狀,根據(jù)形狀文法規(guī)則[13～14]生成最小圖元,然后進(jìn)行仿射變換操作實(shí)現(xiàn)伊斯蘭幾何圖案設(shè)計(jì)。該方法對(duì)圖案進(jìn)行參數(shù)化生成,更加方便快捷地對(duì)圖案進(jìn)行修改,結(jié)合形狀文法,可以保持圖案的風(fēng)格不變。

2　形狀文法

形狀文法是Stiny等[15]在1980年提出的。形狀文法可以定義為一個(gè)四元組,記作：SG(S,L,R,I),其中：

1)S是一個(gè)有限的形狀集合；

2)L是一個(gè)有限的標(biāo)記集合；

3)R是有限的形狀規(guī)則集合,當(dāng)α∈(S,L)+,β∈(S,L)*時(shí),其形式為α→β；

4)I是初始標(biāo)記形狀且I∈(S,L)+。

形狀文法由一系列的形狀和文法規(guī)則組成,以帶標(biāo)記的形狀作為基本要素,通過文法分析產(chǎn)生新的形狀[16],當(dāng)設(shè)計(jì)師預(yù)先設(shè)定了明確的初始形狀和文法規(guī)則,所有可能的設(shè)計(jì)方案都將包含在形狀文法所定義的規(guī)則范圍之內(nèi),如將這一方法與衍生設(shè)計(jì)相結(jié)合,并由計(jì)算機(jī)實(shí)現(xiàn)文法規(guī)則的應(yīng)用,可大大拓展設(shè)計(jì)的可能性,生成更加豐富多彩的圖案。

目前,形狀文法在國際CAD(Computer Aided Design)領(lǐng)域中已成為一個(gè)重要研究方向,在國內(nèi)研究發(fā)展中,形狀文法的研究也受到了很多研究人員的重視,如黃琦等[17]將其應(yīng)用在產(chǎn)品風(fēng)格方面的研究,但由于影響產(chǎn)品風(fēng)格的因素比較多,單一特征的實(shí)驗(yàn)只能反映產(chǎn)品風(fēng)格認(rèn)知的部分信息,很難滿足消費(fèi)者對(duì)產(chǎn)品的需求；崔嘉等[18]通過形狀文法進(jìn)行了建模,并產(chǎn)生大量的刺繡設(shè)計(jì)圖案,然而在生成圖案的過程中,特征矩陣是由系統(tǒng)設(shè)計(jì)人員指定的,進(jìn)一步研究交互過程動(dòng)態(tài)地決定特征矩陣的數(shù)值,以便更好地獲取用戶的主觀設(shè)計(jì)特征；王偉偉等[19]提出一種基于形狀文法的產(chǎn)品形態(tài)創(chuàng)新設(shè)計(jì)模型,以輔助實(shí)現(xiàn)品牌基因、參考形態(tài)元素與流行設(shè)計(jì)元素之間的融合和推演,但是,形狀文法的推演機(jī)制在智能設(shè)計(jì)技術(shù)方面還有待進(jìn)一步研究。

3　二維圖案設(shè)計(jì)

本文方法將生成圖案最小的單位作為基本圖元。基本圖元作為初始形狀,根據(jù)形狀文法規(guī)則生成最小圖元,然后進(jìn)行仿射變換操作實(shí)現(xiàn)伊斯蘭幾何圖案設(shè)計(jì)。

3.1基本圖元

本文以Joules Bourgoin設(shè)計(jì)的Les éléments de l’art arabe圖集作為實(shí)驗(yàn)樣本,伊斯蘭圖案是一種自相似性圖案,圖案在不同尺度上保持一致性,也就是同樣的形狀和圖樣在以不同的規(guī)格重復(fù),而且圖案的重復(fù)可以無限的進(jìn)行下去。不過在實(shí)際應(yīng)用中伊斯蘭圖案通常會(huì)被裁成矩形并以主要圖案的中心作為矩形的四角,這樣處理不僅保持了優(yōu)美的幾何形狀,同時(shí)也清晰地表明這種圖案的邊緣可以無限的延伸下去。部分圖集如表1所示。分析樣本圖案得到大量組成伊斯蘭圖案的基本圖元,根據(jù)幾何圖形的基本特征,通過幾何圖形的外接圓半徑和圓心計(jì)算出圖形的各個(gè)頂點(diǎn)坐標(biāo),然后調(diào)用圖形庫AGG(Anti-Grain Geometry)中的函數(shù),生成基本圖元。

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

為了能夠更好地實(shí)現(xiàn)基本圖元的表示,通過三角函數(shù)公式對(duì)基本的幾何圖形的各頂點(diǎn)坐標(biāo)進(jìn)行計(jì)算。基本圖元及其表達(dá)公式如圖2所示。

圖2　硬件平臺(tái)結(jié)構(gòu)

以正六角星為例,其中心點(diǎn)為外接圓的圓心(x0,y0),半徑為r,通過三角函數(shù)公式計(jì)算出正六角星個(gè)頂點(diǎn)坐標(biāo),并通過圓心(x0,y0)和半徑r表示,表達(dá)公式如圖3所示。

圖3　正六角星表達(dá)公式

3.2圖案生成算法

圖案生成算法的思想是把生成的基本圖元作為初始形狀,然后根據(jù)形狀文法的規(guī)則進(jìn)行操作, 得到幾何圖案中的最小圖元,再通過仿射變換操作, 生成伊斯蘭幾何圖案。算法流程圖如圖4所示。

圖4　算法流程圖

算法步驟如下：

Step 1：輸入基本圖元作為初始形狀I(lǐng)并對(duì)其做標(biāo)記L,同時(shí)輸入形狀語法規(guī)則rule 1, …, rulen；

Step 2：判斷I是否滿足rule 1,如果不滿足則結(jié)束,否則輸出變化后的形狀F1,判斷F1是否滿足rule 2,如果不滿足則結(jié)束,否則輸出變化后的形狀F2,判斷F2是否滿足rule3,如果不滿足則結(jié)束,否則輸出變化后的形狀F3,即圖案的最小圖元；

Step 3：對(duì)F3進(jìn)行仿射變換操作；

Step 4：輸出伊斯蘭幾何圖案。

以一幅伊斯蘭幾何圖案為例,根據(jù)形狀文法規(guī)則對(duì)伊斯蘭幾何圖案的生成過程進(jìn)行規(guī)則的設(shè)置,圖5(a)為伊斯蘭幾何圖案樣本圖,圖5(b)為伊斯蘭幾何圖案生成規(guī)則,分析過程：首先把正六角星作為初始形狀,執(zhí)行rule 1操作,對(duì)初始形狀做標(biāo)記,檢測(cè)到標(biāo)記則執(zhí)行rule2操作,然后判斷生成的圖形是否有三個(gè)標(biāo)記,如果有則執(zhí)行rule 3操作,最后則執(zhí)行rule 4操作去掉標(biāo)記,實(shí)現(xiàn)圖案的生成,效果圖如圖5(c)所示。

圖5　伊斯蘭幾何圖案設(shè)計(jì)

根據(jù)用戶需求對(duì)圖案的生成規(guī)則進(jìn)行修改,實(shí)驗(yàn)效果圖如圖6所示。

圖6伊斯蘭幾何圖案效果圖

4　結(jié)語

通過對(duì)伊斯蘭幾何圖案進(jìn)行實(shí)驗(yàn)探索其內(nèi)部結(jié)構(gòu)及其現(xiàn)實(shí)意義,總結(jié)為以下幾點(diǎn)：

1) 通過應(yīng)用簡單的幾何關(guān)系相互組合的方法,將一個(gè)正方形網(wǎng)格衍生成一系列迥然不同的正方形組合圖樣。

2) 五次對(duì)稱和十次對(duì)稱的幾何圖案體現(xiàn)了優(yōu)雅的黃金分割：一條線段上某點(diǎn)將整個(gè)線段分為兩部分,其中較短部分與較長部分之比等于較長部分與整個(gè)線段長度之比。

3) 星形圖案的各角上經(jīng)常表現(xiàn)為上下交疊的兩個(gè)線段,這是一種常見的表現(xiàn)形式。

本文主要對(duì)伊斯蘭幾何圖案進(jìn)行了分析,將形狀文法與圖案生成相結(jié)合,進(jìn)行二維圖案的生成研究,通過算法控制,提高圖案生成效率和美觀度,實(shí)現(xiàn)了圖案的可視化操作。本文只是對(duì)二維圖案設(shè)計(jì)過程進(jìn)行了分析,對(duì)于二維圖案配色設(shè)計(jì)方面尚未涉及,下一步主要針對(duì)二維圖案進(jìn)行智能配色填充設(shè)計(jì),對(duì)新的色彩方案進(jìn)行風(fēng)格等方面的評(píng)價(jià)。

[1] 張寶云,黃敏.一種新的分形樹遞歸算法的研究[J]. 微計(jì)算機(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].計(jì)算機(jī)系統(tǒng)應(yīng)用,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] 趙海英,徐正光,張彩明.一類新疆民族風(fēng)格的織物圖案生成方法[J].圖學(xué)學(xué)報(bào),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] 趙海英,張俊慧.新疆民間藝術(shù)圖案數(shù)字化技術(shù)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,12:167-172.

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

[6] 趙海英,潘志庚,徐正光.基于構(gòu)型風(fēng)格的新疆民族織物圖案自動(dòng)生成[J].圖學(xué)學(xué)報(bào),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] 汪浩.基于多媒體技術(shù)的圖案設(shè)計(jì)研究[D].武漢:武漢理工學(xué),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算法庫的通用圖形接口設(shè)計(jì)[J].微計(jì)算機(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] 崔嘉,唐明晰,劉弘.形狀動(dòng)態(tài)表示在產(chǎn)品概念設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]黃翔,周棟.簡述形狀語法及其應(yīng)用[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] 王仁華,趙憲忠.形狀語法驅(qū)動(dòng)空間桿系結(jié)構(gòu)的構(gòu)型合成[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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] 黃琦,孫守遷.產(chǎn)品風(fēng)格計(jì)算研究進(jìn)展[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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] 崔嘉,唐明晰,陸宏菊.主觀評(píng)估模型在計(jì)算機(jī)衍生設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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] 王偉偉,楊延璞,楊曉燕,等.基于形狀文法的產(chǎn)品形態(tài)創(chuàng)新設(shè)計(jì)研究與實(shí)踐[J].圖學(xué)學(xué)報(bào),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.

附錄

以正六角星為例,代碼實(shí)現(xiàn)過程如下所示：

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日

李園,女,碩士,研究方向:計(jì)算機(jī)圖形圖像處理。王化雨,男,副教授,碩士生導(dǎo)師,研究方向：計(jì)算機(jī)圖形圖像處理。崔嘉,男,講師,碩士生導(dǎo)師,研究方向：計(jì)算機(jī)輔助設(shè)計(jì)、形狀語法、遺傳算法、計(jì)算機(jī)視覺、人機(jī)交互。

TP391DOI:10.3969/j.issn.1672-9722.2016.09.038