The question probably applies to drawing systems in general. I was wondering how the undo functionality is implemented in PS. Does the program take snapshots of the canvas before each operation? If so, wouldn't this lead to huge memory requirements? I've looked into the Command pattern, but I can't quite see how this would be applied to drawing.
Regards, Menno
It's called the command pattern. It's simple to implement as useful for any sort of editor.
Photoshop applies stacked transformations upon the original image. One opetation one command. It simply unapplies the transformation when you undo. So it just keeps the original and latest versions, but I guess it might cache the last few versions just for performance.
Since some operations will be non-reversable and as you say snapshoting the entire image every time would be out of the question then the only other alternative I can see would be a stack of deltas. A delta being the set of masks containing the modified pixels prior to the operation. Of course many operations may be reversable so their deltas could be optimised.
I'm not sure how Adobe Photoshop implements undo, but the Paint node within Apple Shake compositing application is pretty easy to explain:
x strokes (10 I think) the current image is cached into memory.There are two problems with this:
Well, there is a third problem, that being Shake is horribly buggy and poorly implemented in many areas, the Paint node beign one of them - so I'm not sure how good an implementation this is, but I can't imagine Photoshop being too dissimilar (albeit far better optimised).
The easiest way I've found to solve this problem, though I don't know how Adobe tackles it, is to use a persistent data structure, like so:
You think of an image as a collection of image tiles, say 64x64 pixels each, and they get garbage collected or reference counted (ex: using shared_ptr in C++).
Now when the user makes changes to an image tile, you create a new version while shallow copying the unmodified tiles:
Everything except those dark tiles are shallow copied upon such a change. And when you do it that way, your entire undo system boils down to this:
before user operation:
store current image in undo stack
on undo/redo:
swap image at top of undo stack with current image
And it becomes super easy like that without requiring the entire image to be stored over and over in each undo entry. As a bonus when users copy and paste layers, it barely takes any more memory unless/until they make changes to that pasted layer. It basically provides you an instancing system for images. As yet another bonus, when a user creates a transparent layer that's, say, 2000x2000 pixels but they only paint a little bit of the image, like say just 100x100 pixels, that also barely takes any memory because the empty/transparent tiles don't have to store any pixels, only a couple of null pointers. It also speeds up compositing with such mostly-transparent layers, because you don't have to alpha blend the empty image tiles and can just skip over them. It also speeds up image filters in those cases as well since they can likewise just skip over the empty tiles.
As for PS actions, that's a bit of a different approach. There you might use some scripting to indicate what actions to perform, but you can couple it with the above to efficiently cache only modified portions of the image. The whole point of this approach is to avoid having to deep copy the entirety of the image over and over and blow up memory usage to cache previous states of an image for undoing without having to fiddle with writing separate undo/redo logic for all kinds of different operations that could occur.
Photoshop uses History to track their actions. These also serve as Undo as you can go back in history at any point. You can set the size of history in preferences.
I also suggest you look into Adobe Version Cue as a tool for retrospect undo or versions, it's built into the suite for that sole purpose. http://en.wikipedia.org/wiki/Adobe_Version_Cue
