Automated topology improvements

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.