一種支持紙的折疊、剪切與展開的計(jì)算模型

劉金義， 張笑伶

（遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，遼寧 撫順 113001）

兒童剪紙是培養(yǎng)兒童動(dòng)手能力、開發(fā)兒童空間想象力的極好手段，現(xiàn)已成為國(guó)內(nèi)許多中小學(xué)的手工活動(dòng)課程內(nèi)容。兒童剪紙的典型過程為[1]：從初始的一張正方形或長(zhǎng)方形的彩紙開始，經(jīng)過若干次的折疊，再以一剪或多剪方式剪去紙的一部分，最后將剩余部分展開，得到各式各樣的平面形象?！凹粑褰切恰毕嘈攀窃S多人都經(jīng)歷過的最經(jīng)典的兒童剪紙過程。本文所關(guān)心的問題是，一張紙經(jīng)過多次折疊和剪切，展開后所得的形狀是什么？這個(gè)問題是開發(fā)一個(gè)計(jì)算機(jī)輔助兒童剪紙方案設(shè)計(jì)系統(tǒng)必須解決的問題。

與本文關(guān)心的問題相近的一個(gè)領(lǐng)域是兒童折紙(origami)的設(shè)計(jì)。該領(lǐng)域?qū)埖牟僮髦挥姓郫B并且允許一些非簡(jiǎn)單的復(fù)雜折疊。關(guān)于計(jì)算機(jī)輔助折紙?jiān)O(shè)計(jì)，已有許多相關(guān)的研究，例如，如何在數(shù)學(xué)和算法上描述折紙和定義折疊過程[2-3]，給定一張紙的折痕如何判斷它是否對(duì)應(yīng)一個(gè)合法的折紙作品[4]，特別是 Kishi等開發(fā)了一個(gè)可以交互進(jìn)行折疊操作并進(jìn)行動(dòng)態(tài)演示的網(wǎng)站[5]。與本文關(guān)心的問題相近的另一個(gè)領(lǐng)域是中國(guó)傳統(tǒng)民間剪紙的設(shè)計(jì)。該領(lǐng)域?qū)埖牟僮髦挥屑羟校▽?shí)際上叫“刻”操作更合適，因?yàn)樗试S生成孔洞），所以一般都把民間剪紙?jiān)O(shè)計(jì)看成是一個(gè)平面設(shè)計(jì)問題，研究的重點(diǎn)放在如何生成典型的紋樣方面，而不關(guān)心它們是如何剪出的[6-7]。

為了開發(fā)一個(gè)既能進(jìn)行兒童剪紙方案設(shè)計(jì)又能向兒童演示典型折剪過程的程序，作者設(shè)計(jì)了一個(gè)能夠支持折疊、剪切和展開操作的計(jì)算模型，設(shè)計(jì)了模型的具體數(shù)據(jù)結(jié)構(gòu)以及相關(guān)功能的實(shí)現(xiàn)算法，并且按照該模型開發(fā)了初步的原型軟件Virtual Paper。本文的第1節(jié)將給出相關(guān)的約定與術(shù)語，第2節(jié)將介紹這個(gè)模型的具體數(shù)據(jù)結(jié)構(gòu)，第3節(jié)將介紹在這個(gè)模型中相關(guān)功能的實(shí)現(xiàn)算法，第4節(jié)給出由Virtual Paper生成的一個(gè)折剪實(shí)例。

1 基本約定與術(shù)語

為了建模的需要，計(jì)算機(jī)對(duì)虛擬紙張的操作與人對(duì)真實(shí)紙張的操作應(yīng)該有所不同，為此需對(duì)虛擬紙張和其上的操作做出約定并且給出相關(guān)術(shù)語。這些約定與術(shù)語大部分與前人文獻(xiàn)相同[2-4]。

首先，參與折剪的虛擬紙是沒有厚度的平面多邊形，分為正面與反面，兩面的顏色可以不同。在折疊過程中，折出的頁片(facet)也看作平面多邊形，它們的面積總和與初始紙張的面積相等，即不考慮由于折痕造成的面積損失。

對(duì)于折疊操作，目前只考慮簡(jiǎn)單折疊(simple fold)，即一次折疊只能沿著一條直線進(jìn)行。把這條直線叫做折疊線(folding line)，它把相關(guān)頁片分成2個(gè)頁片，使得其中一個(gè)繞著折疊線向上或向下旋轉(zhuǎn)180°。如果是向上折疊，則相對(duì)于原頁片的上面產(chǎn)生一條溝谷折痕(valley crease)；否則，產(chǎn)生一個(gè)山峰折痕(mountain crease)。約定折出的頁片相互貼合在一起，之間距離為0。

把初始紙張經(jīng)過折疊、剪切和展開能夠達(dá)到的狀態(tài)叫做一個(gè)紙態(tài)(paper state)。值得注意的是簡(jiǎn)單折疊所能達(dá)到的紙態(tài)是受限制的，圖1給出的紙態(tài)就不能通過簡(jiǎn)單折疊獲得。但是大部分兒童剪紙都采用簡(jiǎn)單折疊。

對(duì)于剪切操作，約定它是剪刀的“剪”而不是“裁”或“刻”，剪切軌跡只能是一條開曲線。剪切后，頁片之間可以是一體的也可以是分離的。約定折疊操作和剪切操作可以任意組合，但是對(duì)于展開操作，一旦展開后，就不再進(jìn)行折疊和剪切。

圖1 不能通過簡(jiǎn)單折疊獲得的紙態(tài)

2 數(shù)據(jù)結(jié)構(gòu)

2.1 設(shè)計(jì)目標(biāo)

數(shù)據(jù)結(jié)構(gòu)是一個(gè)人機(jī)交互系統(tǒng)的計(jì)算模型的核心。它的設(shè)計(jì)目標(biāo)就是要滿足兒童剪紙方案的交互設(shè)計(jì)以及經(jīng)典折剪方案演示的需要。具體地說，必須能夠支撐下面基本功能：

（1）每當(dāng)一個(gè)操作完成后，可以立即顯示出當(dāng)前紙態(tài)的真實(shí)效果圖。這個(gè)效果圖可以是二維的，但是應(yīng)該消除隱藏線。

（2）根據(jù)需要，可以以動(dòng)畫形式展示操作過程。

（3）在紙張展開后，仍然保留折痕痕跡，且區(qū)分山峰折痕和溝谷折痕，以便用戶詳細(xì)考察折疊機(jī)理。

（4）整個(gè)折剪方案可以被記錄下來，存儲(chǔ)成文件，以滿足批處理演示的需要。

2.2 問題分析

這里需要進(jìn)一步澄清折疊、剪切和展開3種操作，然后導(dǎo)出哪些信息是計(jì)算模型所必需的。

首先考察初始紙態(tài)經(jīng)過m次折疊、n次剪切的任意組合到達(dá)某紙態(tài)的過程，圖2給出了這個(gè)過程的一個(gè)例子。在圖中，對(duì)于任意0≤i≤m及0≤j≤n，Si,j表示初始紙態(tài)經(jīng)過i次折疊和j次剪切所獲得的紙態(tài)，其中S0,0是初始紙態(tài)。紙態(tài)的變化是通過如下折疊變換與剪切變換完成的

觀察 1 給定當(dāng)前紙態(tài) Si,j的合理表示及折疊變換Fi+1的完整描述，則下一紙態(tài)Si+1,j是可計(jì)算的；給定當(dāng)前紙態(tài)Si,j的合理表示及剪切變換Ci+1的完整描述，則下一紙態(tài)Si,j+1是可計(jì)算的。

再考察展開過程，仍然參見圖2的例子。展開變換可以看成折疊的逆變換

其中 S'i,j為與Si,j對(duì)應(yīng)的紙態(tài)，S'm,n＝Sm,n，S'0,0是最終所要的平面紙態(tài)。

圖2 一個(gè)具有4次折疊和2次剪切的組合及其展開

觀察2 如果從Si,j到Sm,n的過程中沒有剪切操作，即 j＝n，那么除了保留一些折痕外，S'i,j與Si,j的形狀相同。

觀察3 對(duì)于任意k≥0，如果給定當(dāng)前紙態(tài)S'i+1,j+k的合理表示及折疊變換Fi+1的完整描述，那么S'i+1,j+k展開后的下一紙態(tài)S'i,j是可計(jì)算的，而與Si,j到Si+1,j+k之間的k個(gè)剪切變換無關(guān)。

根據(jù)前面的分析，模型中保存一份當(dāng)前的紙態(tài)Si,j或S'i,j是必需的。為了實(shí)現(xiàn)展開變換，還需要順序記錄全部的折疊變換F1～Fm。但是為了能夠把完整的折剪方案存儲(chǔ)成文件，剪切變換C1～Cn也需要被順序記錄。

總之，為了目標(biāo)要求，計(jì)算模型的數(shù)據(jù)結(jié)構(gòu)應(yīng)由2部分組成：一是當(dāng)前紙態(tài)的表示，二是全部折剪操作及其順序的保存。這2部分不是孤立的，只有互相聯(lián)系在一起才能實(shí)現(xiàn)展開功能。

2.3 紙態(tài)的表示

紙態(tài)是一個(gè)特殊的幾何實(shí)體，是頁片以及它們之間拓?fù)溧徑雨P(guān)系的集合。一個(gè)頁片的幾何形態(tài)就是一個(gè)多邊形，如果單純從描述的角度，把它表示為頂點(diǎn)的列表即可，但是考慮到頁片在折疊和剪切的過程中是動(dòng)態(tài)的，所以參照實(shí)體幾何模型的半邊表示法[8]，增加了半邊節(jié)點(diǎn)(即有向線段)。這樣一個(gè)頁片就表示為一系列首尾相接的半邊。這里與二維流形體的半邊數(shù)據(jù)結(jié)構(gòu)有所不同是沒有Edge節(jié)點(diǎn)，但是增加了一個(gè)與其相近的Crease節(jié)點(diǎn)。一個(gè)Crease也由2條半邊構(gòu)成，但是只有折疊形成的半邊才有對(duì)應(yīng)的 Crease。Crease節(jié)點(diǎn)的加入可以方便折疊與展開的實(shí)現(xiàn)以及折痕的顯示。

struct Vertex

{

int vertexID; //頂點(diǎn)標(biāo)號(hào)

float coord[3]; //z坐標(biāo)是為了三維夸張顯示的需要

};

struct HalfEdge

{

HalfEdge *prv, *nxt; // 前驅(qū)與后繼半邊

Facet *ownerf; //所屬的頁片

Vertex *startv; //起始頂點(diǎn)

Crease *crease; //所對(duì)應(yīng)的折痕，可以是NULL

};

struct Crease

{

HalfEdge *he1, *he2; //對(duì)應(yīng)的2條半邊

char mv; //折痕的屬性(相對(duì)于he1與he2所屬頁片的正面)：

//山峰為1，溝谷為-1

};

struct Facet

{

int faceID; //頁片的標(biāo)號(hào)

int layer; //頁片的層次優(yōu)先級(jí)

char direct; //頁片的方向：正面朝上為1，否則為-1

HalfEdge *he; //頁片的任一半邊

};

list facets;

list creases;

一個(gè)幾何模型中最重要的內(nèi)容是拓?fù)潢P(guān)系的表示，但是嚴(yán)格地表示紙態(tài)中頁片之間的重疊與鄰接關(guān)系是非常困難的。幸運(yùn)的是，本文目前關(guān)心的紙態(tài)中的頁片都是通過簡(jiǎn)單折疊產(chǎn)生的，所以可以根據(jù)折疊順序?yàn)槊總€(gè)頁片賦予一個(gè)唯一的層次優(yōu)先級(jí)（展開后可以存在優(yōu)先級(jí)相同的頁片），以整數(shù)形式存儲(chǔ)在Facet節(jié)點(diǎn)中。

例1 圖3中的紙態(tài)由3個(gè)頁片、12條半邊、8個(gè)頂點(diǎn)和2條折痕構(gòu)成。頁片f1的層次優(yōu)先級(jí)為0。頁片f2與f3盡管互不重疊，但它們的優(yōu)先級(jí)是不同的，取決于折疊順序。如果先疊出f2后疊出f3，則f2的優(yōu)先級(jí)為1，f3的優(yōu)先級(jí)為2。

圖3 一個(gè)紙態(tài)

2.4 折剪過程的記錄

全部折疊和剪切操作最適合被順序地記錄在一個(gè)棧中，棧的每一項(xiàng)對(duì)應(yīng)一次操作。為了將來能夠順利實(shí)現(xiàn)展開功能，如果一個(gè)操作是折疊，那么在節(jié)點(diǎn)中需記錄哪些新產(chǎn)生的頁片被旋轉(zhuǎn)。下面代碼中的列表 rot_facets就是為了完成此目的。值得注意的是，一個(gè)折疊操作的rot_facets內(nèi)容是動(dòng)態(tài)的。如果以后的折疊操作將前面 rot_facets的某個(gè)頁片分割，就應(yīng)該用分割出的2個(gè)頁片替代該頁片。如若不然，在展開時(shí)一定會(huì)少恢復(fù)一些頁片。

struct Operation

{

char op_type; //操作類型：折疊為0，剪切為1

union {

list cut_path; //剪切軌跡

struct Fold{

float fold_line[3]; //折疊線的方程

char fold_mode; //向上還是向下折疊

list rot_facets; //折疊中被旋轉(zhuǎn)的頁片

} fold;

};

};

stack operations;

3 實(shí)現(xiàn)相關(guān)功能的算法

這里給出一般情況下相關(guān)功能的算法步驟，由于篇幅限制，不對(duì)退化情況進(jìn)行詳細(xì)討論。

3.1 折疊操作

給定折疊線的描述并且指定參加折疊的頁片，折疊操作可以通過如下4步實(shí)現(xiàn)：

Step 1 對(duì)于每個(gè)將被折疊的頁片，計(jì)算它們與折疊線的交點(diǎn)，通過增加頂點(diǎn)和半邊，把交點(diǎn)變成頁片的頂點(diǎn)。

Step 2 用折痕及其對(duì)應(yīng)的半邊連接交點(diǎn)，把每個(gè)頁片分割為 2個(gè)或多個(gè)頁片。（如果被折疊的頁片是凹的，可能產(chǎn)生多個(gè)頁片。）

Step 3 按照事先約定的原則，將折疊線某側(cè)的頁片做旋轉(zhuǎn)，計(jì)算旋轉(zhuǎn)后的頂點(diǎn)坐標(biāo)，更改頁片的方向?qū)傩浴?/p>

Step 4 更新頁片的層次優(yōu)先級(jí)。更新的原則是：如果是向上折疊，則把參與旋轉(zhuǎn)的頁片的當(dāng)前優(yōu)先級(jí)顛倒，然后把它們放在最高層次；如果是向下折疊，則也把參與旋轉(zhuǎn)的頁片的當(dāng)前優(yōu)先級(jí)顛倒，然后把它們放在最低層次。

Step 5 遍歷前面已記錄的每個(gè)折疊操作，查找它所旋轉(zhuǎn)的頁片是否包含當(dāng)前被分割的頁片，如果包含，則將分割后的頁片替換分割前的頁片。

3.2 剪切操作

給定剪切路徑的描述，剪切操作可以由如下3步實(shí)現(xiàn)：

Step 1 按照事先約定的原則，把用戶輸入的剪切軌跡的外側(cè)做成一個(gè)足夠大的多邊形PCUT。

Step 2 對(duì)于當(dāng)前紙態(tài)中的每個(gè)頁片，做該頁片與多邊形PCUT的布爾減運(yùn)算。

Step 3 對(duì)于當(dāng)前紙態(tài)中的每條折痕，把它作為一條線段減去多邊形PCUT，如果該折痕沒有被全部減掉，則合成剩余折痕的半邊。合成的方法是根據(jù)坐標(biāo)匹配原則，即如果某剩余折痕的2個(gè)端點(diǎn)與該折痕兩側(cè)頁片的某2個(gè)半邊的坐標(biāo)相同，則將該折痕與這2條半邊關(guān)聯(lián)在一起。

3.3 展開操作

盡管通常僅需要最終的展開紙態(tài)，但它必須是逐步獲得的。在當(dāng)前紙態(tài)的基礎(chǔ)上進(jìn)行一次展開，可以通過下述步驟完成：

Step 1 從折剪操作棧中彈出一個(gè)操作，如果操作為空(到達(dá)棧底)，則結(jié)束；否則如果該操作是折疊操作，則轉(zhuǎn)到Step 2；如果該操作是剪切操作，則繼續(xù)Step 1。

Step 2 把 rot_facets中記錄的頁片做反向180°旋轉(zhuǎn)，計(jì)算旋轉(zhuǎn)后的頂點(diǎn)坐標(biāo)，更改頁片的方向?qū)傩浴?/p>

Step 3 重新設(shè)置參與旋轉(zhuǎn)頁片的層次優(yōu)先級(jí)。

3.4 顯示算法

因?yàn)橛涗浟隧撈膶哟蝺?yōu)先級(jí)，所以對(duì)紙態(tài)進(jìn)行二維真實(shí)感顯示變得非常簡(jiǎn)單，畫家算法即可完成此工作：首先對(duì)全部頁片按照層次優(yōu)先級(jí)由小到大的順序進(jìn)行排序，然后順序以實(shí)心填充的形式畫出每個(gè)頁片內(nèi)部，以不同的線型或顏色畫出它的邊界線和折痕線。

4 應(yīng)用實(shí)例

按照本文給出的計(jì)算模型，以Visual C++ 6.0為開發(fā)工具，實(shí)現(xiàn)了一個(gè)即可以進(jìn)行兒童剪紙方案設(shè)計(jì)又可以展示已有折剪方案的原型軟件，命名為Virtual Paper。目前該軟件還是一個(gè)純二維的，沒有提供操作的動(dòng)態(tài)演示功能。在折疊操作的人機(jī)交互方面，用戶除了可以任意設(shè)計(jì)折疊線外，還可以采用“沿對(duì)角線折”、“二等分對(duì)邊折”、“二等分角折”等非常常用的經(jīng)典折疊命令。圖4給出了在該軟件內(nèi)進(jìn)行折剪窗花的過程。注意在展開圖中區(qū)分了2種不同類型的折痕。

圖4 折剪一個(gè)窗花的過程截圖

5 結(jié) 論

與前人給出折紙計(jì)算模型相比[2-3,5]，本文給出的計(jì)算模型綜合考慮了折疊、剪切和展開的計(jì)算，并且詳細(xì)考慮了折痕的生成與表示。所開發(fā)的原型軟件Virtual Paper驗(yàn)證了這個(gè)模型的可行性。

本文所提出的模型雖然是為計(jì)算機(jī)輔助兒童折紙和剪紙?jiān)O(shè)計(jì)而設(shè)計(jì)的，但是它也可以應(yīng)用在其他方面，如服裝的裁剪方案設(shè)計(jì)。

進(jìn)一步工作應(yīng)重點(diǎn)放在如下2方面：一是進(jìn)一步擴(kuò)展該模型，使得它能夠兼容非簡(jiǎn)單折疊；二是進(jìn)一步完善Virtual Paper軟件，使得它能夠在三維空間以夸張的形式顯示當(dāng)前紙態(tài)并且能夠以動(dòng)畫形式演示各種操作。

[1]禾 稼. 彩版兒童剪紙大全[M]. 長(zhǎng)春: 吉林美術(shù)出版社, 2007. 1-342.

[2]Lang R J. A computational algorithm for origami design [C]//Proceedings of the 12th Annual ACM Symposium on Computational Geometry, Philadelphia,1996: 98-105.

[3]Ida T, Takahashi H, et al. Computational origami system Eos [C]//Proceedings of the 4th International Conference on Origami, Science, and Mathematics and Education, Pasadena, 2006: 69-73.

[4]Bern M, Hayes B. The complexity of flat origami [C]//Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms,Atlanta, 1996: 175-183.

[5]Kishi N, Fujji Y. Origami, folding paper over the web [C]//Proceedings of the 3rd Asian Pacific Conference on Computer and Human Interaction,Shonan Village Center, 1998: 337-342.

[6]Peng D, Sun S, Pan L. Research on Chinese paper-cut CAD system [C]//Proceedings of the 4th International Conference on Image and Graphics, Sichuan, 2007:892-896.

[7]張顯全, 于金輝, 蔣凌琳, 等.計(jì)算機(jī)輔助生成剪紙形象[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(6):1378-1382.

[8]Mantyla M. An introduction to solid modeling [M].Rockville: Computer Science Press, 1988. 69-76.