Thread: RE: [Algorithms] Fastest way to rotate a vector by a quaternion in a shader
Brought to you by:
vexxed72
From: Willem de B. <wd...@pl...> - 2005-04-29 07:54:15
|
Okay a not-so-rigorous derivation of a fast rotation: Let q=3D(cos(theta/2),sin(theta/2).r) denote a unit quaternion, representing a rotation of theta radians about the unit vector r. It is a basic fact of linear algebra that a rotation leaves=20 one axis invariant (which happens to be our r; hey it's an=20 eigenvector belonging to the eigenvalue 1!), and rotates its=20 orthogonal complement, W, -a plane- by theta radians. So if=20 we orthogonally project v onto W, perform a 2d rotation in W=20 and add v's orthogonal projection onto r to the result,=20 we're done. This amounts to v' =3D (v,r)r + (v - (v,r)r)cos(theta) + (r x v)sin(theta) (1) where we have assumed a right-handed orientation, and (. x .) denotes the cross product, and (. , .) denotes the dot product. This equation can be shown to be equivalent to conjugation, v'=3Dqvq* where v has been mapped to the quaternion v=3D(0,v). All we have to do now is take our quaternion, q, extract r from it as well as cos(theta/2) and sin(theta/2), use some standard trigonometric identities to get cos(theta), and sin(theta), to wit: cos(theta) =3D 2*cos^2(theta/2) - 1, and sin(theta) =3D 2*cos(theta/2)*sin(theta/2), and then apply equation (1) to v, and we're done! So that's 1 dot product (v,r), 1 cross-product (rxv),=20 8 multiplies and 4 adds, and one sqrt (to get sin(theta/2)).=20 I think that should do it, I have used Eq. (1) successfully in the past. Cheers, --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 |
From: Willem de B. <wd...@pl...> - 2005-04-29 08:00:00
|
I should mention that if you store q as (cos(theta/2), sqrt(sin(theta/2).r) you can get rid of the sqrt in the vertex shader. --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Willem de Boer > Sent: Friday, April 29, 2005 9:54 AM > To: gda...@li... > Subject: RE: [Algorithms] Fastest way to rotate a vector by a=20 > quaternion in a shader >=20 > Okay a not-so-rigorous derivation of a fast rotation: >=20 > Let q=3D(cos(theta/2),sin(theta/2).r) denote a unit quaternion,=20 > representing a rotation of theta radians about the unit vector r. >=20 > It is a basic fact of linear algebra that a rotation leaves=20 > one axis invariant (which happens to be our r; hey it's an=20 > eigenvector belonging to the eigenvalue 1!), and rotates its=20 > orthogonal complement, W, -a plane- by theta radians. So if=20 > we orthogonally project v onto W, perform a 2d rotation in W=20 > and add v's orthogonal projection onto r to the result, we're=20 > done. This amounts to >=20 > v' =3D (v,r)r + (v - (v,r)r)cos(theta) + (r x v)sin(theta) (1) >=20 > where we have assumed a right-handed orientation, and (. x .)=20 > denotes the cross product, and (. , .) denotes the dot product. > This equation can be shown to be equivalent to conjugation, > v'=3Dqvq* where v has been mapped to the quaternion v=3D(0,v). >=20 > All we have to do now is take our quaternion, q, extract r=20 > from it as well as cos(theta/2) and sin(theta/2), use some=20 > standard trigonometric identities to get cos(theta), and=20 > sin(theta), to wit: >=20 > cos(theta) =3D 2*cos^2(theta/2) - 1, and > sin(theta) =3D 2*cos(theta/2)*sin(theta/2), >=20 > and then apply equation (1) to v, and we're done! >=20 > So that's 1 dot product (v,r), 1 cross-product (rxv), > 8 multiplies and 4 adds, and one sqrt (to get sin(theta/2)).=20 >=20 > I think that should do it, I have used Eq. (1) successfully=20 > in the past. >=20 > Cheers, > --- > Willem H. de Boer > Homepage: http://www.whdeboer.com=20 >=20 >=20 >=20 >=20 > ------------------------------------------------------- > SF.Net email is sponsored by: Tell us your software development plans! > Take this survey and enter to win a one-year sub to=20 > SourceForge.net Plus IDC's 2005 look-ahead and a copy of this=20 > survey Click here to start! =20 > http://www.idcswdc.com/cgi-bin/survey?id=105hix > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 |
From: <c.s...@ph...> - 2005-04-29 09:16:23
|
off the top of my head, try this x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) if it doesnt work, try changing - with + or reverse the cross prod = arguments. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Thursday, April 28, 2005 11:59 PM To: gda...@li... Subject: [Algorithms] Fastest way to rotate a vector by a quaternion in = a shader Looking through the list archives I came across this snippet from Jarkko = Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total = of 6 instructions, which is the same as your 2*cross-prod + 2 mads I = guess" I've been playing around with the definitions for quaternion = multiplication and rotating a vector by a quaternion and the best I've = been able to do is 8 instructions. Can anyone enlighten me on how it's = done in 6? Bonus points for a derivation I can follow :-) This was my = best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to = the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt. ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Willem de B. <wd...@pl...> - 2005-04-29 12:13:46
|
Hi, > off the top of my head, try this >=20 > x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) >=20 After some mulling over the result I previously obtained, I arrived at the following routine for rotating a vector=20 v by a unit quaternion q: float3 RotateVector3ByQuaternion( float3 v, float4 q ) { w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w - 0.5f) * v + q.w*cross(v,w) ); return res; } That's 1 dot product, 1 cross product, 7 adds, 11 multiplies, compared to 2 cross products, 6 adds, 6 multiplies for Christian's solution. --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 |
From: <c.s...@ph...> - 2005-04-29 13:12:18
|
...? I count 6 instructions: // cross( Q.xyz, X ) mul r0, Q.yzx, X.zxy mad r0, Q.zxy, -X.yzx =20 // ... - Q.w * X mad r0, -Q.w, X, r0 // cross( Q.xyz, ... ) mul r1, Q.yzx, r0.zxy mad r1, Q.zxy, -r0.yzx // X' =3D X + 2 * ... mad r0, 2, r1, X =20 -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Willem de Boer Sent: Friday, April 29, 2005 2:14 PM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader Hi, > off the top of my head, try this >=20 > x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) >=20 After some mulling over the result I previously obtained, I arrived at the following routine for rotating a vector=20 v by a unit quaternion q: float3 RotateVector3ByQuaternion( float3 v, float4 q ) { w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w - 0.5f) * v + q.w*cross(v,w) ); return res; } That's 1 dot product, 1 cross product, 7 adds, 11 multiplies, compared = to 2 cross products, 6 adds, 6 multiplies for Christian's solution. --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Willem de B. <wd...@pl...> - 2005-04-29 13:23:25
|
> ...? > I count 6 instructions: Sure, I was just comparing methods by counting the number of _actual_ additions and multiplications they take up; I wasn't counting vertex shader instructions. I'm not very good at hand-optimising vertex shader assembly, if someone more in the know could translate the following routine into assembly, we can start comparing instruction counts: > float3 RotateVector3ByQuaternion( float3 v, float4 q ) { > w =3D q.xyz; > float3 vww =3D dot(v,w)*w; > float3 res =3D 2.f * (vww + > (q.w*q.w - 0.5f) * v + > q.w*cross(v,w) > ); > return res; > } Cheers, Willem |
From: <c.s...@ph...> - 2005-04-29 13:37:39
|
I guess it's not very optimal since there seems to be a longer = dependency chain on scalar values. HLSL says this float4 q; float4 test( float3 v : POSITION ) : POSITION { float3 w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w - 0.5f) * v + q.w*cross(v,w) ); return float4( res, 1 ); } // "q" is c1 vs_1_1 def c0, -0.5, 1, 0, 0 dcl_position v0 mov r0.x, c1.w mad r0.w, r0.x, r0.x, c0.x mul r1.xyz, r0.w, v0 dp3 r2.x, v0, c1 mul r0.xyz, v0.zxyw, c1.yzxw mad r1.xyz, r2.x, c1, r1 mad r0.xyz, v0.yzxw, c1.zxyw, -r0 mad r0.xyz, c1.w, r0, r1 add oPos.xyz, r0, r0 mov oPos.w, c0.y -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Willem de Boer Sent: Friday, April 29, 2005 3:23 PM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader > ...? > I count 6 instructions: Sure, I was just comparing methods by counting the number of _actual_ additions and multiplications they take up; I wasn't = counting vertex shader instructions. I'm not very good at hand-optimising vertex shader assembly, if someone more in the know could translate the following routine into = assembly, we can start comparing instruction counts: > float3 RotateVector3ByQuaternion( float3 v, float4 q ) { > w =3D q.xyz; > float3 vww =3D dot(v,w)*w; > float3 res =3D 2.f * (vww + > (q.w*q.w - 0.5f) * v + > q.w*cross(v,w) > ); > return res; > } Cheers, Willem ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Willem de B. <wd...@pl...> - 2005-04-29 13:48:31
|
> I guess it's not very optimal since there seems to be a=20 > longer dependency chain on scalar values. Ah, that's a pity; if I'm not mistaken our methods require the same number of adds, but mine requires 2 fewer multiplies. Shame that doesn't carry over into the actual number of instructions.. :( Cheers, Willem |
From: jarkko l. <ja...@vi...> - 2005-04-29 17:45:38
|
Hmh, seems my email got stuck somewhere. Anyway, Christians method is actually 4 muls less than yours with 18 muls + 12 adds vs. 22 muls + 12 adds. Jarkko ----- Original Message ----- From: "Willem de Boer" <wd...@pl...> To: <gda...@li...> Sent: Friday, April 29, 2005 9:48 AM Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion in a shader > I guess it's not very optimal since there seems to be a > longer dependency chain on scalar values. Ah, that's a pity; if I'm not mistaken our methods require the same number of adds, but mine requires 2 fewer multiplies. Shame that doesn't carry over into the actual number of instructions.. :( Cheers, Willem ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a one-year sub to SourceForge.net Plus IDC's 2005 look-ahead and a copy of this survey Click here to start! http://www.idcswdc.com/cgi-bin/survey?id5hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Newport, M. <mne...@ea...> - 2005-04-29 18:02:58
|
I actually reached exactly the same result by manipulation of my original version on further investigation yesterday. My orignal version (presented more compactly than in my original email) was: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 wv_plus_qcrossv =3D q.w * v + cross(q.xyz, v); return dot(q.xyz, v) * q.xyz + (q.w * wv_plus_qcrossv + cross(q.xyz, wv_plus_qcrossv)); } Which compiles down to 8 instructions. My version of the routine you give below was this: float3 RotateVectorByQuaternion2(float3 v, float4 q) { return 2 * (dot(q.xyz, v) * q.xyz + (q.w * q.w - 0.5) * v + q.w * cross(q.xyz, v)); } Which compiles to 9 instructions but has a scalar operation which some hardware may be able to do in parallel with one of the vector ops so it's probably the same speed.=20 Your original derivation is a lot simpler than the working I went through to get the second routine though :-) Thanks, Matt. -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Willem de Boer Sent: Friday, April 29, 2005 5:14 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion in a shader Hi, > off the top of my head, try this >=20 > x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) >=20 After some mulling over the result I previously obtained, I arrived at the following routine for rotating a vector v by a unit quaternion q: float3 RotateVector3ByQuaternion( float3 v, float4 q ) { w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w - 0.5f) * v + q.w*cross(v,w) ); return res; } That's 1 dot product, 1 cross product, 7 adds, 11 multiplies, compared to 2 cross products, 6 adds, 6 multiplies for Christian's solution. --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a one-year sub to SourceForge.net Plus IDC's 2005 look-ahead and a copy of this survey Click here to start! http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Newport, M. <mne...@ea...> - 2005-04-29 18:12:29
|
Cool, that works if I change the - Q.w * x to + Q.w * x. Now I just have = to try and figure out how it works :-) Thanks a lot, I was beginning to think it wasn't possible to get it down = to 6 instructions after playing around with it for quite a while = yesterday.=20 Matt. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Christian Sch=FCler Sent: Friday, April 29, 2005 2:16 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader off the top of my head, try this x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) if it doesnt work, try changing - with + or reverse the cross prod = arguments. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Thursday, April 28, 2005 11:59 PM To: gda...@li... Subject: [Algorithms] Fastest way to rotate a vector by a quaternion in = a shader Looking through the list archives I came across this snippet from Jarkko = Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total = of 6 instructions, which is the same as your 2*cross-prod + 2 mads I = guess" I've been playing around with the definitions for quaternion = multiplication and rotating a vector by a quaternion and the best I've = been able to do is 8 instructions. Can anyone enlighten me on how it's = done in 6? Bonus points for a derivation I can follow :-) This was my = best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to = the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt. ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: <c.s...@ph...> - 2005-04-29 18:29:43
|
I did the Q*v*Q~ expansion in geometric algebra, a long time back, and = buried the result some .h file somewhere. I could have a look if I find = the original derivation and post it later. My quaternions are "GA"-quaternions, not Hamiltonians. This explains the different sign :) -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Friday, April 29, 2005 8:03 PM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader I actually reached exactly the same result by manipulation of my = original version on further investigation yesterday. My orignal version = (presented more compactly than in my original email) was: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 wv_plus_qcrossv =3D q.w * v + cross(q.xyz, v); return dot(q.xyz, v) * q.xyz + (q.w * wv_plus_qcrossv + cross(q.xyz, wv_plus_qcrossv)); } Which compiles down to 8 instructions. My version of the routine you = give below was this: float3 RotateVectorByQuaternion2(float3 v, float4 q) { return 2 * (dot(q.xyz, v) * q.xyz + (q.w * q.w - 0.5) * v + q.w * cross(q.xyz, v)); } Which compiles to 9 instructions but has a scalar operation which some = hardware may be able to do in parallel with one of the vector ops so = it's probably the same speed.=20 Your original derivation is a lot simpler than the working I went = through to get the second routine though :-) Thanks, Matt. -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of = Willem de Boer Sent: Friday, April 29, 2005 5:14 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader Hi, > off the top of my head, try this >=20 > x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) >=20 After some mulling over the result I previously obtained, I arrived at = the following routine for rotating a vector v by a unit quaternion q: float3 RotateVector3ByQuaternion( float3 v, float4 q ) { w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w - 0.5f) * v + q.w*cross(v,w) ); return res; } That's 1 dot product, 1 cross product, 7 adds, 11 multiplies, compared = to 2 cross products, 6 adds, 6 multiplies for Christian's solution. --- Willem H. de Boer Homepage: http://www.whdeboer.com=20 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- This SF.Net email is sponsored by: NEC IT Guy Games. Get your fingers limbered up and give it your best shot. 4 great events, = 4 opportunities to win big! Highest score wins.NEC IT Guy Games. Play to = win an NEC 61 plasma display. Visit http://www.necitguy.com/?r=20 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Newport, M. <mne...@ea...> - 2005-04-29 18:47:10
|
Ok, knowing what the final result was supposed to be I managed to derive = it from my original expression. Funny how much easier it is when you = know what you're supposed to end up with :-) Here's the derivation for anyone who's interested: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* I'd already expanded this through to get: v' =3D (s.v)s + w(wv + s x v) + s x (wv + s x v) Where s is the vector part of the quaternion and w is the scalar part (q = =3D (w, s)) Expanding this out further gives: v' =3D (s.v)s + (w^2)v + 2w(s x v) + s x (s x v) The cunning trick which I hadn't spotted before is then to use the = vector triple product identity: a x (b x c) =3D b(a.c) - c(a.b) To give v' + s(s.v) - v(s.s) =3D (s.v)s + (w^2)v + 2w(s x v) + 2(s x (s x v)) Cancelling to: v' =3D (w^2 + s.s)v + 2(s x (s x v + wv)) From the definition of a quaternion representing a rotation, w =3D = cos(a/2), s =3D sin(a/2)*r where r is a unit vector representing the = axis of the rotation. So (w^2 + s.s) =3D (cos(a/2))^2 + (sin(a/2))^2 =3D = 1, giving us the final formula: v' =3D v + 2(s x (s x v + vw)) Neat :-) Thanks, Matt. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Friday, April 29, 2005 11:12 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader Cool, that works if I change the - Q.w * x to + Q.w * x. Now I just have = to try and figure out how it works :-) Thanks a lot, I was beginning to think it wasn't possible to get it down = to 6 instructions after playing around with it for quite a while = yesterday.=20 Matt. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Christian Sch=FCler Sent: Friday, April 29, 2005 2:16 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader off the top of my head, try this x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) if it doesnt work, try changing - with + or reverse the cross prod = arguments. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Thursday, April 28, 2005 11:59 PM To: gda...@li... Subject: [Algorithms] Fastest way to rotate a vector by a quaternion in = a shader Looking through the list archives I came across this snippet from Jarkko = Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total = of 6 instructions, which is the same as your 2*cross-prod + 2 mads I = guess" I've been playing around with the definitions for quaternion = multiplication and rotating a vector by a quaternion and the best I've = been able to do is 8 instructions. Can anyone enlighten me on how it's = done in 6? Bonus points for a derivation I can follow :-) This was my = best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to = the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt. ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- This SF.Net email is sponsored by: NEC IT Guy Games. Get your fingers limbered up and give it your best shot. 4 great events, = 4 opportunities to win big! Highest score wins.NEC IT Guy Games. Play to = win an NEC 61 plasma display. Visit http://www.necitguy.com/?r = _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |
From: Jarkko L. <Jar...@ub...> - 2005-04-29 19:17:15
|
I did basically the same but went to the final formula by: q=3D[qv, w] v'=3D2((qv.v)qv - (qv.qv)v + w(qv x v)) + v by using the triple product again: :(a.c)b - (a.b)c =3D a x (b x c), a=3Db=3Dqv, c=3Dv v'=3D2(qv x (qv x v) + w(qv x v))+v :a x b + a x c =3D a x (b + c) v'=3D2(qv x (qv x v) + (qv x wv))+v v'=3D2(qv x (qv x v + wv)) + v Was a good way to refresh the dusted vector math part of my brain again = ;) Jarkko -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: April 29, 2005 2:47 PM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader Ok, knowing what the final result was supposed to be I managed to derive = it from my original expression. Funny how much easier it is when you = know what you're supposed to end up with :-) Here's the derivation for anyone who's interested: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* I'd already expanded this through to get: v' =3D (s.v)s + w(wv + s x v) + s x (wv + s x v) Where s is the vector part of the quaternion and w is the scalar part (q = =3D (w, s)) Expanding this out further gives: v' =3D (s.v)s + (w^2)v + 2w(s x v) + s x (s x v) The cunning trick which I hadn't spotted before is then to use the = vector triple product identity: a x (b x c) =3D b(a.c) - c(a.b) To give v' + s(s.v) - v(s.s) =3D (s.v)s + (w^2)v + 2w(s x v) + 2(s x (s x v)) Cancelling to: v' =3D (w^2 + s.s)v + 2(s x (s x v + wv)) From the definition of a quaternion representing a rotation, w =3D = cos(a/2), s =3D sin(a/2)*r where r is a unit vector representing the = axis of the rotation. So (w^2 + s.s) =3D (cos(a/2))^2 + (sin(a/2))^2 =3D = 1, giving us the final formula: v' =3D v + 2(s x (s x v + vw)) Neat :-) Thanks, Matt. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Friday, April 29, 2005 11:12 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader Cool, that works if I change the - Q.w * x to + Q.w * x. Now I just have = to try and figure out how it works :-) Thanks a lot, I was beginning to think it wasn't possible to get it down = to 6 instructions after playing around with it for quite a while = yesterday.=20 Matt. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Christian Sch=FCler Sent: Friday, April 29, 2005 2:16 AM To: gda...@li... Subject: RE: [Algorithms] Fastest way to rotate a vector by a quaternion = in a shader off the top of my head, try this x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x ) - Q.w * x ) if it doesnt work, try changing - with + or reverse the cross prod = arguments. -----Original Message----- From: gda...@li... = [mailto:gda...@li...] On Behalf Of = Newport, Matthew Sent: Thursday, April 28, 2005 11:59 PM To: gda...@li... Subject: [Algorithms] Fastest way to rotate a vector by a quaternion in = a shader Looking through the list archives I came across this snippet from Jarkko = Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total = of 6 instructions, which is the same as your 2*cross-prod + 2 mads I = guess" I've been playing around with the definitions for quaternion = multiplication and rotating a vector by a quaternion and the best I've = been able to do is 8 instructions. Can anyone enlighten me on how it's = done in 6? Bonus points for a derivation I can follow :-) This was my = best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2 - v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to = the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt. ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a one-year sub to SourceForge.net Plus = IDC's 2005 look-ahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgi-bin/survey?id=105hix _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- This SF.Net email is sponsored by: NEC IT Guy Games. Get your fingers limbered up and give it your best shot. 4 great events, = 4 opportunities to win big! Highest score wins.NEC IT Guy Games. Play to = win an NEC 61 plasma display. Visit http://www.necitguy.com/?r = _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 ------------------------------------------------------- This SF.Net email is sponsored by: NEC IT Guy Games. Get your fingers limbered up and give it your best shot. 4 great events, = 4 opportunities to win big! Highest score wins.NEC IT Guy Games. Play to = win an NEC 61 plasma display. Visit http://www.necitguy.com/?r = _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 |