Procedural mesh skinning

Hey,
I'm struggling with some logic on creating skinning code at runtime.

Background info:
-user creates the character mesh
-user places the joints.

Everything is in place, now the final step is to bind the mesh to the joints in a visually pleasing way

As a start, I'm looping through all vertices and attaching them to whatever joint is closest in 2D space.

This is a good start, but obvious problems occur quickly. For example, technically, the verticies on the foot here are closer to the hand than they are to the leg. The problem areas are circled in red.




Its easy for you and I to see with our eyes how it should work, but I'm in search of a set of rules that I can implement on a per vertex basis while in the loop. I'm thinking something that has to do with grouping of vertices and local connections? Perhaps something based on the immediate neighbor vertices? Maybe multiple passes?


If anyone has experience with this, fresh ideas would be welcome! Thanks!

 

Assuming that neighbor triangles/vertices is actual indexed at +- 1 in your arrays then you could iterate through them until you find that a joint position is inside a triangles.

http://www.blackpawn.com/texts/pointinpoly/

 

@BFgames Thanks! That was helpful.

Alright folks, here is an update.

I will start with the order in which things happen

1) I start with a group of outline points
2) Then I create delaunay triangulated mesh with steiner points
3) User defines the joint locations
4) I calculate limb width (by sending perpendicular rays and seeing where they intersect the outline)




The last step in detail. The reason I calculate the width of the limb: For example: if I was doing a flood fill on the verts in the lower hand, I would want a way to ensure I set up a blockade from the fill leaking into the upper arm.





My master plan is to start with the limbs and work inwards toward the body.

1 - Start with the closest vert to the right hand
2 - loop +/- until I reach the right elbow
3 - color those limbs appropriately and assign their bone weight to be 1 for the right elbow bone
4 - repeat for right upper arm etc

I think this is correct in theory, but the +/- loop isnt enough. Sometimes I reach the right elbow before I have completely filled the lower arm

Here is the process if I live update the mesh while its happening. (In this example I am only using 1 vertex as a "stopper vert" instead of a group, so there are lots of "leaks"), But it gives you a good idea of the unpredicatableness of the mesh.

But either way the problem still remains as a standard loop isn't thorough enough.

So I think I need another solution. Something that works flood fill for pixels, and checks all possible directions?
I probably need to use something other than +/- vertices since they are so unpredictable in their layout.



Sorry for the rambling, some fresh eyes on this would be helpful.
Anyone have any suggestions?

PS HAPPY 4TH OF JULY!

 

You might want to look at some papers on heat map skinning - here's a page with an easy to understand description (although this particular version uses voxelization) http://blog.wolfire.com/2009/11/volumetric-heat-diffusion-skinning/

 

@ecurtz Thanks so much! I should have looked around more before trying to implement my own shoddy logic. It appears there is a good deal of research in automatic skinning.

Incase others are looking I will make a big list of helpful topics and examples of automatic skinning out in the wild:
Pinocchio Automatic Rigging - http://www.mit.edu/~ibaran/autorig/pinocchio.html - Youtube Example - https://www.youtube.com/watch?v=EklzamltEgM
Blender's Bone Heat weighting - http://www.blender.org/development/release-logs/blender-246/skinning/
Maya PM_heatWeight plugin - http://www.creativecrash.com/maya/script/pm_heatweight
After Effects Puppet Tool
Mixamo Auto-Rigger - http://www.mixamo.com/c/auto-rigger

Note: I don't need anything as polished as these above examples, just something that is better than my first post would be a good start.

By far the most helpful blog post on understanding the whole process was by David Maletz found here:
http://david.fancyfishgames.com/2012/07/bones-and-automatic-vertex-weights.html

The core problem is that by using eulcidian distance to calculate the boneWeights, you will almost always get problems like my first post. The key is to get the geodesic distance, which is the distance within the mesh.

Dijkstra's algorithm is one example of geodesic distance, here is a good visual example of it in action.
http://www.youtube.com/watch?v=0aGz4eh5XG4

Since Unity's pixel operations are pretty slow, I've decided to go the voxel route as described in the Wolfire blog post. Here is my character voxelized. (big voxels for performance)








If I understand it correctly I need to run a version of that algorithm on the entire voxel set, 12 times, starting once from each joint.
I can then loop through the verts and set boneWeights by looking up the distances of the voxel in the same location.

I'm a bit worried about getting an algorithm that can calculate the geodesic distance for these bones in a reasonable amount of time on mobile. I would like to keep the wait time to under 3-5 seconds, I will report back with how it goes.

Any more words of wisdom would be helpful!

 

Hey guys! Just reporting back to say I figured it out! At least the first stages, It was a good amount of work, but it was more daunting to wrap your head around than it was to actually code it

Here's what I did:
-I created a voxel model of the character,
-Grew bones between limb joints (white lines), used all intersecting voxels as starting points for Dijkstras Algorithm. Using a whole bone vs just a single point for a a starting location is very very important and makes a big difference.

Here is an example of an influence heat map of the upper arm. Looking pretty good.




Tomorrow or Friday I will report back with the final results, and speed tests etc.

Whoo hoo!!
One day soon I will put together a massive blog post on all this.

 

Hey everyone, I wanted to come back and post the results so people could see the kind of quality this process can generate. I added some smoothing to the skin weight values and here is a simple animation gif.




This is with a skin smoothness of 1, with something higher like 10, I get super wavy raver arms, which could be an interesting look depending on the character. At more extreme angles some of the mesh quality breaks down, I think this can be fixed with joint specific smoothness. (ie 0 at the elbows + knees, 1 at shoulders, 2 at torso)

My quest is now to clean up/simplify the mesh I think and perhaps expand it a bit to remove the jaggies on the edges. I will also experiment with different skin smoothnesses and combinations.

If anyone has an suggestions as to how I can make it look better I would love to hear them!

 

@dchen05 This is amazing! i know this post is very old, but im wondering if you made an asset with this, is exactly what im looking for at runtime. And it would be perfect if basic animations could be procedurally adapted to that skeleton like in the video you posted