Undo for a paint program

Question

I am looking into how to write a paint program that supports undo and seeing that, most likely, a command pattern is what I want. Something still escapes me, though, and I'm hoping someone can provide a simple answer or confirmation.

Basically, if I am to embody the ability to undo a command, for instance stamping a solid circle on the screen, does this mean I need to essentially copy the frame buffer that the circle covers into memory, into this command object? I don't see any other way of being able to undo what might be, for instance, stamping over a bunch of random pixel colors.

I've heard that one approach is just to keep track of the forward actions and when an undo is performed, you simply start from step 1 and draw forwards to the step before the undo, but this seems unfeasible if you are to support a large undo stack.

Perhaps the solution is something in between where you keep a bitmap of every 15-20 actions and start from the last 'save' forwards.

Can someone provide any insight on what is the typical accepted approach in this case, either saving buffer rectangles in the commands, redo-ing every action forwards, or something I've altogether missed?

Update: Plenty of good responses. Thanks, everyone. I'm thinking from what I'm reading that I will approach this by saving out the buffer every N actions and when the user issues an undo command redo all commands from the most recent saved buffer. I can tweak N to as high a value as possible that doesn't noticeably bog down the user experience of needing responsive undo (in order to minimize memory usage), but I suspect without really knowing for sure at this point, that I should be able to get away with performing quite a few actions in one frame such that this isn't too bad. Hopefully this approach will let me quickly determine whether to turn the other direction and instead go with saving bitmap rects for the previous states for actions that require it.

Answer 1

First, beware overdesign: if your app isn't complex and your images small, you may find 'just store everything' to be quick, cheap and feasible. But assuming that's not so:

You are correct that it is not feasible to redraw the entire canvas from step 1 forward for each undo; unless your paint program is very simple some operations simply take too long. Also, an infinite undo buffer is probably not called for (and could be very space-consuming to store).

If your art program is complex, I'd actually start with a hybrid approach, to deal with the variety of operations. Save frame buffer every so often (the every 15-20 commands you suggest seems OK; I might start with 10 and adjust once I had it working) and go forward from last save. But don't make the 'every 15 operations' rigid, because it is likely that a few extra rules of thumb would make it seem much more fluid to the user.

For example, some time-consuming or tricky-to-reverse operations could always create a new save point:
- Any canvas resize (crop etc.)
- Any save. ("I just saved" is a very likely place for the user to undo back to.)
- Any operation which is extremely time-consuming should create a new save point after, not before, the operation; i.e. it should flag the next operation to save the buffer to undo. (Why? If the op takes 30 seconds, you don't want every undo in the stack afterwards to take an extra 30+ seconds.)
- Conversely, any operation which has an easily performed mathematical negative, or is self-inverting (like photonegative) need never bother to save frame buffer, and shouldn't count towards the next save.

All of this leaves out the question of layers; if your program has them it's obviously sufficient to save only those layers that change.

Definitely my highest-priority suggestion though: regardless of what method you use, you should always save frame buffer for the most recent operation performed. "Whoops, didn't mean that" is the most likely reason for undo, so you always want undo-one-step to be responsive. You can discard this buffer after the next command execution if it's not one you're keeping.

You'll also need to consider what constitutes one atomic undo operation. (For example, is a set of strokes with a single brush tool one operation or many? Both have advantages and drawbacks.)

Answer 2

Perhaps the solution is something in between where you keep a bitmap of every 15-20 actions and start from the last 'save' forwards.

I would go with something like this one. You have to bound your command stack at some point anyway, so you'll need a starting point if the user empties it.

You could get clever and save the buffer when you reach the bound and use that as your save point, since you have to drop a command from the stack anyway. Essentially, your save point buffer is the representation of the dropped actions, so as you're dropping actions from your undo stack, you just write them onto that buffer.