Pushed some changes tonight that improve the output of dyntopo when collapse edges is enabled. Should fix the random “flaps” of isolated triangles. Various crashes also fixed.

I’ve just pushed updates to the dyntopo branch that fix the grab, rotate, and thumb brushes for dynamic-topology sculpting.

Since these brushes rely on grabbing a static set of vertices, the topology is not updated by these brushes.

I’ve pushed a few updates for dyntopo:

• As a follow-up to yesterday’s post about better flat-shaded drawing for regular sculpt mode, you can now toggle between smooth and flat shading in dyntopo. This is just a display setting for now, doesn’t alter the actual mesh at all.
• Edge collapse is now available again, but disabled by default. When making large alterations to the mesh (e.g. with the snake hook brush), you can enable the “Collapse Short Edges” toggle to get smoother and more regular topology. The trade-off is that, while enabled, brushes will tend to erase fine details. For example, if you use the crease brush to define a sharp indent in the mesh, you probably don’t want to collapse short edges in that area.
• Added a “Simplify” brush that only modifies topology. It’s pretty much the same as using a regular brush with zero strength and Collapse Short Edges enabled. (Note that as this is a new brush it won’t show up in your brush list by default, you have to add a simplify brush manually.)

OK, time for some updates. Based in part of some useful feedback on BlenderArtists, I’ve spent the past week experimenting with various approaches to the topological update step. I think it’s now getting much closer to what people want to see; in particular the subdivision is localized to the area directly around the brush.

Until now, the topological updates were based on the paper “Freestyle: Sculpting meshes with self-adaptive topology”. This paper assumes that the entire mesh will have a consistent detail size. Note that since the algorithm collapses short edges, you can lose detail if you change your brush to a coarser detail size.

In contrast, the approach I am using now is to only do edge splits. If you create very dense topology and then set a coarse detail size, the dense topology will remain and not be collapsed. To handle situations where you want to make the topology less dense, a separate simplify brush will be added. (I haven’t done that yet, but the code is largely already written.)

In order to get a good boundary between a dense portion of the mesh and larger polygons, I used a trick that Farsthary described in his unlimited clay research: identify nearby pole vertices (in this case, defined as having nine or more adjacent edges) and split the adjacent edges. This isolates the pole vertex and prevents it from distorting the mesh. This wasn’t an issue with edge collapses, which implicitly force triangles to be relatively regular, but in a subdivision-only approach it turns out this is a really critical step. Without it the mesh quickly develops degenerate triangles that can’t be smoothed away.

Some other changes: the topology update now occurs before each sculpt step, so the result should match the brush shape a bit better. The brush also avoids the accumulation problem now, so repeatedly brushing over an area won’t continually build the surface up (unless the brush accumulate option is on, of course.)

I’m still looking into surface relaxation; I suspect a smoother result can be achieved while still maintaining detail, but haven’t found a good way to do it yet. My current short-term goal is to do some brush work: add the reduce/simplify mentioned earlier and fix the guaranteed-crash brushes like grab.

As usual, the code is available from the dyntopo branch on Github.

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.