Sign in to follow this  
sakana321

Quaternion really faster?

Recommended Posts

sakana321    133
Sorry guys if this is stupid question but, I read about quaternion somewhere (I can't remember) it say it faster than rotaion matrix. However, when i implemented it. It's somehow slower :( This is my rotation matrix version. double c = Math.cos(degree); double s = Math.sin(degree); double t = 1-c; double sx = s * axis[0]; double sy = s * axis[1]; double sz = s * axis[2]; double tx = t * axis[0]; double ty = t * axis[1]; double tzz = t * axis[2] * axis[2]; double txy = tx * axis[1]; double txz = tx * axis[2]; double tyz = ty * axis[2]; out[0] = ( ((tx*axis[0]+c)*vertex[0]) + ((txy+sz)*vertex[1]) + ((txz-sy)*vertex[2]) ); out[1] = ( ((txy-sz)*vertex[0]) + ((ty*axis[1] + c) * vertex[1]) + ((tyz+sx)*vertex[2]) ); out[2] = (((txz+sy)*vertex[0]) + ((tyz-sx)*vertex[1]) + ((tzz+c)*vertex[2])); As you can see it need 20 multiplication and 1 cos and sin operation. But when I try to implement quaternion rotation. double sinHalf = Math.sin( angle / 2d ); rotator.quatet[0] = Math.cos( angle / 2d ); rotator.quatet[1] = sinHalf * axis[0]; rotator.quatet[2] = sinHalf * axis[1]; rotator.quatet[3] = sinHalf * axis[2]; Quaternion inv = Quaternion.conjugate(rotator); temp[0] = - vertex[0]*inv.quatet[1] - vertex[1]*inv.quatet[2] - vertex[2]*inv.quatet[3]; temp[1] = vertex[0]*inv.quatet[0] + vertex[1]*inv.quatet[3] - vertex[2]*inv.quatet[2]; temp[2] = vertex[1]*inv.quatet[0] + vertex[2]*inv.quatet[1] - vertex[0]*inv.quatet[3]; temp[3] = vertex[2]*inv.quatet[0] + vertex[0]*inv.quatet[2] - vertex[1]*inv.quatet[1]; vertex[0] = rotator.quatet[0]*temp[1] + rotator.quatet[1]*temp[0] + rotator.quatet[2]*temp[3] - rotator.quatet[3]*temp[2]; vertex[1] = rotator.quatet[0]*temp[2] + rotator.quatet[2]*temp[0] + rotator.quatet[3]*temp[1] - rotator.quatet[1]*temp[3]; vertex[2] = rotator.quatet[0]*temp[3] + rotator.quatet[3]*temp[0] + rotator.quatet[1]*temp[2] - rotator.quatet[2]*temp[1]; As you can see it need 2 division 27 multiplication 1 sin and cos operation It have 2 division and 7 multiplication overhead! Or did i do something wrong? Thanks in advanced.

Share this post


Link to post
Share on other sites
Alrecenk    400
Quaternions are only faster in certain cases. Transforming a point with a quaternion is slower than transforming a point with a matrix, but I believe concatenating quaternions is faster than concatenating matrices. Also finding the inverse of a quaternion is much faster. They probably have other advantages, but I can't recall any off the top of my head.

Share this post


Link to post
Share on other sites
sthomas    163
Alrecenk is right, whether or not quaternions are computationally faster than matrices depends on what you're doing with them. I'm having a bit of trouble figuring out what you're doing in that code to be honest. It looks like you're converting an angle/axis pair to a matrix/quat and then transforming a vector using the matrix/quat. Usually you want to store your rotations as either a matrix or a quat and not as an angle/axis pair, so that conversion shouldn't be happening to often and thus shouldn't be factored into your cost calculations.

Towards the end of this document is a comparison of the efficiency of matrices and quaternions for various geometric operations. The two most common/important operations are rotation concatenation and transformation of a vector. Quaternions are faster for rotation concatenation but slower for vector transformation. Typically if you're transforming a lot of vectors using a quaternion you'd convert the quaternion to a matrix first and then do matrix-vector multiplications.

Having said all that, I think you're making too big a deal about the performance aspects of the quats vs. matrices debate. Consider the context you're working in and use whichever fits better. If all I were doing is rotating vectors, I'd probably use a matrix. If I'm doing orientation interpolation of any sort, I'd prefer quaternions.

Share this post


Link to post
Share on other sites
sakana321    133
Thank you so much for your fast response,

Look like i am totally wrong about quaternion. Then i am going to stick with my rotation matrix.

PS. To clearify sthomas question

sthomas: It looks like you're converting an angle/axis pair to a matrix/quat and then transforming a vector using the matrix/quat.

sakana321: Yes i convert angle/axis pair to quaternion with this 5 line code

double sinHalf = Math.sin( angle / 2d );
rotator.quatet[0] = Math.cos( angle / 2d );
rotator.quatet[1] = sinHalf * axis[0];
rotator.quatet[2] = sinHalf * axis[1];
rotator.quatet[3] = sinHalf * axis[2];

Actually i am impressed how fast it can convert from angle/axis pair to quaternion (it use only 3 multiplication and 2 division and 1 sin and cos)
compare to 10 multiplication 1 sin and cos of rotation matrix.
However most intense operation is on qvq* operation (rotation by quaternion)

sthomas: Usually you want to store your rotations as either a matrix or a quat and not as an angle/axis pair, so that conversion shouldn't be happening to often and thus shouldn't be factored into your cost calculations.

sakana321: Regretably, in my application axis and angle always change and can't be predicted.:-( So i have to conside axis/angle conversion to matrix/quat cost as well.

sthomas: I think you're making too big a deal about the performance aspects of the quats vs. matrices debate.

sakana321: I agreed. However, this is my hobbies ^_^". Sorry for your troubled.

Share this post


Link to post
Share on other sites
sakana321    133
Recently I optimize my quaternion rotation to this

double[] temp = new double[10];
double[] qtemp = new double[4];

// convert angle/axis pair to quaternion
double halfAngle = angle * 0.5d;
double sinHalf = Math.sin( halfAngle );
rotator.quatet[0] = Math.cos( halfAngle );
rotator.quatet[1] = sinHalf * axis[0];
rotator.quatet[2] = sinHalf * axis[1];
rotator.quatet[3] = sinHalf * axis[2];

// vq*
temp[0] = (vertex[2] -vertex[1]) * (rotator.quatet[3] - rotator.quatet[2]);
temp[1] = vertex[0] * (rotator.quatet[0] - rotator.quatet[1]);
temp[2] = -vertex[0] * -(rotator.quatet[2] + rotator.quatet[3]);
temp[3] = (vertex[1] +vertex[2]) * (rotator.quatet[0] + rotator.quatet[1]);
temp[4] = (vertex[2] -vertex[0]) * (rotator.quatet[2] - rotator.quatet[1]);
temp[5] = (vertex[2] +vertex[0]) * -(rotator.quatet[1] + rotator.quatet[2]);
temp[6] = vertex[1] * (rotator.quatet[0] + rotator.quatet[3]);
temp[7] = -vertex[1] * (rotator.quatet[0] - rotator.quatet[3]);
temp[8] = temp[5] + temp[6] + temp[7];
temp[9] = 0.5d * (temp[4] + temp[8]);
qtemp[0] = temp[0] + temp[9] - temp[5];
qtemp[1] = temp[1] + temp[9] - temp[8];
qtemp[2] = temp[2] + temp[9] - temp[7];
qtemp[3] = temp[3] + temp[9] - temp[6];

// qvq*
temp[1] = (rotator.quatet[0] + rotator.quatet[1]) * (qtemp[0] + qtemp[1]);
temp[2] = (rotator.quatet[0] - rotator.quatet[1]) * (qtemp[2] + qtemp[3]);
temp[3] = (rotator.quatet[2] + rotator.quatet[3]) * (qtemp[0] - qtemp[1]);
temp[4] = (rotator.quatet[3] - rotator.quatet[1]) * (qtemp[1] - qtemp[2]);
temp[5] = (rotator.quatet[3] + rotator.quatet[1]) * (qtemp[1] + qtemp[2]);
temp[6] = (rotator.quatet[0] + rotator.quatet[2]) * (qtemp[0] - qtemp[3]);
temp[7] = (rotator.quatet[0] - rotator.quatet[2]) * (qtemp[0] + qtemp[3]);
temp[8] = temp[5] + temp[6] + temp[7];
temp[9] = 0.5d * (temp[4] + temp[8]);

out[0] = temp[1] + temp[9] - temp[8];
out[1] = temp[2] + temp[9] - temp[7];
out[2] = temp[3] + temp[9] - temp[6];

Now it need only 21 multiplication (17 on qvq* and 4 on conversion) and one sin and cos operation.
Speed should be comparable to rotation matrix.
However, i think it can be optimize more but I couldn't figure it out yet. ^_^"

Share this post


Link to post
Share on other sites
sakana321    133
Ok, here is my final version.

double[] temp = new double[8];
double[] temp2 = new double[10];

// convert angle/axis pair to quaternion
double halfAngle = angle * 0.5d;
double sinHalf = Math.sin( halfAngle );
rotator.quatet[0] = Math.cos( halfAngle );
rotator.quatet[1] = sinHalf * axis[0];
rotator.quatet[2] = sinHalf * axis[1];
rotator.quatet[3] = sinHalf * axis[2];

// vq*
temp[0] = (vertex[2] -vertex[1]) * (rotator.quatet[3] - rotator.quatet[2]);
temp[1] = vertex[0] * (rotator.quatet[0] - rotator.quatet[1]);
temp[2] = -vertex[0] * -(rotator.quatet[2] + rotator.quatet[3]);
temp[3] = (vertex[1] +vertex[2]) * (rotator.quatet[0] + rotator.quatet[1]);
temp[4] = (vertex[2] -vertex[0]) * (rotator.quatet[2] - rotator.quatet[1]);
temp[5] = (vertex[2] +vertex[0]) * -(rotator.quatet[1] + rotator.quatet[2]);
temp[6] = vertex[1] * (rotator.quatet[0] + rotator.quatet[3]);
temp[7] = -vertex[1] * (rotator.quatet[0] - rotator.quatet[3]);

// qvq*
temp2[1] = (rotator.quatet[0] + rotator.quatet[1]) * (temp[0] + temp[4] + temp[1] - temp[5]);
temp2[2] = (rotator.quatet[0] - rotator.quatet[1]) * (temp[2] + temp[3] + temp[4] + temp[5]);
temp2[3] = (rotator.quatet[2] + rotator.quatet[3]) * (temp[0] - temp[1] + temp[6] + temp[7]);
temp2[4] = (rotator.quatet[3] - rotator.quatet[1]) * (temp[1] - temp[2] - temp[5] - temp[6]);
temp2[5] = (rotator.quatet[3] + rotator.quatet[1]) * (temp[1] + temp[2] + temp[4] - temp[7]);
temp2[6] = (rotator.quatet[0] + rotator.quatet[2]) * (temp[0] + temp[6] - temp[3] - temp[5]);
temp2[7] = (rotator.quatet[0] - rotator.quatet[2]) * (temp[0] + temp[3] + temp[4] + temp[7]);
temp2[8] = temp2[5] + temp2[6] + temp2[7];
temp2[9] = 0.5d * (temp2[4] + temp2[8]);

out[0] = temp2[1] + temp2[9] - temp2[8];
out[1] = temp2[2] + temp2[9] - temp2[7];
out[2] = temp2[3] + temp2[9] - temp2[6];

Now it need only 20 multiplication 1 cos and sin
I don't think it can use less multiplication now.

Time to move on for me >_< (still obsessed)

Share this post


Link to post
Share on other sites
RobTheBloke    2553
you can pretty much do everything with a quaternion that you can do with an axis angle pair. So, basically whichever you choose, you still ultimately have to convert to a rotation matrix. A quaternion can save you a few cos and sin calls when manipulating rotations compared to an axis angle representation. Sometimes it 's quicker to use an axis angle, other times it's quicker to use a quaternion.

Share this post


Link to post
Share on other sites
haegarr    7372
The advantage of quaternions is definitely not its speed when it comes to transformations. For trafos there is a quat to matrix conversion senseful as soon as more then two or three vertices are to be transformed. Also multiplying 2 quats is effort.

However, quats are definitely better in the sense of numerical stability, and it is easier to be normalized. For example, I know of a thread elsewhere in GDnet that has discussed the problem of warped space due to too many concatenated rotations w/ matrices. After switching to quats the app runs as expected, w/o the need of re-normalization.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this