CAX系统中智能Undo/Redo操作的研究

CAX系统中,对于复杂操作和关联操作,现有Undo/Redo机制很难保证Undo/Redo操作语义一致性,避免破坏图形数据,从而导致实现具体的Undo和Redo方法困难、二次开发难度大的问题。分析了CAX复杂操作和关联操作的特点,讨论了Undo操作中事务的原子性和一致性以及触发器机制,提出了基于事务保证操作语义一致性和基于触发器机制降低操作复杂度和关联度的解决策略,描述了具体的执行流程及主要算法。在大型CAD软件开发中实例分析证明了该方法的有效性。     

基于对象的Any Undo策略

Undo是基于对象的协同图形编辑系统的重要功能,可用于误操作的恢复。Undo的实现极具挑战性,因为分布协同环境下操作具有并发性,Undo的实现与一致性维护密切相关。提出的基于对象的Any Undo策略从操作语意的角度探讨了Undo操作的一致性维护,并给出了具体的实现机制。给出的支持机制都得到了实例证明,其可行性也在原型系统CoDraftPaint中得到初步验证。     

基于图形编辑的实时协同设计系统中的同步性问题研究

基于图形编辑的实时协同设计系统允许多个用户同步地对同一图形文档进行编辑,由此产生了不同步、执行顺序冲突、意图冲突等同步性问题。该文对实时协同设计过程中的这个同步性问题的产生原因和表现形式进行了分析,同时提出了较为完善的解决方案,通过采用状态矢量算法、历史记录法等方法保证了系统中操作的同步性。该文还通过与其他解决方案的对比,验证了该文所提出的方案的有效性。     

基于版本复制的版本存储技术研究

协同图形编辑系统中采用基于版本复制的多版本技术解决编辑过程中冲突操作的意愿保证问题．每个版本存储了在此版本上执行的所有操作,因此存在同一操作被多次存储和版本存储量随编辑过程大规模增加的情况。本文讨论了协同图形编辑系统中基于版本复制的版本存储技术,并给出了一个改进的版本存储模型。     

实时协同图形编辑系统中的对象版本管理

基于对象复制的多版本策略是实时协同图形编辑系统实现意愿保证的有效手段,多版本管理是其中的关键问题之一.本文从操作的Do、Undo/Redo出发,在总结已有研究成果的基础上,提出一个全新的对象版本管理框架,并对其中涉及的算法和机制做了深入分析.     

AutoCAD讲座：第六讲 编辑命令（EDIT）

一、选择集（Selectionset）一条图形编辑命令通常包含两部分内容：目标选择和图形编辑。目标选择是在已有的图形中选择一个或一组图形实体作为编辑操作的目标，这些目标应该是屏幕内可见的实体。被选中的目标构成选择集。图形编辑就是对选择集执行指定的图形编辑操作。对于每条图形编辑命令来说，构造选择集是一个共性的问题。为了操作方便，Allt。CAD提供了多种选取目标的方式，供用户选用。在输入～条编辑命令之后，Allt。CAD通常出现下列提示：Selectobjects：（选取目标）这条提示信息，要求用户从已有图形中选取待编辑的目标组成…     

基于操作转换的并发控制算法的研究

为解决协同图形编辑中出现的结果不一致、因果不一致、操作意愿不一致和语意不一致问题,提出一种基于操作转换的并发控制算法。该算法定义了操作序列的上下文有序、操作序列的上下文并发等概念。从协同编辑操作的预处理及实际执行时的操作转换两个方面,对基于上下文的操作转换(COT)算法进行改进,并进行实例验证分析。研究发现,其可有效地减少COT算法中存在的操作转换冗余的问题。     

协同图形编辑系统设计与实现

给出了基于图形对象的协同编辑系统的操作冲突／相容关系及其基于逻辑时间钟的检测方法和一致性保证算法。在此基础上，讨论了一个实时协同图形编辑系统的设计方面有关的关键技术。实验结果表明，该方法是可行和有效的。     

协同图形编辑系统中改进的多版本技术

基于版本复制的多版本技术采用全复制的系统结构实现协同图形编辑系统中冲突操作的意愿保证问题.每个版本存储了编辑过程中所有在此版本上执行过的操作,故存在同一操作被存储多次和操作存储量随编辑过程的继续出现大规模增加的情况.本文从冲突操作集合着手,提出了一种改进的多版本技术,通过理论证明和模拟实验结果表明这种改进的多版本技术能有效地克服以上问题.     

基于多版本的对象标识与垃圾收集算法

研究与设计全复制结构的实时协同编辑系统的关键问题之一是多个复制数据视图的一致性 ,其中操作意愿保证是一致性维护的根本 .分析了基于多版本的对象标识问题 ,提出一个对象标识模型 ,并针对多版本环境对冲突定义进行了修改 ;采用操作列表 OL取代历史缓冲区 HB,维护对象版本上执行过的所有操作 ,并进一步分析了操作列表的垃圾收集算法 .本文提出的算法都得到实例验证     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

A structure for efficient update,incremental redisplay and undo in graphical editors

The design of a graphical editor requires a solution to a number of problems, including how to (1) support incremental redisplay, (2) control the granularity of display updates, (3) provide efficient access and modification to the underlying data structure, (4) handle multiple views of the same data and (5) support Undo operations. It is most important that these problems be solved without sacrificing program modularity. A new data structure, called an ItemList, provides a solution to these problems. ItemLists maintain both multiple views and multiple versions of data to simplify Undo operations and to support incremental display updates. The implementation of ItemLists is described and the use of ItemLists to create graphical editors is presented.     

Domain-specific application analysis for customized instruction identification

With the increasing importance of Application Domain Specific Processor (ADSP) design, a significant challenge is to identify special-purpose operations for implementation as a customized instruction. While many methodologies have been proposed for this purpose, they all work for a single algorithm chosen from the target application domain. Such algorithm-specific approaches are not suitable for designing instruction sets applicable to a whole family of related algorithms. For an entire range of related algorithms, this paper develops a methodology for identifying compound operations, as a basis for designing “domain-specific” Instruction Set Architectures (ISAs) that can efficiently run most of the algorithms in a given domain. Our methodology combines three different static analysis techniques to identify instruction sequences common to several related algorithms: identification of (non-branching) instruction sequences that occur commonly across the algorithms; identification of instruction sequences nested within iterative constructs that are thus executed frequently; and identification of commonly-occurring instruction sequences that span basic blocks. Choosing different combinations of these results enables us to design domain-specific special operations with different desired characteristics, such as performance or suitability as a library function. To demonstrate our approach, case studies are carried out for a family of thirteen string matching algorithms. Finally, the validity of our static analysis results is confirmed through independent dynamic analysis experiments and performance improvement measurements.     

A group Undo/Redo method in 3D collaborative modeling systems with performance evaluation

Undo/Redo is an indispensable function in 3D collaborative modeling systems where a single mistake conducted by one user is propagated to all participants. Both intention preservation and consistency maintenance should be satisfied when applying group Undo/Redo. Besides, fast local responsiveness and timely group awareness are accepted performance metrics in interactive systems. In this paper, we contribute a novel group Undo/Redo mechanism for 3D collaborative modeling systems to support the “any time, any where” Undo/Redo. Response time will be shortened noticeably with a Model State Stream kept on each collaborative site. In the case of concurrent Undo/Redo, an Undo State Vector is proposed to ensure the Undo/Redo intention preservation and model consistency maintenance. Furthermore, the paper studies the performance of the algorithm including the worst, best and average cases with theoretical analyses. Our experiments show that responsive time is actually depending on a number of factors such as size of the history buffer, execution time for a single modeling operation.     

利用排序对遗传算法的改进和自适应交叉概率

作为一种并行、自适应,全局搜索方法,遗传算法已在多种领域得到应用。文中先简单介绍了遗传算法的发展、基本程序与几种遗传操作,然后详细说明了排序选择。在此基础上文中提出了在非线性排序中加入适应值信息和交叉前进行排序两种改进方法。为了减少近新遗传,文中还设计了一种自适应交叉概率。实验中选择具有不同特点的四个测试函数进行测试,寻优结果表明改进的算法对加快收敛速度,提高寻优效果起到了作用。     

基于双种群模糊引力搜索算法的舰载机甲板作业调度

舰载机甲板作业调度问题是一类具有NP-hard特性的资源受限多项目调度问题.首先,分析舰载机甲板作业调度问题的工序流程约束和各类资源约束,构建舰载机甲板作业调度混合整数规划模型.然后,基于基本引力搜索算法,提出双种群模糊引力搜索算法用于模型求解.算法采用基于作业时序修正的优先数编码,并采用双种群交替迭代结构,将基于个体的双向对齐技术扩展到种群层面,基于串行调度生成机制产生调度方案.为了提高算法性能,采用边界修正策略修正越界粒子编码,在引力计算阶段,采用模糊逻辑控制策略进行参数自适应控制.最后,通过案例仿真和算法对比验证了双种群模糊引力搜索算法的有效性,所提出的算法适合求解大规模的舰载机甲板作业调度问题.     

A contour processing method for fast binary neighbourhood operations

In this paper new fast algorithms for erosion dilation, propagation and skeletonization are presented. The key principle of the algorithms is to process object contours. A queue is implemented to store the contours in each iteration for the next iteration. The contours can be passed from one operation to another as well. Contour filling and object labelling become available by minor modifications of the basic operations. The time complexity of the algoriths is linear with the number of contour elements to be processed. The algorithms prove to be faster than any other known algorithm.     

可动态生成具有优先级工序集的动态Job-Shop调度算法

为了在满足约束条件的前提下使不同时刻加入到作业集合中的全部作业所用的加工总时间尽可能地少,提出算法:根据动态的作业集合构造虚拟加工树,虚拟加工树上的叶结点代表最先加工的工序,虚拟根节点代表最后一道工序,边代表偏序关系;以层优先为虚拟加工树上的工序设置优先级,工序的优先级可作为调度过程中考虑的一个因素;除了在工序需要动态调整的情况下,在调度过程中始终遵循着机器忙原则.在调度过程中,首先根据虚拟加工树动态地生成备选工序集合,然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序,直到备选集合为空,即所有作业加工完毕.这里提到的调度策略包括短用时策略、长路径策略和动态调整策略.通过实例验证,该算法对于动态Job-Shop问题可以获得比较好的解.