undo_ideas.txt

In reply to this tweet https://twitter.com/ApoorvaJ/status/649276841505624064

Two things first
  1) I have no idea how Papaya works. Haven't looked at the code. =)
  2) A paint app is a simpler problem than an image editor. It's possible that I'm not seeing something
  
So, Milton has infinite undo/redo because every operation is defined declaratively.
All it does is apply "strokes". A stroke is either a brush stroke or an eraser stroke.
When displaying a drawing, it computes this:

Bitmap = Background + Stroke1 + Stroke2 + ... + StrokeN 

So my implementation of undo is simply `num_strokes--;` 

I think something like this can be extended to Papaya.

Let's say that you have a way of declaratively describing mutations. 

M = <Array of mutation descriptions> 

M[0] = Apply_Blur(x,y, radius)
M[1] = Add_New_Layer(name)
M[2] = Brush_Stroke(layer, brush, input_points)
M[3] = Crop_To_Rect(rect)
...

So the current image could be obtained by an "ApplyMutation" function that
takes an image and a mutation and returns a new image.

Image = OriginalImage
for (i = 0..N-1):
  Image = ApplyMutation(Image, M[i])
  
// You would probably never do this because it would be dog slow.
// This pseudocode is just to illustrate that storing mutations declaratively
// lets you go back or forward in time.

If you want N levels of undo, you can keep a data structure with the following properties:
  1) It has a snapshot: A copy of the image at some point in time.
  2) It has between 0 and N mutations.
  3) The current image is a result of the mutations applied to the snapshot.
  
With this data structure, you could implement undo by popping the latest
mutation and recomputing. 
You would keep a "redo stack", a stack of mutations that have been undone.
So that implementing re-do is simply popping a mutation from the redo stack 
and inserting it into the main data structure.

So that's what I would try and do. Again, I don't have any idea of the
implementation details of Papaya, and maybe you have already thought of
this and discarded it. Hopefully it will be useful in some way :)

Hey Sergio, thanks for taking the time to write this out. It gives me a very good picture of your undo strategy, and your implementation of Milton (sans the snapshot of course, which I presume won't be possible because of infinite resolution). Here's my take on the undo system:

No mutations for me
Papaya supports brushes of varying opacity, hardness and size. It will also support drawing tablets, and will allow the user to vary any/all of the aforementioned brush parameters based on pen pressure. At some point, I may even want to add randomness to brushes in the form of brush dynamics.

It becomes too cumbersome to store all of this data as mutations and complicates the system considerably. I think Substance Painter does do all of this in some form, but I'm not looking to replicate that feature.

How my current implementation works
When the user opens a document, I allocate a contiguous block of memory. I maintain three pointers to that memory: Base(B), Current(C) and Top(T).

Here's how the memory looks initially. Base, Current and Top all point to the start of the buffer.

[...........................................................................]
^
B,C,T

When the user performs an undoable action (currently, there's only one action: brushing), I write an Undo record at the location of the Top pointer, and increment the top pointer by the size of the record.

Each undo record consists of two parts:

1. An UndoData struct. This struct is like a node in a doubly linked list. It contains pointers to Prev and Next records (which are null at the first and last nodes respectively). The struct also contains data about the nature of the operation (currently always set to PapayaUndoOp_Brush), and the size (in bytes) of the second part of the undo record, which is:
2. Variable-sized data block. Currently, this only holds image data.

When the user opens a document, I store an undo record as follows. Note that the top pointer is incremented by sizeof(UndoData) + 4 * ImageWidth * ImageHeight.

[......|.................................................................]
^      ^
B,C    T

When the user brushes on the image, I store a record as follows:

[......|......|..........................................................]
^      ^      ^
B      C      T

And maybe another one:

[......|......|......|...................................................]
^             ^      ^
B             C      T

Now, when the user uses Undo/Redo, I move the Current pointer using its Prev and Next pointers, and load the correct image data that it points to.

This implementation is very similar to a stack, except popping does not discard the popped data right away. If you undo to a point and then operate on the image, only then is the future data is lost, along with your ability to redo. This is how most applications' undo systems work.

The slightly tricky bit occurs when the buffer is near full. When this happens, I store the part of the undo record that fits at the end, and then wrap around to the start and store the rest there. I have to increment the base pointer accordingly as well. This is where the system acts like a ring buffer.

[......|......|......|......|......|......|......|......|......|......|..]
^                                                              ^      ^
B                                                              C      T

[....|.|......|......|......|......|......|......|......|......|......|..]
     ^ ^                                                              ^
     T B                                                              C

An important point to note here is that the system is designed to store variable-width data. Not all undo operations are born equal - a layer name change will require less data than a brush operation.

Keepin' it simple
The way the system currently works, I store a copy of the entire image in the undo buffer even if you change a single pixel of it. While the systems engineer part of me hates this, I think this is good enough for the following reasons:

1. I'm currently the only developer on Papaya, and I think it's more important to focus on features right now than memory optimization.
2. The memory usage is not that bad. A 4096 x 4096 image consumes 64 MB of memory. Even a 1 GB buffer can store up to 16 steps of undo history. On modern machines, if you're editing a 4k image, I think I'd be able to get away with an even larger undo buffer.
3. Papaya is going to support layers in the near-ish future. Layers really relieve the pressure of long-term undos.

So, that's it. TL;DR: The current solution, at least for now, is good enough. Instead of over-engineering, this is one of those times where I prefer to throw more RAM at the problem.

I started out writing a comment, but ended up writing a blog post. :D