Undo for dynamic topology

I’ve been working the past couple days on the issue of undo/redo for dynamic-topology sculpting. The approach I’m looking into is one that should have general applicability outside of sculpting too.

Currently, changes made to the mesh while in edit mode create a full copy of the mesh. This is the simplest and least error-prone way to do it, but certainly not the most efficient. As noted in the BMesh wiki doc, a potentially better way to do it is to take advantage of the so-called Euler operators used to manipulate the mesh topology.

Euler operators are a set of functions that make small changes to a localized area of a mesh. They also have inverses, so they can be cleanly undone. The BMesh doc gives more info, but a simple example is vertex creation. The function BM_vert_create() is an operator that creates a new vertex in the mesh; it’s inverse is BM_vert_kill(), which deletes the vertex.

These operators can be used to create an efficient undo system by logging each operator as it is called, as well as its inputs. (There’s actually some extra indirection there because the inputs are pointers which might change after undoing and redoing an edit, so we assign each mesh element a unique ID and store that in the log.) These logs form a list that essentially records the history of the mesh (linear history, that is, not including any undo/redo steps themselves.) Additional log entries must be created for non-topological operations such as selection and transform operations.

I’ve written up some more technical information in a proposal on the wiki, and there’s test code in the bmesh-undo branch of my github repo. I’ve sent the proposal to bf-committers; hopefully there are no major issues with this idea, but we’ll see.

Next goal is to continue working on logging for more of BMesh’s operators, then I’ll rebase the dynamic-topology branch on top of bmesh-undo and try to integrate the new undo system in sculpt mode. So much work just to make CTRL+Z do something! :)