3D協(xié)作系統(tǒng)下基于DOAG的選擇性Undo/Redo研究

高麗萍，劉珊珊

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

1 引 言

當(dāng)?shù)谝淮翁剿餍孪到y(tǒng)時(shí)，用戶需要反復(fù)執(zhí)行和取消操作，以充分理解每個(gè)功能."任何具有復(fù)雜交互界面的系統(tǒng)都應(yīng)該提供Undo/Redo支持"的想法被屢次提出來(lái)[1]."沒(méi)有人會(huì)懷疑在交互系統(tǒng)中提供Undo/Redo功能的重要性"這一事實(shí)也指出了這一點(diǎn)[2].

協(xié)同CAD系統(tǒng)是地理上分散的設(shè)計(jì)師共同工作的重要平臺(tái).作為協(xié)作系統(tǒng)中的一個(gè)重要特性，Undo/Redo可以幫助減少錯(cuò)誤消除誤解[3,4].幾種選擇性Undo/Redo方法已經(jīng)在國(guó)內(nèi)外得到廣泛研究，主要在圖形編輯器和文本編輯器[5,6]中探索了選擇性Undo/Redo,很少對(duì)3D模型進(jìn)行探究，都是通過(guò)插件的形式來(lái)實(shí)現(xiàn)選擇性Undo/Redo,針對(duì)的目標(biāo)對(duì)象也是以前所作的操作，撤銷以前的操作，使得最后編輯的效果能滿足用戶意圖.在CAD協(xié)作系統(tǒng)下，要實(shí)現(xiàn)選擇性Undo/Redo是復(fù)雜的，比單機(jī)環(huán)境下更具有挑戰(zhàn)性.

要設(shè)計(jì)出一個(gè)復(fù)雜而有創(chuàng)意的工件，選出有意義的操作序列對(duì)快速設(shè)計(jì)出一個(gè)復(fù)雜的工品是有意義的，通過(guò)有意義的操作序列設(shè)計(jì)出滿足用戶需求的CAD模型，在進(jìn)行的一系列操作序列中，我們可以將操作之間的關(guān)系都詳細(xì)地描述出來(lái)，當(dāng)選擇其中的一個(gè)操作作為撤銷目標(biāo)時(shí)，依賴它的所有操作將會(huì)一起撤銷.在這種情況下，怎么更新剩下的邊界模型，當(dāng)對(duì)撤銷的目標(biāo)對(duì)象進(jìn)行重做時(shí)，怎么重構(gòu)新的邊界模型，這些都應(yīng)該清楚地表示說(shuō)明出來(lái).

一個(gè)通用的協(xié)作環(huán)境的基本正確性應(yīng)該得到滿足，例如意圖維護(hù)和一致性維護(hù).Undo/Redo的目的是消除并重新創(chuàng)建由特定的建模操作所生成的特性.操作在不同的站點(diǎn)之間是交叉的，并且在執(zhí)行了許多操作之后可以檢測(cè)到錯(cuò)誤.Undo/Redo的含義應(yīng)該被清楚地解釋.

此次我們不同于前面人提出的一種多用戶的Undo/Redo方法，而是用于三維協(xié)作CAD中.在我們的方法中，可以在每個(gè)站點(diǎn)中唯一地標(biāo)識(shí)Undo/Redo目標(biāo).我們還研究了設(shè)計(jì)工件的復(fù)雜操作，用提出的DOAG來(lái)表示一個(gè)構(gòu)成CAD模型的操作關(guān)系圖.在此基礎(chǔ)上，闡明了特征與操作之間的依賴關(guān)系.在每次撤銷或重做時(shí)，必須對(duì)邊界模型進(jìn)行更新和重構(gòu)，可以通過(guò)DOAG來(lái)幫助實(shí)現(xiàn).

這篇論文是在前人研究的基礎(chǔ)上[7-9]進(jìn)行詳細(xì)拓展的，詳細(xì)介紹了操作組合DOAG的構(gòu)造(第3部分),關(guān)于Undo/Redo的算法(第4部分)會(huì)詳細(xì)介紹，一個(gè)詳細(xì)的例子在第5部分會(huì)介紹.

2 相關(guān)工作

在Undo/Redo上的研究引發(fā)了Undo/Redo模型和機(jī)制，在Undo/Redo模型領(lǐng)域已經(jīng)做了大量的相關(guān)研究.最早的的的Undo/Redo是用在單機(jī)環(huán)境中，在單機(jī)環(huán)境中的Undo/Redo模型分為4類.

1) 單步Undo/Redo模型;

2) 線性Undo/Redo模型[10];

3) US&R模型[11];

4) 歷史Undo/Redo模型[12].

然而，在多用戶協(xié)作編輯系統(tǒng)中，在不同站點(diǎn)上的操作是相互交叉的.在本地站點(diǎn)上的最后一個(gè)操作未必是其他站點(diǎn)上的最后一個(gè)操作.所以選擇性Undo/Redo模型是多數(shù)用戶選擇的Undo/Redo模型.它的靈活度受到Undo/Redo范圍的限制.AnyUndo[13]是一個(gè)將撤銷策略與撤銷機(jī)制分離的框架.它允許用戶設(shè)計(jì)一個(gè)單一的撤銷算法來(lái)支持本地和全局的Undo/Redo和多個(gè)模型.選擇性撤銷模型，第一次在COPE[14]中提出用在多用戶系統(tǒng)中.它也被Knister和Ferrié J在[15,16]介紹.選擇性撤銷這一想法在協(xié)作系統(tǒng)[17]，協(xié)作編輯系統(tǒng)中[18,19]和協(xié)作圖形編輯系統(tǒng)[21]中采用.在協(xié)作編輯系統(tǒng)中的撤銷算法都屬于操作轉(zhuǎn)換.所有的3個(gè)撤銷模型，即單步撤銷，按時(shí)間先后順序的撤銷和選擇性撤銷，前兩種撤銷模式已經(jīng)被廣泛研究，后面選擇性撤銷方式在CAD中提出通過(guò)分解3D模型[22]，構(gòu)造特征組合層次結(jié)構(gòu)，將一個(gè)CAD模型進(jìn)行分解，基于特征組合結(jié)構(gòu)，特征間的依賴關(guān)系可以清楚得表現(xiàn)出來(lái)，簡(jiǎn)化了B-Rep重新評(píng)估，證明了提出的Undo/Redo重做方法滿足了協(xié)作系統(tǒng)的意圖保存和一致性維護(hù)的正確性.

Abowd[2]和Choudhary[17]提出的多用戶Undo/Redo模型沒(méi)有考慮到操作的依賴集，但GINA[15]中的選擇性撤銷模型和任意撤銷模型[13]有考慮到這點(diǎn).在MSS[9]中,要撤銷的目標(biāo)操作不是歷史緩存中的最后一個(gè)，做過(guò)的操作要重新安排，用MSS來(lái)記錄實(shí)際的操作順序，MSS是由在收到的模型操作執(zhí)行完后代表實(shí)現(xiàn)部分模型的狀態(tài)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都有相應(yīng)的拓?fù)鋵?shí)體集，相關(guān)的拓?fù)鋵?shí)體集可以分開(kāi)，組合和消除，TEST在每個(gè)站點(diǎn)都有副本，它可以跟蹤拓?fù)鋵?shí)體的改變，并弄清來(lái)自原始模型和新版本的TE之間的關(guān)系，在TEST中的每個(gè)節(jié)點(diǎn)都有唯一地標(biāo)識(shí)，這樣它可以指定它的創(chuàng)建操作.然而，在選擇性撤銷模型中，一個(gè)操作不能撤銷或重做，當(dāng)它與后面執(zhí)行的操作有依賴關(guān)系時(shí)，在前面的兩個(gè)模型中，當(dāng)做一個(gè)重做命令時(shí)，操作參數(shù)需要進(jìn)行轉(zhuǎn)換.當(dāng)面對(duì)未解決的沖突，他們采取一個(gè)多版本方法作為解決方法，在單機(jī)環(huán)境中，主要用的是多級(jí)模型和級(jí)聯(lián)選擇性撤銷模型.在操作中，相關(guān)性的解決方案是基于任務(wù)ID和任務(wù)相關(guān)性的.也就是說(shuō)，當(dāng)撤銷一個(gè)操作時(shí)，所有與之相關(guān)的任務(wù)都將被撤銷.

在多用戶Undo/Redo的領(lǐng)域中，在協(xié)同CAD系統(tǒng)下實(shí)現(xiàn)多用戶Undo/Redo的研究工作很少.我們以前提出的多用戶的Undo/Redo的解決方案的仍然存在缺陷，當(dāng)發(fā)現(xiàn)操作有依賴集時(shí)，會(huì)檢查每個(gè)附加的依賴集的特性是否引用了撤銷目標(biāo)所創(chuàng)建的拓?fù)鋵?shí)體.這樣撤銷目標(biāo)對(duì)象的效率非常低.其次，模型恢復(fù)在每個(gè)建模操作執(zhí)行之后通過(guò)存儲(chǔ)模型狀態(tài)來(lái)完成的.撤銷目標(biāo)的效果是首先通過(guò)執(zhí)行模型狀態(tài)并重新執(zhí)行所有有效操作來(lái)消除的.如果撤銷目標(biāo)位于歷史緩沖區(qū)的前端，并且減少了對(duì)它的處理，那么恢復(fù)效率將非常低.也有相關(guān)研究者為了表示設(shè)計(jì)工件的結(jié)構(gòu)和特性之間的相互依賴關(guān)系，采用了ACIS的邊界表示CAD模型的形狀.在ACIS中，屬性被附加到實(shí)體來(lái)描述它們的系統(tǒng)定義和用戶定義的特征.在此基礎(chǔ)上，由特定的建模操作創(chuàng)建的每一個(gè)實(shí)體都以(Create_SiteID,Create_SEQ)的形式作為其ID的輔助信息而被創(chuàng)建，每一個(gè)拓?fù)鋵?shí)體都可以獲得它的相關(guān)操作.為了方便獲得相關(guān)的拓?fù)鋵?shí)體，在協(xié)作CAD提出了FCH[22],特征組合層次是一種樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示CAD模型中每個(gè)特征實(shí)體之間的關(guān)系.

圖1 復(fù)雜模型的操作圖Fig.1 Diagram of complex model operation

在前面的研究中，恢復(fù)模型都采用這幾種方法，一種是重新執(zhí)行歷史緩沖區(qū)中的所有有效操作.盡管計(jì)算工作量巨大，但由于硬件速度加快，這仍然是可行的.第二種方法是在相鄰的建模操作之間存儲(chǔ)臨時(shí)的幾何模型或增量式的值.該方法是由國(guó)家CAD工程中心的王教授所采用的.再一種是通過(guò)邊界模型重構(gòu)以消除目標(biāo)操作和依賴操作集的執(zhí)行效果.該發(fā)明與已有技術(shù)相比較，效果是積極明顯的.

圖1是一個(gè)復(fù)雜模型的分解圖，由不同站點(diǎn)協(xié)同構(gòu)造該模型.以下用例子說(shuō)明在原型協(xié)同系統(tǒng)下不同站點(diǎn)上操作的執(zhí)行過(guò)程.如圖2所示，在站點(diǎn)1，6種特征模型操作O1,O2,O3,O4,O5,O6依次到達(dá)站點(diǎn)1，在站點(diǎn)2，操作O1，O2,O4,O4,O5,O6依次按順序到達(dá)，每個(gè)操作所引用的拓?fù)鋵?shí)體集在執(zhí)行時(shí)都能正確地通信，在站點(diǎn)1和站點(diǎn)2都不用重新調(diào)整操作順序.在站點(diǎn)3，來(lái)到的操作順序是O1,O3,O4,O2,O5,O6,當(dāng)執(zhí)行O3時(shí)，對(duì)模型上的邊進(jìn)行倒圓角，當(dāng)O4到達(dá)時(shí)，對(duì)模型進(jìn)行挖圓洞，接著，O2到達(dá)，在模型的中間挖凹槽，凹槽的位置大小受到了O3,O4操作的影響，O2→O4,為了保存O2的用戶意圖，必須重新調(diào)整O3,O4，O2的操作順序，由于O5→O6,也要一起撤銷O5,O6構(gòu)成的子模型，重新調(diào)整O1,O3,O4,O2,O5,O6的操作順序.

圖2 協(xié)同站點(diǎn)上操作執(zhí)行順序圖 Fig.2 Operation sequence in collaborative site

針對(duì)上圖的例子，我們需要調(diào)整站點(diǎn)3上的O3,O4,O2的操作順序來(lái)維護(hù)用戶意圖，但又要撤銷O5,O6操作構(gòu)成的子結(jié)構(gòu)，怎樣能快速撤銷掉已經(jīng)做過(guò)的操作又重新對(duì)撤銷的操作順序進(jìn)行安排呢，又不影響其他的操作構(gòu)成的子結(jié)構(gòu).通過(guò)有意義的操作序列來(lái)快速建立起一個(gè)實(shí)體模型，效率將大大提高，雖然每個(gè)站點(diǎn)上的操作序列是不一樣的，但我們將會(huì)在每個(gè)站點(diǎn)上都存儲(chǔ)了一個(gè)有意義維護(hù)用戶意圖的操作序列，方便用戶撤銷目標(biāo)操作及關(guān)于目標(biāo)操作的子結(jié)構(gòu)，而不影響其他沒(méi)有任何關(guān)系的操作.

3 在3D協(xié)作系統(tǒng)下設(shè)計(jì)操作聚合結(jié)構(gòu)

我們認(rèn)為一件工件的設(shè)計(jì)是多位不同用戶協(xié)同一起操作的完成的結(jié)果.作為一項(xiàng)正在進(jìn)行的研究，我們主要關(guān)注的是對(duì)于已經(jīng)做過(guò)的操作，不同站點(diǎn)的用戶如何快速地找到目標(biāo)操作及目標(biāo)操作攜帶的操作集進(jìn)行撤銷，調(diào)整操作順序來(lái)完成最終的設(shè)計(jì)意圖.通過(guò)挖掘一個(gè)有意義的設(shè)計(jì)操作序列，處理好這些有意義的操作序列，會(huì)使得選擇性撤銷的效率更加明顯，在一個(gè)協(xié)作的CAD系統(tǒng)中，每個(gè)站點(diǎn)都有操作依賴聚合結(jié)構(gòu)拓?fù)鋵?shí)體的副本.在將其發(fā)送到其他遠(yuǎn)程站點(diǎn)之前，在本地站點(diǎn)發(fā)出的操作優(yōu)先執(zhí)行.一個(gè)復(fù)雜的CAD模型可以分解成若干個(gè)不同的子結(jié)構(gòu)，構(gòu)成每個(gè)子結(jié)構(gòu)的操作具有依賴關(guān)系，主要用到的操作為幾何操作和布爾操作，幾何操作是指從一個(gè)已有的實(shí)體模型中選擇拓?fù)鋵?shí)體為目標(biāo)，如將一個(gè)實(shí)體的邊倒圓角，將這個(gè)實(shí)體縮小旋轉(zhuǎn)等等.布爾操作指的是聯(lián)合，減法和交叉.通過(guò)執(zhí)行布爾運(yùn)算，一個(gè)新的實(shí)體從兩個(gè)已有的實(shí)體中得到.盡管每個(gè)站點(diǎn)上的歷史緩沖區(qū)可以記錄所有建模操作的到達(dá)順序并進(jìn)行保存，但是當(dāng)要撤銷已做過(guò)的操作時(shí)，通過(guò)回溯歷史緩沖區(qū)，撤銷沒(méi)有任何依賴關(guān)系的操作是多余的，因此我們提出使用DOAG來(lái)找出有意義的操作集來(lái)快速獲得要撤銷的部分子結(jié)構(gòu)，而不影響其他操作構(gòu)成的子結(jié)構(gòu).在DOAG中，操作間的依賴關(guān)系，分為相關(guān)依賴或?qū)傩砸蕾?，相關(guān)依賴是指先用一個(gè)操作創(chuàng)建實(shí)體，后面的操作要借助實(shí)體或在實(shí)體上執(zhí)行，比如Oa,會(huì)被后面生成的操作Ob引用,可以表示Oa→Ob；屬性依賴是指如果對(duì)某個(gè)生成操作的定義的某些參數(shù)受到前面創(chuàng)建操作的大小或位置的影響，通過(guò)利用DOAG，當(dāng)要撤銷操作時(shí)，可以快速的找到目標(biāo)操作及目標(biāo)操作的子結(jié)構(gòu)，也不會(huì)影響其他沒(méi)有依賴關(guān)系的操作.特定的建模操作創(chuàng)建的實(shí)體都以(CreateSiteID,CreateSeq)的形式作為其ID的輔助信息附加到相應(yīng)的建模操作屬性中，在DOAG中，我們通過(guò)ID可以快速找到這個(gè)建模操作所代表的子結(jié)構(gòu)，進(jìn)行選擇性撤銷而進(jìn)行重做，而我們主要對(duì)這些要撤銷的復(fù)雜模型的操作進(jìn)行討論，而其他與要撤銷的目標(biāo)對(duì)象沒(méi)有關(guān)系的操作的執(zhí)行在各個(gè)站點(diǎn)都不會(huì)違背用戶的意圖和最后模型的一致性.

3.1 DOAG的簡(jiǎn)單介紹

在基于協(xié)作特征的三維CAD環(huán)境中生成的工件模型是由多個(gè)設(shè)計(jì)者共同操作的復(fù)雜對(duì)象，這些設(shè)計(jì)者迭代地添加，刪除各種類型的特征.它用B-Rep表示，其形狀由大量不同的拓?fù)鋵?shí)體組成，如拓?fù)涿?，邊和頂點(diǎn).布爾運(yùn)算(如聯(lián)合，減法和交叉)提供了一種有效的方法來(lái)將特征和實(shí)體組合一起.接下來(lái)我們介紹一個(gè)有意義的操作聚合圖[20]的基于圖形的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱DOAG.

定義1.因果順序關(guān)系"→".任意兩個(gè)操作Oa和Ob,如果Oa因于Ob之前，表示為Oa→Ob,則Oa創(chuàng)建的相應(yīng)拓?fù)鋵?shí)體由Ob引用.

定義2.因果維護(hù)"→".任意兩個(gè)操作Oa和Ob,如果因于Ob之前，表示為Oa→Ob，則在任意站點(diǎn)上Oa總是在Ob之前執(zhí)行.

定義3.依賴關(guān)系.給兩個(gè)操作Oa和Ob，如果Ob屬性依賴或相關(guān)依賴于Oa,則表示為Oa→Ob.

定義4.DOAG的描述.一個(gè)DOAG=是由一組Nv個(gè)頂點(diǎn)V，Ne條邊E組成的，一條邊(Vi,Vj)表示頂點(diǎn)Vi與Vj之間有依賴關(guān)系.

定義5.意圖維護(hù).一個(gè)模型操作O的意圖能夠得到保存當(dāng)且僅當(dāng)1)為了幾何目的與O相關(guān)的sub-DOAG不會(huì)改變或者存在CAD模型對(duì)應(yīng)的DOAG.2)與O相關(guān)的每個(gè)sub-DOAG對(duì)應(yīng)的拓?fù)鋵?shí)體一定存在.

一個(gè)頂點(diǎn)V被定義為五元組,其形式如下.，type表示操作類型，timestamp表示為所有協(xié)作站點(diǎn)上操作的執(zhí)行順序統(tǒng)一自動(dòng)生成的整數(shù)，reference_dependency表示與頂點(diǎn)Vi有相關(guān)依賴關(guān)系的代表操作的一組頂點(diǎn)(v1,v2,…,vn)，attribute_dependency表示與頂點(diǎn)Vi有屬性依賴關(guān)系的代表操作的一組頂點(diǎn)(v1,v2,…,vn).

DOAG是一種樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示操作之間的聚合關(guān)系，在協(xié)作設(shè)計(jì)過(guò)程中很多操作具有很多依賴關(guān)系，將這些因依賴關(guān)系聚合在一起的操作構(gòu)成的模型稱為子結(jié)構(gòu).一個(gè)復(fù)雜的CAD模型可以分解為很多子結(jié)構(gòu).

在一個(gè)協(xié)作CAD系統(tǒng)中創(chuàng)建的CAD模型是以一個(gè)原始模型操作而開(kāi)始創(chuàng)建的，而這個(gè)原始模型操作的依賴集在整個(gè)模型中是最大的，這個(gè)操作所構(gòu)成的模型在DOAG中相當(dāng)于中心點(diǎn)Vcentral，檢索在與當(dāng)前中心點(diǎn)的有引用依賴和屬性依賴的操作，每個(gè)操作作為子DOAG的中心點(diǎn)被自動(dòng)識(shí)別為連接到Vcentral.中心點(diǎn)按操作的時(shí)間戳來(lái)排序的，這樣整個(gè)操作序列都是連貫的，如果要檢索某個(gè)節(jié)點(diǎn)的依賴集及構(gòu)成的子結(jié)構(gòu)，我們進(jìn)行了如下總結(jié)：

1) DOAG是一種描述復(fù)雜CAD模型的樹(shù)型結(jié)構(gòu)，其根節(jié)點(diǎn)對(duì)應(yīng)協(xié)同站點(diǎn)上的開(kāi)始的操作，在檢索這個(gè)操作的所有DOS，所構(gòu)成的模型就是一個(gè)子結(jié)構(gòu)，當(dāng)某個(gè)子結(jié)構(gòu)不滿足用戶意愿時(shí)，可以再進(jìn)行分解，構(gòu)成用戶想要的子結(jié)構(gòu)，而不會(huì)影響沒(méi)有任何依賴關(guān)系的操作及操作集構(gòu)成的子結(jié)構(gòu)，每個(gè)子結(jié)構(gòu)和操作都由節(jié)點(diǎn)和葉子節(jié)點(diǎn)保存著；DOAG的根節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)使用基對(duì)象指針指向代表該復(fù)雜子結(jié)構(gòu)的基特征的節(jié)點(diǎn)，并且保存了其代表的復(fù)雜子結(jié)構(gòu)分解生成的子結(jié)構(gòu)對(duì)應(yīng)的節(jié)點(diǎn)集，子節(jié)點(diǎn)使用基對(duì)象指針指向代表該原子結(jié)構(gòu)的定位特征的節(jié)點(diǎn).圖3中用虛線圈的操作可以構(gòu)成一個(gè)子結(jié)構(gòu).

圖3 圖1中復(fù)雜模型的DOAG圖Fig.3 DOAG of complex model in Fig.1

3.2 特征模型操作表示

可以用下面的結(jié)構(gòu)表示一個(gè)特征操作構(gòu)成的子結(jié)構(gòu)：

Struct

{

long int CentralOperatin;

long int ReferDepOpPointer;

Long int AtrDepOpPointer;

long int SubConf_Node;

int SubConf_No;

}Sub_Configuration

Struct

{

long int subConfBoundaryModelPointer;

Std..listm_listSubConfPointer;

}3D Modeling

通過(guò)上面兩個(gè)類，通過(guò)執(zhí)行第1個(gè)類可以獲得所有操作的操作集，第2個(gè)類可以幫助找到目標(biāo)操作.

4 在復(fù)制式協(xié)同系統(tǒng)下的Undo/Redo方法

在提到Undo/Redo方法之前，有必要討論一下我們?cè)趨f(xié)作CAD系統(tǒng)中采用的一致性維護(hù)機(jī)制.一個(gè)協(xié)作性的CAD系統(tǒng)需要執(zhí)行一個(gè)建模操作來(lái)滿足因果關(guān)系的保存和意圖的保存.所有副本在協(xié)作任務(wù)結(jié)束時(shí)達(dá)到收斂的狀態(tài).為了識(shí)別在一個(gè)復(fù)制的協(xié)作式CAD系統(tǒng)中協(xié)作站點(diǎn)所發(fā)布的同步操作的順序，使用基于Lamport State Vector[23]的時(shí)間戳排序技術(shù)，狀態(tài)矢量是N個(gè)分量矢量，其中N代表所有協(xié)作站點(diǎn)的總數(shù)，并且每個(gè)站點(diǎn)都有一個(gè)唯一的ID，范圍從0到N-1.每個(gè)站點(diǎn)都保留一個(gè)狀態(tài)向量，其中i-1組件表示站點(diǎn)中已經(jīng)執(zhí)行了多少操作.兩個(gè)狀態(tài)向量，SVi和SVj,是通過(guò)這種方式比較的，

1) SVi=SVj當(dāng)且僅當(dāng)SVi中的值與SVj中相應(yīng)的值相等;

2) SVi

3) SVi>SVj，當(dāng)且僅當(dāng)SVi中的值大于SVj中的值.

任何操作生成時(shí)或傳到其他站點(diǎn)時(shí)都會(huì)攜帶自身的狀態(tài)向量，當(dāng)SVi≤SVj時(shí)，i站點(diǎn)上的操作優(yōu)先執(zhí)行，通過(guò)采用一種樂(lè)觀的序列化并發(fā)控制方法實(shí)現(xiàn)了目標(biāo)的保存.在很多協(xié)同系統(tǒng)中，為了維護(hù)用戶意圖的一致性和收斂性，都采用了狀態(tài)向量來(lái)解決出現(xiàn)的并發(fā)問(wèn)題[24,25].

當(dāng)要撤銷一個(gè)操作時(shí)，在協(xié)同CAD環(huán)境中實(shí)現(xiàn)Undo/Redo方法需要考慮到操作之間的依賴關(guān)系，結(jié)合上面提出的DOAG，我們很快檢索到任意操作所攜帶的子結(jié)構(gòu)，首先要檢查相應(yīng)的操作所帶的DOS構(gòu)成的子結(jié)構(gòu)，然后，所有依賴于撤銷目標(biāo)的操作都應(yīng)該全部撤銷，并且不會(huì)影響其他操作.

當(dāng)一個(gè)撤銷命令被發(fā)布時(shí)，它的意圖是將已經(jīng)做過(guò)的操作進(jìn)行撤銷掉，而不影響其他操作，需要包括：

1)正確地找到撤銷目標(biāo)的依賴集；

2)成功地將撤銷目標(biāo)和依賴于它的操作的效果一起撤銷，而不影響其他的子結(jié)構(gòu).

當(dāng)一個(gè)重做命令發(fā)出時(shí)，它的意圖是撤銷由同一用戶發(fā)出的最近的撤銷.在這一節(jié)中，我們提出了一個(gè)局部的Undo/Redo方法，用戶只能撤銷由他/她所發(fā)出的操作，該操作可能不是最后的操作.

4.1 確定Undo/Redo目標(biāo)

當(dāng)某一個(gè)有意義的操作序列在站點(diǎn)i上依次執(zhí)行，當(dāng)傳到其他站點(diǎn)時(shí)，出現(xiàn)操作順序和站點(diǎn)i上的不一致，要通過(guò)局部Undo/Redo來(lái)調(diào)整操作順序，維護(hù)用戶意圖.由于網(wǎng)絡(luò)延時(shí)和基于狀態(tài)向量上的因果關(guān)系，在每個(gè)協(xié)作站點(diǎn)上的歷史操作都有以下特點(diǎn)：

1)來(lái)自同一站點(diǎn)上的操作在所有站點(diǎn)上都以相同的順序執(zhí)行.

2)來(lái)自不同協(xié)作站點(diǎn)上的模型操作都是交叉的和在不同的站點(diǎn)以不同的順序執(zhí)行.

因?yàn)橛脩粢蜂N的目標(biāo)對(duì)象不可能永遠(yuǎn)是最后一個(gè)，當(dāng)定位到要撤銷的目標(biāo)時(shí)，首先要考慮到兩種情況：

1)定位到本地站點(diǎn)的撤銷對(duì)象；

2)定位遠(yuǎn)程站點(diǎn)的撤銷目標(biāo)對(duì)象.

一個(gè)建模操作在生成過(guò)后在相應(yīng)的站點(diǎn)會(huì)立即執(zhí)行，所以撤銷的目標(biāo)操作只存在本地站點(diǎn)上的執(zhí)行列表中.

在一個(gè)協(xié)作CAD的原型系統(tǒng)中，有N個(gè)站點(diǎn)，Ai,j(0

當(dāng)一個(gè)任意的遠(yuǎn)程的站點(diǎn)Sj收到Undo要求，這個(gè)要撤銷的對(duì)象可能不是最后一個(gè)執(zhí)行的操作，所以它要撤銷的目標(biāo)操作可能在ExecutedListj和WaitListj中，為了找到要撤銷的目標(biāo)，就要采用SiteId和StateVector,任意站點(diǎn)發(fā)送的操作都會(huì)攜帶狀態(tài)向量信息，當(dāng)撤銷命令發(fā)送到其他站點(diǎn)時(shí)，首先在ExecutedListj搜索，然后在WaitListj中搜索，直至找到要撤銷的目標(biāo).

當(dāng)找到要撤銷的目標(biāo)時(shí)，由于每個(gè)站點(diǎn)都存儲(chǔ)了整個(gè)操作所構(gòu)成的DOAG，當(dāng)要撤銷的目標(biāo)在DOAG中進(jìn)行遍歷時(shí)，就會(huì)找到相應(yīng)的該操作所攜帶的子DOAG，并和該操作一并撤銷掉，并且不影響其他的操作所構(gòu)成的模型結(jié)構(gòu)，當(dāng)對(duì)撤銷的操作進(jìn)行重做時(shí)，對(duì)它本身所攜帶的子DOAG進(jìn)行重做，重構(gòu)整個(gè)邊界模型.對(duì)于在本地站點(diǎn)和遠(yuǎn)程站點(diǎn)的撤銷目標(biāo)的處理，我們?cè)O(shè)計(jì)了如下幾個(gè)算法：

算法1.對(duì)于如何獲得撤銷目標(biāo)的子DOAG的算法

Input. the identified Undo target operation Op,current DOAG

Output.DOAG(Op)

1.root=root node of DOAG

2.From root to Scan all object_nodes

3.Op_Node=the object node of Op in DOAG

4.DOS(Op)=Empty;

5.SubConf_Node=Op_Node.m_listSubConfPointer[i];

6.Temp_Node=Op_Node.next;

7.while(Temp_Node!=SubConf_Node)

8.if(Temp_Node->ReferDepOpPointer==Op_Node)

9. Temp_Node is put into sub_DOAG(Op);

10. if(Temp_Node->AtrDepOpPointer!=Op_Node)

11. Temp_Node is put into sub_DOAG(Op);

12. SubConf_Node=sub_DOAG(Op);

13. CentralOperation=Op_Node;

14. while(SubConf_Node!=NULL)

15. if(SubConf_Node->subConfBoundaryPointer==Op_Node)

16. Op_Node is put into sub_DOAG(Op);

17. endif

18. endwhile

19. endif

20. endif

21.Temp_Node=Temp_Node->next

22.endwhile

該算法首先找到DOAG中原始的根節(jié)點(diǎn)，將其設(shè)為中心點(diǎn)Vcentral，再檢索與當(dāng)前中心點(diǎn)的有引用依賴和屬性依賴關(guān)系的操作，將其存儲(chǔ)到每個(gè)中心點(diǎn)的DOAG中，每個(gè)操作作為子DOAG的中心點(diǎn)被自動(dòng)識(shí)別為連接到Vcentral，依次往下遍歷所有的操作節(jié)點(diǎn)，直到所有操作遍歷完為止.

算法2.在協(xié)同站點(diǎn)上的選擇性Undo方法算法

Input. Undo request,history buffer HBi at Sitei,current Sub_DOAG(Op)

Output. Re-evaluated geometry model

1.Op= the identified undo target in history buffer;

2.sub_DOAG(Op)=Op's dependency operation set;

3.Op_Node=the object node of Op in the DOAG;

4.i=Op_Node.SubConf_No;

5.SubConf_Node=Op_Node.m_listSubConfPointer[i];

6.Op_Node=the central node of the SubConf_Node;

7.SubConf_Node=the base model of the Op_Node;

8.while(Op_Node!=Temp_Node)

9. if(Temp_Node is in sub_DOAG(Op_Node))

10. delete Op_Node from DOAG;

11. else

12. SubConf_Node=SubConf_Node->subConfBoundaryModelPointer[i];

13. endif

14. Temp_Node=Op_Node->Next;

15.endwhile

16.Op_Node.m_listSubConfPointer[i]=SubConf_Node;

17.combine all the exiting sub_configurations to obtain the re-evaluated boundary model;

該算法從根節(jié)點(diǎn)進(jìn)行出發(fā)開(kāi)始遍歷，通過(guò)遍歷不同的子結(jié)構(gòu)，找到目標(biāo)操作及目標(biāo)操作的子DOAG進(jìn)行撤銷，撤消目標(biāo)操作后對(duì)所剩的邊界模型進(jìn)行重構(gòu).

算法3.在協(xié)同站點(diǎn)上的Redo算法

Input.Redo request,history buffer HBiat sitei,current DOAGi

Output. Re-evaluated geometry model

1.if(Op_Node.RefDepOpPointer==NULL&&Op_Node.AtrDepOpPointer==NULL)

2.Temp_Node=Op_Node->next;

3.Op_Node=Temp_Node;

4.Op_Node.m_listSubConfPointer[i]=NULL;

5.SubConf_Node=the base model of Op_Node;

6.subConfBoundaryModelPointer=the boundary model physical adreess of SubConf_Node;

7.Op_Entity=new SubConf_Node();

8.Ob_Entity.subConfBoundaryModelPointer[i]=SubConf_Node;

9.endif

10.if(Op_Node.RefDepOperationList!=NULL||Op_Node.AtrDepOperationList!==null)

11.identity the operation creating the referenced topological entities;

12.Temp_Node=the object nodes of the operation;

13.Op_New=new SubConf_Node();

14.Op_New->next=Temp_Node;

15.SubConf_Node_New.subConfBoundaryModelPointer=pointer points to the new subconfiguration;

16.if(the topological entities of Op.ReferenceEntityLis are from the base feature)

17.i=m_listSubConfPointer.count();

18.Op_Ref|Atri.the_i+1th_Configuration_Pointer=new SubConfiguration();

19.Op_Ref|Atri.the_i+1th_Configuration_Pointer=Op_New;

20.else

21.Op_Ref|Arti.This_SubConfigurationPointer=Op.New;

22.endif

23.endif

Undo/Redo的命令的目的是消除又重做某個(gè)特征，當(dāng)用戶要撤銷已經(jīng)做過(guò)的操作及該操作構(gòu)成的子結(jié)構(gòu)時(shí)，又要對(duì)撤銷的目標(biāo)對(duì)象進(jìn)行重做，通過(guò)獲得撤銷操作的DOAG再更新一個(gè)新的DOAG子結(jié)構(gòu)來(lái)滿足用戶意圖，對(duì)更新后的DOAG子結(jié)構(gòu)進(jìn)行重做而不會(huì)影響其他的操作所構(gòu)成的邊界模型.

5 算法正確性證明

在這小部分，我們將證明提出關(guān)于選擇性Undo/Redo一致性解決方案的正確性.

定理1.我們的選擇性Undo/Redo算法遵循do和undo意圖.

證明：來(lái)自同一站點(diǎn)上的操作在所有站點(diǎn)上都是以相同順序執(zhí)行，所以(SiteID,Create_SEQ)能用來(lái)準(zhǔn)確地標(biāo)識(shí)要undo的目標(biāo)，假如O是要撤銷的目標(biāo)操作，根據(jù)我們的算法，通過(guò)DOAG，遍歷所有的操作，找到要撤銷的目標(biāo)操作及目標(biāo)操作的sub-DOAG,所以在整個(gè)DOAG中就沒(méi)有O及O的sub-DOAG的影響.當(dāng)redo命令喚起時(shí)，撤銷的目標(biāo)操作O及O的sub-DOAG被標(biāo)識(shí)，再次重做.所以redo意圖得到了維護(hù).

論點(diǎn)1.執(zhí)行過(guò)的操作都遵循因果關(guān)系.

證明：為了證明這個(gè)論點(diǎn)，我們只需要證明一個(gè)新來(lái)的模型操作的執(zhí)行不會(huì)違背已經(jīng)建立好的因果關(guān)系.

舉DOAG{sub-DOAG1(O1),sub-DOAG2(Oi)...sub-DOAG(On)為一個(gè)例子，它相應(yīng)的歷史緩存為HB={O0,O1,O2,...On},假設(shè)已經(jīng)執(zhí)行過(guò)的操作都遵循因果關(guān)系，On+1是收到的最新的操作，如果On+1的執(zhí)行不違背已經(jīng)執(zhí)行過(guò)的操作的操作順序，那么On+1立即執(zhí)行，On+1的執(zhí)行不會(huì)對(duì)DOAG有影響.如果違背了相關(guān)的CAD模型的DOAG，然后通過(guò)DOAG，找到On+1的sub-DOAG.那么sub-DOAG(On+1)={Oi...Ok},0<=i<=k<=n,所以DOAG={sub-DOAG(O1),sub-DOAG(Oi)...sub-DOAG(On+1)...sub-DOAG(On)},sub-DOAG(On+1)是On+1的相應(yīng)的子結(jié)構(gòu).

首先，On+1的執(zhí)行不會(huì)違背O0到Oi-1的因果順序，第二，On+1依賴{O0...Oi-1}中的一些操作，因?yàn)镺n+1是在它們之后而又獲得sub-DOAG(On+1)之前喚起的，因此，On+1執(zhí)行的因果維護(hù)得到了滿足，第三On+1與{Oi,...,On}中的操作沒(méi)有因果關(guān)系.所以它們是可以交換的，在{Oi,...On}之前喚起On+1不會(huì)違背因果關(guān)系，所以，論點(diǎn)1被證明是成立的.

論點(diǎn)2.我們的選擇性Undo/Redo算法不會(huì)違背建立好的因果順序.

證明：當(dāng)要撤銷一些操作，為了可以看到撤銷目標(biāo)操作過(guò)后的結(jié)果，主要需要兩步：獲得O執(zhí)行時(shí)的模型狀態(tài)并重新評(píng)估撤銷目標(biāo)操作及目標(biāo)操作的子結(jié)構(gòu)后的部分模型.

第一步，通過(guò)遍歷DOAG獲得撤銷目標(biāo)之前的模型狀態(tài)，所以在撤銷目標(biāo)操作O之前執(zhí)行過(guò)的操作都滿足因果依賴關(guān)系.第二步，重構(gòu)剩下的沒(méi)有任何關(guān)系的子結(jié)構(gòu)模型，撤銷完目標(biāo)操作后，此時(shí)將DOAG中目標(biāo)操作及目標(biāo)操作構(gòu)成的子結(jié)構(gòu)設(shè)為無(wú)效，其他的操作及相應(yīng)的子結(jié)狀態(tài)保持不變.

定理2.我們的選擇性Undo/Redo算法滿足因果維護(hù).

證明：根據(jù)論點(diǎn)1和論點(diǎn)2，選擇性Undo/Redo的執(zhí)行不會(huì)違背已設(shè)計(jì)好的DOAG，所以因果維護(hù)性質(zhì)得到滿足.

定理3.通過(guò)選擇性Undo/Redo算法，模型一致性得到維護(hù).

證明：通過(guò)正式的正確性標(biāo)準(zhǔn)和定理1和定理2，執(zhí)行選擇性Udo/Redo能維護(hù)所有站點(diǎn)上模型的一致性.

5.1 實(shí)例分析

對(duì)同一模型，用戶在不同的站點(diǎn)有不同的操作順序O0(0,POLYGON,1),O1(1,CYLINDER,1), O2(2,ROUNDHOLE,1),O3(0,SPIRAL-POLYGON,2), O4(1,SPIRAL-CYLINDER,2), O5(2,UNION,2),O1與O2,O3與O4是屬性依賴，用戶設(shè)計(jì)的DOAG如圖4所示，每個(gè)站點(diǎn)的執(zhí)行順序必須嚴(yán)格按照設(shè)計(jì)的DOAG來(lái)安排操作順序.

每個(gè)站點(diǎn)上都保存DOAG，當(dāng)用戶要撤銷相應(yīng)的操作時(shí)，通過(guò)DOAG能夠快速地找到目標(biāo)操作的子結(jié)構(gòu)一起撤銷，再重新調(diào)整操作順序，滿足用戶意圖.

圖4 簡(jiǎn)單模型的DOAG圖 Fig.4 DOAG for the simple model

在圖5示例中，站點(diǎn)0上O0,O1,O2,O3,O4,O5先后到達(dá)，在站點(diǎn)1，當(dāng)O4,O3到達(dá)時(shí)與用戶地意圖相違背，由站點(diǎn)1發(fā)出Undo(O3)命令，撤銷O3及O3操作所帶的子結(jié)構(gòu)，重新調(diào)整操作O3,O4的操作順 序.同樣在站點(diǎn)2，當(dāng)O2到達(dá)時(shí)，與用戶期望的O1→o2相違背，當(dāng)O4到達(dá)時(shí)也同樣違背了用戶的意圖，因此要撤銷O1和O3及Sub-DOAG(O1)和Sub-DOAG(O3).根據(jù)每個(gè)站點(diǎn)上的DOAG，可以很快找到目標(biāo)操作的子結(jié)構(gòu)，并對(duì)其一起撤銷.撤銷過(guò)后，對(duì)Sub-DOAG(O1)和Sub-DOAG(O3)中的操作順序重新調(diào)整，重構(gòu)邊界模型.過(guò)程如圖6及圖7所示.

圖5 協(xié)同建模過(guò)程的例子Fig.5 Example of the collaborative modeling process

圖6 站點(diǎn)1上撤銷O3后操作重做過(guò)程 Fig.6 Operation rearrangement process after Undo(O3) on site1

5.2 實(shí)驗(yàn)結(jié)果討論

圖7 站點(diǎn)2上撤銷O3和O1后操作重做過(guò)程 Fig.7 Operation re-arrangemen process after Undo(O3) and Undo(O1)on site2

通過(guò)上面的例子，站點(diǎn)0，站點(diǎn)1和站點(diǎn)2同時(shí)對(duì)同一工件進(jìn)行設(shè)計(jì)，首先用戶通過(guò)DOAG來(lái)描繪出構(gòu)成工件的操作關(guān)系圖，將DOAG存放在每個(gè)站點(diǎn)上，到達(dá)站點(diǎn)0上的操作順序是O1,O2,O3,O4,O5,此操作順序滿足用戶的設(shè)計(jì)意圖和用戶設(shè)計(jì)的DOAG，O1→O2,(O3→O4)→O5,其中O1,O2和O3,O4都屬于屬性依賴，O3,O4和O5屬于相關(guān)依賴.當(dāng)站點(diǎn)1收到遠(yuǎn)程站點(diǎn)發(fā)過(guò)來(lái)的O4,O3和O5操作時(shí)，操作的執(zhí)行順序O4,O3,O5違背了用戶設(shè)計(jì)的DOAG，因此要撤銷已經(jīng)做過(guò)但不能滿足用戶意愿的操作，通過(guò)算法2和算法1找到要撤銷的目標(biāo)操作O3以及O3的依賴集，一起進(jìn)行撤銷，O3的依賴集O4,O5一起撤銷后，構(gòu)造出新的并滿足DOAG但又不會(huì)影響其他操作構(gòu)成的子模型，通過(guò)算法3進(jìn)行重做.同樣在站點(diǎn)2上，當(dāng)O2,O1到來(lái)時(shí)，該操作順序也違背了O1→O2,根據(jù)算法2和算法1找到要撤銷的目標(biāo)操作O1及目標(biāo)操作的依賴集O2，一起撤消后并構(gòu)造出新的子結(jié)構(gòu)模型，通過(guò)算法3進(jìn)行重做，但又不影響其他的操作構(gòu)成的子結(jié)構(gòu)，同樣，當(dāng)O4,O3,O5到來(lái)時(shí)，該情況和站點(diǎn)1的情況相同，通過(guò)算法1找到要撤銷的目標(biāo)操作O3及O3的依賴集，通過(guò)算法2對(duì)目標(biāo)操作進(jìn)行撤銷，撤銷過(guò)后，通過(guò)算法3對(duì)撤銷的操作進(jìn)行重構(gòu)，再對(duì)重構(gòu)后的子結(jié)構(gòu)進(jìn)行重做.最后所有站點(diǎn)上的操作順序都滿足了用戶預(yù)先設(shè)計(jì)的DOAG，每個(gè)站點(diǎn)上都存有如圖8的模型關(guān)系圖，圖9和圖10表示撤銷目標(biāo)操作后的模型關(guān)系圖，用戶可以根據(jù)剩余的邊界模型進(jìn)行重構(gòu)，使得各個(gè)站點(diǎn)上所有的模型都能達(dá)到一致.維護(hù)了用戶的意圖，所有站點(diǎn)上的最后設(shè)計(jì)出的模型相同，也滿足了一致性.

圖8 每個(gè)站點(diǎn)上簡(jiǎn)單模型的關(guān)系圖Fig.8 Simple model at each site after the collaborative modeling process

6 結(jié) 論

我們?cè)趶?fù)制的協(xié)同三維建模系統(tǒng)中提出了選擇性多用戶的Undo/Redo方法.通過(guò)Site ID和Lamport 狀態(tài)向量在本地站點(diǎn)和遠(yuǎn)程站點(diǎn)上標(biāo)識(shí)要Undo/Redo的目標(biāo)操作，通過(guò)Undo/Redo來(lái)實(shí)現(xiàn)維護(hù)用戶設(shè)計(jì)意圖.摘要提出在設(shè)計(jì)操作聚合結(jié)構(gòu)圖的輔助下，詳細(xì)地說(shuō)明了操作之間的關(guān)系.通過(guò)這種方式，依賴于撤銷目標(biāo)的子結(jié)構(gòu)很容易的獲得，并且也將消除目標(biāo)操作而不影響其他沒(méi)有任何關(guān)系的操作或子結(jié)構(gòu)，對(duì)撤銷后的子結(jié)構(gòu)重做來(lái)維護(hù)用戶的設(shè)計(jì)意圖，使得最后模型的一致性得到了維護(hù).最后，我們的算法的正確性得到了驗(yàn)證，并在我們構(gòu)建的原型中執(zhí)行了實(shí)驗(yàn).

圖9 在站點(diǎn)1上撤銷O3后的模型關(guān)系圖Fig.9 Simple model after undo(O3) command at site1

圖10 在站點(diǎn)2上撤銷O3和O1后的模型關(guān)系圖Fig.10 Simple model after undo(O3) and undo(O2) command at site2