4 Edited old post to include some more info applicable beyond painting contexts.
source | link

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.

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.

3 added 113 characters in body
source | link

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 64x64 pixels each:

enter image description here

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

enter image description here

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.

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.

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 64x64 pixels each:

enter image description here

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

enter image description here

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.

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 64x64 pixels each:

enter image description here

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

enter image description here

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.

2 added 88 characters in body
source | link

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.

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 64x64 pixels each:

enter image description here

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

enter image description here

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 restuntouched 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.

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.

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 64x64 pixels each:

enter image description here

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

enter image description here

Now you can just allocate the image tiles which have been touched by the operation. You can shallow copy the rest.

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.

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.

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 64x64 pixels each:

enter image description here

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

enter image description here

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.

1
source | link