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