Thread: [Algorithms] Representing Animation Key Frame with Quaternion + Translation Vector
Brought to you by:
vexxed72
From: Lim S. C. <si...@ga...> - 2008-06-23 04:43:35
|
Since a quaternion is compact compared to a 4x4 homogeneous matrix, I am considering representing our animation key frame data with pairs of orientation quaternion and translation vector. Naively, this seems to save me 56.25% of memory space and that sure comes in handy when we have a lot of animation data. Just wondering if anyone has done this before and whether it is really better in terms of performance and accuracy. One problem I still haven't solved is concatenating my quaternion-vector key frames without converting them into matrices first. I know I can concatenate quaternion by taking their cross product, but I do not know how to do so for the translation vector. I will be much obliged if someone could show me a few hints or pointers. Cheers! |
From: Marc B. R. <mar...@or...> - 2008-06-23 07:57:58
|
There's tons of material avail. You have a 3-bivector, 3-vector & scalar. So you can check out "dual-quaternions" (aka study parameter quaternions) and similarly: Clifford algebra (aka Geometric Algebra). Using any of these will give an algebraic framework to do your development. Personally I STRONGLY suggest choosing an algebra and learning the basics rather than using an algorithmic "black-box". As a caveat I should mention that much of the literature concerning quaternions & dual-quaterions are loaded errors, so if you start to look deeper into the algebra, don't assume that all statements are correct...luckly for your usage these are a non-issue. -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Lim Sin Chian Sent: Monday, June 23, 2008 6:44 AM To: gda...@li... Subject: [Algorithms] Representing Animation Key Frame with Quaternion +Translation Vector Since a quaternion is compact compared to a 4x4 homogeneous matrix, I am considering representing our animation key frame data with pairs of orientation quaternion and translation vector. Naively, this seems to save me 56.25% of memory space and that sure comes in handy when we have a lot of animation data. Just wondering if anyone has done this before and whether it is really better in terms of performance and accuracy. One problem I still haven't solved is concatenating my quaternion-vector key frames without converting them into matrices first. I know I can concatenate quaternion by taking their cross product, but I do not know how to do so for the translation vector. I will be much obliged if someone could show me a few hints or pointers. Cheers! |
From: Bill B. <wb...@gm...> - 2008-06-23 08:01:44
|
On Mon, Jun 23, 2008 at 4:57 PM, Marc B. Reynolds <mar...@or...> wrote: > So you can check out "dual-quaternions" (aka study parameter quaternions) Is "study parameter" a typo there? I couldn't find any google hits on that phrase. --bb |
From: Marc B. R. <mar...@or...> - 2008-06-23 08:25:22
|
> Is "study parameter" a typo there? I couldn't find any google hits on that phrase. Try "study parameters", with an additional key, such as: kinematics, screw, wrench, twist, robotics, etc. Some works use "Study parameters" to replace the "dual", since dual is heavily overloaded in mathematics. |
From: Lim S. C. <si...@ga...> - 2008-06-23 10:08:40
|
Thanks for the replies, guys. Suppose I have a hierarchy with 2 connected bones. One of them (bone0) is the root, the other (bone1) is the child. Say bone0 has transformation T0 (q0, p0) and bone 1 has T1 (q1, p1), where q0, q1 are quaternions representing modelling space rotation, and p0, p1 are vectors representing modelling space translations. To compute the world space orientation for bone1, I would do the following: q1World = qWorld X q0 X q1; I am really interested to find out if there is a similar way to compute the world space translation for bone1. Thanks! "Marc B. Reynolds" <mar...@or...> wrote: > Is "study parameter" a typo there? I couldn't find any google hits on that phrase. Try "study parameters", with an additional key, such as: kinematics, screw, wrench, twist, robotics, etc. Some works use "Study parameters" to replace the "dual", since dual is heavily overloaded in mathematics. ------------------------------------------------------------------------- Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://sourceforge.net/services/buy/index.php _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jason H. <jas...@di...> - 2008-06-23 18:02:00
|
From what you're asking, if you want to transform a relative-space vector from the leaf node, you do something like this: rv = relative to p1 wv = desired world vector wv = p0 + -q0 * (p1 + -q1 * rv) = p(n-1) + (-q(n-1) * v) ... You simply need to invert the quaternions (negation) to transform the opposite direction. Transforming a point is just loading a quaternion with XYZ0 and doing a quaternion multiply, if I recall correctly. Since each node has translation relative to its parent, you add that after you transform the point into the parent space. Of course, you'll want to look over the Matrix and Quaternion FAQ for the exact math for it. It's sufficient for a layman to get the code working. Note that the above configuration is completely incompatible with scale, unless you allow non-unit quaternions and can wrangle that beast... Hope that helps, JH Lim Sin Chian wrote: > Thanks for the replies, guys. > > Suppose I have a hierarchy with 2 connected bones. One of them (bone0) > is the root, the other (bone1) is the child. > > Say bone0 has transformation T0 (q0, p0) and bone 1 has T1 (q1, p1), > where q0, q1 are quaternions representing modelling space rotation, > and p0, p1 are vectors representing modelling space translations. > > To compute the world space orientation for bone1, I would do the > following: > q1World = qWorld X q0 X q1; > > I am really interested to find out if there is a similar way to > compute the world space translation for bone1. > > Thanks! > > > */"Marc B. Reynolds" <mar...@or...>/* wrote: > > > > > Is "study parameter" a typo there? I couldn't find any google > hits on > that phrase. > > Try "study parameters", with an additional key, such as: > kinematics, screw, wrench, twist, robotics, etc. > > Some works use "Study parameters" to replace the "dual", since dual is > heavily overloaded in mathematics. > > > > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://sourceforge.net/services/buy/index.php > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://sourceforge.net/services/buy/index.php > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: pontus b. <her...@ho...> - 2008-06-23 21:19:15
|
Intressting topic, how would you go about skinning a mesh using this kind of data? Is hardware skinning still an option? I assume matrix and vector operations are heavily optimized on current gpus. In the current solution I'm working with we keep the animation data as quaternions and vectors (all transforms relative the parent) in order to interpolate efficiently as well as perform blending operations. In the end we still convert them into matrices, then do a full hierarchy matrix mul before sending the matrices to the gpu. Pontus Date: Mon, 23 Jun 2008 13:01:52 -0500From: jas...@di...To: gda...@li...Subject: Re: [Algorithms] Representing Animation Key Frame with Quaternion+Translation Vector >From what you're asking, if you want to transform a relative-space vector from the leaf node, you do something like this:rv = relative to p1wv = desired world vectorwv = p0 + -q0 * (p1 + -q1 * rv) = p(n-1) + (-q(n-1) * v) ...You simply need to invert the quaternions (negation) to transform the opposite direction. Transforming a point is just loading a quaternion with XYZ0 and doing a quaternion multiply, if I recall correctly. Since each node has translation relative to its parent, you add that after you transform the point into the parent space. Of course, you'll want to look over the Matrix and Quaternion FAQ for the exact math for it. It's sufficient for a layman to get the code working.Note that the above configuration is completely incompatible with scale, unless you allow non-unit quaternions and can wrangle that beast...Hope that helps,JHLim Sin Chian wrote: Thanks for the replies, guys. Suppose I have a hierarchy with 2 connected bones. One of them (bone0) is the root, the other (bone1) is the child. Say bone0 has transformation T0 (q0, p0) and bone 1 has T1 (q1, p1), where q0, q1 are quaternions representing modelling space rotation, and p0, p1 are vectors representing modelling space translations. To compute the world space orientation for bone1, I would do the following: q1World = qWorld X q0 X q1; I am really interested to find out if there is a similar way to compute the world space translation for bone1. Thanks! "Marc B. Reynolds" <mar...@or...> wrote: > Is "study parameter" a typo there? I couldn't find any google hits onthat phrase.Try "study parameters", with an additional key, such as:kinematics, screw, wrench, twist, robotics, etc. Some works use "Study parameters" to replace the "dual", since dual isheavily overloaded in mathematics. -------------------------------------------------------------------------Check out the new SourceForge.net Marketplace.It's the best place to buy or sell services forjust about anything Open Source.http://sourceforge.net/services/buy/index.php_______________________________________________GDAlgorithms-list mailing lis...@li...https://lists.sourceforge.net/lists/listinfo/gdalgorithms-listArchives:http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------- Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://sourceforge.net/services/buy/index.php _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list _________________________________________________________________ Ladda ner hela Windows Live gratis och upptäck fördelarna! http://get.live.com/ |
From: Jon W. <jw...@gm...> - 2008-06-23 21:31:35
|
pontus birgersson wrote: > > Intressting topic, how would you go about skinning a mesh using this > kind of data? Is hardware skinning still an option? I assume matrix > and vector operations are heavily optimized on current gpus. Yes, you can still hardware skin. In fact, you can do more bones per pass, because offset+quaternion is only 2 constant registers, whereas a matrix is at least 3 constant registers. The code to transform a vertex by a quaternion is slightly more expensive than the code to transform by a matrix, as is the code to blend quaternions, but it will still fit in a shader model 2 vertex shader. > > In the current solution I'm working with we keep the animation data as > quaternions and vectors (all transforms relative the parent) in order > to interpolate efficiently as well as perform blending operations. In > the end we still convert them into matrices, then do a full hierarchy > matrix mul before sending the matrices to the gpu. We do the same thing, except we do the hierarchy multiplication in quaternions/offsets, and only convert to matrices when sending to the card (as 3x4 mats). It's a decent compromise. Sincerely, jw |
From: pontus b. <her...@ho...> - 2008-06-23 21:44:50
|
> pontus birgersson wrote:> > In the current solution I'm working with we keep the animation data as > > quaternions and vectors (all transforms relative the parent) in order > > to interpolate efficiently as well as perform blending operations. In > > the end we still convert them into matrices, then do a full hierarchy > > matrix mul before sending the matrices to the gpu.> > We do the same thing, except we do the hierarchy multiplication in > quaternions/offsets, and only convert to matrices when sending to the > card (as 3x4 mats). It's a decent compromise. Yes I'm also sending 3x4 matrices and then reconstructing them as 4x4 matrices in the vertex shader but I've been thinking of discarding that solution in order to avoid the reconstruction but not sure whether or not it's a good tradeoff. Have you measured any of this? I'm guessing it depends on the target plattform. Early rather crude tests on my old GeForce 6800 told me that it might be worth sending a bit more data in order to releave the vertex shader of the additional reconstruction. Since since we're mainly targetting the Xbox 360 which I've heard has a beast for vertex processor, the same will probably not be true there. Pontus _________________________________________________________________ Trött på jobbet? Hitta nya utmaningar här! http://msn.jobbguiden.se/jobseeker/resumes/postresumenew/postresumestart.aspx?sc_cmp2=JS_INT_SEMSN_NLPCV |
From: Jon W. <jw...@gm...> - 2008-06-23 23:45:10
|
pontus birgersson wrote: > I'm guessing it depends on the target plattform. Early rather crude > tests on my old GeForce 6800 told me that it might be worth sending a > bit more data in order to releave the vertex shader of the additional > reconstruction. Since since we're mainly targetting the Xbox 360 which > I've heard has a beast for vertex processor, the same will probably > not be true there. > Why reconstruct a 4x4 for a bone matrix? You can blend the bones as three vector4s, and you can transform the vertex using three dot products. Only the projection matrix really needs a full 4x4. The point about "sending more data" does not have to do with the data throughput, it has to do with how many bones you can cram into a single pass, without splitting your mesh. With 4x4 matrices, you can do about 60; with 4x3 you can do about 80; with offset + quaternion you can do about 120! Sincerely, jw |
From: pontus b. <her...@ho...> - 2008-06-24 06:28:12
|
Thanks! I think I might be seing some intresting opmitizations ahead. Pontus > Date: Mon, 23 Jun 2008 16:45:05 -0700> From: jw...@gm...> To: gda...@li...> Subject: Re: [Algorithms] Representing Animation Key Frame with Quaternion+Translation Vector> > pontus birgersson wrote:> > I'm guessing it depends on the target plattform. Early rather crude > > tests on my old GeForce 6800 told me that it might be worth sending a > > bit more data in order to releave the vertex shader of the additional > > reconstruction. Since since we're mainly targetting the Xbox 360 which > > I've heard has a beast for vertex processor, the same will probably > > not be true there.> > > > Why reconstruct a 4x4 for a bone matrix? You can blend the bones as > three vector4s, and you can transform the vertex using three dot > products. Only the projection matrix really needs a full 4x4.> The point about "sending more data" does not have to do with the data > throughput, it has to do with how many bones you can cram into a single > pass, without splitting your mesh. With 4x4 matrices, you can do about > 60; with 4x3 you can do about 80; with offset + quaternion you can do > about 120!> > Sincerely,> > jw> > > -------------------------------------------------------------------------> Check out the new SourceForge.net Marketplace.> It's the best place to buy or sell services for> just about anything Open Source.> http://sourceforge.net/services/buy/index.php> _______________________________________________> GDAlgorithms-list mailing list> GDA...@li...> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list> Archives:> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list _________________________________________________________________ Utmana dina kompisar i Sten, sax, påse! http://www.live.msn.se/messenger/#/News/ |
From: Marc B. R. <mar...@or...> - 2008-06-24 11:14:36
|
Cayley in [1,2] demonstrates general 3D rotations via quaternions, (left-handed and right-handed respectively). >From [2]: P' = Q P (1/Q) (e.1) Notice that if you multiply Q by an non-zero scale factor 's', you get: P' = (sQ) P (1/(sQ)) = (s/s) Q P (1/Q) = Q P (1/Q) So if we consider some quaternion Q to respresent a rotation using (e.1), all scalar multiples of Q represent the same rotation. If we additionally consider Q to be a point in some 4D space, then the point is homogenous and (since we've dropped one degree of freedom) is a 3D object embedded in the 4D space. The set of all quaternions which represent the same rotation may be described as 'sQ', again for all 's' except zero and is a line through the space. Unit quaterions come into play since the inverse can be replaced by the conjugate, which has nice algebraic, numeric and computation properties. So if U is a unit quaternion we can instead use the following: R' = U R U* (e.2) The set of all unit quaternions is a sphere and the line of all quaternions which represent a given rotation intersects the sphere at two points (thus the double coverage). Continuing to use (e.2), let's plug in a non unit quaternion: Q=sU R'' = Q R Q* = (sU) R (sU)* = (s^2) U P U* = (s^2) R' So R'' is R' scaled by a factor of (s^2). Composition of rotations is achieved by the product: C = A B Multiply 'A' and 'B' by non-zero scales 'a' and 'b' respectively: C = (aA)(bB) = (ab)AB Combining all of the above, to effect a scaled rotation, use a quaternion which has a magnitude of the square-root of the desired scaled factor in (e.2). ---- [ 1] "On certain results concerning quaternions", Arthur Cayley, 1845 [ 2] "On the Application of Quaternions to the Theory of Rotation", Arthur Cayley,1848 |
From: Jon W. <jw...@gm...> - 2008-06-24 17:27:44
|
Marc B. Reynolds wrote: > Cayley in [1,2] demonstrates general 3D rotations via quaternions, > (left-handed and right-handed respectively). I'm sorry, but what separates a "left-handed" from a "right-handed" rotation? In what space interpretation? It should be obvious that a rotation in left-handed space interpretation is exactly equal to that same rotation in right-handed space interpretation, but, because of the differences in interpretation, if rendered into a fixed device space they will appear as mirror images. More directly: rotation the Z unit vector around the Y unit vector as axis by PI/2 radians always generates the X unit vector, no matter whether you choose to interpret your coordinates left-handed, or right-handed. In a left-handed coordinate space, you use the left hand to visualize the rotation; in a right-handed coordinate space, you use the right hand to visualize the rotation, but the actual math is exactly the same in both cases! Maybe what you (or the original paper author) mean to say is "both forward and inverse rotations" ? Rotation math, in itself, has no handedness; it is only the interpretation of the coordinates in the coordinate space that is handed. That should be obvious to anyone who does computer graphics, but time and again, I hear the mis-nomers "left/right-handed rotation" and it drives me nuts! It's as bad as talking about "row major matrices" without specifying whether you're using row vectors (on the left) or column vectors (on the right). Sincerely, jw |
From: Marc B. R. <mar...@or...> - 2008-06-25 14:25:39
|
>> Cayley in [1,2] demonstrates general 3D rotations via quaternions, >> (left-handed and right-handed respectively). > I'm sorry, but what separates a "left-handed" from a "right-handed" > rotation? In what space interpretation? The space is the field around the directed line (in the case of 3D), so it is independent of any coordinate frame convention and has the same meaning if you're "coordinate-free". So if your thumb (in "thumps-up" position) points in direction of the directed line, curled fingers point in the direction of the surrounding the field. (If your very double-jointed, fingers toward your palms please!) Obviously the only difference between the two is direction of the surrounding field and the two flavors are mutual inverses. Of course you can flip one into the other by either changing the direction of the directed line or negation of the angle. > It should be obvious that a rotation in left-handed space interpretation > is exactly equal to that same rotation in right-handed space > interpretation, but, because of the differences in interpretation, if > rendered into a fixed device space they will appear as mirror images. > More directly: rotation the Z unit vector around the Y unit vector as > axis by PI/2 radians always generates the X unit vector, no matter > whether you choose to interpret your coordinates left-handed, or > right-handed. What I'm calling 'right-handed' will return X, 'left-handed' will return -X. (Or vice-versa) Flip any of your coordinate definitions and the signs will flip. Stick your thumb pointing in 'Y', finger out straight on 'Z', turn pi/2 radian in the direction of your palm. Repeat with other hand and you're rotating in the opposite direction...regardless of how you name your coordinate frame. > In a left-handed coordinate space, you use the left hand > to visualize the rotation; in a right-handed coordinate space, you use > the right hand to visualize the rotation, but the actual math is exactly > the same in both cases! We're obviously using the same term to refer to two different things, because the algebraic formulations differ. Here's some sample formulas that represent rotations in quaternions, with various different constraints: Q P (1/Q) R.1 (1/Q) P Q L.1 Q P Q* R.2 |Q|=1 Q* P Q L.2 |Q|=1 Q P R.3 P.Q=0, |Q|=1 P Q L.3 P.Q=0, |Q|=1 The differences between each pair are trivially once expanded (sign differences), but they are algebraically distinct and are valid representations of rotations. > Maybe what you (or the original paper author) mean to say is "both > forward and inverse rotations" ? Cayley came up with all kinds of cool stuff, so if he wants to call stuff right & left handed...I'm all for it. <http://en.wikipedia.org/wiki/Arthur_Cayley> http://en.wikipedia.org/wiki/Arthur_Cayley (The proceeding was "tongue-in-cheek"). I personally find "forward" and "reverse" more ambiguous terms, since they require a given convention. Let's say 'counter-clockwise' and 'clockwise' when the directed line is going into your eye, and then call them 'forward' and 'reverse' or 'inverse' respectively? > Rotation math, in itself, has no > handedness; it is only the interpretation of the coordinates in the > coordinate space that is handed. It should be obvious that I disagree with this statement. And it might be more useful during algebraic manipulation to choose one form over the other, regardless of the choose direction of a 'forward' rotation. > That should be obvious to anyone who > does computer graphics, but time and again, I hear the mis-nomers > "left/right-handed rotation" and it drives me nuts! It's as bad as > talking about "row major matrices" without specifying whether you're > using row vectors (on the left) or column vectors (on the right). |
From: Jon W. <jw...@gm...> - 2008-06-25 17:45:22
|
Marc B. Reynolds wrote: > What I'm calling 'right-handed' will return X, 'left-handed' will > return -X. > (Or vice-versa) Flip any of your coordinate definitions and the signs > will flip. To be specific, what you're calling "right-handed" (rotations) will return X (in a right-handed coordinate space). My point is that the words in parentheses are important, because leaving them out leaves the text open for ambiguity. There's way too much ambiguity in geometrics and especially graphics papers, because there are two conventions for everything, and the authors usually assume that everyone is using the particular conventions that he (the author) is used to, without stating what they are. > > We're obviously using the same term to refer to two different things, > because the algebraic formulations differ. Here's some sample > formulas that represent rotations in quaternions, with various > different constraints: > > Q P (1/Q) R.1 > (1/Q) P Q L.1 I see you are assuming column vectors on the right in a right-handed space. You might want to state those assumptions to make your formulas unambiguous. For examples of popular graphics APIs that don't use those assumptions, look no further than to Direct3D. > > I personally find "forward" and "reverse" more ambiguous terms, since > they require a given convention. Let's say 'counter-clockwise' and > 'clockwise' > when the directed line is going into your eye, and then call them > 'forward' and > 'reverse' or 'inverse' respectively? I guess my point is that ALL those words are ambiguous, because they require that you specify at least two pieces of data when writing down on paper: vector convention (left or right) and coordinate system interpretation (right-handed or left-handed). Using the same names as used for coordinate systems to also tell clockwise and counter-clockwise rotations sans coordinate system apart leads to too much ambiguity. Just look at the number of quaternion resources on the web that are, at best, misleading, because they don't state their conventions, or even mix and match conventions maybe without even understanding what they're doing. > > > Rotation math, in itself, has no > > handedness; it is only the interpretation of the coordinates in the > > coordinate space that is handed. > > It should be obvious that I disagree with this statement. And it might be > more useful during algebraic manipulation to choose one form over the > other, regardless of the choose direction of a 'forward' rotation. Because authors all over the planet have chosen one or the other at different times, you need to choose, you need to stay internally consistent, and you need to DOCUMENT YOUR CHOICE. Sorry, I'm more than a little frustrated by this. It took me many years to get comfortable enough with the literature to realize that this was one reason why it seemed so much more confusing than it should be. Sincerely, jw |
From: Marc B. R. <mar...@or...> - 2008-06-26 13:30:04
|
Believe me, I understand pet-peeves very well. I was attempting to quickly address a couple of them in my original post. 1) The notion that only unit quaternions may be used to represent a rotation. They are merely the most practical from a computational standpoint. 2) The big deal that is made out of double coverage. 3) That there is more than one way to formulate a rotation and most formulations effect a uniform scale as well. I chose the two forms from my first post, because they are the only ones that seem to show up in modern literature. >> What I'm calling 'right-handed' will return X, 'left-handed' will >> return -X. >> (Or vice-versa) Flip any of your coordinate definitions and the signs >> will flip. > To be specific, what you're calling "right-handed" (rotations) will > return X (in a right-handed coordinate space). > My point is that the words in parentheses are important, because leaving > them out leaves the text open for ambiguity. There's way too much > ambiguity in geometrics and especially graphics papers, because there > are two conventions for everything, and the authors usually assume that > everyone is using the particular conventions that he (the author) is > used to, without stating what they are. Yes, you are correct...I acknowledge your point. >> Here's some sample >> formulas that represent rotations in quaternions, with various >> different constraints: >> >> Q P (1/Q) R.1 >> (1/Q) P Q L.1 > I see you are assuming column vectors on the right in a right-handed > space. You might want to state those assumptions to make your formulas > unambiguous. For examples of popular graphics APIs that don't use those > assumptions, look no further than to Direct3D. Now, here you have lost me. There are no matrices in the above equations. And if you were to convert them into matrices, there would be neither column nor row vectors. Or do you mean converting the entire function...and if that is the case it would depend on whether your inject 3 results into row or columns. Am I missing something here? |
From: Jon W. <jw...@gm...> - 2008-06-26 16:34:03
|
Marc B. Reynolds wrote: >>> Here's some sample >>> formulas that represent rotations in quaternions, with various >>> different constraints: >>> >>> Q P (1/Q) R.1 >>> (1/Q) P Q L.1 >>> > > >> I see you are assuming column vectors on the right in a right-handed >> space. You might want to state those assumptions to make your formulas >> unambiguous. For examples of popular graphics APIs that don't use those >> assumptions, look no further than to Direct3D. >> > > Now, here you have lost me. There are no matrices in the above equations. > And if you were to convert them into matrices, there would be neither > column nor row vectors. Or do you mean converting the entire function...and > if that is the case it would depend on whether your inject 3 results into > row > or columns. Am I missing something here? > > > > I was not disambiguous enough. This is why it's hard :-) Also, I was confusing the vector multiplication order (qp vs pq) with the point transform functions, because I've recently had a discussion with some Microsofties about the insanity of using pq order for matrices but qp order for quaternions in the same API (XNA), especially when they use pq for both in another API (D3DX). What I should have said regarding your point transform functions: you are assuming a right-handed coordinate space when you write those formulas. In a left-handed space, what you call R.1 would actually result in a left-handed (real-world) rotation. I think we're mostly in understanding at this point, though. And regarding the double coverage pet peeve: as far as I can tell, Euler angles have double coverage too, if you let each of the angles range from -180 to 180. I'm wondering if that has some deeper meaning. Sincerely, jw |
From: Marc B. R. <mar...@or...> - 2008-06-23 10:22:43
|
I should have also mentioned that (unit) quaternions are sometimes called euler parameters and that some robotics text toss all kinds of representations into dual-quaternions: (WARNING: I grabbed the stuff below from some really old notes I made to myself...might be loaded with errors) Using set notation, a quaternion Q={V,t}, where V is the bivector and t is the scalar, and 'e' is the Dual number basis (ee = 0): Q = q = {R,r}+e{0,0} quaternion q T = 1 + e t = {0,1}+e{t,0} translation by 2t P = 1 + e p = {0,1}+e{p,0} point p E = n + e d = {n,0}+e{d,0} plane n+d==0 L = t + e m = {t,0}+e{m,0} plucker line: t is direction vector, m is moment about origin Screw motion: S = Cos[a]+Sin[a]t + e (-d Sin[a] + Sin[a]m + d Cos[a]t) = {Sin[a]t, Cos[a]} + e{Sin[a] m + d Cos[a]t , -d Sin[a]} screw axis = (t,m) {plucker} angle of rotation = 2a displacment = 2d General motion: G = q + e u, (q.q)=1 (q.u)=0 (mech engineer term 'G' unit or normalized) Involutions (conjugates): (where a* is quaternion conjugate) X* = (a* + e b*) = {-R,r}+e{-S,s} X~ = (a - e b ) = { R,r}-e{ S,s} X' = (a* - e b*) = {-R,r}-e{-S,s} Incidence EP + PE = 0 point on plane LP - PL' = 0 point on line LP + PL' = 0 line on plane |
From: Jon W. <jw...@gm...> - 2008-06-23 17:59:18
|
Lim Sin Chian wrote: > > Just wondering if anyone has done this before and whether it is really > better in terms of performance and accuracy. I'm under the impression that everybody does that. Not only does it save space (assuming you don't need scale), but it also interpolates much better. Interpolating between two frames with a matrix looks pretty crufty. The only thing to watch out for is to make sure you go the "short way" around -- dot product the two quaternions, and if the outcome is negative, negate all the values of the destination. To compose quaternions, you just multiply them. Because it's a rotation-translation pair, if it's parent relative, then you apply the parent rotation to the child translation, and then apply your own rotation around that point. Sincerely, jw |
From: Cedric P. <mor...@pl...> - 2008-06-26 21:16:20
|
Hi, Interesting topic, i am currently doing skinning and i would like to have some other point of views. I use similar technique from http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm 1 - in the pre process i identify set of vertex by uniq transform set (eg v0 v1 and v2 are transformed by bone1 and bone2 with the weight1 and weight2). 2 - Then i have a flaten list of transform by vertex group to update each frame eg: so to have the final transform (in animation space) for the set of vertex ( v0, v1,v2) i have to collapse ( transform bone1 * w1 + transform bone2 *w2) 3 - Then in cpu or gpu i have to do only one matrix * the vertex. Because previous work computed the concatenation of matrix, it reduces the number of matrix needed in the vertex shader. the method is describe here, http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm What do you think about that ? Cedric Jon Watte wrote: > Lim Sin Chian wrote: > >> Just wondering if anyone has done this before and whether it is really >> better in terms of performance and accuracy. >> > > I'm under the impression that everybody does that. Not only does it save > space (assuming you don't need scale), but it also interpolates much > better. Interpolating between two frames with a matrix looks pretty > crufty. The only thing to watch out for is to make sure you go the > "short way" around -- dot product the two quaternions, and if the > outcome is negative, negate all the values of the destination. > > To compose quaternions, you just multiply them. Because it's a > rotation-translation pair, if it's parent relative, then you apply the > parent rotation to the child translation, and then apply your own > rotation around that point. > > Sincerely, > > jw > > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://sourceforge.net/services/buy/index.php > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- +33 (0) 6 63 20 03 56 Cedric Pinson mailto:mor...@pl... http://www.plopbyte.net |
From: Jason H. <jas...@di...> - 2008-06-26 21:31:41
|
Cedric, For what it's worth, it's the only way to do hardware skinning on one of the current gen consoles. I'll give you three guesses which. Yes, it works. But it also means that if you want to shift skinning over to the GPU, you have to do it in several times the number of batches, because you explode the number of matrices requires (because they're a combination of ALL the weights and ALL the bone matrix requirements for a whole vertex). For a last-gen game with relatively few verts and relatively few matrices, it's probably a good trade off. If your game has 200+ bones and several thousand verts and allows for >3 bone skinning per vertex, you may be looking at close to half as many matrices as you have vertices, depending on how your art is generated. The artist has almost no feel for how many matrices they're effectively creating given standard tools at their disposal, as well. But there's nothing wrong with it, if it works for you. JH Cedric Pinson wrote: > Hi, > Interesting topic, i am currently doing skinning and i would like to > have some other point of views. I use similar technique from > http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm > 1 - in the pre process i identify set of vertex by uniq transform set > (eg v0 v1 and v2 are transformed by bone1 and bone2 with the weight1 and > weight2). > > 2 - Then i have a flaten list of transform by vertex group to update > each frame eg: > so to have the final transform (in animation space) for the set of > vertex ( v0, v1,v2) i have to collapse ( transform bone1 * w1 + > transform bone2 *w2) > > 3 - Then in cpu or gpu i have to do only one matrix * the vertex. > Because previous work computed the concatenation of matrix, it reduces > the number of matrix needed in the vertex shader. > > the method is describe here, > http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm > What do you think about that ? > > Cedric > > Jon Watte wrote: > >> Lim Sin Chian wrote: >> >> >>> Just wondering if anyone has done this before and whether it is really >>> better in terms of performance and accuracy. >>> >>> >> I'm under the impression that everybody does that. Not only does it save >> space (assuming you don't need scale), but it also interpolates much >> better. Interpolating between two frames with a matrix looks pretty >> crufty. The only thing to watch out for is to make sure you go the >> "short way" around -- dot product the two quaternions, and if the >> outcome is negative, negate all the values of the destination. >> >> To compose quaternions, you just multiply them. Because it's a >> rotation-translation pair, if it's parent relative, then you apply the >> parent rotation to the child translation, and then apply your own >> rotation around that point. >> >> Sincerely, >> >> jw >> >> >> ------------------------------------------------------------------------- >> Check out the new SourceForge.net Marketplace. >> It's the best place to buy or sell services for >> just about anything Open Source. >> http://sourceforge.net/services/buy/index.php >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> >> > > |
From: Cedric P. <mor...@pl...> - 2008-06-26 22:06:46
|
Hi, I was just curious if it's used mostly or not, and why. Cedric Jason Hughes wrote: > Cedric, > > For what it's worth, it's the only way to do hardware skinning on one > of the current gen consoles. I'll give you three guesses which. > > Yes, it works. But it also means that if you want to shift skinning > over to the GPU, you have to do it in several times the number of > batches, because you explode the number of matrices requires (because > they're a combination of ALL the weights and ALL the bone matrix > requirements for a whole vertex). For a last-gen game with relatively > few verts and relatively few matrices, it's probably a good trade > off. If your game has 200+ bones and several thousand verts and > allows for >3 bone skinning per vertex, you may be looking at close to > half as many matrices as you have vertices, depending on how your art > is generated. The artist has almost no feel for how many matrices > they're effectively creating given standard tools at their disposal, > as well. > > But there's nothing wrong with it, if it works for you. > > JH > > Cedric Pinson wrote: >> Hi, >> Interesting topic, i am currently doing skinning and i would like to >> have some other point of views. I use similar technique from >> http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm >> 1 - in the pre process i identify set of vertex by uniq transform set >> (eg v0 v1 and v2 are transformed by bone1 and bone2 with the weight1 and >> weight2). >> >> 2 - Then i have a flaten list of transform by vertex group to update >> each frame eg: >> so to have the final transform (in animation space) for the set of >> vertex ( v0, v1,v2) i have to collapse ( transform bone1 * w1 + >> transform bone2 *w2) >> >> 3 - Then in cpu or gpu i have to do only one matrix * the vertex. >> Because previous work computed the concatenation of matrix, it reduces >> the number of matrix needed in the vertex shader. >> >> the method is describe here, >> http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm >> What do you think about that ? >> >> Cedric >> >> Jon Watte wrote: >> >>> Lim Sin Chian wrote: >>> >>> >>>> Just wondering if anyone has done this before and whether it is really >>>> better in terms of performance and accuracy. >>>> >>>> >>> I'm under the impression that everybody does that. Not only does it save >>> space (assuming you don't need scale), but it also interpolates much >>> better. Interpolating between two frames with a matrix looks pretty >>> crufty. The only thing to watch out for is to make sure you go the >>> "short way" around -- dot product the two quaternions, and if the >>> outcome is negative, negate all the values of the destination. >>> >>> To compose quaternions, you just multiply them. Because it's a >>> rotation-translation pair, if it's parent relative, then you apply the >>> parent rotation to the child translation, and then apply your own >>> rotation around that point. >>> >>> Sincerely, >>> >>> jw >>> >>> >>> ------------------------------------------------------------------------- >>> Check out the new SourceForge.net Marketplace. >>> It's the best place to buy or sell services for >>> just about anything Open Source. >>> http://sourceforge.net/services/buy/index.php >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> GDA...@li... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >>> >> >> > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://sourceforge.net/services/buy/index.php > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list -- +33 (0) 6 63 20 03 56 Cedric Pinson mailto:mor...@pl... http://www.plopbyte.net |
From: Jon W. <jw...@gm...> - 2008-06-27 17:32:23
|
Cedric Pinson wrote: > Hi, > I was just curious if it's used mostly or not, and why. > I vote for "not," because the CPU work to generate the matrices takes more time than the GPU shading work to combine the matrices per vertex. And I have better use for the CPU :-) I don't write code for the more limited or esoteric platforms, though. Also, NVIDIA apparently recommends using stream-out with scatter to do skinning on G80 hardware and up. This means that you store each vertex in bones space per bone, and then loop over the bones, and multiply-add-accumulate into an output array. Once all bones are processed, you take that stream-out and use as a transformed vertex array. I believe this is also how Doom III did it, although on the CPU instead. The benefit is that you can have certain vertices influenced by 30 bones if you want, and other vertices influenced by only 1, and you get no redundant calculation. The draw-back of this method are that you store vertices multiple times (so the size grows by your average bone influence count), and you require scatter-write, which means it doesn't work on most installed hardware (most current PCs, 360 or Wii). Sincerely, jw |
From: Florian A. S. <fst...@bl...> - 2008-06-30 05:23:33
|
I've done a system like this in the past for PS2/GC/Wii and it worked out well for us. To cope with the potential explosion of combinations of bone weightings, the palette of weightings required for the mesh was quantised. The default setting for entries in the palette was 1.5 times the number of bones in the original mode, and this got good results nearly all the time. The worst case for this (as with any sort of palletisation) was when there was a gradient of weightings over a large area. This case doesn't occur on a human or animal type model, but can occur on other cases. To get around this, the quality could be increased (by changing the size of the palette) and the artists could also specify verts that be given greater importance during the quantization process. The downsides are as have been mentioned on this thread: increase in the number of meshes. For hardware that has proper vertex shaders, this technique is probably not as important, but I have been wondering if you could use a similar approach to create morph targets without requiring extra meshes by creating a bone per vert and then quantise down the palette of bones (this would require a different quantizer from what I mentioned above). -Florian -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Jon Watte Sent: Saturday, 28 June 2008 3:32 AM To: Game Development Algorithms Subject: Re: [Algorithms] Representing Animation Key Frame with Quaternion + Translation Vector Cedric Pinson wrote: > Hi, > I was just curious if it's used mostly or not, and why. > I vote for "not," because the CPU work to generate the matrices takes more time than the GPU shading work to combine the matrices per vertex. And I have better use for the CPU :-) I don't write code for the more limited or esoteric platforms, though. Also, NVIDIA apparently recommends using stream-out with scatter to do skinning on G80 hardware and up. This means that you store each vertex in bones space per bone, and then loop over the bones, and multiply-add-accumulate into an output array. Once all bones are processed, you take that stream-out and use as a transformed vertex array. I believe this is also how Doom III did it, although on the CPU instead. The benefit is that you can have certain vertices influenced by 30 bones if you want, and other vertices influenced by only 1, and you get no redundant calculation. The draw-back of this method are that you store vertices multiple times (so the size grows by your average bone influence count), and you require scatter-write, which means it doesn't work on most installed hardware (most current PCs, 360 or Wii). Sincerely, jw ------------------------------------------------------------------------ - Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://sourceforge.net/services/buy/index.php _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t |
From: Jim S. <jsc...@sl...> - 2008-06-26 23:45:27
|
I would say no, the difficulty in creating all the matrices especially for a system that supports 4 weights per bone is not really feasible. You really have to limit the weighting and even the artists to discrete 'steps' (like 0.0f to 1.0f weight in 8 steps) to limit the permutations. It's a lot more work on the CPU as well and the whole point of hardware skinning,... is to unload the work onto the GPU. On the Wii this is the only method you have available and depending on how much animation you have to do CPU based skinning may be a better solution especially as vertex counts on the Wii tend to be significantly lower than other consoles. If only the Wii had multiple cores. ----- Original Message ----- From: "Cedric Pinson" <mor...@pl...> To: "Game Development Algorithms" <gda...@li...> Sent: Thursday, June 26, 2008 3:06 PM Subject: Re: [Algorithms] Representing Animation Key Frame with Quaternion + Translation Vector > Hi, > I was just curious if it's used mostly or not, and why. > > Cedric > > Jason Hughes wrote: >> Cedric, >> >> For what it's worth, it's the only way to do hardware skinning on one >> of the current gen consoles. I'll give you three guesses which. >> >> Yes, it works. But it also means that if you want to shift skinning >> over to the GPU, you have to do it in several times the number of >> batches, because you explode the number of matrices requires (because >> they're a combination of ALL the weights and ALL the bone matrix >> requirements for a whole vertex). For a last-gen game with relatively >> few verts and relatively few matrices, it's probably a good trade >> off. If your game has 200+ bones and several thousand verts and >> allows for >3 bone skinning per vertex, you may be looking at close to >> half as many matrices as you have vertices, depending on how your art >> is generated. The artist has almost no feel for how many matrices >> they're effectively creating given standard tools at their disposal, >> as well. >> >> But there's nothing wrong with it, if it works for you. >> >> JH >> >> Cedric Pinson wrote: >>> Hi, >>> Interesting topic, i am currently doing skinning and i would like to >>> have some other point of views. I use similar technique from >>> http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm >>> 1 - in the pre process i identify set of vertex by uniq transform set >>> (eg v0 v1 and v2 are transformed by bone1 and bone2 with the weight1 and >>> weight2). >>> >>> 2 - Then i have a flaten list of transform by vertex group to update >>> each frame eg: >>> so to have the final transform (in animation space) for the set of >>> vertex ( v0, v1,v2) i have to collapse ( transform bone1 * w1 + >>> transform bone2 *w2) >>> >>> 3 - Then in cpu or gpu i have to do only one matrix * the vertex. >>> Because previous work computed the concatenation of matrix, it reduces >>> the number of matrix needed in the vertex shader. >>> >>> the method is describe here, >>> http://www.intel.com/cd/ids/developer/asmo-na/eng/172124.htm >>> What do you think about that ? >>> >>> Cedric >>> >>> Jon Watte wrote: >>> >>>> Lim Sin Chian wrote: >>>> >>>> >>>>> Just wondering if anyone has done this before and whether it is really >>>>> better in terms of performance and accuracy. >>>>> >>>>> >>>> I'm under the impression that everybody does that. Not only does it >>>> save >>>> space (assuming you don't need scale), but it also interpolates much >>>> better. Interpolating between two frames with a matrix looks pretty >>>> crufty. The only thing to watch out for is to make sure you go the >>>> "short way" around -- dot product the two quaternions, and if the >>>> outcome is negative, negate all the values of the destination. >>>> >>>> To compose quaternions, you just multiply them. Because it's a >>>> rotation-translation pair, if it's parent relative, then you apply the >>>> parent rotation to the child translation, and then apply your own >>>> rotation around that point. >>>> >>>> Sincerely, >>>> >>>> jw >>>> >>>> >>>> ------------------------------------------------------------------------- >>>> Check out the new SourceForge.net Marketplace. >>>> It's the best place to buy or sell services for >>>> just about anything Open Source. >>>> http://sourceforge.net/services/buy/index.php >>>> _______________________________________________ >>>> GDAlgorithms-list mailing list >>>> GDA...@li... >>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>>> Archives: >>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>>> >>>> >>> >>> >> ------------------------------------------------------------------------ >> >> ------------------------------------------------------------------------- >> Check out the new SourceForge.net Marketplace. >> It's the best place to buy or sell services for >> just about anything Open Source. >> http://sourceforge.net/services/buy/index.php >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > -- > +33 (0) 6 63 20 03 56 Cedric Pinson mailto:mor...@pl... > http://www.plopbyte.net > > > > ------------------------------------------------------------------------- > Check out the new SourceForge.net Marketplace. > It's the best place to buy or sell services for > just about anything Open Source. > http://sourceforge.net/services/buy/index.php > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |