Rigging Tool WIP - ShapeKey Transfer Continued (Part 2)

After doing a bit more hacking, I've now got this tool working better for the remaining troublesome cases, and also substantially faster! How much faster? Well read on and download the script yourself to see :)

Same links as last time, but here they are again in case you need a reminder:
https://sites.google.com/site/aligorith/remap_shapekeys.py?attredirects=0&d=1  <-- the script itself.
It's probably possible to try and register/install this as an addon, but for now, I'd recommend just loading in a text editor and running to get it ready for use.

https://sites.google.com/site/aligorith/remapShapekeys_Test-01.blend?attredirects=0&d=1 <-- the test suite


Since my last update, I've been working on the todo's I mentioned in the last post (in reverse order, roughly similar to the order in which I worked on things):
4) Assorted fixes
- Support for timing how long the copy operations actually take has been added (used below)
- Hid more of the printing lines behind a "DEBUG" flag, though this is still enabled by default at least until I can be sure it all works nicely.

3) Drivers Support
As of r.36342, I've added the necessary PyAPI support for copying drivers in SVN. Having done that, I've now hooked up the support for copying over drivers for these shapekeys too, which means that you should be able to start animating immediately.

The downside is that this was after the 2.57b release was tagged for building, so unless we face a 2.57c release (horrid as the thought of it sounds), this tool will only work in SVN for the time being.

2) "Destroyed" test case working
Having written down the method already, coding it was a relative breeze.

The one point here I'd like to highlight is the threshold it uses for determining when a vert can be considered a match (the so-called "Neighbour Threshold"). This is performed using the source mesh's adjacency table, since if we used the target one, we may pick up a few merge situations as being ok (i.e. they'd be picked up as the triangle case below).

Originally, I was going to go with 3/4, which would mean that if a vert had 4 edges incident to it (i.e. the corner of a quad), this should mean that there are 3 verts that are connected to either outer-shells (i.e. 1) or neighbouring verts in the same shell (i.e. 2, one left, one right), leaving one edge leading to an inner vert (possibly another inner shell). However, this would fail if we were to encounter a situation where the vert was at the tip of a triangle, where it is connected to two verts from the outside, and to a single inner vert. Such a situation would therefore be a 2/3.

Now, what if in the 2/3 case we had two unknown verts fanning out from the current vertex? Well, that would be a 2/4 case, and since 1/2 < 2/3, it is dropped. 


1) Runtime Optimisations
I managed to get the total runtime on the production mesh down from 25.14s to 3.80s, by doing some code rearranging to minimise the amount of recalculation that takes place

By moving the building of the adjacency maps for the targets out of the inner loops (i.e. once per iteration instead of once per source vertex that hadn't been mapped yet), I managed to get some tiny improvements in speed. However, these were not as dramatic as I had hoped, and ended up shaving off perhaps only 3s at most. In the console though, the prints could be seen moving at two speeds (fast through the loops, pausing, then fast through another loop, then pausing, etc.) compared to only moving a single speed (i.e. slow but steady for every step).

At this point, I packed up for the night. Clearly something more had to be done.

In the morning, I suddenly had an idea. What if instead of going through and filtering/figuring out which vertices we knew how to map each time from the adjacency table, the adjacency table actually stored that information already, so that we'd just need to modify the few verts that we'd managed to match up? It's obvious now, but by setting up the data structure in this way, we can make it do more of the work for us (the age old: storage vs computation, or knowledge-base vs heuristic search from AI), and apparently much faster too!

After making these changes, I also noticed a few other places where things had been running a bit slow. One such place was the building of the adjacency tables, where I had been firstly copying the keys of the unmapped-verts mapping (i.e. the indices) to a list before passing that to the adjacency table builder for clarity, but it turned out that this was actually causing a bit of an unnecessary lag in this part of the process which I had previously been blaming on the large number of edges instead. This seemed to shave off quite a bit of time off that step.

With these changes in place, I set about checking that everything still worked. At this point, I made a surprise discovery: I had a stray (i.e. no edges are incident to it) vertex left in the target mesh! While the old method would have overlooked it, the new method would not be able to find an entry in the adjacency table for it, and would crash (before I fixed it, that is). It took a bit of error printing and manual checking before I verified the cause. So, this is a good example of why we shouldn't just test on simple artificial test-cases all the time, but rather on some complicated wild-world specimens instead! 

---

It should be working much better now, so go out and try it out on some of your own characters/meshes. Barring any problematic cases, I'll look into getting this into one of our SVN repositories for scripts/addons, and then we'll see where we go from there.

Weightpaint support should probably be quite straightforward to add (I haven't checked yet, though I don't imagine that there should be any terrible problems there), though UV's might be more difficult and better left for after my SoC work this year.