Vertex Rotation Calculations - Work one at a time, but fail in groups?

Recommended Posts

gbMike    152
I have a ray, that I am trying to convert the vertices in, from global space, to the local space of an object. Converting translations and scale were easy enough, but rotations are giving me trouble.

Specifically, when I apply a apply a rotation in only the x, y, or z coord, it will calculate correctly. But if I apply rotation in two directions, it does not calculate correct coords. I'm not sure why they would fail running with multiple rotations, since if they each work individually. Here is my code:

[source lang="cpp"]
/////////// Z /////////////

// atan2( 0, 0 ) will throw an error
if( !(point.x == 0 && point.y == 0) )
{
//get initial 'rotation' of the vert from (0,0,0)
rot = atan2( -point.x, -point.y );

length = Vector3( point.x, point.y, 0 ).Length();
point.x = -sin( rot ) * length;
point.y = cos( rot ) * length;
}

/////////// Y /////////////
if( !(point.x == 0 && point.z == 0) )
{
rot = atan2( -point.x, -point.z );

length = Vector3( point.x, point.z, 0 ).Length();

point.x = sin( rot ) * length;
point.z = -cos( rot ) * length;
}

/////////// X /////////////
if( !(point.z == 0 && point.y == 0) )
{
rot = atan2( -point.z, -point.y );
length = Vector3( point.z, point.y, 0 ).Length();

point.z = sin( rot ) * length; //adj
point.y = -cos( rot ) * length; //opp
}
[/source]

Share on other sites
alvaro    21246
First of all, rotating by using atan2, adding an angle and then using sine and cosine to get coordinates is a very inefficient way to perform 2D rotations. That's actually the same procedure I came up with when I did this kind of thing the first time around, at the age of 13. So many memories...

So here's the better way:
[code]new_x = old_x * cos(angle) - old_y * sin(angle)
new_y = old_x * sin(angle) + old_y * cos(angle)[/code]

With that out of the way, what your code is doing is composing three rotations around axes. You haven't explained why you think the results are incorrect. Chances are your intuitions about rotations are a bit off and the code is working just fine.

So what's an example of inputs into this function that produce output that you consider incorrect? What result did you expect instead? Edited by alvaro

Share on other sites
gbMike    152
Thanks for the optimization tip [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] I've just swapped out my code for the better version.

Let me go into a bit more detail. I'm working on a simple 3D engine with openGL. I am using this function for collision calculation between a model, made up of triangles, and a ray. In order to run the collision test, I need to convert the ray (which has coordinates relative to global space) to the local space of the model (by applying the rotation, translation, and scale to the origin and end point of the ray)

For now, the ray I'm testing with is a pick ray, generated by a mouse click. That ray's coords are then moved into object space, and run a collision test against each face in the model. The collisions register perfectly one at a time (I'm not outputting any fixed values, rather simply clicking around the edges of my object, to make sure the collisions are accurate) As I mentioned, this functions perfectly with only rotation applied, but becomes inaccurate when a second or 3rd rotation direction is put in place. I've traced the collision area with my mouse, and it looks like, it is testing collisions against the model, with a different rotation. But again, it works perfectly when rotated on only one angle.

I know the pick ray generation is working properly, as is the collision test. (They've both been tested pretty thoroughly in several previous instances) I'm not sure if this helps, but here is the rest of the code for the globalToLocal function. Btw, I've been learning this on my own, so if you happen to catch any other poorly written bits of code, please let me know.

[source lang="cpp"]

/*
Hierarchy is the set of transformations to apply. In this case, only one element is in
the list.
*/
void Mesh::globalToLocal( vector<Vector3 *> &in_vertices, list<Transform *> hierarchy )
{
for ( int i = 0; i < (int)in_vertices.size(); i++ )
{
list<Transform *>::iterator it;
for ( it = hierarchy.begin(); it != hierarchy.end(); it ++ )
{
applyVertexTranslation ( (*in_vertices[i]), (*it)->translate );
applyVertexRotation ( (*in_vertices[i]), (*it)->rotation );

//scale is not currently added to the heirarchy, since it is never changed/used
}
}
}
void Mesh::applyVertexRotation ( Vector3 &point, Vector3 &rotations )
{
float rot, oldX, oldY, oldZ;
/////////// Z /////////////
if( !(point.x == 0 && point.y == 0) )
{
oldX = point.x;
oldY = point.y;
point.x = oldX * cos(rot) - oldY * sin(rot);
point.y = oldX * sin(rot) + oldY * cos(rot);
}

/////////// Y /////////////
if( !(point.x == 0 && point.z == 0) )
{
oldX = point.x;
oldZ = point.z;
point.x = oldX * cos(rot) - oldZ * sin(rot);
point.z = oldX * sin(rot) + oldZ * cos(rot);
}

/////////// X /////////////
if( !(point.z == 0 && point.y == 0) )
{
oldZ = point.z;
oldY = point.y;
point.z = oldZ * cos(rot) - oldY * sin(rot);
point.y = oldZ * sin(rot) + oldY * cos(rot);
}
}
void Mesh::applyVertexScale ( Vector3 &point, Vector3 &scale )
{
point.x /= scale.x;
point.y /= scale.y;
point.z /= scale.z;
}

void Mesh::applyVertexTranslation ( Vector3 &point, Vector3 &translations )
{
point.x -= translations.x;
point.y -= translations.y;
point.z -= translations.z;
}

[/source]

Share on other sites
haegarr    7372
You apply each particular transformation one-by-one. That is horribly inefficient and not the way to go. Instead compute an overall transformation by composing all the particular transformations, and apply that thing as a whole. Mathematically spoken, you compute (using column vectors here)
[b]v[/b]' = [b]T[/b][sub]2[/sub] * ( [b]R[/b][sub]2[/sub] * ( [b]T[/b][sub]1[/sub] * ( [b]R[/b][sub]1[/sub] * [b]v[/b] ) ) )
for all vertices [b]v[/b], assuming 2 transformations in your list, where the usual way would look like
[b]v[/b]' = ( [b]T[/b][sub]2[/sub] * [b]R[/b][sub]2[/sub] * [b]T[/b][sub]1[/sub] * [b]R[/b][sub]1[/sub] ) * [b]v [/b]= [b]M[/b] * [b]v[/b] with [b]M[/b] := [b]T[/b][sub]2[/sub] * [b]R[/b][sub]2[/sub] * [b]T[/b][sub]1[/sub] * [b]R[/b][sub]1[/sub]
instead. The inefficiency becomes more and more relevant the more transformations you have and the more vertices you transform, of course.

Now, when looking at your given problem, you want to transform from global to local space. In other words, you want to compute [b]v[/b] from [b]v[/b]' when still using the above naming scheme. Hence you require to apply the [i]inverse[/i] transformation, because
[b]M[/b][sup]-1[/sup] * [b]v[/b]' = [b]M[/b][sup]-1[/sup] * ( [b]M[/b] * [b]v[/b] ) = [b]v[/b]

When using a composed transformation then inverting it is all you have to do. However, for the sake of clarity and perhaps you insist of using the particular transformations, the effect of inversion is
[b]M[/b][sup]-1[/sup] = ( [b]T[/b][sub]2[/sub] * [b]R[/b][sub]2[/sub] * [b]T[/b][sub]1[/sub] * [b]R[/b][sub]1[/sub] )[sup]-1[/sup] = [b]R[/b][sub]1[/sub][sup]-1 [/sup]* [b]T[/b][sub]1[/sub][sup]-1[/sup] * [b]R[/b][sub]2[/sub][sup]-1[/sup] * [b]T[/b][sub]2[/sub][sup]-1[/sup]
so that not only each each transformation is inverted but also the order is reversed. Do you have considered this?

Now let us assuming that [b]M[/b] is the the local-to-global transformation of your model. You can transform the model into global space using [b]M[/b] on the model's vertices, followed by doing the hit test in global space. This would be inefficient, so you want to go the other way: Transform the ray into model's local space and apply the hit test therein. Hence you have to do
[b]r[/b][sub]1[/sub]' = [b]M[/b][sup]-1[/sup] * [b]r[/b][sub]1[/sub]
[b]r[/b][sub]2[/sub]' = [b]M[/b][sup]-1[/sup] * [b]r[/b][sub]2[/sub]
onto the both points [b]r[/b][sub]1[/sub] and [b]r[/b][sub]2[/sub] defining the ray, and do the hit test with [b]r[/b][sub]1[/sub]' and [b]r[/b][sub]2[/sub]'. Edited by haegarr

Share on other sites
gbMike    152
I had considered that the order would need reversed, in addition to negating the transformations. I actually was previously using a working local to global function. However, as you said, trying to convert all the verts in a 13000 poly model uses absurd amounts of processing power, made worse by my method of calculation. I had reversed the order, and inverted the calculations. Transformation and scale worked out fine, only rotation was behaving strangly.

That being said, I was unaware a method of calculating all transformations at once, and applying it existed. Shows where my math skills are at. In any case, that looks like it would solve my problem, so I'm going ot give it a shot.

I'll let you know how it goes.

Share on other sites
haegarr    7372
[quote name='gbMike' timestamp='1335694042' post='4935789']
I had considered that the order would need reversed, in addition to negating the transformations. I actually was previously using a working local to global function. However, as you said, trying to convert all the verts in a 13000 poly model uses absurd amounts of processing power, made worse by my method of calculation. I had reversed the order, and inverted the calculations. Transformation and scale worked out fine, only rotation was behaving strangly.

That being said, I was unaware a method of calculating all transformations at once, and applying it existed. Shows where my math skills are at. In any case, that looks like it would solve my problem, so I'm going ot give it a shot.
[/quote]
To be exact: You have to [i]invert[/i] the transformation. Negation is the inversion for addition, but we have a multiplication here. Due to the fact that we deal with matrix math (where an equivalent of a division as the inverse of a normal scalar multiplication isn't defined) we speak of the matrix inverse. I mention this because [i]negation[/i] is also a defined matrix operation but it will not result in what you want here.

W.r.t. the underlying math a rotation isn't different from a translation or even scaling. If you have considered the reverse order (notice please that this is also necessary within the 3 particular rotations if you deal with Euler angles) and inversions, then you probably just had a implementation bug. However, using the composed transformation makes things easier and will probably erase the bug anyway. Edited by haegarr

Share on other sites
gbMike    152
I found a pretty straightforward explination of this process, for those of you like myself, who are still just getting into matrix math. Unless I'm mistaken, (correct me if I am) this is what haegarr is refering to:

[url="http://msdn.microsoft.com/en-us/library/ms536397%28v=vs.85%29.aspx"]http://msdn.microsoft.com/en-us/library/ms536397%28v=vs.85%29.aspx[/url]

The page is about microsoft GDI, but it explains the math pretty well, at least imho.

Share on other sites
gbMike    152
Just wanted to follow up. Switching to the matrix calculation, solved my issue perfectly and made the whole process a great deal better. You've been a big help.

Thanks!

Share on other sites
gbMike    152
Minor hiccup. It seems that calculating a transformation matrix (only using rotations in the x, y, and z for now) is calculating all the rotations, relative to the world's x,y and z. How would I apply this to get the rotations, relative to the object's current rotation? (i.e. if I performed a 90 degree rotation on the z axis to an upright soda bottle, and then applied a rotation in the y, using the matrix based calculations, the bottle will spin, where as I would like it to roll )

Is there a different set of rotation matrices for this, or simply a different way to apply them?

Please let me know if I am not being clear enough.

EDIT:

Never mind, aswered my own question. I had the rotations correct, but I failed to apply them in the correct order to match my glRotate calls. All is well now. Edited by gbMike