Fast undo facility for bitmap editor application

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 reve开发者_运维百科rt 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.

Checkpoint each bitmap with memory mapping The flash memory on iOS devices is fast enough to support undo/redo operations on large bitmaps. Using the mmap system call, I memory mapped 1024x768 ABGR bitmaps with ease, saving my program from using precious DRAM. I don't know how you would like to abstract the undo/redo patterns but the way to avoid any high-overhead copy operations is to have the pointers for undo and redo bitmaps swap each undo/redo. You have specified more than one undo level, but I bet you can get away with some pointer swapping (I am suffering from some insomnia right now and trying to demonstrate the pointer swapping proved too much--it was some pretty garbage psuedocode).

Also, I would not recommend marking your mmap'd pages as F_NOCACHE. It is preferable to have iOS cache writes to the bitmap in DRAM because:

• It's faster if you don't flush to flash
• Flash memory is designed for a fixed number of writes--it's not nice to burn out users' flash (I think it takes somewhere on the order of 5 million writes with the quality flash in iOS devices)
• I believe iOS is aggressive enough in memory management that it will unmap your cached writes and flush them during a memory crisis (I never cared enough to check, though)

Shout out to John Carmack for the tip-off that the iDevice Flash memory is quite fast (He uses F_NOCACHE, though, to get predictable read performance).

Note that I had to make the file be the size of the actual bitmap before calling mmap on the fd. Don't go nuts memory mapping 100 bitmaps, though (just kidding--DO IT!) I mean, how many undos can a user perform? They are weak and their fingers get tired after mere seconds of button-mashing.

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.

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.

I'd go for a hybrid approach. On top of that, organize your data in parts (eg tiles) so that you only have to store states of the modified parts (using a delayed copy mechanism).

What you are facing seems like a resource limitation to me, so this is something that concerns your UI/Application Design. There are no nifty tricks to get more memory, faster "disk" access etc.

I would go a hybrid approach using memeton in a ringbuffer and processing each filter in the next free preallocated slot. This will give you a limited fast undo/redo without heap corruption. For the unlimited undo/redo steps you have your command log. If you really need 400 undo steps, you may also save like every 10 operations a snapshot with the commands and compress 10 of those snapshot into a bigger snapshot.

The most important thing is to make it clear to the user that they are operating at the limits of the device, like a warning sign when your fast undo is used up.

Also it may be beneficial to prepare your fast undo/redo buffer in the background, so when the user undos 2 times you already prepare the 3rd undo. Most times the user looks at the image for a few ms (Around 200-400) before he executes the next undo.

Also you may implement different undo/redo strategies for reversible operations that use minimum memory. A fast losless compression algorithm (lzma, etc.) in the background may reduce memory consumption even further.

But as this seems to be a resource limit (IO vs. Memory vs. CPU) all your options are to live with it and try to make the user experience the best you can. And this sometimes becomes a difficult task.