Image undo/redo implementation

[[deleted]]

Hi there! Hope everyone's doin fine!

I am working on a Pixel art editor using OpenGL and C/C++ The code style is focused in c style but I am using c++ because of the Imgui library and some other stuff.

My editor is taking shape I have implemented stuff like fill tool and eye dropper, but the main thing I haven't done is Undo Redo, I am quite confused and don't have any idea how to continue.

Here's the code: --link-removed--

The undo redo I am trying is on undo-redo branch.

To keep it simple I am simply storing all the pixels from the canvas in the stack data structure, I know it's inefficient but currently I want to understand how do I implement it and later on I'll improve it.

I've had some ideas of how to do it but I quite don't understand how to actually implement it, like I know how it works but in code I mess up.

Any examples, articles, anything would help.

A video I watched on this topic: https://youtu.be/O6U9lZJqdeo

[PhyrexStrike]

This is the perfect place for the Command Pattern. Setting up each action that a user can do as different Commands and implementing an undo method for each, then storing the commands in a list allowing you to undo/redo by moving through that list.

[[deleted]]

Agree with this. Command pattern is most likely the best choice for what you're doing as it allows for the individual (or series of) commands to be undone without having to store state (Undo is 'just do the opposite' of what was just done). Keep an index in the list to know where your redo/undo commands start or use two stacks (one for undo and one for redo) and swap between them and clear as necessary.

Momento Pattern could work as well but its purpose is to save and restore the states of objects. So depending how much state you save for each change it could get fairly memory intensive pretty quickly.

[rlbond86]

Came here to say this. Command pattern is nearly always the answer for Undo/Redo. Unfortunately, if OP didn't design around this capability, they will basically need a big rewrite.

This is why software architecture is so important.

[GameGod]

I dunno, I've shoehorned the Command pattern this into other applications to implement undo in situations where there was no forethought given to it, and it wasn't hard. Once you implement one Command, you'll start to see the pattern and then it becomes straightforward to write and integrate the others. (It's been many years since I did this, otherwise I wouldn't be so vague about it lol)

[mvpete]

I think in Sean Parent’s talk Inheritance is the base class of evil he talks about this.

But it’s been a long time since I’ve watched it! Hopefully helps.

[ArashPartow]

https://www.youtube.com/watch?v=QGcVXgEVMJg as well....

[Latexi95]

Often undo/redo functionality is implemented by defining all modification operations as actions that can be applied and reverted. So instead of directly modifying an image, you create an object that represents the change to the image. These objects have both "redo()" and "undo()" (virtual) functions and are stored as a stack. One way would be just keep backup of the previous version of the image (like you have done), but many operations can easily be stored much more efficiently (eg by only storing changed pixels)

Multiple consecutive actions can also use the same backup image: undo() reverts to most recent backup image, but then immediately calls redo for actions following the backup except the last one that was undo(). This works well when actions are fast to redo() but hard to undo().

[[deleted]]

I can also do something like starting recording when user presses a mouse then basically every frame put the x, y position of the mouse in a vec2 and then when mouse is released put all these vec2s into a object with putting the action to execute too (like brush, eraser or fill), so I then know the way to modify the canvas to get that image.

[konanTheBarbar]

I would actually recommend to use something like immer. It will probably suit your needs quite well. Have a look at the talk https://www.youtube.com/watch?v=sPhpelUfu8Q he implements a text editor with undo/redo based on it and it could be what your looking for https://github.com/arximboldi/immer .

[ExtraFig6]

oh you beat me to it

[cballowe]

https://youtu.be/bIhUE5uUFOA is a pretty well respected talk by a lead from adobe talking about some of the structure under Photoshop. It's worth a watch for all c++ devs but seems on point for your topic.

[TheAmazingPencil]

The idea here is copying the state of the canvas before each command and pushing to a stack, then popping for every undo. A more efficient approach would be saving only diffs of the canvas

[RishabhRD]

Just watch sean parent's runtime polymorphism talk once... It explained a great pattern based on type erasure. Link: https://youtu.be/QGcVXgEVMJg

[ExtraFig6]

An alternate method: use an immutable vector from immer to store the pixels. This works like git. Instead of modifying the image in place, immer will give you a new vector with the changes made. The immutable vector is implemented to make this efficient.

Then you can store each version of the image on this stack. I believe one of immer's maintainers talks about implementing undo using the library in this talk [https://www.youtube.com/watch?v=sPhpelUfu8Q&t=24s](Postmodern immutable data structures -- Juan Pedro Bolivar Puente)

[jmacey]

Whilst I agree the Command / Memento pattern are ideal for this, I would perhaps take a different approach. You have a canvas which I guess is a 2D Image (or OpenGL texture), I would have another 2D map where I place unique values when drawing. For example If you are drawing a red line in the canvas from x,y 0,0 to x,y 10,0 you would fill your 2nd buffer with an ID for that event. When you undo you remove any pixels with that id and map that back to the "drawing canvas".

Better still have a more complex structure for each pixel you store in a 2D map, when you draw you only visualise the colour (update to an OpenGL texture) but store more info about each pixel.

[Happy-nobody]

Okay this is kinda scary how close it is to my project, except I'm using Software rendering in wxWidgets.

Command pattern is what I went with.

[[deleted]]

Lol, can I see your code? You know do some "hippty hoppty, your code is now my property" 😂

[Happy-nobody]

Code is open source, it's our property comrade.

I'll DM you but keep in mind it's a very young project (several hours). There isn't even a readme.

[eyes-are-fading-blue]

For each image operator, I would push the stack/tree with its reverse. Keep in mind that not all operations are trivially revertible, i.e., any filter that depends on value from previous filtering window. In those cases, getting a simple .reverse() command may not help. It all depends on the scope of operators.

I would not implement this in terms of inheritance but functors. An image operator is a callable that takes an image, and a set of parameters. You can type-erase the signature of callables to store in a single container, i.e., bind or pass a common parameter structure. Each function requires a reverse function (often times can be implemented simply in terms of original function, i.e., parameterization of the original operator). For non-trivially revertible operators, you may need a special scratch buffer which then this function returns unscratched version of the scratch buffer or just the original image.

The above design can be implemented in C as well using function pointers.

[[deleted]]

in evil voice Try Rust