This is an intermediate report of my past two weeks' explorations of animated character graphics for Eulora, as part of working towards a parametrised generator of trillions (infinity!) of models. While I usually do any write-ups at more clearly defined stopping points -basically when I got *somewhere* rather than in the middle of going-somewhere- in this case I had to do this write-up simply to unload all the stuff that I explored¹. The main reason for taking the time now in the middle of it to write up what I have so far is simply that I found myself already going back through my own notes just to *remember* fully one detail or another. And rather than wasting the time to keep going back and forth through the notes, it's way, way better to write it all up and publish it - at the very least because then I'll actually remember it (that's my meaning for mentally archiving something) and otherwise because it also allows others to provide any feedback they might have.

Keeping in mind therefore that this is simply a stop *on the way* to somewhere rather than any planned somewhere as such, here's what I looked at so far, what I did and what I found out as a result:

1. Sockets for attaching one mesh to another on the fly with CS+Cal3d.

   In principle this is absolutely needed so that one can show visually the result of actions such as equipping tools/weapons/cloths and the like. Theoretically and from reading the relatively sparse documentation & examples of both CS and Cal3d, I had naively set this as an "easy and quick" sort of thing - in practice it turned out to be of course not all that easy and quick at all. I've spent a bit less than 2 days on trying to make it work in client 2.0 and while I managed to create from code any sockets I choose on a Cal3d mesh and moreover to write the code that uses them (aka attaches another mesh to that socket) according to what all the docs say, the results so far are annoying like hell: there's no error and no complaint and according to everything available all is perfect, except the "attached" mesh does not bloody show at all!

   While I am quite sure that I *will* have to sort it out and make it actually work sooner or later, at this stage I decided against spending more time on it because on one hand it's not yet burning and on the other hand, giving it some time will most likely help since in the meanwhile I'll anyway get to know everything relevant way better than I do right now. So much for "easy and quick" task though - and I can't tell you how annoying this "result" here actually is. For what it's worth, I even suspect already where the issue might be, namely at the exact positioning of the socket, because the positioning has to explicitly choose a *triangle* of the whole bloody mesh to which you want to attach something. And so either you know that mesh in full detail or it's very easy I guess to attach the thing in a way that doesn't show. Anyways, that's pretty much why I think I'll have a way easier time sorting this out at a later stage - this part will become clearer as part and parcel of writing my own mesh generator.

2. Detailed study of Cal3d formats to fully get what my generator would need to produce exactly anyway. As a practical example for this I used the files for the Cally example character (see next item) but I took initially some time to go through the formats with pen and paper at hand as there's a marked difference between knowing the formats to be able to plug them into the client (as I knew them already) and otherwise knowing them to the level of detail that I need to be able to generate new files that would match exactly what I intended to represent in the first place.

   The full set of Cal3d formats consist in 5 types of files: skeleton, mesh, animation, morphanimation and material. There's a binary and an xml version for each of those but Cal3d's handy converter works to convert both ways so there's no issue on this front that I can currently see. As CS can't use materials in Cal3d format anyways and Eulora is currently not interested in morphanimations, I focused exclusively on the remaining 3 types: skeleton, mesh and animation.

   The skeleton file held the first surprise for me in that the name is misleading really: it's not at all a skeleton (aka bones, despite being called everywhere "bones") that is stored in there but at most a set of ...articulation points, I'd call them. Essentially a "bone" in cal3d's format is simply ONE POINT and that makes a huge practical difference because one point does not have any length or thickness - it has merely a parent and 2 sets of transformations (where by one transformation I mean a set of one translation and one rotation, with the rotation given as a quaternion in cal3d's format): one that is relative to the parent bone (so effectively defining the point's position with respect to the parent bone rather than with respect to the whole model's origin point) and one that is basically the reverse transformation for the position in the model's space (aka with respect to the model's origin space).

   The transformation relative to the parent bone is confusingly called just "translation" and "rotation". The root bone is the one that has no parent and - implicitly because explicitly would be way too clear - its own origin is in fact the model's origin. Then the other set of transformations are called - for added confusion points - "local" though they are essentially relative to the model's origin rather than the bone's origin. The thinking behind that local though is that they are the transformations applied to a mesh's vertices to bring it from the model's space to the bone's space. I can see the reasoning but I find it very unhelpful and the reason is of course the fact that I'm looking at it with the aim to generate the darned thing while all of it is built with the aim to render it so everything is pretty much falling the wrong way around, every time. Not that it's unexpected or any news, no.

   Moving on from the skeleton, the mystery of how come the bones are in fact only points has its solution in the mesh file - as long as you remember that it's again made for a quite different purpose that mine. A bone's length and thickness matter because it's those that determine otherwise which parts of the attached mesh move and in what way in the end. But since the cal3d formats are not concerned with figuring out which parts need to move, there is indeed no need to store that information (length and thickness) explicitly in the skeleton file, right? So, what you get instead is the already-calculated (pre-chewed, rather) exact values - and in the mesh file at boot, since yeah, it's the mesh's vertices that are affected. Moreover, you get to further realise that the whole pretense of "meshes being attached to bones" is misleading as apparently CG² ~always aims to be: there is no attachment as such because when you render a mesh, the skeleton and any "attachments" are anyway totally ignored - it's only during animations that the skeleton matters at all and even then, only for those "bones" that are explicitly present in the animation's keyframes.

   To recap the above mess, my current understanding is this: in the skeleton file there are only the origins of each "bone" given in a hierarchical set of transformations starting with a root bone (that has no parent and that actually is as a result at the origin of what's considered the "model space") as well as the transformations from model space to each bone's space; in the mesh file, there is a full list of vertices given through position & rotation *in the model space* (so no, not hierarchically at all, you need the damned foot itself to know where the foot for that particular character needs to be) and having further attached to them "influences"³ from any number of "bones" - note that those "influences" have any...influence only at animation time, as they don't do anything at all when just rendering the mesh itself; finally, the animation file consists in sequences of transformations (translation and rotation, as everywhere) given for each "bone" with respect to its parent (so supposedly in the "bone's space").

   The above better understanding of the formats came in a small part from re-reading the Cal3d docs (that didn't take that long since there's really not much to those docs) and otherwise in a lot bigger part from the practical messing about with generating some stuff (see below, after the Cally mapping item).

3. Mapping the Cally example as a means to get a better understanding of what goes into a fully working animated character and figure out in all the needed gory detail just how all the different parts work together.

   As this was purely a study task, everything went fine: I converted the binary cal3d files (skeleton, meshes and animations) for Cally to xml format with cal3d's own convertor (in cal3d/bin) and then went through them in detail with pen and paper at hand. As a result, I got the "skeleton" in clear, all its 37 "bones", I admired the horror of the meshes being defined as lists of vertices and triangles making up the surfaces ("faces") and I finally understood more precisely what's with the "tracks" for animation - it's just how Cal3d decided to name the set of keyframes defined for each bone as part of one single animation.

   The benefit of the above is not as much something I can show as concrete result but it's a lot in terms of practical experience and otherwise more concrete understanding that helps me going further and that I otherwise simply needed. It took only a few hours as the model is not huge and the main part was mapping the skeleton and otherwise just a bit of a mesh and one animation to get an idea.

4. Prototype toolchain as a means to experiment and explore as well as allow this part to work outside the client itself since it really makes little sense to have to plug any attempt into the full client just to see the mess.

   The current prototype toolchain relies on CS and Cal3d, of course, but otherwise it's very light. I adapted the previous viewer and bashscript for Cal3d models so that it works as a quick way to test whatever my own generator spits out in cal3d format. Then I wrote a quick prototype (it's less than 1k lines of cpp code itself) that can currently correctly write so far csf (skeleton) and cmf (mesh) files in cal3d format, while also playing around for a bit with some code-generation of "mesh parts" that relies for the shapes themselves on CS's regular shapes (ellipse, specifically) and otherwise allows tweaking of the generation through a set of parameters (so far the desired height of the model and the ratios x:y, z:y; while in principle I had in mind also the number of various limbs aka legs, arms, fingers and tits, so far I fixed those to just get something working and showing since at this point it's anyway not helping much to spend more time on additional parameters). The current code successfuly generated as a result a "ellipse-figure" aka a biped that has 1 or 2 ellongated/flattened spheres (based on an ellipse rather than a circle) making each body part, manages to keep them together in a recognisable biped-shape and otherwise got its head bobbing about -if rather to the side for now- by stealing the relevant head-bobbing part of cally's "walk" animation. It's of course not only ugly but not at all the approach I intend otherwise for the generation of chars but it served well for this initial exploration anyway.

   The above prototype is *not* intended in any way to be the generator (or even part of it) as such - it is just the initial practical exploration mainly to start figuring out what the output needs to even consist in & how it works. For the actual generation approach there are quite a few directions I have in mind to look into and filter to see what is worth giving a proper spin and/or start from, otherwise (see the next item in the list - the state of theory review).

   NB: the animation format is NOT yet spit out by the current prototype, but since it's still xml, I don't expect it will be any bigger trouble than the rest really. The more painful part with all those formats is at most this bridging of the gap between the logical place of some parts when generating the model vs what the format wants because of rendering convenience (e.g. the influences on a per vertex basis and located in the mesh rather than in the skeleton). As it is, I lost quite some time to make that head bob and it's still not exactly bobbing in the right place - there's some further detail that I still don't fully grok on how the animation is exactly specified. So this is still on the list as such, but my current plan on it is that I'll work on in parallel with and as part of advancing with more concrete explorations of actual generation of stuff.

   The above prototype was quite invaluable really and on the very bright side, I have now the assurance that it IS indeed possible to spit out -even from my own generated mesh from scratch- the exact formats that the current client can work with, even if otherwise the geometry and possibly the meshing too can be perhaps described sanely aka through the chosen parameters rather than through the full resulting sets of everything. On the side, I also got as part and parcel of this to explore the regular 3d shape generation that CS currently provides: while there are supposedly cones, cyllinders, spheres (built based on ellipses), boxes and capsules, the practice shows that many of those are not all that great generators since the result fails CS's own checks - the engine itself complains either that the object is "not closed" or that there are "degenerate faces" and in principle both of those complaints can create visible performance problems if the number of such objects is high enough. This came as a surprise really but I don't think it actually matters much since I don't plan to use CS's capsules and the like anyway. (The sphere works fine and it's actually used for the current default sky but I don't plan using it for the generator anyway.)

5. Theory exploration as a means to improve my own knowledge in this field (since I hadn't otherwise much exposure to it so far) and to get some more ideas as to possible options and promising directions.

   For the theory exploration I started from character modeling, thinking - rather naively, on hindsight - that it's precisely where one gets to figure out what the whole process is there and what are its key parameters, constraints, requirements and issues. Possibly these are indeed hidden somewhere in plain sight - and if you know where, please leave a comment pointing me to that where - but at least within the limited time I had, what I got instead of process and all that jazz was the realisation that the focus is at almost all times on "assisting artists" rather than exploring the space and possibilities that automation offers (such as it is, maybe for good or for worse but it...is).

   Basically the automation is considered at most a sort of crutch to do what the artists don't know (and would rather not learn either, from what I can tell), a data cruncher (for instance to extract features out of large databases of human faces) and otherwise a reliable grinder where the task requires one, as is the case for instance with mirroring the two halves of a character so that the result is perfectly symmetrical. This reliance on the machine for perfect symmetry ignores of course - while specifically and vocally aiming for "realism" and "real-like" results - the fact that no human being is actually perfectly symmetrical or even regularly "asymmetrical" anyway. This sort of mismatches aside, the overall point is simply that there is precious little exploration of fully automated generation as such⁴, the little there is tends to be found anyway in the CAD⁵ domain and otherwise unearthed in some incipient forms from quite a few years ago, which by now is not at all surprising if you remember Chomsky⁶

   Besides the unexpected pleasure of Blum's paper on the medial axis⁷, the few useful bits I got nevertheless out of this part: a better understanding of some terms dear to artists, most notabbly rigging and skinning. While there is some loose usage of those two terms, what I've got pinned down as more or less reliably explaining what is going on would be that rigging is concerned with how the movement of internal parts - be it "bones" if you must give them that name but more generically, whatever internal parts are considered for modeling purpose - affects the vertices at the surface of the visible shape, while skinning would be the opposite of this, so focusing instead on how movements or changes to the outer vertices correspond to movements and more specifically rotations mainly of inner joints. In the usual simplified manner of a type of practice, rigging often turns into the building of a skeleton and positioning it just-so to fit at exactly desired places inside an individual model (because god forbid it would fit more than one!!!) while skinning turns into deciding which vertices get linked to which bones and how much/in what exact way do they move/change with that bone.

   Besides the terms themselves, I further got to go at least for a quick scan of a few algorithms that are apparently most used (in CG it seems to go exactly like this - for all the huge pile of papers, the algorithms actually used are very few in any given domain anyway) for calculating at rendering time the results of a given model that is already fully rigged and skinned ("smooth skinning" seems to be a very popular choice of algorithm for being good enough, pretty much). And from there on, I had a quick look at skin binding and bone linking approaches too, though not in a lot of detail. The point and gain of those was mainly to get some idea of what the known problems and issues even tend to be and what sort of solutions have been found. Apparently when it comes to bone positioning and linking, the core (other than hand-picking/adjusting and/or machine learning based on image datasets) is still Blum's medial axis and when it comes to meshing (describing a surface through those vertices and triangles dear to CG because of fast rendering), the core is Delauney's triangulation.

   The above narrowed the further space for exploration to looking at least at what has been done perhaps using Blum's and Delauney's work (and Voronoi I suppose I should say, since it's linked anyway). While I still want to have a further look in there as it's not otherwise a domain I was very familiar with, the exploration so far has turned out at least one rather interesting approach to mesh generation⁸ by Persson and Strang⁹, relying on a rather neat I'd say physical analogy of finding the equilibrium of an underlying truss structure. Basically the generator starts with a random number of vertices in the pre-defined bounding box in which the end shape will fit. Using the physical analogy of a truss, those vertices would be the nodes of the truss and there are force-displacement relationships considered to be acting for each "bar" (aka edge between vertices, as calculated) in the truss. Those force-displacement relationships depend on the length of the bar and moreover, there are further "reaction" forces introduced at the extreme boundaries so that vertices are kept within the bounding box. The algorithm adjusts iteratively the positions of those nodes until the whole structure reaches an equilibrium. At each iteration, Delauney triangulation is applied to adjust the edges (hence the "truss' bars") between the new positions of the vertices. The geometry itself is simply and neatly described by a distance function that gives for any point its distance to the boundary of the domain, returning negative values for points inside and positive values for those outside.

Conclusion and Next Steps

As it turns out, this stop in the middle of the road to put stuff down was more than needed - given that it took almost 2 days just to select, structure and do the proper write-up of the main points of interest. Nevertheless, it's still just somewhere in the middle so the next steps will just push each part further - only it should be a rather easier push, now that I archived the last bulging set of notes and can therefore start on a new one.

On the implementation side, the next step is to write the code to spit out the animation file too (and that would mean I at least have the working writers for all three formats that are an absolute must from the cal3d set: skeleton, mesh, animation). Then I'll need to decide on some concrete generation approach (beyond the prototype/testing let's play with spheres) that I want to try in practice and give that a go, see what comes out of it and then iterate on this. I must say that I really like the idea of a generator that effectively looks for an equilibrium solution for a set of displacement functions that are let loose in the 3D space that can maximally contain a piece of (or the whole) model. Nevertheless, given the discovery of the dubious "skeleton" actual meaning, I'm keeping for now a very open mind here and I don't really want to fix much upfront since I can't quite tell how one or another approach really would turn out.

On the supporting implementation side (aka "theory"), I still need to do quite some reading both on the Maths side and on the applications, such as they are, to CG. In particular, I think I have a bit more to explore to put my mind at rest regarding automated generators of geometry & mesh. I also need a better grasp on Delauney's work and on Blum's medial axis at the very least.

Considering the above, it might very well be that the next write-up finds me still somewhere in the middle of the road rather than moving on to something-other-than-generator but at the very least it should be *further ahead* on this road, I would think.

1. And as a result of the write-up fully structure and archive it all in my head, as it always happens with write-ups. ↩

2. Computer Graphics ↩

3. Technically, Cal3D also allows some "weights" to be attached to each vertex with the purpose of specifying the "rigidity" of each vertex. Those are called in the documentation "springs" and the underlying idea is to provide cloth-like or hair-like effects (when fully not rigid). ↩

4. Even approaches that state "generation" and seem bent on using automated approaches turn out at a closer look to still see the whole exercise as ultimately at most supporting some "artist" and therefore absolutely focused in a...GUI. For example and among the better attempts at least (as it provides some concrete skeletons (and some variations obtained at least programmatically on those): "Creature Generation using Genetic Algorithms and Auto-Rigging", by Jon Hudson, 2013. ↩

5. Computer-assisted design ↩

6. And a good example specifically here for automated generation is to my eyes a 1967 paper by Harry Blum, on "A Transformation for Extracting New Descriptors of Shape." To quote directly from his introduction, the very first paragraph: "I have approached the problem of shape by assuming that the current mathematical tools were somehow missing essential elements of the problem. For despite more than two millennia of geometry, no formulation which appears natural for the biological problem has emerged. This is not surprising perhaps when one recognizes that geometry has been born of surveying and has grown in close collaboration with physical science and its mensuration problems. A corollary to this position is that there is some central difference between the biological problem that we are trying to deal with and the physical problem that we have been dealing with. Consequently, such an approach requires a restudy of visual function to assess what such a geometry should indeed try to accomplish. Unfortunately, the problem of exploring function is not easy to do in isolation, since the visual world is extremely rich, and hypotheses about visual shapes and their functional value to an organism may reflect the cultural bias of the experimenter to a large degree. I have chosen to enter the problem from the middle by hypothesizing simple shape processing mechanisms, and then exploring together the geometry and visual function that result. One such mechanism is presented in this paper. Since it leads to a drastic reformulation of a number of notions of visual shape, it may be useful to review briefly some of the notions implicit in our views and experiments." - It was simply a pleasure to read this, especially after sifting through quite a lot of what I can only summarise as "and now we tweaked this so it looks more like that and/or it's easier for the artist to do with just a few clicks." And yeah, in case you are wondering - Blum's medial axis is still used, very useful and very much studied, as it represents the topological skeleton of a shape, way better than hand-placed "bones" and whatnots, at that. As an aside, apparently even possibly too well from at least one computational perspective, in that even small changes to the boundary of the whole shape can trigger large changes to the medial axis. ↩

7. And for a *very* unfair comparison, I'll quote here some modern production, on page 12 of Desmond Eustin van Wyk's 2008 vintage "thesis submitted in fulfilment of the requirements for the degree of MAGISTER SCIENTIAE in the Department of Computer Science, University of West Cape": "Also, programming in general is difficult and operators or functions used in procedural modelling are of a low level and requires understanding of programming concepts during script development." Full marks for the candid admission but this is it - the newly minted magister scientiae in recognition for the work done to avoid the difficulties of programming and the horrible requirements of understanding concepts. What, do you have any problem with that? ↩

8. Note that CS's and more generally CG's use of "mesh" is annoyingly loose from a stricter, more mathematical I guess, perspective: while "mesh" is used to stand for what is rendered on the screen as a model's appearance, strictly speaking it's simply the description of a surface through simpler shapes - most usually triangles for 2D; when looking into generating models though, one needs to consider before that the generation of "geometry" aka of the actual 3D shape that exposes those surfaces to be meshed. So the generation of a 3D model has to include at the very least 4 parts (generated through whatever means and possibly shared across multiple models but still generated at *some point* in time and through *some method*, nevertheless): a skeleton aka a hierarchical set of joints and a way to describe how they act upon a given geometry+mesh when such is attached; the geometry of the model's parts and the concrete meshing of its outer surfaces (hence, the vertices and triangles that the graphics engine ultimately works with); the animations that describe essentially movement of vertices anyway, whether it's done indirectly via the "bones" of a skeleton or directly as is the case for the so-called morph-animations. ↩

9. Per-Olof Persson and Gilbert Strang, "A Simple Mesh Generator in Matlab", SIAM Review, Vol. 46 (2), pp. 329-345, June 2004 ↩

Category: Coding, Computer Graphics

Comments feed: RSS 2.0