Simple undo history for a mesh graph using diffs

Undo is a fundamental feature in many software applications, and my app ShapeReality - 3D Modeling is no exception. Due to the ubiquity of undo, one might expect implementing it to be a solved problem, but there commonly isn't a one-size-fits-all approach.

This post will go into how I implemented undo for my mesh graph data structure, and how this fits into the complete undo history of an application containing multiple data structures and contexts. These principles should be applicable to other applications and data structures too.

Command pattern

At the core of implementing an undo history is the command pattern. Each operation that should be reversable via undo, and executed again via redo, is stored in an ICommand:

struct ICommand {
    virtual void undo() = 0;
    virtual void redo() = 0;
};

Undo and redo stack

Commands get stored in an undo_stack and redo_stack:

struct History{
  std::stack<ICommand*> undo_stack;
  std::stack<ICommand*> redo_stack;
};

Any time a command is performed, it gets pushed onto the undo_stack, and the redo_stack gets cleared.

Alternatively, one could create branching undo, where each time you undo, and then perform new changes, it creates a new branch. While this could be an interesting feature, it requires a lot of additional UI to communicate the existence and state of this branching history. Compared to two simple buttons, this complexity doesn't weigh up against the benefits.

When History::undo() is called, it takes the top of the undo_stack, calls Command::undo() on it, and pushes it onto the redo_stack. The inverse is done for History::redo().

Note about invalid states

When the user performs any modification to the data structure, it must be stored as a command. If a change is not recorded, and History::undo() is called afterwards, the data structure can end up in an invalid state. See the following simplified example:

State before	Operation	State after	Undo stack after operation
ABCDEF	erase(1), store	ACDEF	[EraseCommand(1, 'B')]
ACDEF	erase(0), don't store	CDEF	[EraseCommand(1, 'B')]
CDEF	undo EraseCommand(1, 'B')	CBDEF	[]

If the letters are required to be in alphabetical order, the non-recorded operation caused the undo operation to make the state invalid.

The mesh graph also has such requirements, for example:

• When two vertices are selected that connect to each other via an edge, the edge must also be selected
• When all vertices / edges are selected that make up a face, the face must also be selected

For this reason, it's important that anything modifying the mesh graph is pushed to the history as an undoable command.

Command implementation for mesh graph - the dumb approach

There are many operations that can be performed on the mesh graph. Take for example:

struct Mesh{
    // ...
    void insert_vertex(...);
    void insert_edge(...);
    void insert_face(...);
    
    void erase_vertex(...);
    void erase_edge(...);
    void erase_face(...);

    void insert_face_or_edge_from_selected(...);
    void extrude_selected(...);
    void select_linked(...);
    // ...
};

To make these operations undoable, I considered a naive approach, where a corresponding command has to be created for each operation. e.g.:

struct InsertVertexCommand : ICommand {
    // ...
    void undo() override;
    void redo() override;
};
struct InsertEdgeCommand : ICommand {
    // ...
    void undo() override;
    void redo() override;
};
// etc.

However, life's too short for this. Not only does this make the code needlessly verbose, it's also a pain to figure out what data to store in the command and how to reverse the operation. Each function can also call the other functions recursively, thus making this approach highly complex to implement.

The super lazy approach - pool copies

Recall that the mesh graph contains 5 elements (Vertex, Edge, Face, VertexUse and EdgeUse). These elements are stored in a pool.

If we're exceptionally lazy, we can copy the pools before and after executing the operation, and on undo() assign the old pools to the pools, and on redo assign the new pools to the pools.

The issue with this however, is that it takes up an insane amount of memory. For each operation performed, no matter how small, we store an entire copy of the mesh in working memory. For sufficiently large meshes, this approach won't work.

The less lazy approach - pool diffs

This brings me to the final design:

Instead of storing a copy of the entire pool in a command, we only store elements that were changed. Elements are considered changed if they: 1) were deleted, 2) were inserted or 3) had their data changed.

For each changed element, we store the before and after state. This gets stored in a PoolDiff<T>.

template <typename T>
struct PoolDiff {
    struct Entry{
        unsigned int index;
        T before;
        T after;
    }
    std::vector<Entry> entries;

    void undo();
    void redo();
};

Recording a diff

Recording a diff is left as an exercise to the reader.

Conclusion

This post outlines how to implement undo / redo for a more complex data structure, where it is borderline insane to create a separate Command subclass for each operation. Diffs can be a powerful approach, potentially applicable to a wide range of other applications.

Note that specific optimisations can still be done where the mesh does not change topologically.