注意！挑战全国所有图形图像开发专家：请简述图形图像处理软件里的Undo、Redo技术的实现方法和思想！
挑战全国所有图形图像开发专家：请简述图形图像处理软件里的Undo、Redo技术的实现方法和思想！
请全国所有在图形图像处理软件开发领域有经验、有技术的高手畅所欲言、高谈阔论，我将有更多高分奉送！
这个问题我将也在Experts Exchange论坛提出，到时中外编程高手来一次大比拼，看看到底是老外凶，还是国人更猛！
问题点数：300、回复次数：63Top
1 楼wuxfBrave（老婆,别打我,下班就回家）回复于 2000-10-20 23:33:00 得分 5
use stack,save last change in orderTop
2 楼breath（跨马倚斜桥，满楼红袖招）回复于 2000-10-21 00:11:00 得分 10
数据保存在链表中
删除时不delete对象，而是转移的Undo链表中
当Redo时候再复制到Redo链表中一份Top
3 楼tchaikov（）回复于 2000-10-21 01:55:00 得分 100
数据链表应该不是什么难题，关键是如何存放历史数据。
首先要区分图形和图象。
图形（矢量的）数据量比较小，每个链结点存放整个图形即可。
图象则数据量比较大，可以参考AUTODESK公司的FLIC文件的存放格式进行存放，将每次变化部分保存下来，由于需要做UNDO和REDO两部分工作，因此最好建两个链表，分别保存每个操作后的图象的前一次和后一次的改变部分。如果只建一个方向，虽然也可以，但不论怎么样，REDO和UNDO中总有一个需要从最前面（或者最后面）的那次操作开始，逐次计算，这样会影响速度。
FLIC文件的压缩方法比较简单，压缩比不是太高，但还原很快，而且没有失真。当然只是作为参考的一种方法而已，毕竟需要处理的图象的颜色数目不是固定的。
具体格式很多书中都有介绍。
很多图象处理软件只能进行一次UNDO和REDO，如果做成那样，你也不用讨论了。
仅供参考！Top
4 楼Mercedes（）回复于 2000-10-21 09:15:00 得分 5
记录下用户的每次操作，要UNDO时，反向操作即可。Top
5 楼NiceFeather（EDA Router）回复于 2000-10-21 13:27:00 得分 0
谢谢大家，请继续踊跃发言！Top
6 楼cproom（cproom）回复于 2000-10-21 18:08:00 得分 10
可以将每次操作前的图象保存下来以便恢复，如果占用内存太多，可以使用临时文件。Top
7 楼andygood（）回复于 2000-10-21 19:57:00 得分 10
最简单的办法就是使用Keith Rule的CUndo类（www.codeguru.com or www.codeproject.com）。如果你使用Doc/View结构的话保证5分钟搞定，而你根本不需要知道原理。
当然快的方法也有缺陷，他的方法的缺陷就是把历史纪录都存在内存里，这就限制了undo的次数。你可以引入一个cache管理机制，估计一天到两天时间可以搞定。
不管黑猫白猫，能抓老鼠的就是好猫。根据具体的需要确定具体的实现方法就行了。
Top
8 楼andygood（）回复于 2000-10-21 20:15:00 得分 0
最简单的方法就是使用Keith Rule的CUndo类（www.codeguru.com or www.codeproject.com）。只要你的程序使用Doc/View结构的话，保证可以在5分钟内搞定，而你根本不需知道它的原理。
当然快的方法也有它的缺陷。这个类库的缺陷在于它把所有history都存在内存里，这就限制了undo的次数。你可以试着加入cache管理机制，估计一天到两天就可以搞定。
不管黑猫白猫，能抓到老鼠的就是好猫。根据具体需要确定实现方案就可以了。
Top
9 楼wolfman（浪人）回复于 2000-10-21 20:57:00 得分 10
对于矢量图，自然定义正向/逆向操作是比较省事的，也是自然的。但这种操作是很难定义的，这也是计算机图形学中的一个难题。比如裁剪、消隐（3D）等。
对于光栅图，我以为保存（lock）现场是行之有效的办法：安全、可靠、直观。存储空间是它的主要问题，但这个问题的解决却不如前者困难。
Top
10 楼vcbeginner（vcbeginner）回复于 2000-10-22 17:46:00 得分 5
store change,load change, just so so.Top
11 楼hboy（心血来潮）回复于 2000-10-22 19:20:00 得分 5
我做过，而且还是三维图形，数据量很大，可能你要用到临时文件，避免占用大量的内存，速度可能会慢点，但很安全Top
12 楼SCUM（人渣）回复于 2000-10-22 20:07:00 得分 5
photoshop 算不错了，临时文件那么大，一猜就知道它的 UNdo/REdo 大概是怎么搞的了。Top
13 楼WorldCreater（造化天尊）回复于 2000-10-23 01:16:00 得分 0
listenTop
14 楼WorldCreater（造化天尊）回复于 2000-10-23 01:21:00 得分 0
listenTop
15 楼WorldCreater（造化天尊）回复于 2000-10-23 01:30:00 得分 0
listenTop
16 楼WorldCreater（造化天尊）回复于 2000-10-23 04:49:00 得分 0
听听Top
17 楼alwayscy（大力水手）回复于 2000-10-23 08:38:00 得分 15
我认为，每项操作大抵都应该是以一定的参数调用函数。
记录下每次调用的函数及参数，如果能以另外参数再调用函数达到UNDO则好；否则再编一个“反函数”达到该效果。
这样REDO和UNDO都可以实现。Top
18 楼flyingpetrel（陇亩民）回复于 2000-10-23 08:56:00 得分 10
定义一个图形和图象的状态关系图，描述图象可能存在的状态属性，并且定义相邻状态互相变迁的原子操作（函数和过程），然后根据状态关系图的状态变迁规则调用相应的原子操作进行Redo或Undo，应该可以实现。另外，可以采用树的方式维持历史状态及子状态。具体可以参考状态机的思路，但不完全一样，以上所述，供诸位参考。Top
19 楼wang_xiao_jian（崦嵫）回复于 2000-10-23 09:13:00 得分 5
实现undo和redo并不难，不过如何提高效率，既能很快刷新，又少占内存，值得探讨。Top
20 楼andygood（）回复于 2000-10-23 11:51:00 得分 5
这也不是什么太难的问题，值得这么兴师动众吗？关键是看数据量的大小以及你允许的undo次数。至于内存/虚拟内存的管理几乎就是一些if语句嘛。何必搞那么复杂呢。
Top
21 楼DDKProgrammer（好人）回复于 2000-10-23 11:53:00 得分 0
!Top
22 楼DDKProgrammer（好人）回复于 2000-10-23 11:55:00 得分 0
23 楼DDKProgrammer（好人）回复于 2000-10-23 12:03:00 得分 0
想看看回复，只有6条，显示有35个了。Top
24 楼andygood（）回复于 2000-10-23 12:14:00 得分 0
这也不是什么太难的问题，值得这么兴师动众吗？关键是看数据量的大小以及你允许的undo次数。至于内存/虚拟内存的管理几乎就是一些if语句嘛。何必搞那么复杂呢。
Top
25 楼tchaikov（）回复于 2000-10-23 14:51:00 得分 0
关注。Top
26 楼wuxin（wuxin）回复于 2000-10-23 22:23:00 得分 40
我同意wang_xiao_jian的观点。实现undo和redo并不难，堆栈、虚拟内存等都不是问题的关键，难点是如何提高效率。
用过word的人都知道，word可以实现无限次undo。有一次我敲完一篇文档，发现undo框里有1000多项。文档的大小是500k，如果采用保存现场的方法，至少需要500M内存!!!!!!! 显然微软采用了某种优化方法。
我的想法是对各种不同的操作使用不同的undo算法，使保存的数据量最小。举例如下：
1. 对一些画点画线的操作，可以记录下每次的操作类型和被改变的像素点及一些关键数据，如点的坐标和线的起始位置等。
2.对一些处理操作，如移动等，可以保存移动前后的位置。
3.对颜色反转等可逆运算，可以保存操作步骤，undo时用逆运算恢复。
4.对一些不可逆运算，如模糊、锐化等，可以保存一些关键点，使操作可逆。
在保存过程中，可以采用一些压缩算法，尽量减少数据量。最终结果是在数据量、效率、复杂度间取一个折衷。
以上仅一些不成熟的想法，望大家指正。Top
27 楼tchaikov（）回复于 2000-10-24 00:34:00 得分 0
和wuxin探讨：
其实你只要了解 一下FLIC文件的结构，就可以知道用类似的方法可以用很少的数据区存放很多步操作的。同时为什么选择这种格式，主要是要考虑两方面，一是绝对不能是有损压缩，二是压缩/还原速度要快。
你提出的各种方式区别对待，固然可行，但如果操作者不停的用“喷枪”效果，该怎么办？
Top
28 楼actinia（海葵）回复于 2000-10-24 02:50:00 得分 0
关注！Top
29 楼actinia（海葵）回复于 2000-10-24 02:52:00 得分 0
关注！Top
30 楼onion（葱头）回复于 2000-10-24 07:38:00 得分 5
我只对位图懂一点，我自己是通过栈实现的。不过我读过的一本图象处理的编程书，他也是
通过栈实现的。我也觉得没必要搞的这么复杂。Top
31 楼Searph（ViK.Lee）回复于 2000-10-24 08:25:00 得分 5
我记得这个问题在<<电脑编程与维护>>有说，查一下，去年和今年上半年的。
BTW:有人知道深圳哪儿有卖这本杂志的么？Top
32 楼lhztco99（环保概念股）回复于 2000-10-24 13:10:00 得分 0
看来WuXin是高手，比较有条理。
不错不错。其余的嘛.....Top
33 楼lhztco99（环保概念股）回复于 2000-10-24 13:12:00 得分 0
看来WuXin是高手，比较有条理。
不错不错。其余的嘛.....
至于有人提到的 Flic 文件，有没有搞错....Top
34 楼dingsg（丁丁）回复于 2000-10-24 13:53:00 得分 10
首先对用户的操作进行分类;
设定相应的ID,然后分类存放在列表或栈中;
要UNDO,REDO时，依次对照相应的处理,进行即可!
....
丁丁Top
35 楼dingsg（丁丁）回复于 2000-10-24 14:12:00 得分 0
首先对用户的操作进行分类;
设定相应的ID,然后分类存放在列表或栈中;
要UNDO,REDO时，依次对照相应的处理,进行即可!
....
丁丁Top
36 楼LiangFomu（Phourm）回复于 2000-10-24 17:01:00 得分 30
我刚刚完成一个图像处理的DLL,不过我们不要求Undo和Redo,但我想过.
可以用牺牲CPU的时间来换取内存(实际上要多个Undo,Redo你不可能全部用内存来保存每一个操作的图像全部信息),操作大概可以分两种:可循环和不可循环.
1 可循环指图像可以用某一操作回到上一操作状态(如:反色)只要执行逆操作即可.
2 不可循环指不可恢复操作(如:变成灰度图)就麻烦点了,就从头开始恢复吧.
你至少要为你的图像开辟两个内存空间一个用于保存当前值另一个为原始值.选用链表或其它的数据结构保存你的每一步操作(只作操作的描述 如:这步是缩小从1024*768到800*600),如果是情况2从原始图像开始一步一步根据操作描述顺序完成操作到Undo(或Redo)那步(就好像用户从原图开始重新来一遍),情况1很简单不说了!
要是你不怕内存消耗太大在若干步后(如:20步)或执行情况2之前保存一个图像,这样恢复时执行步骤就少多了,就看你如何调节CPU与内存的矛盾了!Top
37 楼NiceFeather（EDA Router）回复于 2000-10-24 21:59:00 得分 0
这个问题我已在Experts Exchange论坛提出，地址为：
http://www.experts-exchange.com/Computers/Graphics/Q_11644098.html
欢迎喜欢e文的朋友去那里发表发表意见，让老外也瞧瞧咱中国人的厉害！Top
38 楼smartkid（）回复于 2000-10-24 23:43:00 得分 5
use the Command Pattern that described in 《Design Patterns》Top
39 楼prefix（MtSC）回复于 2000-10-27 15:46:00 得分 5
老兄，你不是会vc吗？方法是一样的啦！Top
40 楼NiceFeather（EDA Router）回复于 2000-10-27 22:26:00 得分 0
这个问题，大家可去看以下几篇文章和示例进行参考：(Undo/Redo方向）
http://www.csdn.net/dev/Visual%20C++/source%20code/Misc/multiundoredo.shtml.htm
http://www.csdn.net/dev/Visual%20C++/source%20code/Misc/undo_manager.shtml.htm
http://www.csdn.net/dev/Visual%20C++/source%20code/Misc/undo_redo_cdocument.shtml.htmTop
41 楼NiceFeather（EDA Router）回复于 2000-10-27 22:56:00 得分 0
更正一下Experts Exchange论坛此问题的地址：
http://www.experts-exchange.com/Computers/Programming/Q_11679938.html
欢迎去发表高见！Top
42 楼NiceFeather（EDA Router）回复于 2000-11-07 21:49:00 得分 0
请高手继续高谈阔论、畅所欲言！Top
43 楼NiceFeather（EDA Router）回复于 2000-11-23 09:02:00 得分 0
谢谢大家的讨论，使我获益匪浅！Top