Fast undo/redo for bitmap editor when memory is limited?

Question

I'm trying to write a bitmap editor for a mobile device (i.e. a limited version of Photoshop). The user's document consists of ~4 bitmaps around 1000x500 in size each.

I want a robust and efficient undo/redo system that's as simple as possible. I'm aiming for about ~0.2s to undo or redo an edit. I'm looking for some feedback on my current intended approach or for some new ideas I can use. I think what I have is too complex so I'm cautious about proceeding so just knowing it's about the best I could do would be good.

I've experimented with combinations of using the Command pattern and the Memento pattern for my undo/redo system. Some conclusions I've come to so far are:

1. I don't have enough memory and I cannot write memory to disk fast enough to use a memento to support an "unexecute" operation on the previous command in many situations e.g. if the user does several individual paint strokes very quickly, I won't be able to store bitmaps that represent what the user painted over without making the user wait for them to be saved.

2. If I restore the document to its initial state and replay all the commands except for the last one to implement undo, this is far too slow after even a modest number of commands e.g. replaying 10 paint strokes or 5 smudge strokes takes ~1s which is too sluggish.

3. I can get around the previous point by saving the whole document in the background periodically to disk and restoring to this checkpoint before playing back commands. To undo further back than the last checkpoint, we reload the checkpoint before this and replay the commands.

Approach 2 with 3 works OK except saving the entire document gets slower and slower as more layers are added and it's already slow with 4 bitmaps (~5 - 10 seconds wait). I therefore need to modify 3 so that I only save what has changed since last time.

Since many commands operate on only one layer, it makes sense to only save the layers that have been modified since the last checkpoint. For example, my command stack might look like this if I have 3 initial layers where I've indicated where checkpoints might be saved.

(Checkpoint1: Save layer 1, 2 and 3.)
Paint on layer 1
Paint on layer 1
(Checkpoint2: Save layer 1. Reuse saved layers 2 and 3 from Checkpoint1.)
Paint on layer 2
Paint on layer 2
(Checkpoint3: Save layer 2. Reuse saved layers 1 and 3 from Checkpoint2.)
Paint on layer 3
Paint on layer 3
Flip layer 3 horizontally.
(Checkpoint4: Save layer 3. Reuse saved layers 1 and 2 from Checkpoint3.)
Resize layer 1, 2 and 3.
(Checkpoint5: Save layer 1, 2, 3.)

During editing, I keep track of which layers have been modified since the previous checkpoint. When I restore a checkpoint I only restore the layers that have changed e.g. to restore Checkpoint4 after modifying layer 2 and 3, I reload the backups of layer 2 and 3 from disk. When adding a checkpoint, I save only the layer that has been modified so far. I can make all this mostly automatic except there needs to be places in my interface where the user is forced to wait for checkpoints to be saved because I can only keep about 1 temporary copy of a layer in memory at a time.

What do you think? It's much more complex than I'd like it to be but I can't see any other way. Are there any other useful patterns I can use to make my life easier?

Answer 1

This following might be handy for layers and undo buffers using images:

• Keep the latest image as an image
• Previous versions are stored as an xor with the next version and then (assuming not everything changed or changed in the same manner) compressed using a simple compression algorithm (like run length encoding)

This has the following advantages

• previous versions could be easily merged (xor them together).

This might not work well with:

• color adjustments (hue, brightness etc)
• coordinate transformations (crop, morphing, etc)

Answer 2

One approach is to keep certain 'frames' as complete frames, and others as the the command necessary to create a frame from the previous one. You allude to this in your #2. It may be helpful to keep some frames in memory.

A trick that may help to balance performance with the space/time available to hold complete frames is to discard a some fraction of the 'old' frames, so that at any given time you might have undo states from e.g. 1, 2, 4, 8, 16, 32, and 64 operations ago. Undoing one or two operations will require simply reading a frame. Undoing three will require reading a checkpoint and repeating one operation. Undoing five will require reading a checkpoint and repeating three operations. Undoing thirty-three will require reading a checkpoint and repeating 31 operations.

To improve application smoothness, it may in some cases be helpful to recompute checkpoint frames in the background during an undo operation. For example, after having undone seventeen operations, one might in the background start working on computing the states for 48, 40, and 36 steps back from the starting point, so that if one wants to go back further one will have already done some of the work. Note that one may jettison the frames that were back 1, 2, 4, 8, or 16 operations, since one can recreate them by replaying commands forward from the current state.