Smok Code's video: Algorithm to create bones for character animation

Tedious preparation of game characters - could it be automated with coding? In this AA meeting (Animation Automation) I show how I dealt with the problem. The long way. I really enjoy simplicity in games, and when it comes to graphics - pixelart is my style of choice. However I wanted a 3d world, and for that we of course need 3d graphics. 3d version of a pixel is called voxel, and represents color data in a 3d grid. Voxels aren’t new and there are a lot of tools available to create voxel graphics. The one I like the most is called MagicaVoxel and is available for free. So I open up magicavoxel and I design this character I’ll be using. If you had freedom to play whoever you want - who would you choose? Leave a comment, or better yet - download magica voxel and come up with a creature yourself - maybe I’ll add that. Okay, so here is the model I’ll put into my game. You might not know this but MagicaVoxel format is available openly and you can parse it. It contains many things, but most importantly: every voxel is represented by position (x,y,z) and color id. I’ve read that into memory of my code and produced a static model. If you’re curious how I’ve done it - there is another video for that. Now here comes the tricky part - how to make this thing move? Computers don’t understand the world like we do, so just telling them “move that hand” isn’t going to work. What you see here is actually a collection of colorful triangles that creates an illusion of a character. And it’s quite tricky to make those behave like a real person. Here are three obstacles that I had to overcome: * How to determine where exactly a character has arms, legs, head and torso, and more importantly: at which points they’re attached to each other? * How to translate that information into bones and joints: bendy and not-so bendy things * And finally: How to add this information back to the generated model in a way that 3d engine can understand and animate I’m not gonna lie - these steps were quite hard to get right, and I spent much more time than I originally planned. I considered giving up more often that I’d like to admit, and honestly doing this manually for my small needs probably would be quicker. First step, which is dividing our guy into sections may seem easy, but really it is not. What we’re starting with | is just a 3d array of points and some color information. We don’t care for colors, but we can surely figure out which points are close to each other and which aren’t. I had multiple ideas how to properly do it - I could try and find where the model has right angles, or maybe try to find surfaces and detect the alignment of voxel clusters, but all that didn’t quite fit in my mental model. I have searched the internet far and wide to figure out a good solution and I found it - voxel thinning algorithms. There are few of them invented over the years by mathematicians and computer scientists, and quite often they’re hard to understand and recreate in the code. After extensive research I’ve found one that’s going to work for me: OpenThinning. It’s fast, relatively simple and comes with a C++ implementation. Even better. So I took C++ code and rewrote it in C #, and it just worked. Look at this - almost like a skeleton, so it means we’re getting near. I check how voxels are connected and I end up with a graph that represents all of the axes of the model. These aren’t bones yet - I need to somehow merge these 1-unit long connections between nodes into something that can approximate the bone. First step is easy - just merge everything that is in a straight line. Then - just check which neighboring joints have angle close enough that they could be merged to form a simpler, less complex skeleton. Remember that we need this to be able to animate it later. All that is left to do is removal of some overlapping bones. -- So we solved the second problem: we know where bendy joints and not so bendy bones are. This algorithm still cannot tell us which of these bones is an arm or a leg, but at least we know exactly where they start and end. Since we have a very rough skeleton - we could probably write some simple rules to come up with proper matching, but let’s focus on the third part of the problem instead: how to map bones to actual voxels we are getting from the magicavoxel? Let’s start by saying exactly what bones are in this scenario: this is a relation between two points in space. I’ll use A* algorithm to traverse the voxel skeleton from one point to another to get a list of voxels that are the bone. To assign all voxels to bones we’ll just select all the neighbours of bone voxels and make it part of the same list over and over until we assign all voxels. There may be some overlap and that’s what we want.