I finally spent a bit of time re-implementing my skin weight loading script in the api – more specifically, the python api bindings.  why?  well mel is super slow when working with skinning and I figured doing it in the api might help relieve the problem.

some numbers for you.  for a 3000 vert character its roughly 21 seconds using maya.cmds.  if you tune the numbers you can get that down to 12 seconds, but lets assume worst case scenarios here which I’ll describe in a bit more detail soon.  so using the api to do vertex iteration and skin weight assignment takes that down to 8 seconds.  thats a speed up of 2.4 times – which is not huge, but nothing to be scoffed at either.  lets looks at some details.

first up, the searching is being done entirely in python.  so given a vertex, i need to search through a cloud of 3000 points to find the closest matches in python.  the best case scenario above (12 seconds) uses a tiny search radius, which is useful for restoring weighting with minimal mesh changes.  the worst case scenario is for restoring weighting when the mesh has changed drastically – which happens, especially early on.  so the worst case scenario the search radius grows until it finds some matches, and then it averages the weighting found for the found verts and applies the weighting.  so it is this worst case scenario which is the most interesting.

so how does the searching work?  well basically it uses a binary search algorithm on the point cloud.  what does this mean?  i didn’t really know what a binary search was either until recently when a programmer friend of mine told me.  its pretty simple: basically given a sorted list of values, you look at the middle value and figure out whether the value you want to match is greater than or less than that value and throw away the other half of the values.  because its sorted you know the best match cannot be in that half.  so with each iteration of doing this, you cut the number of values you need to search in half.  do this a few times and you’ve narrowed the number of values you need to do more expensive comparisons on to a mere handful.

so using a simple binary search algorithm you can do searching pretty quickly.  ideally you’d write some sort of spatial partitioning that considers all 3 values instead of just one value, but that is more complex and I got really good results using a simple binary search.

so anyway, the search uses the same code for the maya.cmds and api method (this code sharing is one of the many awesome things about python.  in fact I also use the same search code for tools that don’t live in maya at all).  the main difference between them is how the skin weights are actually set.  using maya.cmds.skinPercent is really slow when you’re doing it many thousands of times.  but swapping this out for the api (which isn’t quite as easy as you’d think – you basically need to restructure the entire loop to use the MIt classes for iteration) gives you the speed improvements above.  so now i just need to figure out how to speed up the search algorithm.

i could write it all in c++, but then I have to worry about things like writing data to and from disk when storing and loading weighting data.  plus its harder to share code.  the way i’ve done it now, the searching algorithms are actually used by non maya tools, so improvements there are felt across tools instead of just within maya.  so yeah, c++ sucks for all of the above.

This entry was posted on Friday, January 29th, 2010 at 11:55 and is filed under main. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.