Many years back, I wrote some mesh manipulation code to help me with the development of my Antonia figure. The crucial features were subD and reverse subD transformations and a purely topological method for fixing vertex orders. I am now in the process of porting this code from Scala to Python 3 and was wondering if anyone might find it useful to have those features in the form of functions that could be called from a Poser Python script.

By purely topological I mean that the function does not have to look at where in space the vertices are, just how the vertices and faces relate to each other. There's of course the little caveat that if the mesh has symmetries, there will be multiple possible solutions and one has to be picked based on geometry. But for say, a human figure, that just means deciding whether the mesh needs to be flipped along the x-axis or not.

Now I realize Poser itself contains some functionality for fixing vertex ordering, for example when importing morph targets, but I'm not sure what algorithm is used there and what its limitations are. Hence my question here.

Oh sorry, I missed this!

Sure, I'm interested!

I am sure there would be a lot of interest, sadly, the scripting forum is not as busy as once it was. 

Thanks adp001 and structure! I'm still working on the code, but once I'm satisfied it's correct, I'll have a go at integrating it with Poser 12. I'm also happy to provide a Python 2 version if anyone wants it, but since the most recent Poser version I have before P12 is P8, I may not do a lot in terms of testing the integration with that one.

Let me sketch the basic idea for reference. I have a nice write-up that's unfortunately behind a paywall, but I could probably make a couple of screenshots and post them here.

If one looks at something like just the 'f' lines in an .obj file and disregards the normal and texture information, that completely describes the topology of a mesh. So cutting this down to just the lists of vertex indices and replacing the line breaks with vertical lines for compactness, a cube might look something like this (assuming I made no errors):

1 2 3 4 | 2 1 5 6 | 3 2 6 7 | 4 3 7 8 | 1 4 8 5 | 8 7 6 5

This is of course far from unique. For starters, I could replace the second section 2 1 5 6 with 1 5 6 2 without changing anything. In general, seeing as we want the vertices to be listed counterclockwise when we look at the object from the outside, for any quad I have four ways to write it down depending on which vertex I start at. So with the convention that we always start at the vertex with the lowest number, for the cube we'd now get this

1 2 3 4 | 1 5 6 2 | 2 6 7 3 | 3 7 8 4 | 1 4 8 5 | 5 8 7 6

In the next step we can also sort the faces lexicographically:

1 2 3 4 | 1 4 8 5 | 1 5 6 2 | 2 6 7 3 | 3 7 8 4 | 5 8 7 6

So that's kind of nice in that for a given topology and a given assignment of numbers to vertices, it produces a unique string describing this topology and vertex numbering. But actually that's just the warm-up, because now we have to take all the different ways to assign number to vertices into account.

(Splitting this up a bit in case the forum eats my comments.)

So the basic idea now is that for a connected mesh, we can go through all the ways of assigning numbers to vertices, construct the unique string that describes that specific numbering, and pick the smallest of all those strings. Doing this for two separate meshes gives us the exact same string if and only if those meshes have identical topology, and the two vertex mappings we used to go from the original mesh description to that so-called "canonical form" can be used to construct a correspondence between the vertices of the two meshes.

For the cube there are only 40320 ways of assigning numbers to the vertices, or 840 distinct ways if we take symmetries into account. That's easy to go through with a computer, but for a typical Poser figure with tens of thousands of vertices, that's of course completely out of the question.

So we need a way to drastically reduce the number of vertex number assignments we need to look at. Noticed that I snuck in the word "connected" up there. For a connected mesh, once we pick a vertex to assign the number 1 to, and one of its neighbors to assign the number 2 to, there is in fact a simple algorithm that uniquely assigns all the other numbers. That algorithm is basically just a breadth-first search with some extra rules determining which order the neighbors of a vertex are to be visited in.

So that takes us down from a number of operations that to call astronomical would be a massive understatement to maybe a few billion at worst. There are extra tricks one can apply to reduce that further, for example to always use a pole as the first vertex, stop as soon as it is clear that the new numbering cannot be better than the previous best, and so on. My implementation starts at a pole with the largest degree, which reminded me that Antonia has four 6-poles in her gums. At any rate, from my tests so far it looks as if the final method is quite fast. It takes less than a second for the roughly 38k vertices in Antonia's main body mesh.

There's some extra work to be done for non-connected meshes, but it is basically just an extension of the same idea. Also if a mesh had more than just the one bilateral symmetry, one would have to take those into account when matching two meshes with each other. But I think at least in the Poser world, that's probably not a very common use case.

Interesting development! No problem if the numbering is not optimal as long as the result is consistent.

The issue of ordering and renumbering has been on my mind for quite a while, to please forgive me to throw in a few bits. They may be helpful or not. If they are not, or when I completely miss the point, please disregard this.  

I always wondered why we bother to save both the positive x side and the negative x side of a base mesh and then worry about keeping it symmetrical. If we would, for a mesh we want to be symmetrical simply store only the zero-or-positive x side and leave it to Poser to build, while loading, the symmetry according in a consistent process, our meshes would be always symmetrical and because it can be recorded which vertex is the symmetrical twin, we would have a direct method to mirror morphs and vertex weights. The one-side definition of course would be in both 2D and 3D, leaving the uv's symmetrical around u=0.5. 

Obviously any tri's with 2 vertices with both x = 0.0; u= 0.5 would have to be resolved to quad kites.

This simplification would as far as I can see:

- reduce the sorting work by a factor 2. 

- give a general direction for the sorting work: from x=0.0 (or minimal if the model does not cross) 

- give a 2d starting section (at x=0.0) in which ordering is more easily done than in a 3d section. 

One more thing about 6-poles: they could serve as a point of recognition, so starting point. Whatever reordering of vertices took place, if the topology is not changed,  a 6-pole remains a 6-pole. If one exists, it may be the best point to start the search. A connected 5- pole could provide orientation. 

.... which brings me to the suggestion for meshes that may be subjected to a process of vertex number reordering but not topology change to ensure a unique combination of n-poles exists ( by cutting up a few quads) that in the process of re-establishing the original numbering can serve to uniquely identify the vertices to start the restoration.  

This would work also in case the uv mapping is not retained, and serve to assist the restoration of uv's as long as the islands are left intact.

Forgot to add: After restoration of the vertex order the tris around the n-poles can be replaced with the original quads. 

Some interesting ideas, @FVerbaas, not too unlike some I've toyed with myself. I guess Antonia may have a bit of an unfair advantage with those 6-poses, but I don't think they're strictly necessary in order to get reasonable execution times. I think the code will soon be at a point where it makes sense to throw some of the other figures I own at it and see how the long the computation takes. Then I'll decide if it makes sense to be more fancy about combinations of poles. I think it's quite likely that most figures have some unique constellations, and it would not be too hard to look for them by following edge loops. But I'm still suspecting that's not really necessary.

By the way, Antonia's 6-poles are actually a bit of a pain in my butt, because they're right in the center and break up the nice edge loop that would otherwise split the left from the right side. Blender does not seem to follow edge loops through vertices of degrees other than four, even if the degree is even. I don't know if it's a conscious decision or if they just didn't foresee that someone would be silly enough to make a mesh with 6-poles.

About the idea of only storing half the mesh because of bilateral symmetry: it sounds quite intriguing at first. But I've done decades of work with implicit meshes where one encodes only a part of the mesh and applies symmetries to get the complete shape, and those things get way more tricky than one would imagine. Usually I switch to a regular mesh as soon as I can get away with it.

The idea of artificially introducing unusual poles might actually be helpful with loose parts such as eyes, lashes, teeth, finger- and toenails. Especially when there are several parts with the same topology and possible some extra symmetries, finding the correct correspondence could be tricky based on where the vertices are.

If one controls the exporter, one could add some dummy faces to make the whole mesh connected and remove them again on import and after matching. But that would probably destroy some of the advantage of having loose parts in the first place. For example, in Blender I can hover over a part and press "L" to select it, then hide everything else.

Mangling the topology somewhere in a corner of such a part might be less obtrusive, although it could  still lead to unexpected results when morphing.

Probably the best solution for loose parts would be to find the closest vertices in the main mesh before morphing, see where those vertices go in the morph and match with the part closest to those positions.

That might still break down for figures where the inner and outer eye spheres have exactly the same topology, so in that case one might have to fall back on shape.

So, I just tried my code on some larger meshes, including the original Miki, and have I ever mentioned how much I love snakeviz?

It turns out that Miki has at least one 13-pole, and the Gen3 DAZ figures have 16-poles. I feel less bad about Antonia's 6-poles now.

Also, can someone remind me what the deal is with the extra face-less vertices in exported Poser meshes? I got that for La Femme, and my script didn't like it.

Last comment for today, I promise: the Gen8 female has a 6-pole in her ear, and that one, unlike Antonia's 6-poles, actually makes sense.

The unconnected vertices in LF may result from Poser Unimesh export. That option 'welds' identical vertices keeping AFAIK the vertex with the lower index number and making the vertex/ices with higher number obsolete. This of course leaves the original numbering intact, so weights and morph deltas still work, but this results in unconnected vertices that may cause problems in other apps. These other apps may clean the mesh, throw out the unconnected  vertices and so mess up the numbering.  

I was under the impression your quest aimed at solving exactly that problem. 

Thanks for the explanation! No, I hadn't been thinking about that specific source of mangled vertex numbering. My feeling was that it's just generally a big nuisance to be so uber-careful with one's workflow to avoid the dreaded renumbering.

Anyway, orphaned vertices shouldn't be a big deal. I'll just teach my script to tolerate them.

A worse offender are non-manifold meshes. Apparently Apollo Maximus has an edge somewhere that belongs to more than two faces. Very naughty! There are probably ways to deal with that kind of thing, but unless I come across it in a mainstream figure, I simply won't.

Okay, it looks as if I've got isolated vertex support working now. I should probably run some more tests and also add some special code in order to not treat them like regular loose parts. Turns out La Femme's personal best for poles is 14, so the Gen3 figures still hold the record with 16.

By the way, I've got the code on github in case anyone feels like following along: https://github.com/odf/pydeltamesh

If anyone *is* looking at the code, be aware that I probably won't keep the mesh API and data structure like that. I pulled it from a library in a very different language with a very different purpose just to have a starting point. Since I'll be writing something that'll play nice with Poser, I'll soon take a look at how the Poser mesh API works these days. If I recall correctly, Numeric was still a thing the last time I did that.

1. You are aware Poser12 supports all of SciPy (see SciPy.org), right? There's quite some stuff there that may be useful.  

2. Non-manifold meshes are quite common in clothing models. Think of ruffles and hems. In conforming garments you do not need structural integrity, but in dynamic garments it is essential. In figures they may appear in eyelashes etc. You could consider the non-manifold edges as free edges 

Thanks again for the info and the SciPy reminder! We use SciPy at work, as well. I've spent a few months speeding up our production code and a large part of that was removing certain Numpy and SciPy calls. (Fine print: and mostly replacing them with low-level Numba code.)

I'll see if I can figure out where Apollo's non-manifold bits are located. I think lashes would be fairly easy because if I "cut" the mesh along the offending edges, the main part would still remain connected. Ruffles in a garment that go all around would be much trickier. Probably not worth trying to support in the first version, but it's an interesting problem to think about.

With something like ruffles, I think the key would be to recognize what's the main mesh and what's the attached part. If I'm naïve about it and just systematically try out all possible matches at all the attachment edges, the complexity of the algorithm would explode.

If it's something like a polygon-efficient eye construction, on the other hand, there's no obvious main and attached part, but in that case there would only be a single "gluing" line, which is probably fine.

Honestly, clothes could become quite the nightmare for any attempt at a purely topological matching algorithm. But if the garment is fully UV-mapped, one could cheat and use UV-positions for resolving ambiguities.

Since there are (far) more garments than base figures, and the garments have much greater freedom of shape variation (volume,  folds, dynamic effects) I expect there will probably be more demand for re-establishing vertex order in garments than in base figures.

In the UV domain there normally should not be any non-manifold edges so indeed jt would be an easier starting point. Also most used apps doing geometry alterations will not change the 2D representation. (It would be a good thing if they did, but that is another discussion.)

A good 2D representation in general is much more powerful and straight-forward. It would work even after complete remeshing, provided the shape and location of the uv islands is maintained. Maintaining continuity at edges/seams needs attention though.  

Interesting rabbit hole we've stumbled upon there.

Wanna jump?

We'll see. Two more weeks until I go on my personal projects summer break. Then I'll have plenty of time to ponder these things and decide how deep I want to go into the rabbit hole.

To whom it may concern: I just checked and it turns out that Apollo's naughty - i.e. non-manifold - bits are the eyes and his upper jaw-partial-glued-together-teeth thing. The eyes I can somewhat understand, but what's going on in that mouth is ... strange.

So, I had a little email exchange with a friend who knows way more about these things than me, and now I'm pretty confident that I can do non-manifold meshes in reasonable time.

Ha, I just made myself a simple test case without meaning to. Did a little head morph in Blender for practice and forgot to import with the option to keep the vertex order. Argh! Well, more motivation to get this to a usable state soon.

So API-wise I'm now thinking I will define a class called Mesh or TopoMesh or something like that, the initializer of which would take a list of vertex positions and a list of face definitions, and that class would have an instance method vertexMapping that would take another instance of the same class and spit out a list specifying how to renumber the vertices in the argument to match self.

I would have normally preferred not to use classes, but performance could be a bit of a concern for larger meshes. So I'd like to avoid any necessary or duplicate computations, and a class with lazily computed instance properties is a fairly painless way to do that.

s/necessary/unnecessary/

So processing Miki with my current code takes a staggering 20 seconds because her eyeballs are cylinders. Lots of polys and 120 symmetries, so none of my clever shortcuts work. Other eye parts are similar. The Gen8.1 female mesh straight out of DS has more than twice the polys, but takes less than half the time.

If I were to make a face morph, I'd export the eyes separately, but I'm not sure if that works for full-body morphs. Probably not too worrisome in the grand scheme of things, though. Now I also wonder if Miki 2 etc. have similar quirks.

Okay, so technically the eyeballs are UV-spheres, it's just that the vertices at the top and bottom ends are not merged. It wouldn't help with the algorithm if they were, I just would have been less confused about the topology.

It would probably not be too hard to recognize proper UV-spheres and handle them specially if that turned out to be a serious bottleneck. Weirdly broken UV-spheres not so much, I fear.

So processing Miki with my current code takes a staggering 20 seconds because her eyeballs are cylinders. Lots of polys and 120 symmetries, so none of my clever shortcuts work. Other eye parts are similar. The Gen8.1 female mesh straight out of DS has more than twice the polys, but takes less than half the time.

Straight out of DS means subdivision level 2, apparently. Base level is obviously much, much faster. But ideally we want to match subdivision morphs, as well, so the fact that a quarter million vertices can be processed faster than I can put on the kettle for a cup of tea is very  encouraging.

I'd be interested in a Python 2 version of this if you're entertaining the notion... I'm generally pretty careful, but I imagine I'd find instances of usefulness to be less careful if presented the option.

...as an aside I use Colorcurvature's PML exporter script almost continuously, so the script might be redundant for my usage. PML's exporter/loader seems to do a welding /difference/post transform interpretation that's just ridiculously useful for morph "layering" operations, at least from a figure perspective. I can definitely see the need for that amongst Poser 12 users... and the main reason my installation of 11 will remain present for the foreseeable future. The fact that full Unimesh is verifiably a very real end goal in Poser development keeps me hopeful, Nerd himself mentioned the additional possibility of subdivision morph target obj files also being feasible.

Anyway, still interesting to eavesdrop on the commentaries here, even if I don't speak the language in certain aspects.

primorge posted at 6:24 AM Sun, 28 November 2021 - #4430971

I'd be interested in a Python 2 version of this if you're entertaining the notion... I'm generally pretty careful, but I imagine I'd find instances of usefulness to be less careful if presented the option.

In the near future I might write a bit more about tie breaking - the case that one has multiple loose parts, all with the same topology. Something like finger nails comes to mind, also lashes, eye parts and possibly individual teeth if the modeler was a bit  lazy there. What one needs in that case is to use extra information such as vertex positions or UVs to evaluate how good a part of the base mesh matches one with the same topology in the morphed mesh. What I think I will do is use positions by default, but allow the caller to pass in a custom quality function. Then in order to handle tricky cases well I'll probably use a Ford-Fulkerson style method to determine the final matches.

primorge posted at 6:47 AM Sun, 28 November 2021 - #4430973

Anyway, still interesting to eavesdrop on the commentaries here, even if I don't speak the language in certain aspects.

Yeah, I agree that the script would probably be redundant for most cases with today's software. More of a safety belt in case a numbering accident should happen. Back in the day with my weird Wings3d work flow it was absolutely essential.

@FVerbaas So it turns out that I can in fact make use of SciPy, specifically scipy.optimize.linear_sum_assignment, which is exactly what I needed for resolving ties.

By George I've got it!

This is Antonia's head together with a morph I made in Blender without ever using the "keep vertex order" button. I haven't written an .obj output function yet for my script, so haven't tested in Poser, but the two meshes shown here (via PolyScope) use the exact same face definitions, so if the vertex renumbering hadn't worked, we'd know it.

Now that I have the complete algorithm done, I looked at the execution times for various figures.

Miki takes the cake with 45 seconds for loading and processing, which goes down to 7 (!) seconds if I leave out her eyes. The fastest of the ones I tried were Gen8.1 at base resolution with about 1.5 seconds and Antonia low-res with 1 second.

That's of course on my new computer I bought in January with a relatively beefy CPU.

API question: when I grab the face data for a mesh from inside Poser, do the vertex indices start at 0 or 1? If it's 1 like in .obj files, I might make that the default in my script, but if it's 0, it probably makes more sense to go with 0 internally and tweak the face lists upon reading and writing OBJs.

Forgive the attention-grabbing eye candy, but I'm almost ready to "release" the first version of the code, where release will probably just mean to tag it with a version number on github. It's easy to download a ZIP file for a github repo, so I don't really see a strong reason to host the code somewhere else.

If no one complains, I will be assuming that vertex numbers start at 0 as far as the API is concerned, so when reading from and writing to OBJ files I will subtract/add 1.

Speaking of the API: there will be two functions, topology() and match(). The first takes a list of faces and a list of vertex positions and returns a preprocessed object. The second takes two such objects and an optional cost function and returns a list of pairs where each pair contains a vertex number from the first argument and the corresponding number for the second argument. The metric function should take two lists of vertex numbers and return a number that measure how well they match, smaller numbers being better. If none is given, the distances between paired-up vertices according to the provided lists are used. An alternative could be to use UV coordinates if present or say group information and such, but I suspect in most cases vertex positions will do just fine.

Does that sound reasonable? I can post an example if the description is too abstract. But there'll also be a simple "applyMorph" script as part of the "package."

Okay, first version is a go. I'll start a separate thread on it.