BMesh Undo/Redo

Background

I'm working on implementing dynamic topology sculpting by combining BMesh with the PBVH. To support undo/redo, it would be good to avoid making a complete copy of the BMesh as is currently done in Edit Mode. I'm looking into creating a more efficient undo system for BMesh that uses the Euler operators and their inverses to compactly store topology edits. It also tracks non-topological edits such as changes to vertex coordinates.

Implementation

https://github.com/nicholasbishop/blender/commits/bmesh-undo

The BMLog source files are:

Testing

The bmesh-undo branch contains some quick hacks to test the logging code: pressing CTRL+A and CTRL+SHIFT+A in editmode will undo/redo using the BMLog. (Some of the normal editmesh-undo code is also commented out to prevent copying of the BMesh.) The current state of the BMLog can be viewed from the new (temporary) "BMesh Log" in the outliner space.

BMLog

Most of the new data is kept in struct BMLog. The top-level BMesh structure has an opaque pointer to a BMLog. The BMLog gets created at the same time as the BMesh.

Element IDs

In order to redo the creation of mesh elements from the log, sub-elements (e.g. the vertices of an edge) need to have a stable ID. Element pointers can't be used for this, since they could be reallocated at a different address due to prior undo/redo. The element index also is not safe since it gets used as temporary storage. Instead, each mesh element is assigned a unique ID when it is created (the ID is also released when an element is killed.) The unique ID is an unsigned int, and is only unique with respect to the current mesh state -- other entries in the log might reuse an ID.

The BMLog contains a GHash map from element IDs to their current address.

When a mesh element is re-created from the log, BMLog.skip_id_assign is temporarily set to TRUE to prevent a new ID from being assigned; the undo/redo function can then manually assign the correct ID from the log.

RangeTreeUInt

In order to efficiently keep track of unused IDs, a new data structure has been added that stores ordered, non-overlapping ranges. It's implemented in C++ to take advantage of the std::set structure. Original source code is on github: https://github.com/nicholasbishop/RangeTree. For BMLog, the three source files have been added to intern/rangetree.

Log Entries

As the mesh is edited, new log entries are appended to BMLog.entries. BMLogEntry is the base entry type, then each type of change to the BMesh has its own log entry type (BMLogVertCreate, BMLogCoordsSet, BMLogSEMV, etc.) The entries contain everything needed to either undo or redo an action. For example, the SEMV operator logs the IDs of the original edge, the target vertex, the new output vertex, and the new output edge. The SEMV undo action then calls JEKV on the new vertex and new edge. The SEMV redo action calls SEMV again with the original edge and target vertex.

Entry Merging

For operations that set lots of attributes at once, a single log entry is used. This is currently just BM_LOG_COORD_SET and BM_LOG_HFLAG_SET. These entries store a hashmap from element ID to the old+new values.

Locking

The BMLog can be locked to prevent entries from being added. This is needed during undo/redo, and also needed for Euler operators that call other operators. For example, SEMV calls BM_vert_create and BM_edge_create, but these should not be logged. (If they were logged, undoing would kill the new edge and vertex, making it impossible to use JEKV.)

Issues and Todo

Mesh elements each grow by four bytes due to the new ID field. If logging is used for undo/redo this seems acceptable, although if it were added as an optional feature the ID field could be removed in favor of an extra map in BMLog (e.g. struct GHash *elem_to_id).
High-level undo operations. The BMLog will typically record many actions for a high-level action such as subdivision. I added a BM_LOG_FENCE type to separate high-level actions, but not sure if there's a nice generic place to insert this (rather than manually adding it to a hundred editmesh functions.)
Normals have to be manually updated right now, maybe should add functions to log vert/face normals as is done with vertex coords.
CustomData changes should be logged, haven't looked into this at all yet.
Lots of other euler operators still need logging added, may be unforeseen issues.
The BMesh docs http://wiki.blender.org/index.php/Dev:2.6/Source/Modeling/BMesh/Design#Efficient_Undo mention that not all mesh changes are being done with eulers, not sure how big of a project it is to fix that.
Could save some space by not storing both old and new values in log entries. E.g. vertex coords could store just the "old" value, then on undo the "new" value gets swapped in (similar to sculpt mode's undo.)
Check over API -- what is needed publicly?

利用者:Nicholasbishop/BMeshUndo

目次