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.
Quick test of dynamic topology. The original mesh was a cube (12 triangles.)
I’ve pushed the dyntopo branch to my github repository, so you can give it a try if you’d like. The code is only about two days old now, so be warned that it’s at a very incomplete stage.
There’s no UI for dynamic topology yet, so as soon as you go into sculpt mode (on a non-multires mesh) it’s active. At some point of course, a switch will be added so you can choose between regular sculpting and dynamic topology.
The detail size is hardcoded at 0.1 BU right now, so you can increase or decrease the mesh density by scaling up or down in edit mode.
Note also that plenty of brushes and features don’t work yet, notably the smooth and grab brushes, as well as undo.
Supporting undo will likely be the biggest challenge for dynamic topology; it’s not at all clear how to store undo data without copying the entire mesh (which would cripple performance.)
Just a quick note to say that I’m (a) not dead and (b) working on dynamic topology for sculpt mode again (see crappy screenshot.) I have a lot more to say about this (and other topology-related stuff), but I want to get the code a bit further along first.
Top left: original mesh. Top right: mesh with SPR. Bottom row shows the subsurfed versions.
Getting a bit closer with SPR, image at right shows my first successful test on “real” input. There’s still more optimization work needed to make this practical (even this small input sample takes about five seconds to finish calculating), but that’s for tomorrow (been up all night, now 7am here), so time for some sleep… but nice to have an actual result.
Tests on various inputs. It gets interesting towards the bottom; note that the very last shape at the bottom could be remeshed many different ways, but it has automatically chosen a set of quads that results in no extraordinary vertices, producing a nice looking grid.
As Blender’s sculpt maintainer, I’m always interested in improving the “clayish” nature of the tool. Ideally you shouldn’t have to think much about the underlying topology and resolution of your mesh. We’re obviously a long way away from that goal (although unlimited clay and dynamic topology sculpting have shown a couple interesting approaches.)
The remesh modifier is also a step in the right direction; it can take an ugly input (non-manifold, stretched polygons, low-res, etc.) and make the output reasonably OK for sculpting. Unfortunately, it isn’t shy about outputting extraordinary vertices (vertices with less or more than four adjacent edges/faces.) The result therefore doesn’t have that nice grid-like structure you’d get from creating a low-res base mesh and subdividing with Catmull-Clark.
There are many potential ways to address this shortcoming; there is a lot of research out there on different remeshing techniques. At some point we may indeed implement additional remeshing algorithms for the skin modifier other than dual contouring. For now though, I’m looking into a simpler post-processing step that could be used to clean up the remesh modifier’s output (or any mesh, really.)
Essentially, the idea with SPR is to find extraordinary vertices in the input mesh and replace the local neighborhood with a set of polygons that contain fewer extraordinary vertices (ideally no extraordinary vertices.) Once an irregular patch is found, all possible replacements are tested to find a better result, and the best one replaces the original irregular patch in the mesh. Repeat until no further improvements can be found.The specific technique I’m attempting to implement is called SPR (from the paper titled “A new method of quality improvement for quadrilateral mesh based on small polygon reconnection” by Jian-Fei Liu, Shu-Li Sun, and Yong-Qiang Chen). The algorithm only works on quad meshes, though of course you can convert a triangle mesh into a quadrilateral mesh as a pre-processing step. The remesh modifier’s output is all quads though, so it fits well there.
The real trick is that even for relatively small patches, the number of possible quad remeshes is huge. Without aggressive pruning, even ten or twelve vertices could take many minutes to finish (it’s a O(n!) search space). Clearly anything that slow would be impractical for use in Blender, so the real trick is figuring out how to stop a dead-end search path as early as possible.
So! That was a lengthy bit of explanation. The code is basically working now, although for now I’m testing it by replacing simple ngons (optionally with unconnected internal vertices) in 2D before attempting full mesh cleanups. It’s still not working fast enough to be practical, but I’m hopeful that with additional pruning tests I can get the time down quite a bit. The image at the top of the post shows examples of the output.
