3D协作系统下基于DOAG的选择性Undo/Redo研究

2019-03-13高丽萍刘珊珊

小型微型计算机系统 2019年3期

高丽萍，刘珊珊

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来实现维护用户设计意图.摘要提出在设计操作聚合结构图的辅助下，详细地说明了操作之间的关系.通过这种方式，依赖于撤销目标的子结构很容易的获得，并且也将消除目标操作而不影响其他没有任何关系的操作或子结构，对撤销后的子结构重做来维护用户的设计意图，使得最后模型的一致性得到了维护.最后，我们的算法的正确性得到了验证，并在我们构建的原型中执行了实验.