Automated topology improvements

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.

7 thoughts on “Automated topology improvements”

  1. Wouldn’t a uniform face size be the perfect goal? If two variations of topology only vary by x% average face size then you are as close as you will get.

  2. A more clean and subsurf friendly topology for re-meshing sounds really cool.

    I would also love to see Shane’s idea implemented in the Remesh modifier, because if i currently sculpt a mesh bigger and remesh it with the same octree level as before, i loose details (the faces become bigger).

    batFINGER made a modification of your Dynamic-topology Script for me, that make it possible to change the octree-level in a textBox. Maybe an idea to have something like this in sculptmode by default, because remeshing is so powerful for sculpting and the remesh code is already there.
    Link:
    http://blenderartists.org/forum/showthread.php?255149-Request-Number-Box-for-changing-octree-depth-in-Nicholas-Dynamic-topology-Script

  3. Omg, omg, omg! Another great feature for Blender! You should call yourself: Nicholas “the godfather of coding” Bishop. :-)

    I’m going to visit your blog every day to see an update. ;-)

    Great work!

Leave a Reply to Ike Cancel reply

Your email address will not be published. Required fields are marked *