Thread: [Algorithms] Hardware skinning with quaternions
Brought to you by:
vexxed72
From: Benjamin R. <ben...@gm...> - 2006-12-22 16:04:48
|
Hi, We are currently working to change our skinning shader to allow it to perform quaternion skinning, inspired by the article "Harware Skinning with Quaternions" in Game Programming Gems 4. I ran into a problem, and I wanted to know if someone already met (an solved) it. The algorithm is the following: - convert all rotation matrices to quaternion and send them to GPU. Also send translations For each vertex v, influenced by a bone B1, and B2 - Perform linear combination for translation: t = t1*w1 + t2*w2; - Perform linear combination for quaternion : q = q1*w1+q2*w2; - normalize q - build Matrix M from q and t - transform vertices with M After having tested my skinning with a simple cylinder (and saw it working), I tried it with our old matrix skinned based characters. This is where things get bad. I uploaded two screenshots of the problem (each vertex has 2 bones affecting it) : "Good pose": http://brouveyrol.free.fr/pics/skinning-matrix.jpg "Bad pose" : http://brouveyrol.free.fr/pics/skinning-quaternion.jpg The problem seems to appear for vertices which are influenced equally by multiple bones. This is what makes me think that the problem comes from the interpolation. At first, I thought that this came from the fact that I needed to negate some of the quaternions, based on the dot product: for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = -quat(i) But this doesn't seem to solve the problem. I also tried slerp, instead of lerp/normalize, and the result is not better. Has anybody already tried quaternion skinning ? And if yes, do they know where the problem might be ? Many thanks, Ben |
From: emmanuel c. <emm...@gm...> - 2006-12-22 17:19:59
|
Did you remove the contribution of the base position of the vertices by multipling them by the inverse transformation of the base pos ? The error seem to be in the same range. Emmanuel Caradec |
From: Jon W. <hp...@mi...> - 2006-12-22 21:15:35
|
1) Are you sure that you're normalizing the quaternion based on all four components? 2) Are you sure that the original matrix contains no scale? Cheers, / h+ Benjamin Rouveyrol wrote: > Hi, > > We are currently working to change our skinning shader to allow it to > perform quaternion skinning, inspired by the article "Harware Skinning > with Quaternions" in Game Programming Gems 4. I ran into a problem, > and I wanted to know if someone already met (an solved) it. > > The algorithm is the following: > > - convert all rotation matrices to quaternion and send them to GPU. > Also send translations > > For each vertex v, influenced by a bone B1, and B2 > - Perform linear combination for translation: t = t1*w1 + t2*w2; > - Perform linear combination for quaternion : q = q1*w1+q2*w2; > - normalize q > - build Matrix M from q and t > - transform vertices with M > > After having tested my skinning with a simple cylinder (and saw it > working), I tried it with our old matrix skinned based characters. > This is where things get bad. I uploaded two screenshots of the > problem (each vertex has 2 bones affecting it) : > "Good pose": http://brouveyrol.free.fr/pics/skinning-matrix.jpg > "Bad pose" : http://brouveyrol.free.fr/pics/skinning-quaternion.jpg > > The problem seems to appear for vertices which are influenced equally > by multiple bones. This is what makes me think that the problem comes > from the interpolation. > > At first, I thought that this came from the fact that I needed to > negate some of the quaternions, based on the dot product: > for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = > -quat(i) > But this doesn't seem to solve the problem. I also tried slerp, > instead of lerp/normalize, and the result is not better. > > Has anybody already tried quaternion skinning ? And if yes, do they > know where the problem might be ? > > Many thanks, > > Ben > > ------------------------------------------------------------------------ > > ------------------------------------------------------------------------- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys - and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > ------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Benjamin R. <ben...@gm...> - 2006-12-22 21:31:07
|
Jon: 1: Yes, I'm using the hlsl's normalize function on a float4 variable containing my quaternion. 2: I asked the artists if this matrix contained any scale. The told me they never did (they said it was too dangerous :) ) Emmanuel: I think that if I didn't project the object space vertices to skin space, the error would be on all vertices and not only on the ones in the knees or in the shoulders (as shown on the pictures). After having given more thoughts, I realized that the QuaternionToMatrix function is not a linear function. Which means that QuaternionToMatrix(sum(wi*qi)) might not be equal t sum(wi*Mi) where qi is the quaternion form of the rotation of bone i, and Mi the matrix form of the rotation of bone i. Is this the cause of the problems I observe ? I guess I'm not the first trying to do quaternion skinning, and I believe I'm missing something obvious. Thanks for your help, Ben On 22/12/06, Jon Watte <hp...@mi...> wrote: > > 1) Are you sure that you're normalizing the quaternion based on all four > components? > > 2) Are you sure that the original matrix contains no scale? > > Cheers, > > / h+ > > > Benjamin Rouveyrol wrote: > > Hi, > > > > We are currently working to change our skinning shader to allow it to > > perform quaternion skinning, inspired by the article "Harware Skinning > > with Quaternions" in Game Programming Gems 4. I ran into a problem, > > and I wanted to know if someone already met (an solved) it. > > > > The algorithm is the following: > > > > - convert all rotation matrices to quaternion and send them to GPU. > > Also send translations > > > > For each vertex v, influenced by a bone B1, and B2 > > - Perform linear combination for translation: t = t1*w1 + t2*w2; > > - Perform linear combination for quaternion : q = q1*w1+q2*w2; > > - normalize q > > - build Matrix M from q and t > > - transform vertices with M > > > > After having tested my skinning with a simple cylinder (and saw it > > working), I tried it with our old matrix skinned based characters. > > This is where things get bad. I uploaded two screenshots of the > > problem (each vertex has 2 bones affecting it) : > > "Good pose": http://brouveyrol.free.fr/pics/skinning-matrix.jpg > > "Bad pose" : http://brouveyrol.free.fr/pics/skinning-quaternion.jpg > > > > The problem seems to appear for vertices which are influenced equally > > by multiple bones. This is what makes me think that the problem comes > > from the interpolation. > > > > At first, I thought that this came from the fact that I needed to > > negate some of the quaternions, based on the dot product: > > for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = > > -quat(i) > > But this doesn't seem to solve the problem. I also tried slerp, > > instead of lerp/normalize, and the result is not better. > > > > Has anybody already tried quaternion skinning ? And if yes, do they > > know where the problem might be ? > > > > Many thanks, > > > > Ben > > > > ------------------------------------------------------------------------ > > > > > ------------------------------------------------------------------------- > > Take Surveys. Earn Cash. Influence the Future of IT > > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > > opinions on IT & business topics through brief surveys - and earn cash > > > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > > ------------------------------------------------------------------------ > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > ------------------------------------------------------------------------- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys - and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
From: emmanuel c. <emm...@gm...> - 2006-12-22 21:36:36
|
> > > I think that if I didn't project the object space vertices to skin space, > the error would be on all vertices and not only on the ones in the knees or > in the shoulders (as shown on the pictures). > > Right :) |
From: Jon W. <hp...@mi...> - 2006-12-23 04:04:38
|
Benjamin Rouveyrol wrote: > > 2: I asked the artists if this matrix contained any scale. The told me > they never did (they said it was too dangerous :) ) > Well, artists often say what they believe, but the belief and reality may not always be the same. I suggest checking the data in detail, inside the processing code, using the debugger, to make sure. > Which means that QuaternionToMatrix(sum(wi*qi)) might not be equal t > sum(wi*Mi) where qi is the quaternion form of the rotation of bone i, > and Mi the matrix form of the rotation of bone i. Actually, if all the math is implemented the same, they should get the same result. However, the order you multiply two quaternions representing two matrices, and the order you multiply those two matrices, may be the same (Managed DirectX), or may actually differ (XNA) -- check your assumptions by looking at data in detail. Cheers, / h+ |
From: Benjamin R. <ben...@gm...> - 2006-12-23 17:03:04
|
On 23/12/06, Jon Watte <hp...@mi...> wrote: > Well, artists often say what they believe, but the belief and reality > may not always be the same. I suggest checking the data in detail, > inside the processing code, using the debugger, to make sure. I definitely agree with that. I'll check the data as soon as I can. > Which means that QuaternionToMatrix(sum(wi*qi)) might not be equal t > > sum(wi*Mi) where qi is the quaternion form of the rotation of bone i, > > and Mi the matrix form of the rotation of bone i. > > Actually, if all the math is implemented the same, they should get the > same result. However, the order you multiply two quaternions > representing two matrices, and the order you multiply those two > matrices, may be the same (Managed DirectX), or may actually differ > (XNA) -- check your assumptions by looking at data in detail. I'm afraid I'm not following you here. Pardon my ignorance, but I can't see why you have to multiply quaternions (or matrices) together during skinning= : IMHO, we just perform linear combination between them, ie multiply them by = a scalar, and add the results together. Which would imply that the order doesn't matter. We don't work under XNA: just using Gamebryo as a rendering engine (DirectX9 based) and C++. Just for information: I believe that the problem comes from the blending, and not from a scale factor, because I made some experiments where vertices were transformed either only by bone 1 (experiment n=B01), or only by bone = 2 (experiment n=B02), but each time only by one bone. And in both cases, quaternion skinning and matrix skinning gave the exact same results. If there had been a scale related problem, I assume it would have also appeare= d in those cases. But as soon as a vertex has to be transformed in about 50% by bone 1 and 50= % by bone 2 (shoulders, knees, elbows vertices), the quaternion transform seems to be incorrect. I may have done a mistake during my implementation, but I would like to be sure that quaternion skinning is not a dead end. Maybe Jim Hejl (the author of the GPG 4 article) has an idea about it :) ..= . As a reminder, here is what I do in the shader: Quaternions and Translations are some uniform variables, weights is a blendweight at each vertex float4 qRot1 =3D Quaternions[0], qRot2 =3D Quaternions[1]; float3 vTrans1 =3D Translations[0], vTrans2 =3D Translations[1]; if ((dot(qRot1,qRot2))<0) qRot2 =3D -qRot2; float4 qRot =3D normalize(qRot1*weights[0] + qRot2*weights[1]); float3 vTrans =3D vTrans1 * weights[0] + vTrans2 * weights[1]; float4x4 M =3D ComputeMatrixFromQuatAndVector(qRot, vTrans); (...) Out.Pos =3D mul(In.Pos, M); Thank for your help, Ben |
From: Jon W. <hp...@mi...> - 2006-12-23 20:14:33
|
Benjamin Rouveyrol wrote: > I'm afraid I'm not following you here. Pardon my ignorance, but I > can't see why you have to multiply quaternions (or matrices) together > during skinning: IMHO, we just perform linear combination between > them, ie multiply them by a scalar, and add the results together. > Which would imply that the order doesn't matter. We don't work under > XNA: just using Gamebryo as a rendering engine (DirectX9 based) and C++. If your camera is expressed as a quaternion, or if your parent bones are also quaternions, and animations are parent-relative, then you need to multiply quaternions together. However, if bone 1 works, and bone 2 works, then it's likely not scale. Interpolation "should" work fine, assuming you take the short way 'round (make sure the dot product is positive) and normalize correctly. I would look for bugs in the implementation (stepping through the code for a given vertex, looking at the results after each line of code, etc). Cheers, / h+ |
From: speedy <sp...@3d...> - 2006-12-28 00:52:57
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head><title></title> <META http-equiv=Content-Type content="text/html; charset=iso-8859-1"> <meta http-equiv="Content-Style-Type" content="text/css"> <style type="text/css"><!-- body { margin: 5px 5px 5px 5px; background-color: #ffffff; } /* ========== Text Styles ========== */ hr { color: #000000} body, table /* Normal text */ { font-size: 9pt; font-family: 'Courier New'; font-style: normal; font-weight: normal; color: #000000; text-decoration: none; } span.rvts1 /* Heading */ { font-size: 10pt; font-family: 'Arial'; font-weight: bold; color: #0000ff; } span.rvts2 /* Subheading */ { font-size: 10pt; font-family: 'Arial'; font-weight: bold; color: #000080; } span.rvts3 /* Keywords */ { font-size: 10pt; font-family: 'Arial'; font-style: italic; color: #800000; } a.rvts4, span.rvts4 /* Jump 1 */ { font-size: 10pt; font-family: 'Arial'; color: #008000; text-decoration: underline; } a.rvts5, span.rvts5 /* Jump 2 */ { font-size: 10pt; font-family: 'Arial'; color: #008000; text-decoration: underline; } span.rvts6 { font-size: 11pt; font-family: 'tahoma'; font-weight: bold; color: #ffffff; } span.rvts7 { font-size: 11pt; font-family: 'tahoma'; } a.rvts8, span.rvts8 { font-size: 11pt; font-family: 'tahoma'; color: #0000ff; text-decoration: underline; } span.rvts9 { font-size: 8pt; font-family: 'arial'; font-style: italic; color: #c0c0c0; } a.rvts10, span.rvts10 { font-size: 8pt; font-family: 'arial'; color: #0000ff; text-decoration: underline; } /* ========== Para Styles ========== */ p,ul,ol /* Paragraph Style */ { text-align: left; text-indent: 0px; padding: 0px 0px 0px 0px; margin: 0px 0px 0px 0px; } .rvps1 /* Centered */ { text-align: center; } --></style> </head> <body> <p>Hello Benjamin,</p> <p><br></p> <p> the algorithm in that GPG4 article is buggy, it does not work well in the general case.</p> <p> Actually, I'm not sure how it worked at all for the authors.</p> <p><br></p> <p> For a nice solution to your woes, google for "Dual-Quaternion GPU Skinning" papers. :) </p> <p> I could dig the link out for you if you are unable to find it..</p> <p><br></p> <p>Friday, December 22, 2006, 5:04:43 PM, you wrote:</p> <p><br></p> <div><table border=0 cellpadding=1 cellspacing=2 style="border-color: #000000; border-style: solid;"> <tr valign=top> <td width=14 style="background-color: #0000ff;"> <p><span class=rvts6>></span></p> </td> <td width=776 style="background-color: #ffffff;"> <p><span class=rvts7>Hi,</span></p> <p><br></p> <p><span class=rvts7>We are currently working to change our skinning shader to allow it to perform quaternion skinning, inspired by the article "Harware Skinning with Quaternions" in Game Programming Gems 4. I ran into a problem, and I wanted to know if someone already met (an solved) it.</span></p> <p><br></p> <p><span class=rvts7>The algorithm is the following:</span></p> <p><br></p> <p><span class=rvts7>- convert all rotation matrices to quaternion and send them to GPU. Also send translations</span></p> <p><br></p> <p><span class=rvts7>For each vertex v, influenced by a bone B1, and B2 </span></p> <p><span class=rvts7> - Perform linear combination for translation: t = t1*w1 + t2*w2;</span></p> <p><span class=rvts7> - Perform linear combination for quaternion : q = q1*w1+q2*w2;</span></p> <p><span class=rvts7> - normalize q</span></p> <p><span class=rvts7> - build Matrix M from q and t</span></p> <p><span class=rvts7> - transform vertices with M </span></p> <p><br></p> <p><span class=rvts7>After having tested my skinning with a simple cylinder (and saw it working), I tried it with our old matrix skinned based characters.</span></p> <p><span class=rvts7>This is where things get bad. I uploaded two screenshots of the problem (each vertex has 2 bones affecting it) : </span></p> <p><span class=rvts7>"Good pose": </span><a class=rvts8 href="http://brouveyrol.free.fr/pics/skinning-matrix.jpg">http://brouveyrol.free.fr/pics/skinning-matrix.jpg</a></p> <p><span class=rvts7>"Bad pose" : </span><a class=rvts8 href="http://brouveyrol.free.fr/pics/skinning-quaternion.jpg">http://brouveyrol.free.fr/pics/skinning-quaternion.jpg</a></p> <p><br></p> <p><span class=rvts7>The problem seems to appear for vertices which are influenced equally by multiple bones. This is what makes me think that the problem comes from the interpolation. </span></p> <p><br></p> <p><span class=rvts7>At first, I thought that this came from the fact that I needed to negate some of the quaternions, based on the dot product:</span></p> <p><span class=rvts7>for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = -quat(i)</span></p> <p><span class=rvts7>But this doesn't seem to solve the problem. I also tried slerp, instead of lerp/normalize, and the result is not better. </span></p> <p><br></p> <p><span class=rvts7>Has anybody already tried quaternion skinning ? And if yes, do they know where the problem might be ?</span></p> <p><br></p> <p><span class=rvts7>Many thanks,</span></p> <p><br></p> <p><span class=rvts7>Ben</span></p> <p><br></p> </td> </tr> </table> </div> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <p><span class=rvts9>-- </span></p> <p><span class=rvts9>Best regards,</span></p> <p><span class=rvts9> speedy </span><a class=rvts10 href="mailto:sp...@3d...">mailto:sp...@3d...</a></p> </body></html> |
From: Benjamin R. <ben...@gm...> - 2006-12-28 15:41:27
|
Hi Speedy, I read the "Dual-Quaternion GPU Skinning" from Kavan and Zara, but I believe that solving an over-constrained system each vertex / each frame is not feasible in the conditions we want. However, I would be most interested if you could tell me why you are sure the GPG4 article is buggy. Everything written there seems to make sense, and I can't find out why it wouldn't work well in the general case. Best regards, Ben On 28/12/06, speedy <sp...@3d...> wrote: > > Hello Benjamin, > > > the algorithm in that GPG4 article is buggy, it does not work well > in the general case. > > Actually, I'm not sure how it worked at all for the authors. > > > For a nice solution to your woes, google for "Dual-Quaternion GPU > Skinning" papers. :) > > I could dig the link out for you if you are unable to find it.. > > > Friday, December 22, 2006, 5:04:43 PM, you wrote: > > > > > > Hi, > > > We are currently working to change our skinning shader to allow it to > perform quaternion skinning, inspired by the article "Harware Skinning with > Quaternions" in Game Programming Gems 4. I ran into a problem, and I wanted > to know if someone already met (an solved) it. > > > The algorithm is the following: > > > - convert all rotation matrices to quaternion and send them to GPU. Also > send translations > > > For each vertex v, influenced by a bone B1, and B2 > > - Perform linear combination for translation: t = t1*w1 + t2*w2; > > - Perform linear combination for quaternion : q = q1*w1+q2*w2; > > - normalize q > > - build Matrix M from q and t > > - transform vertices with M > > > After having tested my skinning with a simple cylinder (and saw it > working), I tried it with our old matrix skinned based characters. > > This is where things get bad. I uploaded two screenshots of the problem > (each vertex has 2 bones affecting it) : > > "Good pose": http://brouveyrol.free.fr/pics/skinning-matrix.jpg > > "Bad pose" : http://brouveyrol.free.fr/pics/skinning-quaternion.jpg > > > The problem seems to appear for vertices which are influenced equally by > multiple bones. This is what makes me think that the problem comes from the > interpolation. > > > At first, I thought that this came from the fact that I needed to negate > some of the quaternions, based on the dot product: > > for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = > -quat(i) > > But this doesn't seem to solve the problem. I also tried slerp, instead of > lerp/normalize, and the result is not better. > > > Has anybody already tried quaternion skinning ? And if yes, do they know > where the problem might be ? > > > Many thanks, > > > Ben > > > > > > > -- > > Best regards, > > speedy mailto:sp...@3d...<sp...@3d...> > |
From: speedy <sp...@3d...> - 2006-12-28 17:48:58
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head><title></title> <META http-equiv=Content-Type content="text/html; charset=iso-8859-1"> <meta http-equiv="Content-Style-Type" content="text/css"> <style type="text/css"><!-- body { margin: 5px 5px 5px 5px; background-color: #ffffff; } /* ========== Text Styles ========== */ hr { color: #000000} body, table /* Normal text */ { font-size: 9pt; font-family: 'Courier New'; font-style: normal; font-weight: normal; color: #000000; text-decoration: none; } span.rvts1 /* Heading */ { font-size: 10pt; font-family: 'Arial'; font-weight: bold; color: #0000ff; } span.rvts2 /* Subheading */ { font-size: 10pt; font-family: 'Arial'; font-weight: bold; color: #000080; } span.rvts3 /* Keywords */ { font-size: 10pt; font-family: 'Arial'; font-style: italic; color: #800000; } a.rvts4, span.rvts4 /* Jump 1 */ { font-size: 10pt; font-family: 'Arial'; color: #008000; text-decoration: underline; } a.rvts5, span.rvts5 /* Jump 2 */ { font-size: 10pt; font-family: 'Arial'; color: #008000; text-decoration: underline; } span.rvts6 { font-size: 11pt; font-family: 'tahoma'; font-weight: bold; color: #ffffff; } span.rvts7 { font-size: 11pt; font-family: 'tahoma'; } span.rvts8 { font-size: 11pt; font-family: 'tahoma'; font-weight: bold; } a.rvts9, span.rvts9 { font-size: 11pt; font-family: 'tahoma'; color: #0000ff; text-decoration: underline; } span.rvts10 { font-size: 11pt; font-family: 'tahoma'; vertical-align: super; } a.rvts11, span.rvts11 { font-size: 11pt; font-family: 'tahoma'; color: #0000ff; vertical-align: super; text-decoration: underline; } span.rvts12 { font-size: 8pt; font-family: 'arial'; font-style: italic; color: #c0c0c0; } a.rvts13, span.rvts13 { font-size: 8pt; font-family: 'arial'; color: #0000ff; text-decoration: underline; } a.rvts14, span.rvts14 { color: #0000ff; text-decoration: underline; } /* ========== Para Styles ========== */ p,ul,ol /* Paragraph Style */ { text-align: left; text-indent: 0px; padding: 0px 0px 0px 0px; margin: 0px 0px 0px 0px; } .rvps1 /* Centered */ { text-align: center; } --></style> </head> <body> <p>Hello Benjamin,</p> <p><br></p> <p> check out:</p> <p><br></p> <p><a class=rvts14 href="https://www.cs.tcd.ie/publications/tech-reports/reports.06/TCD-CS-2006-46.pdf">https://www.cs.tcd.ie/publications/tech-reports/reports.06/TCD-CS-2006-46.pdf</a></p> <p><br></p> <p> They found a minimal coordinate method for the problem space, which is very</p> <p> nice from both storage and computational sides. </p> <p><br></p> <p> The gist of the problem in the GPG4 article is that the center of combined rotations</p> <p> is not correct and even more - its badly aproximated. The detailed math can be found in </p> <p> the above one and related papers - if you are interested take a peek.</p> <p><br></p> <p>Thursday, December 28, 2006, 4:41:24 PM, you wrote:</p> <p><br></p> <div><table border=0 cellpadding=1 cellspacing=2 style="border-color: #000000; border-style: solid;"> <tr valign=top> <td width=14 style="background-color: #0000ff;"> <p><span class=rvts6>></span></p> </td> <td width=776 style="background-color: #ffffff;"> <p><span class=rvts7>Hi Speedy,</span></p> <p><br></p> <p><span class=rvts7>I read the "Dual-Quaternion GPU Skinning" from Kavan and Zara, but I believe that solving an over-constrained system each vertex / each frame is not feasible in the conditions we want.</span></p> <p><span class=rvts7>However, I would be most interested if you could tell me why you are sure the GPG4 article is buggy. Everything written there seems to make sense, and I can't find out why it wouldn't work well in the general case. </span></p> <p><br></p> <p><span class=rvts7>Best regards,</span></p> <p><br></p> <p><span class=rvts7>Ben</span></p> <p><br></p> <p><br></p> <p><span class=rvts7>On 28/12/06, </span><span class=rvts8>speedy</span><span class=rvts7> <</span><a class=rvts9 href="mailto:sp...@3d...">sp...@3d...</a><span class=rvts7>> wrote:</span></p> <p><span class=rvts7>Hello Benjamin,</span></p> <p><br></p> <p><span class=rvts7> the algorithm in that GPG4 article is buggy, it does not work well in the general case.</span></p> <p><span class=rvts7> Actually, I'm not sure how it worked at all for the authors.</span></p> <p><br></p> <p><span class=rvts7> For a nice solution to your woes, google for "Dual-Quaternion GPU Skinning" papers. :) </span></p> <p><span class=rvts7> I could dig the link out for you if you are unable to find it..</span></p> <p><br></p> <p><span class=rvts7>Friday, December 22, 2006, 5:04:43 PM, you wrote:</span></p> <p><br></p> <div><table border=0 cellpadding=1 cellspacing=2 style="border-color: #000000; border-style: solid;"> <tr valign=top> <td width=19 style="background-color: #0000ff;"> <p><span class=rvts10>></span></p> </td> <td width=727 style="background-color: #ffffff;"> <p><span class=rvts10>Hi,</span></p> <p><br></p> <p><span class=rvts10>We are currently working to change our skinning shader to allow it to perform quaternion skinning, inspired by the article "Harware Skinning with Quaternions" in Game Programming Gems 4. I ran into a problem, and I wanted to know if someone already met (an solved) it. </span></p> <p><br></p> <p><span class=rvts10>The algorithm is the following:</span></p> <p><br></p> <p><span class=rvts10>- convert all rotation matrices to quaternion and send them to GPU. Also send translations</span></p> <p><br></p> <p><span class=rvts10>For each vertex v, influenced by a bone B1, and B2 </span></p> <p><span class=rvts10> - Perform linear combination for translation: t = t1*w1 + t2*w2;</span></p> <p><span class=rvts10> - Perform linear combination for quaternion : q = q1*w1+q2*w2;</span></p> <p><span class=rvts10> - normalize q</span></p> <p><span class=rvts10> - build Matrix M from q and t</span></p> <p><span class=rvts10> - transform vertices with M </span></p> <p><br></p> <p><span class=rvts10>After having tested my skinning with a simple cylinder (and saw it working), I tried it with our old matrix skinned based characters.</span></p> <p><span class=rvts10>This is where things get bad. I uploaded two screenshots of the problem (each vertex has 2 bones affecting it) : </span></p> <p><span class=rvts10>"Good pose": </span><a class=rvts11 href="http://brouveyrol.free.fr/pics/skinning-matrix.jpg">http://brouveyrol.free.fr/pics/skinning-matrix.jpg </a></p> <p><span class=rvts10>"Bad pose" : </span><a class=rvts11 href="http://brouveyrol.free.fr/pics/skinning-quaternion.jpg">http://brouveyrol.free.fr/pics/skinning-quaternion.jpg </a></p> <p><br></p> <p><span class=rvts10>The problem seems to appear for vertices which are influenced equally by multiple bones. This is what makes me think that the problem comes from the interpolation. </span></p> <p><br></p> <p><span class=rvts10>At first, I thought that this came from the fact that I needed to negate some of the quaternions, based on the dot product:</span></p> <p><span class=rvts10>for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = -quat(i)</span></p> <p><span class=rvts10>But this doesn't seem to solve the problem. I also tried slerp, instead of lerp/normalize, and the result is not better. </span></p> <p><br></p> <p><span class=rvts10>Has anybody already tried quaternion skinning ? And if yes, do they know where the problem might be ?</span></p> <p><br></p> <p><span class=rvts10>Many thanks,</span></p> <p><br></p> <p><span class=rvts10>Ben</span></p> <p><br></p> </td> </tr> </table> </div> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <p><span class=rvts7>-- </span></p> <p><span class=rvts7>Best regards,</span></p> <p><span class=rvts7> speedy </span><a class=rvts9 href="mailto:sp...@3d...">mailto:sp...@3d...</a></p> </td> </tr> </table> </div> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <p><span class=rvts12>-- </span></p> <p><span class=rvts12>Best regards,</span></p> <p><span class=rvts12> speedy </span><a class=rvts13 href="mailto:sp...@3d...">mailto:sp...@3d...</a></p> </body></html> |
From: Pal-Kristian E. <pal...@na...> - 2007-01-02 22:47:54
|
speedy wrote: > > Hello Benjamin, > > check out: > > https://www.cs.tcd.ie/publications/tech-reports/reports.06/TCD-CS-2006-= 46.pdf > A very interesting article, and I find it fitting that it is published=20 by Trinity College which is in Dublin, Ireland. (Sir Hamilton, the=20 inventor of the quaternions, also lived there.) However, this work does not consider non-rigid transformations, i.e.=20 transformation that include scale and shear. Would people on this list=20 have any ideas about how one would deal with having non-uniform scale in=20 a skeletal setup if one wanted skinning by dual quaternions? And given a=20 general 3-by-3 matrix, not necessarily orthonormal, how do people go=20 about creating a quaternion from it? One *should* find the best-fitting=20 orthonormal 3-by-3 matrix (or unit quaternion) that matches the original=20 matrix in some sense (e.g. some matrix norm - for the 2-norm this can be=20 done by calculating the square root of the matrix), but these methods=20 are probably too computationally expensive. I presume most simply either disallow (non-uniform) scale and shear, or=20 else just ignore the problem. Finally, I wonder if applying the dual quaternions to the skinning=20 problem might not better be addressed by adding more helper-joints in=20 the problem areas. Indeed, making use of dual matrices to blend /joints/=20 rather than vertexes might be a little more appealing to current=20 graphics/animation engines. Thanks, PKE. --=20 P=E5l-Kristian Engstad (en...@na...), Lead Programmer, ICE team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 633-9112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List |
From: Brian K. <zer...@gm...> - 2007-01-04 05:55:20
|
I don't have the GPG4 article so I can just assume it is about doing vertex shader based skinning using quaternions for the rotations instead of a 3x3 matrix. This seems perfectly logical to me so you can save on the shader constants. I also read that paper although I'm still trying to wrap my head around some of the math. I still don't understand why this wouldn't work. Perhaps you are doing a common optimization and adding up the rotations with weightings like you would with matrices. If you are, try transforming the verts and then adding them together with weightings. Also you could try swapping the ordering that you apply the rotation to before you translate or after if you are doing that already. I'm not sure why that would help but its worth a shot. If you have rotations encoded in whatever, and you have a translation encoded in whatever, you apply these and lerp between the results I don't see how it would act differently based just on how you encoded, especially since with the single weighted verts acting correctly. I'd be curious if you can get this to work because it sounds like a good thing to try when we move our skinning gpu side. -Brian On 12/28/06, Benjamin Rouveyrol <ben...@gm...> wrote: > > Hi Speedy, > > I read the "Dual-Quaternion GPU Skinning" from Kavan and Zara, but I > believe that solving an over-constrained system each vertex / each frame is > not feasible in the conditions we want. > However, I would be most interested if you could tell me why you are sure > the GPG4 article is buggy. Everything written there seems to make sense, and > I can't find out why it wouldn't work well in the general case. > > Best regards, > > Ben > > On 28/12/06, speedy <sp...@3d...> wrote: > > > > Hello Benjamin, > > > > > > the algorithm in that GPG4 article is buggy, it does not work > > well in the general case. > > > > Actually, I'm not sure how it worked at all for the authors. > > > > > > For a nice solution to your woes, google for "Dual-Quaternion > > GPU Skinning" papers. :) > > > > I could dig the link out for you if you are unable to find it.. > > > > > > Friday, December 22, 2006, 5:04:43 PM, you wrote: > > > > > > > > > > > Hi, > > > > > > We are currently working to change our skinning shader to allow it to > > perform quaternion skinning, inspired by the article "Harware Skinning with > > Quaternions" in Game Programming Gems 4. I ran into a problem, and I wanted > > to know if someone already met (an solved) it. > > > > > > The algorithm is the following: > > > > > > - convert all rotation matrices to quaternion and send them to GPU. Also > > send translations > > > > > > For each vertex v, influenced by a bone B1, and B2 > > > > - Perform linear combination for translation: t = t1*w1 + t2*w2; > > > > - Perform linear combination for quaternion : q = q1*w1+q2*w2; > > > > - normalize q > > > > - build Matrix M from q and t > > > > - transform vertices with M > > > > > > After having tested my skinning with a simple cylinder (and saw it > > working), I tried it with our old matrix skinned based characters. > > > > This is where things get bad. I uploaded two screenshots of the problem > > (each vertex has 2 bones affecting it) : > > > > "Good pose": http://brouveyrol.free.fr/pics/skinning-matrix.jpg > > > > "Bad pose" : http://brouveyrol.free.fr/pics/skinning-quaternion.jpg > > > > > > The problem seems to appear for vertices which are influenced equally by > > multiple bones. This is what makes me think that the problem comes from the > > interpolation. > > > > > > At first, I thought that this came from the fact that I needed to negate > > some of the quaternions, based on the dot product: > > > > for every quat(i), i!=1, if (dot(quat(1), quat(i))<0) -> quat(i) = > > -quat(i) > > > > But this doesn't seem to solve the problem. I also tried slerp, instead > > of lerp/normalize, and the result is not better. > > > > > > Has anybody already tried quaternion skinning ? And if yes, do they know > > where the problem might be ? > > > > > > Many thanks, > > > > > > Ben > > > > > > > > > > > > > > -- > > > > Best regards, > > > > speedy mailto:sp...@3d...<sp...@3d...> > > > > > ------------------------------------------------------------------------- > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys - and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > |
From: Jon W. <hp...@mi...> - 2007-01-04 06:30:17
|
Brian Karis wrote: > I still don't understand why this wouldn't work. Perhaps you are doing > a common optimization and adding up the rotations with weightings like > you would with matrices. If you are, try transforming the verts and > then adding them together with weightings. If the quaternions are "close," then interpolating between them with weights and re-normalization will work well enough. If they are, however, "far away," then the rotation you get by weighting and re-normalizing isn't the ideal path. If your bones are not all created in the same coordinate space (i e, may be created 90 or 180 degrees off each other), then the weighting won't look as good. A common way around this is to assume that the bones are all in identity when in the first frame, and export only relative rotations (and then assume that the "init" pose for the bones is that of the first frame). The suggestion of transforming through each quaternion/position first, and then weighting, is good, though, as it gets rid of any quaternion-specific problems. In fact, I've done it that way, and it has seemed to work, although that hasn't gone through the steel bath of real artists using it. Cheers, / h+ |
From: speedy <sp...@3d...> - 2007-01-04 12:05:07
|
Hello Jon, Brian, JW> The suggestion of transforming through each quaternion/position first, JW> and then weighting, is good, though, as it gets rid of any JW> quaternion-specific problems. That technique will get you rid of quaternion-specific benefits, too - namely, avoiding mesh "candywrap" effect through SLERP skinning. And that is a major point of the GPG4 article. -- Best regards, speedy mailto:sp...@3d... |
From: Jon W. <hp...@mi...> - 2007-01-04 16:41:16
|
Let's think about that for a minute, using two matrices for simplicity. First, let's assume that we have the matrix representation of the transformation (row vectors on left): 1a) out = in * M1 * w + in * M2 * (1-w) This is, traditionally, what the skinning function is, and what modeling tools will typically use. We know that this is mathematically equivalent to first computing the matrix, and then transforming: 1b) out = in * (M1 * w + M2 * (1-w)) When you have four or more matrices, creating the matrix first and then multiplying is actually fewer instructions than doing it the straightforward way. However, because of the mathematical equivalence, it is exactly the same as 1a). Now, let's include quaternions: 2a) out = (in * Q1 + D1) * w + (in * Q2 + D2) * (1-w) As long as "(in * Q1 + D1)" is equivalent to "in * M1", this is, again, an equivalent formulation. It can easily be arranged, by having Q1 represent the 3x3 of M1, and D1 represent the bottom row. That, in turn, is not surprising, given that M1 likely comes from composing a quaternion and an offset in the animation track in the first place. The benefit of using this formulation is that you only need to send 7 floats (two vector4 registers) to the graphics card, and thus can fit more bones into the register file than if you sent a 4x3, or even a 4x4 matrix. So, if the benefit you want is "accurately representing the math of the blending, as known from the export pipeline, using fewer registers," then the separate transform and weighting formulation solves that problem -- and should be mathematically equivalent to the matrix formulation (hence, give the same result). Building upon this, we're now examining 2b) out = in * normalize(Q1 * w + Q2 * (1-w)) + D1 * w + D2 * (1-w) // hope I got that right This is not mathematically equivalent, because of the non-linear normalize() function included. The further Q1 and Q2 are from each other, the less equivalent it will be. It may look better; it may look worse, but it likely won't look like how the art pipeline expects skinning to look, except when Q1 and Q2 stay consistently close to each other. It does save even more shader instructions, though, especially when the number of weights is large. However, this formulation gives no additional savings in register count, which is the main limitation when skinning using matrices, so moving to this formulation from 2a) isn't necessary to solve the problems stated up front. As long as the matrices M1 and M2 are each created from a normalized quaternion in the first place, the "candy wrapper" effect really isn't there in most cases I've seen. In my opinion, that effect only shows up if you generate the bone matrices through matrix interpolation (which looks bad). But maybe I'm mis-understanding the effect you're talking about. Cheers, / h+ speedy wrote: > > Hello Jon, Brian, > > > JW> The suggestion of transforming through each quaternion/position first, > > JW> and then weighting, is good, though, as it gets rid of any > > JW> quaternion-specific problems. > > > That technique will get you rid of quaternion-specific benefits, too - > > namely, avoiding mesh "candywrap" effect through SLERP skinning. And that > > is a major point of the GPG4 article. > |
From: Benjamin R. <ben...@gm...> - 2007-01-05 08:59:29
|
On 04/01/07, Jon Watte <hp...@mi...> wrote: > > 1a) out = in * M1 * w + in * M2 * (1-w) > > (...) > > 2a) out = (in * Q1 + D1) * w + (in * Q2 + D2) * (1-w) > > As long as "(in * Q1 + D1)" is equivalent to "in * M1", this is, again, > an equivalent formulation. It can easily be arranged, by having Q1 > represent the 3x3 of M1, and D1 represent the bottom row. That, in turn, > is not surprising, given that M1 likely comes from composing a > quaternion and an offset in the animation track in the first place. I agree, but I read in http://www.euclideanspace.com/maths/algebra/realNormedAlgebra/quaternions/transforms/index.htmthat transforming a point P1 into P2 by Q1 is made by: P2 = Q1 * P1 * Q1' where Q1' is the conjugate of Q1. IMHO, Formula (2a) should be : (2c) out = (Q1 * in * Q1' + D1)*w + (Q2 * in * Q2' + D2)*(1-w) // Hope I got it right this time :) Which is why I suppose the following formula: 2b) out = in * normalize(Q1 * w + Q2 * (1-w)) + D1 * w + D2 * (1-w) > is not equivalent to (2c) and gives different results. I didn't give it a try, but I guess it would explain the differences. I'm not considering here cases like shear / translation in this transfomation since it was not an issue for me in the first place. Ben |
From: speedy <sp...@3d...> - 2007-01-04 19:40:48
|
Hello Jon, JW> 1a) out = in * M1 * w + in * M2 * (1-w) JW> 1b) out = in * (M1 * w + M2 * (1-w)) JW> As long as "(in * Q1 + D1)" is equivalent to "in * M1" JW> 2a) out = (in * Q1 + D1) * w + (in * Q2 + D2) * (1-w) Yep, 1 or 2 registers is gained per bone but you loose scale/shear which is a requirement for at least some of the guys I talked to. JW> However, this formulation gives no additional savings in register count, JW> which is the main limitation when skinning using matrices True, but quite strange that the register count is the limitation? It would seem you don't auto-split the mesh in multiple batches at load-time to fit the register limit but just cap the number of bones per mesh? JW> 2b) out = in * normalize(Q1 * w + Q2 * (1-w)) + D1 * w + D2 * (1-w) // JW> hope I got that right You're right - 2b) approximation will work if you manage to constrain Q1 & Q2 to be similar. I suppose folk who wrote the GPG4 article did manage to do that somehow? Imagine Q1 being the shoulder bone and Q2 the upper-arm bone - Q2 can have pretty arbitrary Q1-relative rotation in the general case so I don't see how can you keep Q1 close to Q2? There are screenshots of the "candywrap" effect in the "dual-quat" paper, which is supposedly mitigated - it's on my TODO list to test & compare both speed & the looks in the corner cases as the implementation over here is pretty fresh. JW> In my opinion, that effect only shows up if you generate the bone matrices through JW> matrix interpolation (which looks bad). Ugh, you mean direct linear interpolation of matrices? Sounds like a mess. :) -- Best regards, speedy mailto:sp...@3d... |
From: Robert D. <bli...@go...> - 2007-01-04 21:58:25
|
Candy wrap appears with linear interpolation of the matrix rotated vertices too ... just imagine if you have two ends of a bone and you twist one 180 degrees relative to the other, any point will rotate to the opposite side, so the midpoint is the centre, where what you want is a rotation of half the amount. However as you rightly pointed out, the quaternion rotations tend not to be around remotely the same axis for most bones, so they tend to produce wierd results too. I suppose the ultimate trick would be to separate out twist and orientation for each bone, since then you can interpolate the twist separately, to prevent candy wrap. However I am by no means certain what would happen at joints, or how you would go about such a trick. |
From: Jon W. <hp...@mi...> - 2007-01-04 22:17:45
|
Robert Dibley wrote: > > I suppose the ultimate trick would be to separate out twist and > orientation for each bone, since then you can interpolate the twist > separately, to prevent candy wrap. However I am by no means certain > what would happen at joints, or how you would go about such a trick. > What artists do is add "fix-up" bones that go in between, to avoid collapsing volume. Hence, more bones. Hence, the need for a more compact bone representation. Cheers, / h+ |
From: Jon W. <hp...@mi...> - 2007-01-04 22:15:25
|
speedy wrote: > > True, but quite strange that the register count is the limitation? It > would > > seem you don't auto-split the mesh in multiple batches at load-time to > fit the > > register limit but just cap the number of bones per mesh? > The motivation is: more bones means fewer batches means higher performance. Also, less data to transfer and generate helps with caches and busses, although is not as critical. Cheers, / h+ |
From: Jon W. <hp...@mi...> - 2007-01-05 16:52:09
|
Benjamin Rouveyrol wrote: > IMHO, Formula (2a) should be : > > (2c) out = (Q1 * in * Q1' + D1)*w + (Q2 * in * Q2' + D2)*(1-w) // Hope > I got it right this time :) Yes, I was being sloppy in my notation, denoting "point transformed by quaternion" using a simple multiplication. The actual implementation uses the quaternion math (treating the point as a quaternion) that you show. I believe the source of the difference is mainly the normalize, which is a non-linear operation. The point, however, is that 2a is equivalent to 1a and 1b, whereas 2b is not. Cheers, / h+ |
From: Benjamin R. <ben...@gm...> - 2007-01-05 18:01:32
|
OK then :-) What I meant is that (2b) is not equivalent to (2a) but not only because of the 'normalize' function, i.e. even if you had out = in * (Q1 * w + Q2 * (1-w)) + D1 * w + D2 * (1-w) with ' * ' being Quaternion transform, it would not be equivalent to (2a). I wrote this notation before because: let Q3 = Q1 * w + Q2 * (1-w) (Q1 * in * Q1' )*w + (Q2 * in * Q2' )*(1-w) != Q3 * in * Q3' Ben On 05/01/07, Jon Watte <hp...@mi...> wrote: > > > > Benjamin Rouveyrol wrote: > > IMHO, Formula (2a) should be : > > > > (2c) out = (Q1 * in * Q1' + D1)*w + (Q2 * in * Q2' + D2)*(1-w) // Hope > > I got it right this time :) > > Yes, I was being sloppy in my notation, denoting "point transformed by > quaternion" using a simple multiplication. The actual implementation > uses the quaternion math (treating the point as a quaternion) that you > show. > > I believe the source of the difference is mainly the normalize, which is > a non-linear operation. > > The point, however, is that 2a is equivalent to 1a and 1b, whereas 2b is > not. > > Cheers, > > / h+ > > |