The latest code in the dyntopo branch now does undo/redo in sculpt mode with dynamic topology enabled.

The bmesh-undo branch on which this is based has gained a simple unit-test framework, although only one test is enabled currently.

The last major change that was needed to get undo working was rewriting the edge-collapse function in dyntopo. Originally it was coded using the vertex/edge splicing euler operators. The two vertices of the edge were spliced (merged), then duplicate edges were spliced, and various cleanups on faces were performed. This was already tricky and error-prone, and getting undo working for splice was not going too well. As a workaround, I replaced all the splicing code by simply creating new faces and deleting the original vertex/edge. Simpler code and the undo code was already working for that case. That said, proper logging of splicing is something that will need to be revisited if the BMLog were considered as a replacement for editmesh-undo.

There are of course still bugs to work through, but this is a good validation of the logging technique.

I’m continuing to work on the BMesh logging system that will provide undo/redo for dynamic-topology sculpting. One aspect of this logging system is assigning unique IDs to elements. In order to do this efficiently, I wrote a small C++ library to efficiently store and query non-overlapping ranges. This code is now used in the bmesh-undo branch to keep track of unused IDs. Since the code is fairly generic and might be useful elsewhere, I’ve pushed the RangeTree code into its own repository on Github.

Another recent change in the bmesh-undo branch is an easier way to examine the BMesh log. I added a new view to the outliner which shows changes to the mesh while in edit mode:

This is of course just a temporary debugging tool, not something that would be released. Note that low-level actions like mesh-element deletion and flag setting are now nicely grouped into high-level actions like “Translate” and “Extrude Region and Move”. Pressing CTRL+A/CTRL+SHIFT+A while in edit mode will now step back by high-level actions, and seems to work fairly well. (Again, the CTRL+A hotkey is just a temporary debugging tool.)

Back on the dynamic topology side, I am continuing to make updates to integrate the BMesh logging system with sculpt’s undo system. It is starting to work a bit, but still lots of glitches and crashes to deal with yet. I’m hoping that by improving the testing tools in the bmesh-undo branch I can work out a lot of these issues separately from dynamic-topology sculpting.

Quick note for anyone testing the dyntopo branch: dynamic topology now has a toggle button in the sculpt options panel. By default a mesh will now use normal static topology, so hit that toggle button to get dynamic topology.

Or at least, things that haven’t worked yet. As a more concrete follow up to yesterday’s post, these are a few things I’ve spent time on recently and that I don’t have much expectation of being ready any time soon.

Small Polygon Reconnection (SPR)

I’ve discussed SPR a couple times before. Essentially it is a way of improving local connectivity to reduce the number of irregular vertices in a quad mesh.

Although the basic SPR algorithm is simple enough, getting it to work quickly enough to be practical is quite challenging. There is a huge space of possibilities to search, so it needs aggressive pruning to get the times down. I wasn’t able to find a solution that gave both good and quick results.

My primary interest in SPR was to improve the output of the remesh modifier. Consider this example:

The remesh modifier often gives results like those on the left with curves surfaces. The mesh at right was hand-edited to encourage a more regular grid. In theory SPR should be able to do this, but given its speed problems a better solution might be to hard-code fixes for some common patterns in remesh’s output. Even a simple collapose on the diamond pattern that shows up a lot could be very helpful.

Projection Quad Coverage (PQC)

After I decided that SPR wasn’t going to work, I spent some time on an alternative idea called Projection Quad Coverage. This experiment was a bit of a departure for me because it wasn’t based on any particular research paper (although the general concept of parameterization has been well studied). Of course, it wouldn’t surprise me much if their is a paper describing this idea, but I have not found one — so I just came up with a nice TLA (three-letter acronym) and carried on.

The basic algorithm for PQC is:

1. Partition the mesh’s polygons into groups (called charts in this context) such that the chart is connected (i.e. not a collection of islands), and all polygons’ normals are within X degrees of some common vector.
2. For each chart, project its component vertices onto the plane whose normal is the chart’s “common vector” mentioned earlier.
3. Overlay a 2D quadrilateral grid onto that plane, with grid squares having some user-defined side length.
4. Assign Z values to each grid vertex by finding the mesh polygon that vertex lies within, and interpolating between the mesh polygon’s projected coordinates. If a grid vertex does not lie within a mesh polygon (note that this a 2D test), just mark the vertex.
5. For each grid square, test if its vertices are unmarked (i.e. have valid Z coordinates). If so, unproject the grid square’s corners back into the mesh’s 3D coordinate space and add the square as a quadrilateral in the output mesh.
6. Connect the boundary edges of charts to adjacent charts.

I’ve glossed over some things in that description… where the common vector comes from, how to efficiently calculate the grid projection, etc. The real trick though is my incredibly unspecific step six. The rest I got working pretty well, and that’s what is shown in the screenshot below. Note how large contiguous sections of the remeshed Suzanne have really nice regular quad distribution, with precisely zero irregular vertices (other than the borders).

Filling in those cracks between charts turns out to be quite hard. A couple “obvious” approaches are apparent: merging close boundary vertices or filling in the cracks with new quads and triangles. The devil is of course in the details though, and I didn’t find a good way to implement either of these high-level ideas. Unfortunately I only have that one screenshot of PQC handy, or I’d demonstrate better the issues that came up.

I had one more involved concept for filling cracks: build an edge network between all adjacent charts using the same projection/division/interpolation approach. When remeshing each chart, it could then greedily fill in quads between the chart edge and the global edge network (though using just those portions of the edge net that it borders). I still think this idea could work, but at that point I’d already spent a week or more on PQC and felt it was time to get back to more “practical” projects.

Unlimited clay’s concepts for dynamic topology

I noted recently that I would be looking into Farthary’s unlimited clay paper to see if it could be used for the dynamic topology project. Unfortunately, the paper is not quite detailed enough for me to reproduce his results. I had to make some guesses about the intended implementation, and quite likely I got some things wrong. I should note also that I probably need to code up a better version of local mesh relaxation to really test his algorithm properly.

On a more positive note, most of the work needed for dynamic topology sculpting is fairly generic. If I get it working well, and if at some future point Farsthary regains Internet access and is still interested in working on Blender, it should be much easier for him to work on this code. Recall that his original attempt at putting unlimited clay into Blender was pre-BMesh, so it used a somewhat slow hack for integrating EditMesh into the PBVH. That whole issue is now nicely avoidable.

And now…

So that’s three recent examples of things that haven’t worked yet. There are others, for example I’ve experimented a bit with getting MyPaint brushes in Blender, but not much of interest to say there. For now I will continue to focus on dynamic topology and the related BMesh-undo project, as well as some general bug fixing for 2.64.

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

I’ve made a lot of updates to the dyntopo branch on Github during the past few days.

Some of the changes include:

• Working smooth brush
• VBO drawing (this is enabled regardless of the VBO setting in the user preferences)
• Removal of loose vertices
• Much more robust topological edits
• Masks display correctly
• Hiding works, still some bugs though
• Builds with scons

A general outline of the work that yet remains:

• Undo/redo
• UI
• Brushes that require original coordinates (grab & co.)
• Stability fixes
• Limit topological edits to the areas directly around the brush
• Performance improvements
• Surface relaxation (to fix blocky appearance after subdivision)
• Surface merging (maybe as a separate brush?)

One side note: switching between sculpt and object mode is very unstable right now; when testing, recommend you switch in and out of sculpt mode from/to edit mode.

The following is in response to a question asked on Google+ about dyntopo’s relation to unlimited clay. This question comes up a lot, so I’ll answer here as a general reference.

Neither the new dyntopo branch nor my older adaptive-sculpt branch on Gitorious share any code or algorithms with Farsthary’s unlimited clay, but that might not be the end of the story.

There are two somewhat separate components at play here. The first is the underlying modifications to sculpt needed to support dynamic topology. This includes adding BMesh support to the PBVH, updating the drawing code to handle topology updates, and eventually undo support.

With just those changes in place though, you wouldn’t really see any difference from regular sculpting except worse performance and more memory usage. You need the second component: topological operators that change the mesh structure. This is what Farsthary’s unlimited clay was really about, an algorithm for adaptive topological updates.

At present, the dyntopo branch contains two of the three topological operators defined in the paper “Freestyle: Sculpting meshes with self-adaptive topology”. Specifically, long edges are subdivided and short edges are collapsed. (Surface merging is not implemented.) This is a quite simplistic model, and we might well want something better.  Farsthary wrote about his algorithm here; I will be examining it soon to see about using those ideas.