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

5 thoughts on “Undo for dynamic topology”

  1. So my thinking was kinda in the right direction (my reply to your last blog).

    Glad you found a solution and I hope it’s accepted as commit! :)

  2. I’m all for anything that will reduce the memory load of undo history and allow more stable tool development.

    I have a couple of questions:

    (1) I’m assuming scupt mode currently operates by direct mesh edits. Would Euler operaters make sculpting more efficient and/or faster?

    (2) You mentioned a few posts back that you planned to read Farsthary’s paper concerning Unlimited Clay to see if you could adapt any of his methods for your work. Has his paper affected your plan on how to best implement dynamic topology?

    1. The Euler operators are only topological changes, so they can’t help (or hurt) for regular sculpt mode.

      Regarding (2), my latest post should answer that.

  3. What about use this function in shapekeys in blender, afaik each shape key is copy of mesh… That would be also usefull

    1. These are separate systems. Shape keys could perhaps be made more efficient by using some sort of conditional data structure… e.g. if less than X% of the shape key is different from the base mesh, store it as a map rather than a fully copy. This would probably require some pretty extensive changes though.

Leave a Reply

Your email address will not be published. Required fields are marked *