PDA

View Full Version : Vertex blending source unrelated to OGL and D3D


Kuroyume0161
06-12-2005, 10:34 PM
Looking for vertex blending (skeletal deformation) source code, preferably in C/C++. The maths are available if I need to battle it out and the only source that has been found all relate to DirectX and OpenGL - useless to me as I'm doing Cinema 4D plugin development (i.e.: software, not hardware).

Thanks for links and references!

arnecls
06-13-2005, 10:43 AM
Well, I did a "Studienarbeit" (don't know the english term for that) in 2003 on that theme (crossplatform skins and bones for short).
I used Cg shader and SIMD-Instructions for that, although my implementation wasn't that good (vertexshader were slower than SIMD and I couldn't figure out why).
I also described and programmed a Maya exporter (MEL) in that work but that's got quite a huge error in it because I ignored the bone-base-matrices (which you SHOULD do) resulting in some strange results (twisted models).
I'm currently working on a new exporter using the Maya-API which will fix that issue, but that will take some month (some secondary part of my Diploma).

If you're capable of german have a look here: http://geri.uni-koblenz.de/Studienarbeiten/arnecls.pdf, otherwise send me a mail, I'll look if I find the code somewhere :)

Oh - and there are a few references on related work at the end of my studienarbeit.

mummey
06-13-2005, 02:13 PM
Looking for vertex blending (skeletal deformation) source code, preferably in C/C++. The maths are available if I need to battle it out and the only source that has been found all relate to DirectX and OpenGL - useless to me as I'm doing Cinema 4D plugin development (i.e.: software, not hardware).

Thanks for links and references!

Having the base is nice and all, but isn't this just straight 3D matrix math? Your best resource in this case may be a book on matrix algebra.

Kuroyume0161
06-14-2005, 12:31 AM
Having the base is nice and all, but isn't this just straight 3D matrix math? Your best resource in this case may be a book on matrix algebra.

Wow. What's a matrix? What's algebra? Man, I've been programming since 1987 - no idea what arithmetic is...

Vertex blending isn't straight forward matrix math. Here's the basic equation:

v' = Sum(i=1...n)[w(i)*F(ji)*(A(ji)^-1)*v]

where
i is the index to joints influencing vertex v
ji is "sub j sub i"
w(i) is the weight
A(ji) = R(0)...R(p(ji))R(ji)
R(ji) is transformation from joint p(ji) to ji

F(ji) = F(p(ji))R(ji)T(ji)
T(ji) is rotation of joint j beyond reference position

How about proferring some useful information, please?

What is not discussed is whether any of these are world or local transformation matrices. ETA: Or whether these are left or right hand coordinate matrix operations (which have a different multiplication order). I'm guessing, assuming, figuring on left. This entire process requires a forward tree traveral (recursive hierarchical root->leaf traveral) and there are probably nice ways to transmit the matrices along the traversal.

Plus, I'm doing Cinema 4D plugin development. No option for zero-based bones. These are fixed bones using HPB rotations. I have to take this into careful consideration when applying the inverse and back transformations.

ETA: Source code may make the "process" of the equation clearer to understand. The equation is for ONE vertex only. Is it more efficient to loop through the vertices and apply the equation or better to traverse the bone hierarchy and apply the equation to all influenced vertices? Questions, questions, and only questions of my mathematical competency.

Please don't respond unless you have something related to say, thank you.

Kuroyume0161
06-14-2005, 03:42 AM
Well, I did a "Studienarbeit" (don't know the english term for that) in 2003 on that theme (crossplatform skins and bones for short).
I used Cg shader and SIMD-Instructions for that, although my implementation wasn't that good (vertexshader were slower than SIMD and I couldn't figure out why).
I also described and programmed a Maya exporter (MEL) in that work but that's got quite a huge error in it because I ignored the bone-base-matrices (which you SHOULD do) resulting in some strange results (twisted models).
I'm currently working on a new exporter using the Maya-API which will fix that issue, but that will take some month (some secondary part of my Diploma).

If you're capable of german have a look here: http://geri.uni-koblenz.de/Studienarbeiten/arnecls.pdf, otherwise send me a mail, I'll look if I find the code somewhere :)

Oh - and there are a few references on related work at the end of my studienarbeit.

Thank you, arnecls. Mein Deutsch ist nicht sehr gut, especially for technical documents. :) I will check the references.

arnecls
06-14-2005, 07:54 AM
> What is not discussed is whether any of these are world or local transformation matrices.

I guess, that depends on your system.
IMHO using local transformation matrices makes more sense because you're using a hierarchical structure here. If you're storing everything in world-transformations it makes updateing a little hard.

> ETA: Or whether these are left or right hand coordinate matrix operations (which have a
> different multiplication order).

Now this depends strongly on your way of implementation. Choose the one you're happy with or your system provides (not sure about Cinema, but I guess that's left-handed).
If you want to go with Shaders or SIMD or FPU, or whatever you always have to code the math-operations yourself (ok - shader provide dot-products, so that's easier) and that means you can do both ways.
After all - switching from left to right is just a transpose :)

> I'm guessing, assuming, figuring on left. This entire process requires a forward tree
> traveral (recursive hierarchical root->leaf traveral) and there are probably nice ways to
> transmit the matrices along the traversal.

That describes the process quite well. You should do some kind of "current state caching", which means -> traverse your hierarchy and calculate the world matrixes for each frame. I used the OGL Matrix stack for matrix-multiplications, but I'm not sure if SIMD is faster there - at least I haven't tested yet.
After you did that - pass the world-matrices to your shader / model class and apply the vertex transformation there. I wrote two "draw-plugin-objects" for my modelclass. The first transformed all the vertices on the CPU using SIMD, the second did nothing but passing the required parameters to my vertex shader. That way you could choose the rendering method during runtime quite easily (just switch objects).

You should also stick to 4 weights per Vertex, because that way you can pass the required information via texture-coordinate to your vertex:
one tc for Bone Index, one tc for weight (per vertex) plus all the matrixes (shader parameter) must be passed.
You should also know that only a certain amount of matrixes can be passed to a shader (how many depends on the card/profile you're using). That's the biggest problem IMHO because parameter-passing seems to be expensive and you have to change matrixes for every model / bone-system.
However - you can "compress" your matrices, because one line (which one depends on left/right system) is always 0 0 0 1 - you can leave that out, gaining space for a few more matrixes.

Hope that helps a bit.

Enki[Mute]
06-16-2005, 01:57 PM
in case it helps .. (I have an implementation that works like this and is 100% compatible
with the LW 8 bone system.)

IMHO, it's always faster to do bones on the cpu.. doing it on the gpu will probably just
disable your options as far as shadowmapping or extrusion shadows are concerned.
(if you do it on the cpu, you'll have to do it only once. on the gpu, for each view you
render for shadowmaps, reflectionmaps, .. over and over again)
(also, on the cpu, you could easily decide not to caclulate bones every frame, you could
have multiple characters doing the same animation and still have to calculate it only once)

Ok, first we'll define the coordinate systems in which we put everything .. you should already
know this, but just to make sure.

1. Object space.

Your vertices are defined in this space. The origin of this space is the base pivot point
of your character.

2. Bone space.

Bones are defined relative to the origin of object space mentioned above. If we wish to
apply the bone, we must first transform object space so that the bone we are considering
sits at the 0.0 origin. This space is called bonespace.

There are some other spaces (worldspace, camera space, clipspace, viewport space), but they are not to our interest.

Ok. So I'm assuming you have vertices, bones defined relative to the object space origin,
and weightmaps that contain how much each vertex is influenced by each bone.

Apart from the obvious "4 closest bones only" optimisation that you find everywhere, the
algorithm looks like this ..

tMatrix instance_matrix(instance T);
{
tMatrix result = identity;
if (T.parent != 0) result *= instance_matrix(T.parent);
result *= matrix_translate(t.x,t.y,t.z);
result *= matrix_heading(t.heading);
result *= matrix_pitching(t.pitching);
result *= matrix_banking(t.banking);
}

tMatrix bone_matrix(tBone T);
{
tMatrix result = identity;
result *= matrix_banking(-T.bone_rest_banking);
result *= matrix_pitching(-T.bone_rest_pitching);
result *= matrix_heading(-T.bone_rest_heading);
result *= matrix_translate(-T.bone_rest_x, -T.bone_rest_y, -T.bone_rest_z);
if (T.parent != 0) result *= bone_matrix(T.parent)
}

reset destination_position vertex coordinates (bones are an additive process)
for each bone
bmtx = instance_matrix(bone) * bone_matrix (bone)
for each vertex
multiply vertex position with bone matrix.
multiply this result with weight.
add that result to destination_position.

the object defined by vertices destination_position is now transformed and ready
for the projection matrix ..

No more to it ..

grtz

CGTalk Moderation
06-16-2005, 01:57 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.