3D協作系統下基于DOAG的選擇性Undo/Redo研究

高麗萍，劉珊珊

1(上海理工大學 光電信息與計算機工程學院，上海 200093) 2(復旦大學 上海市數據科學重點實驗室，上海 200093)

1 引 言

當第一次探索新系統時，用戶需要反復執行和取消操作，以充分理解每個功能."任何具有復雜交互界面的系統都應該提供Undo/Redo支持"的想法被屢次提出來[1]."沒有人會懷疑在交互系統中提供Undo/Redo功能的重要性"這一事實也指出了這一點[2].

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

要設計出一個復雜而有創意的工件，選出有意義的操作序列對快速設計出一個復雜的工品是有意義的，通過有意義的操作序列設計出滿足用戶需求的CAD模型，在進行的一系列操作序列中，我們可以將操作之間的關系都詳細地描述出來，當選擇其中的一個操作作為撤銷目標時，依賴它的所有操作將會一起撤銷.在這種情況下，怎么更新剩下的邊界模型，當對撤銷的目標對象進行重做時，怎么重構新的邊界模型，這些都應該清楚地表示說明出來.

一個通用的協作環境的基本正確性應該得到滿足，例如意圖維護和一致性維護.Undo/Redo的目的是消除并重新創建由特定的建模操作所生成的特性.操作在不同的站點之間是交叉的，并且在執行了許多操作之后可以檢測到錯誤.Undo/Redo的含義應該被清楚地解釋.

此次我們不同于前面人提出的一種多用戶的Undo/Redo方法，而是用于三維協作CAD中.在我們的方法中，可以在每個站點中唯一地標識Undo/Redo目標.我們還研究了設計工件的復雜操作，用提出的DOAG來表示一個構成CAD模型的操作關系圖.在此基礎上，闡明了特征與操作之間的依賴關系.在每次撤銷或重做時，必須對邊界模型進行更新和重構，可以通過DOAG來幫助實現.

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

2 相關工作

在Undo/Redo上的研究引發了Undo/Redo模型和機制，在Undo/Redo模型領域已經做了大量的相關研究.最早的的的Undo/Redo是用在單機環境中，在單機環境中的Undo/Redo模型分為4類.

1) 單步Undo/Redo模型;

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

3) US&R模型[11];

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

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

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

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

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

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

圖1是一個復雜模型的分解圖，由不同站點協同構造該模型.以下用例子說明在原型協同系統下不同站點上操作的執行過程.如圖2所示，在站點1，6種特征模型操作O1,O2,O3,O4,O5,O6依次到達站點1，在站點2，操作O1，O2,O4,O4,O5,O6依次按順序到達，每個操作所引用的拓撲實體集在執行時都能正確地通信，在站點1和站點2都不用重新調整操作順序.在站點3，來到的操作順序是O1,O3,O4,O2,O5,O6,當執行O3時，對模型上的邊進行倒圓角，當O4到達時，對模型進行挖圓洞，接著，O2到達，在模型的中間挖凹槽，凹槽的位置大小受到了O3,O4操作的影響，O2→O4,為了保存O2的用戶意圖，必須重新調整O3,O4，O2的操作順序，由于O5→O6,也要一起撤銷O5,O6構成的子模型，重新調整O1,O3,O4,O2,O5,O6的操作順序.

圖2 協同站點上操作執行順序圖 Fig.2 Operation sequence in collaborative site

針對上圖的例子，我們需要調整站點3上的O3,O4,O2的操作順序來維護用戶意圖，但又要撤銷O5,O6操作構成的子結構，怎樣能快速撤銷掉已經做過的操作又重新對撤銷的操作順序進行安排呢，又不影響其他的操作構成的子結構.通過有意義的操作序列來快速建立起一個實體模型，效率將大大提高，雖然每個站點上的操作序列是不一樣的，但我們將會在每個站點上都存儲了一個有意義維護用戶意圖的操作序列，方便用戶撤銷目標操作及關于目標操作的子結構，而不影響其他沒有任何關系的操作.

3 在3D協作系統下設計操作聚合結構

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

3.1 DOAG的簡單介紹

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

定義1.因果順序關系"→".任意兩個操作Oa和Ob,如果Oa因于Ob之前，表示為Oa→Ob,則Oa創建的相應拓撲實體由Ob引用.

定義2.因果維護"→".任意兩個操作Oa和Ob,如果因于Ob之前，表示為Oa→Ob，則在任意站點上Oa總是在Ob之前執行.

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

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

定義5.意圖維護.一個模型操作O的意圖能夠得到保存當且僅當1)為了幾何目的與O相關的sub-DOAG不會改變或者存在CAD模型對應的DOAG.2)與O相關的每個sub-DOAG對應的拓撲實體一定存在.

一個頂點V被定義為五元組,其形式如下.，type表示操作類型，timestamp表示為所有協作站點上操作的執行順序統一自動生成的整數，reference_dependency表示與頂點Vi有相關依賴關系的代表操作的一組頂點(v1,v2,…,vn)，attribute_dependency表示與頂點Vi有屬性依賴關系的代表操作的一組頂點(v1,v2,…,vn).

DOAG是一種樹狀的數據結構，用來表示操作之間的聚合關系，在協作設計過程中很多操作具有很多依賴關系，將這些因依賴關系聚合在一起的操作構成的模型稱為子結構.一個復雜的CAD模型可以分解為很多子結構.

在一個協作CAD系統中創建的CAD模型是以一個原始模型操作而開始創建的，而這個原始模型操作的依賴集在整個模型中是最大的，這個操作所構成的模型在DOAG中相當于中心點Vcentral，檢索在與當前中心點的有引用依賴和屬性依賴的操作，每個操作作為子DOAG的中心點被自動識別為連接到Vcentral.中心點按操作的時間戳來排序的，這樣整個操作序列都是連貫的，如果要檢索某個節點的依賴集及構成的子結構，我們進行了如下總結：

1) DOAG是一種描述復雜CAD模型的樹型結構，其根節點對應協同站點上的開始的操作，在檢索這個操作的所有DOS，所構成的模型就是一個子結構，當某個子結構不滿足用戶意愿時，可以再進行分解，構成用戶想要的子結構，而不會影響沒有任何依賴關系的操作及操作集構成的子結構，每個子結構和操作都由節點和葉子節點保存著；DOAG的根節點和每個中間節點使用基對象指針指向代表該復雜子結構的基特征的節點，并且保存了其代表的復雜子結構分解生成的子結構對應的節點集，子節點使用基對象指針指向代表該原子結構的定位特征的節點.圖3中用虛線圈的操作可以構成一個子結構.

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

3.2 特征模型操作表示

可以用下面的結構表示一個特征操作構成的子結構：

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

通過上面兩個類，通過執行第1個類可以獲得所有操作的操作集，第2個類可以幫助找到目標操作.

4 在復制式協同系統下的Undo/Redo方法

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

1) SVi=SVj當且僅當SVi中的值與SVj中相應的值相等;

2) SVi

3) SVi>SVj，當且僅當SVi中的值大于SVj中的值.

任何操作生成時或傳到其他站點時都會攜帶自身的狀態向量，當SVi≤SVj時，i站點上的操作優先執行，通過采用一種樂觀的序列化并發控制方法實現了目標的保存.在很多協同系統中，為了維護用戶意圖的一致性和收斂性，都采用了狀態向量來解決出現的并發問題[24,25].

當要撤銷一個操作時，在協同CAD環境中實現Undo/Redo方法需要考慮到操作之間的依賴關系，結合上面提出的DOAG，我們很快檢索到任意操作所攜帶的子結構，首先要檢查相應的操作所帶的DOS構成的子結構，然后，所有依賴于撤銷目標的操作都應該全部撤銷，并且不會影響其他操作.

當一個撤銷命令被發布時，它的意圖是將已經做過的操作進行撤銷掉，而不影響其他操作，需要包括：

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

2)成功地將撤銷目標和依賴于它的操作的效果一起撤銷，而不影響其他的子結構.

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

4.1 確定Undo/Redo目標

當某一個有意義的操作序列在站點i上依次執行，當傳到其他站點時，出現操作順序和站點i上的不一致，要通過局部Undo/Redo來調整操作順序，維護用戶意圖.由于網絡延時和基于狀態向量上的因果關系，在每個協作站點上的歷史操作都有以下特點：

1)來自同一站點上的操作在所有站點上都以相同的順序執行.

2)來自不同協作站點上的模型操作都是交叉的和在不同的站點以不同的順序執行.

因為用戶要撤銷的目標對象不可能永遠是最后一個，當定位到要撤銷的目標時，首先要考慮到兩種情況：

1)定位到本地站點的撤銷對象；

2)定位遠程站點的撤銷目標對象.

一個建模操作在生成過后在相應的站點會立即執行，所以撤銷的目標操作只存在本地站點上的執行列表中.

在一個協作CAD的原型系統中，有N個站點，Ai,j(0

當一個任意的遠程的站點Sj收到Undo要求，這個要撤銷的對象可能不是最后一個執行的操作，所以它要撤銷的目標操作可能在ExecutedListj和WaitListj中，為了找到要撤銷的目標，就要采用SiteId和StateVector,任意站點發送的操作都會攜帶狀態向量信息，當撤銷命令發送到其他站點時，首先在ExecutedListj搜索，然后在WaitListj中搜索，直至找到要撤銷的目標.

當找到要撤銷的目標時，由于每個站點都存儲了整個操作所構成的DOAG，當要撤銷的目標在DOAG中進行遍歷時，就會找到相應的該操作所攜帶的子DOAG，并和該操作一并撤銷掉，并且不影響其他的操作所構成的模型結構，當對撤銷的操作進行重做時，對它本身所攜帶的子DOAG進行重做，重構整個邊界模型.對于在本地站點和遠程站點的撤銷目標的處理，我們設計了如下幾個算法：

算法1.對于如何獲得撤銷目標的子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中原始的根節點，將其設為中心點Vcentral，再檢索與當前中心點的有引用依賴和屬性依賴關系的操作，將其存儲到每個中心點的DOAG中，每個操作作為子DOAG的中心點被自動識別為連接到Vcentral，依次往下遍歷所有的操作節點，直到所有操作遍歷完為止.

算法2.在協同站點上的選擇性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;

該算法從根節點進行出發開始遍歷，通過遍歷不同的子結構，找到目標操作及目標操作的子DOAG進行撤銷，撤消目標操作后對所剩的邊界模型進行重構.

算法3.在協同站點上的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的命令的目的是消除又重做某個特征，當用戶要撤銷已經做過的操作及該操作構成的子結構時，又要對撤銷的目標對象進行重做，通過獲得撤銷操作的DOAG再更新一個新的DOAG子結構來滿足用戶意圖，對更新后的DOAG子結構進行重做而不會影響其他的操作所構成的邊界模型.

5 算法正確性證明

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

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

證明：來自同一站點上的操作在所有站點上都是以相同順序執行，所以(SiteID,Create_SEQ)能用來準確地標識要undo的目標，假如O是要撤銷的目標操作，根據我們的算法，通過DOAG，遍歷所有的操作，找到要撤銷的目標操作及目標操作的sub-DOAG,所以在整個DOAG中就沒有O及O的sub-DOAG的影響.當redo命令喚起時，撤銷的目標操作O及O的sub-DOAG被標識，再次重做.所以redo意圖得到了維護.

論點1.執行過的操作都遵循因果關系.

證明：為了證明這個論點，我們只需要證明一個新來的模型操作的執行不會違背已經建立好的因果關系.

舉DOAG{sub-DOAG1(O1),sub-DOAG2(Oi)...sub-DOAG(On)為一個例子，它相應的歷史緩存為HB={O0,O1,O2,...On},假設已經執行過的操作都遵循因果關系，On+1是收到的最新的操作，如果On+1的執行不違背已經執行過的操作的操作順序，那么On+1立即執行，On+1的執行不會對DOAG有影響.如果違背了相關的CAD模型的DOAG，然后通過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的相應的子結構.

首先，On+1的執行不會違背O0到Oi-1的因果順序，第二，On+1依賴{O0...Oi-1}中的一些操作，因為On+1是在它們之后而又獲得sub-DOAG(On+1)之前喚起的，因此，On+1執行的因果維護得到了滿足，第三On+1與{Oi,...,On}中的操作沒有因果關系.所以它們是可以交換的，在{Oi,...On}之前喚起On+1不會違背因果關系，所以，論點1被證明是成立的.

論點2.我們的選擇性Undo/Redo算法不會違背建立好的因果順序.

證明：當要撤銷一些操作，為了可以看到撤銷目標操作過后的結果，主要需要兩步：獲得O執行時的模型狀態并重新評估撤銷目標操作及目標操作的子結構后的部分模型.

第一步，通過遍歷DOAG獲得撤銷目標之前的模型狀態，所以在撤銷目標操作O之前執行過的操作都滿足因果依賴關系.第二步，重構剩下的沒有任何關系的子結構模型，撤銷完目標操作后，此時將DOAG中目標操作及目標操作構成的子結構設為無效，其他的操作及相應的子結狀態保持不變.

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

證明：根據論點1和論點2，選擇性Undo/Redo的執行不會違背已設計好的DOAG，所以因果維護性質得到滿足.

定理3.通過選擇性Undo/Redo算法，模型一致性得到維護.

證明：通過正式的正確性標準和定理1和定理2，執行選擇性Udo/Redo能維護所有站點上模型的一致性.

5.1 實例分析

對同一模型，用戶在不同的站點有不同的操作順序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是屬性依賴，用戶設計的DOAG如圖4所示，每個站點的執行順序必須嚴格按照設計的DOAG來安排操作順序.

每個站點上都保存DOAG，當用戶要撤銷相應的操作時，通過DOAG能夠快速地找到目標操作的子結構一起撤銷，再重新調整操作順序，滿足用戶意圖.

圖4 簡單模型的DOAG圖 Fig.4 DOAG for the simple model

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

圖5 協同建模過程的例子Fig.5 Example of the collaborative modeling process

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

5.2 實驗結果討論

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

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

圖8 每個站點上簡單模型的關系圖Fig.8 Simple model at each site after the collaborative modeling process

6 結 論

我們在復制的協同三維建模系統中提出了選擇性多用戶的Undo/Redo方法.通過Site ID和Lamport 狀態向量在本地站點和遠程站點上標識要Undo/Redo的目標操作，通過Undo/Redo來實現維護用戶設計意圖.摘要提出在設計操作聚合結構圖的輔助下，詳細地說明了操作之間的關系.通過這種方式，依賴于撤銷目標的子結構很容易的獲得，并且也將消除目標操作而不影響其他沒有任何關系的操作或子結構，對撤銷后的子結構重做來維護用戶的設計意圖，使得最后模型的一致性得到了維護.最后，我們的算法的正確性得到了驗證，并在我們構建的原型中執行了實驗.

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

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