Retopology: Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization

[dfelinto]

Hi,

During Siggraph I met Martin Heistermann. Martin is finishing a phD on quadmesh retopology algorithms and was interested on implementing his algorithm into Blender in the future.

The webpage of the project is Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization — AlgoHex.

I was wondering whether this solution is battled-tested in production, and he asked me to think of some example files that could be used for testing. I would like to hear from other artists/developers what are the cases where the current retopology tool (QuadFlow Remesh) falls short (.blend please?), so we could compare with his solution.

For anyone wanting to try quadwild-bimdf yourself, the best way is to check the command-line interface for now.

More from him (shared with his permission):

Without running any code, you can get a quick glance at possible results from a few renders in the paper (made with Blender, of course). For a more complete picture, we have our whole dataset available, containing results of many different algorithmic variants.

We don’t (yet) have a nice browsing interface for the dataset, but to find “interesting” models in it, you could use the browser from Nico Pietroni’s QuadWild webpage: https://www.quadmesh.cloud/300/ (note that their quad mesh results are not identical to ours).

All results in their as well as in our dataset those were obtained in a completely automated fashion without any parameter tuning or other intervention, which of course limits the result quality in some cases.

For that reason I believe it’s super for a useful end-user-facing tool to include (optional) fine-grained control over the individual steps of the meshing pipeline to get desired results, instead of pushing one button and hoping for the best. From watching some retopology videos on youtube (in an attempt to learn what the real-world requirements of the task really are), I get the impression that currently it’s mostly an all-or-nothing situation, with users either going completely manual or maybe manually improving the quad mesh coming from an automated tool. I think a retopo tool could be much more useful if a user can (optionally!) influence every step of the process. Wenzel Jakob’s “Instant Meshes” tool is a nice example for a (partially) interactive workflow, e.g., allowing a user to guide the cross field which determines desired quad orientations.

[dfelinto]

Oh I almost forgot, @sergey suggested me already that the Suzanne would be a good first test case, since it has its tricky detached eyes.

[meistermann]

Hi everyone!

First of all, a bit of context: The retopology tool I am proposing is an extension of the excellent QuadWild (https://www.quadmesh.cloud/). My work replaces one of many algorithmic steps in that tool (a solver for a specific mathematical optimization problem). Instead of using Gurobi (a powerful, but proprietary/commercial general-purpose solver) with our custom solver that is much faster - and maybe more importantly in this context - available as open source (MIT license). QuadWild itself as well as our extension of it, is GPL licensed.

As with all automatic retopology tools, you can’t expect perfect results in all cases, but if we can achieve a good integration with an interactive workflow (as mentioned in the quoted email above), I hope it could be a valuable tool for artists. Maybe even the fully automatic version of now? (I honestly don’t know how much work it is to manually fix flaws in an imperfect mesh, compared to starting from scratch)

Also, if it turns out the quality of the tool is not there yet, at least we can learn from your feedback what our future research should focus on I am still actively researching quad retopology algorithms, and I want them to be actually useful in the real world.

So, I’ll be very happy to test any input meshes you may have, and of course you’re also invited to try the tool itself. We have compiled executables and instructions for compilation that should “just work” (if they don’t, let me know). Be warned that the current commandline interface is a little bit clunky and you have to edit config files to change any settings. Also, if you find the prototype blender plugin in our repo, please ignore it It is currently just a “my first blender plugin” that barely works (and ignored all settings you give it), I didn’t really have any time to make it usable.

Re Suzanne:
The separated eyes are no problem at all, the individual mesh components are treated as separate meshes and re-topo’d on their own.
I performed 2 levels of catmull-clark subdivision (plus triangulation) and fed it to quadwild-bimdf. The edge flow in many regions is not nice (e.g. very obvious in the region around the mouth), but have a look yourself.
(EDIT: Note that the “clean” source of the mesh here won’t help the method much.)

Also note that there is no automatic detection/handling of symmetry, so if you have symmetry, it’ll be best to only feed one half into the tool and mirror it later on (not done here).

I can’t seem to upload .blend files here, so I put the mesh on my server:
https://tmp.mheistermann.de/suzanne_subdiv2.blend
(I am only allowed to post 2 links in a message a new user, so DIY instructions if you prefer an obj file: same url, just .obj instead of .blend)
(Let me know which filetype you prefer for pure meshes)

[meistermann]

I split this into two posts, as I am only allowed to embed a single image in one post.

To elaborate on the parts I think should be interactive instead of fully automated: Initially, a cross field is computed that assigns 2 orthogonal directions to each point on the surface, indicating desired quad directions. This is very similar to Instant Meshes, where they have a nice editor to actually obtain a cross field that matches the mesh you have in mind.

In the QuadWild pipeline in particular, that cross field is used to create a nonconforming (= with T-junctions) polygonal mesh layout, as shown color-coded in this screenshot:

This is also a point where I believe it would be good if a user could already modify this polygonal layout (Or we might even want to allow completely user-created poly T-mesh topology as an input?)
This poly layout is then “quantized”, that means every edge is assigned an integer length of quad subdivisions, then using these lengths, each polygon is split into quads.
This Quantization (which is the step our work focuses on) is an optimization process that can have different goals, e.g. regularity of the topology, minimizing distortion (actually getting geometry that’s half decent), and coarseness of the mesh. This is definitely something that a user should be able to tune by dragging a slider and getting fast feedback.
Note that when you run quadwild with default settings, it will have a final mesh smoothing step that can be pretty slow for large meshes; but if you leave this out, a preview mesh can be obtained pretty quickly.

[LazyDodo]

@meistermann

I split this into two posts, as I am only allowed to embed a single image in one post.

I bumped your trust level, should be ok now.

[meistermann]

Thanks @LazyDodo

I went ahead and halved suzanne and mirrored the result after quadmeshing:

(Note that in this case I disabled QuadWild’s automatic triangle remesher, as the input mesh has decent enough quality. It is very useful for bad inputs, but in this case, the result is better without initial remesh)
https://tmp.mheistermann.de/half-suzanne.blend or https://tmp.mheistermann.de/half-suzanne.obj

[MetinSeven]

The mirrored result looks nice, with relatively few five-sided edge singularities, but the algorithm has the same issue as all other auto-retopology methods, even the best so far (ZBrush ZRemesher / Blender Quad Remesher, 3ds Max Retopology modifier and 3D-Coat Autopo), and that’s spiraling of edge loops. It’s particularly apparent at the lower side of the mirrored Suzanne’s ear, and around the mouth cavity of the non-mirrored Suzanne.

[TheRedWaxPolice]

Looks like an improvement to quadriflow already…
Often times quadriflow creates holes when you use mesh symmetry…
The overall edgeflow looks nicer too…

[JulianPerez]

The results look very good here, but as @MetinSeven mentioned, the spiraling of edge loops seems to be difficult to handle, so that’s an area where having a manual input would come in very handy, like painting or indicating in any way how loops should go in certain areas of the model.

[JulianPerez]

This is a case I’ve encountered a few times, where the mesh is not quite hard surface and the resulting loops are not spiraling but they are not fully aligned with the shape either.

That was done Exoside’s Quadremesher BTW, Blender’s QuadriFlow just can’t handle something like this.

[thinsoldier]

@MetinSeven

spiraling of edge loops

I’d be happy if I could define a region (the ear) and say don’t let any spiraling edge loops escape this area.

[SpookyDoom]

For me the benchmark of Automatic Quad Retopology also is “Quad Remesher” also prominently used in ZBrush under the name ZRemesher. I would love to offer some of our meshes since we do a lot of retopology in house. Since they are all under very strict NDA I can’t, unfortunately.
(and just for the record: Even with QRemesher available we still do manual retopology of +90% of our models)

But as a general hint I completely agree with what was said so far: The ability to define edgeloops and as few spiraling as possible is top priority for any Quad remeshing Alogrithm for me.
Second closes would be a Heatmap for Quad density distribution.

I mean - if it will be “just” an upgrade to quadriflow that’s absolutely cool, too. Any improvement is fantastic and highly apreciated.

(edit) I did make this fellow here as a personal project over a year ago. If it would help I can upload some of the sculpted parts I used as base for retopology. He certainly is not under NDA

It may not be a good representation since I mostly used a very blobby sculpt as guidelines for clean manual topo:

If it helps in any way I can upload the sculpts above for testing, though. Just let me know if it’s useful and I’ll upload these parts.

Just in case - Link:

FCG_BaseSculpts.zip

[ZedDB]

After wrestling with quadriflow and other “push button, hope for the best” solutions, I think that something that is a bit more manual and controllable is a must.
Besides not being able to put loops where your want them on meshes that is going to be animated, even static meshes be a PITA as small details or extrusions can vanish. (Like the nose of Suzanne in the non mirrored result)

With more manual methods, it is easier to control the quad density on different parts of the mesh to make these areas better.

Despite all this, this seems to be much faster and much better quality than quadriflow (from looking at the paper). So I would be happy if this replaced that.

However, after talking to a lot of artists doing retopology, it seems to me like most would like to be able to create clearly defined patches that then gets automatically filled with quads.

[1D_Inc]

Hi.
Here is my (almost) manifold fireplace model which I made and shared for different stress tests.

Blend Swap | Marble Fireplace MF-0018

A downloadable manifold skull which could be used for similar purposes.

Also I technically can share this variable density retopo of a classic head.

They has 100% quads topology, but the topology is easy to corrupt it with triangulate+subd+decimate modifers actions.
Also the initial topology could be useful for comparisons.

[SpookyDoom]

@1D_Inc

They has 100% quads topology, but the topology is easy to corrupt it with subd+decimate actions.
Also the initial topology could be used for comparisons.

Sculpted hair is more or less the ultimate stresstest for organic subdiv retopology.

[1D_Inc]

Okay, David head is also available for download

It is more detailed than version from the dataset, and its topology follow shapes and preserve all the details, hope it will be useful.

Also a manual skull retopology by stripe-modeling process video cold be interesting for the research.

- YouTube

[1D_Inc]

+1 for the ability to define edgeloops and as few spiraling as possible.
It would be nice to have the ability to define the sharp edges manually and let the algorithm to fill the gaps between them automatically for the sake of a better control over result.

[ThinkingPolygons]

@ZedDB

much faster and much better quality than quadriflow (from looking at the paper). So I would be happy if this replaced that.

+1

Quadrifllow is almost useless at the moment tbh.

[SpookyDoom]

What is this black magic you are shwoing in your video, there?

[Stimes]

Well, I must say this topic is highly interesting, well-structured, and holds great promise regarding this new technology and the automatic retopology process it offers, aiming to provide meshes with exceptional mesh quality and regularity! I’m incredibly excited to witness the final outcome and the evolution of the algorithm. All I can say is, congratulations on your hard work and dedication! You’re poised to assist a multitude of individuals through your research and efforts.

Question:

• Have you already set a release date for a version of Blender? (E.g., Blender 4.1 Stable Release)
• Is it native to Blender or a downloadable extension?
• Will it replace the current “Remesh modifier”?