Logic behind an ‘undo’ for painting on a canvas

I’m working on a module that allows users a basic paint function. I want to support undoing any modifications done to the painting surface. Assuming that we have one layer (for the sake of simplicity), what is a reasonable way to store painting done so they can be undone?

An idea I had was to encapsulate draw events as a kind of Undoable object. If someone presses, draws, and releases, the new data added would be contained in an object of what actions were carried out. This event might contain something like “color ARBG of size X at [array of points the user dragged over]”.

I’m unsure of this being the optimal way to do it. If there’s a lot edit commands done, my logic here would be to rewind back to the beginning and then re-apply every ‘edit’ done to the scene, render and display, without the UI becoming laggy (excluding fringe cases).

Is this feasible? Is there a better/more optimal way? This is the first time I’ve attempted such a thing and I’d like to make sure I’m going to learn the best way I can do it.

Note: My goal is not to use any libraries and handle this through my own coding.

Simplest method? Just limit the undo buffer size. Like you only allow the last 20 actions to be undone and keep a copy of the state 20 actions ago.

If you undo then there will be 19 actions in the undo buffer and redoing those is simpler than all since the beginning.

However extending from that you can keep copies of the state every X actions. This is the same idea of diff backups in databases, every month a full backup is done then a daily diff is taken. Then when needing to restore you just need to grab the latest full backup and reapply the diffs stored from that last backup on.

I used to do this similar to the way you’re proposing where I computed a bounding rectangle for the stroke, figured out what pixels were modified, storing their values before the modification, and recording an undo entry that would swap the old pixel values with the new pixel values on undo/redo. And for big strokes I even optimized it so that instead of one giant rectangle sub-image for the stroke, it would break it into smaller rectangular regions.

That’s a whole lot of work for just one image-related operation! It got to the point where I was spending as much or more time implementing the undoable logic of each operation as the operation itself and definitely spending a whole lot more time debugging faulty undo logic than the logic of the operation itself.

So I came up with a much simpler approach which would let me just apply the same approach to undoing image operations and also making them non-destructive: one approach to rule them all. And that boiled down to just thinking of an image as a collection of image tiles, say 64×64 pixels each:

Now before the user starts painting, you can just copy the whole damn thing into an undo entry, except the copy only shallow copies reference-counted pointers to each image tile. Then as the user starts painting over the image, you make the image tiles which are changed unique with an approach similar to that of immutable persistent data structures or you can use copy-on-write per tile (whatever type of interface and usage pattern suits you; the whole point is to avoid copying the image in its entirety when only parts of it are modified):

Now you can just allocate the image tiles which have been touched by the operation (the dark tiles above which were touched by the user). You can shallow copy the untouched tiles.

With this approach, no matter what image operation is being applied whether it’s drawing shapes and strokes or an image filter applied to an image selection or mask, your undo logic boils down to this:

before user operation:
    copy image to undo entry

on undo/redo:
    swap user image with undo image

That’s it. It may not be theoretically optimal but boy does it simplify things as far as non-destructive editing and undoing goes. The whole point is to optimize the copying so that every tile which isn’t touched by the user just gets shallow copied so that we can copy images left and right without a care in the world about blowing up memory use and wasting excessive time copying everything over and over.

Now I apply this general approach to undoing and non-destructive editing for everything. Just copy the thing beforehand and then apply user operation. That shifts the difficulty away from correctness to optimization. The next step is to optimize by making the copying cheap for parts that weren’t modified.

One Undo Approach to Rule Them All

These days I actually uniformly favor this method for all sorts of disparate applications of undo systems. The no-brainer way to make that work correctly is just copy all the relevant data into the undo stack, at which point the implementation becomes like this:

Before user operation:
    old_state = current_state

After user operation:
    if old_state != current_state:
        clear redos stack
        push old state to undo stack

On undo:
    push current state to redo stack
    set current state to top of undo stack
    pop from undo stack

On redo:
    push current state to undo stack
    set current state to top of redo stack
    pop from redo stack

That shifts all the concerns to optimization (the copying and comparison of equivalence) rather than correctness. And I’ve managed to optimize it sufficiently even for data that would normally span gigabytes by using methods as described in the above approach or alternatively compact structures which capture like the “deltas” (differences between two structures) to the point where the undo system actually takes even less memory than when I was using the command pattern.

And that optimization of hefty copying structures (without deep copying everything) and being able to compare them rapidly for equivalence often has way more practical uses outside of the undo system for other things like exception-safety, thread-safety, non-destructive editing, etc, since if you can cheaply copy things around, then you tend to have fewer reasons to cause side effects in your functions in general.

There is another way you could handle this which I’ve seen done by some apps. Instead of keeping around the result of every action the user has committed, you keep around the original image, the recipe (the list of steps the user followed) to get to the previous image, the previous image, and the current image. The original and previous images as well as the recipe can be on disk rather than in main memory to save space, if necessary.

So now you can get back to any point in the undo chain. The most common undo action is to undo the last thing. Since you have the previous image, you can simply swap it out for the current one. You also remove the last transaction in the recipe. In the background, you can recreate the previous-previous image from the original image and the recipe in case the user decides to undo again.

If you have the memory for it, you can keep the last n versions either in memory or on disk for quick recall after undo. But you can always undo back to the beginning because you have the recipe used to make the current image. You can even save the recipe so the user can undo/redo actions performed during previous launches of your application.

Filed under: softwareengineering - @ 17:58

Thẻ: canvas, logic

Thiết kế website giá rẻ

Danh mục

Logic behind an ‘undo’ for painting on a canvas