Fast undo facility for bitmap editor application

Question

I'm trying to make a bitmap editor app for the iphone which would be similar to Brushes or Layers or a cut-down version of Photoshop. I'd like to be able to support 1000x1000 resolution images with about 4 layers if possible.

I'm trying to design my undo/redo system before I write too much code and I'm having real issues coming up with a good solution because of the limitations of a mobile device and the fact that bitmap editor operations are usually destructive. The most common undo/redo designs I know of are:

1. Use the command pattern. You store the initial state and the commands used to transform this to the current state. To undo, you reload the initial state and replay all the commands except for the last one.

2. Use the memento pattern. After each operation, you store enough information to be able to revert that operation.

The problems I foresee are:

1. Command pattern: What do I do after 500 edit operations and I want to undo the last one? Loading the initial state and applying 499 could be time consuming especially if some of these are costly things like e.g. applying blur filters. I don't like the way undoing takes a different amount of time under different scenarios.

2. Memento pattern: Saving the parts of the bitmap that were modified takes a lot of memory. Caching these bitmaps to disk can be slow as well (so I might have trouble caching the bitmaps if the user is making lots of fast edits) and I'm not sure about the battery usage implications.

The only solutions I can think of are:

1. Use the command pattern and memento pattern where, every 10 commands or so or after an expensive operation, the whole state is also saved (which gives you an autosave feature for free). To undo, I reload the closest snapshot and then replay the commands. I'd rather avoid this complexity though.

2. Use the memento pattern and force the user to wait for the bitmaps to be cached. This isn't too bad if I build this time into e.g. waiting for a filter to apply but it doesn't work well between making brush strokes.

Are advice? I'd be interested to know how some existing apps do this.

I can think of all sorts of weird hybrids of the above but they all have obvious problems. All I can think to do is live with some of these problems or compromise the app to make the problem simpler (e.g. reduce the size of the maximum bitmap size). I have noticed that several apps have quite low maximum bitmap sizes and layer limits.

Answer 1

There's a third option that comes to mind: each action gets executed on its own layer and undo deletes that layer. It needs a fast rendering mechanism and a smart representation of 'action layers' where you don't store 'transparent' (untouched) pixels.

If you assume u levels of undo, you can merge action layers older than u steps into the background.

You could also have a hybrid approach. If the action is 'small', represent it as a layer. If it's big, as a recorded action, that needs to be replayed. As you say, you need a heuristic to decide between the two cases. You could test rendering/saving performance on the first run af the app after setup and decide some parameter values for the heuristic.

Answer 2

To me, the momento pattern looks the best. Which means that I would probably try to think of ways to optimally store that information. You mention that it can be a 1000x1000 bitmap potentially for one action -- could you, for example, represent the bitmap as a 1-bit bitmap with a separate color field stored elsewhere? Now instead of 2MB you have 125KB to store.

Another thing that I would probably look into is building the information while the user is performing the action -- i.e, while they are scribbling, you can be writing those bits into your data structure as it happens. And then when they are done, you can commit the action to your undo history.

You should be able to apply some algorithmic logic to these undo data structures to reduce their memory impact while hiding the CPU usage during times while waiting for the user.