Photoshop Undo System

Question

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

G

Why close? Is this a dupe or something? Closing should be followed by comments – Interfluve

Have a look at this SO thread. – Unscrupulous

Answer 1

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.

Pollak

Answer 2

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.

Interfluve

I've implemented this in a WYSIWYG editor. It seems impossible at first, but once youg grasp the pattern, it's really pretty easy. – Anvil

That's my same experience, I thought it was never going to work, and that there had to be a secret ingridient, but once I finished it just worked :) – Interfluve

Actually, the current version is only existing version and the command history is actually a list of reversed commands. At least that's how a word processor would do it. – Gamba

for a word processor or any editor I think you are right, but when you click revert to original photoshop is too fast, and it's not accessing the HD (I think) so I imagine it's caches as an optimization – Interfluve

Unapplying a transformation may not always be possible, for example, how do you unapply a blur? The information is just lost and is not recoverable. – Unscrupulous

Answer 3

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.

Kharkov

Also Photoshop uses the hard disk for undo information, so no additional memory requirements there. – Lariat

Answer 4

I'm not sure how Adobe Photoshop implements undo, but the Paint node within Apple Shake compositing application is pretty easy to explain:

• Each stoke is stored as a series of points, along with some information like stroke-color, brush-size etc.
• When you draw a stoke, the changes are made on the current image.
• Every x strokes (10 I think) the current image is cached into memory.
• When you undo, it redraws the last ~9 stokes on the previous cached image.

There are two problems with this:

• When you undo more than 10 times, it has to recalculate the whole image. With thousands of strokes this can cause a several second pause.
• With Shake, you save the setup file, containing the stroke information - not the actual pixel values. Then means you have to recalculate the whole image whenever you reopen the Paint node, or render the image (not nearly as big a problem as the undo thing, however).

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).

Tacklind

Answer 5

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

Standard

This question is about implementation details. – Carpo