[GSoC 2011 - Accepted] Dual Quaternion Skinning

Threads related to Google Summer of Code
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

[GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

Project Proposal

I would like to implement Dual Quaternion skinning for the 2011 Google Summer of Code. A description of this algorithm can be found at http://isg.cs.tcd.ie/projects/DualQuaternions/.

Dual quaternion skinning addresses problems commonly associated with the linear blend skinning of animations such as skin collapsing. Implementation of this method is fairly straightforward on the GPU, and does not require extensive modifications of Ogre. This technique utilizes dual numbers to extend quaternions to represent both rotation and translation. This allows for an efficient representation of the transformations and for application of low-cost linear blending.

Dual numbers are an extension of the set of real numbers. Reminiscent of extending the real line to the complex plane by introducing the element i, one defines the dual element ԑ, whose square is zero, to construct the dual plane {a+ԑb|a,b∊R}. In practice, dual numbers are represented by x + ԑy, where x is the real component and ԑy is the dual component. ԑ is represented by the matrix:

Code: Select all

|0 1|
|0 0|
Quaternions are used in 3D graphics to represent a rotation. Quaternions are often used because they avoid problems, such as gimbal lock, associated with using Euler's angles to do rotations. They are defined by three imaginary dimensions and one real dimension. The three imaginary dimensions specify along which axis to rotate, and the real dimension specifies the amount of rotation.

In describing rotations and translations, it proves useful to introduce dual quaternions simply by constructing quaternions by the standard method but with dual number coefficients rather than real ones. These dual quaternions allow one to simultaneously specify the translation and rotation of an object. In contrast to the four components of a quaternion, dual quaternions are represented by eight values. Yet this is a more space-efficient representation of a transformation than the twelve values that would otherwise be sent to the shader for the matrix representation of the transformation. Because it represents both a translation and a rotation, a dual quaternion is in the Special Euclidean group SE(3). SE(3) is simply SO(3) X R^3, where SO(3) is the set of all rotations in three space, and R^3 is a vector in three space. A transformation in SE(3) would be composed of a matrix:

Code: Select all

|R v|
|0 1|
where R is a rotation matrix in SO(3) and v is a vector in R^3.

Animation in standard hardware skinning is done using matrices, and the conversion from a homogeneous transformation matrix to a dual quaternion is fairly straightforward. Yet one of the signs in the conversion is ambiguous, so an algorithm must be used to cope with antipodality. An antipodal point is the point that is diametrically opposite to a point on a sphere. The theoretically perfect algorithm has to be run in the vertex shader, increasing the shader complexity. This is not required because an alternative approximate algorithm can be used which may be pre-computed on the CPU. Though the approximate method may not always produce a correct output, it only produces incorrect results for rotations of bones greater than 180 degrees, which is uncommon in skinning.

In general, in order to achieve fast speeds, a linear blending method is preferred. Due to the nature of the transformation in dual quaternion skinning, however, it is more accurate to employ a spherical blending. An linear approximation method is available that still produces fairly accurate results. With this method, one performs a linear blending of the points and then re-normalizes the resultant dual quaternion to generate a suitable approximation of the blended result at speeds that are comparable to linear blend skinning.
renormalization.jpg
In the diagram above, linear blending of the two points n1 and n2 would produce an incorrect result. The resultant point is then re-normalized, which produces a fairly accurate blending.

The paper proceeds to explain the most accurate method of blending in detail and found that the much simpler method of linear blending of dual quaternions was adequate. In fact, the paper found that the upper bound of error for blended dual quaternions was only 8.15 degrees.

The Dual quaternion Linear Blending (DLB) formula is given by:
DLB.png
DLB.png (7.5 KiB) Viewed 24080 times
Where w(i) are the various weights associated with each transformation and q(i) is the unit dual quaternion representing each transformation to be blended.

Ogre Integration:
Implementation of this method would be fairly similar to the existing hardware skinning in Ogre. In order to expose support for this skinning method in the vertex shader, the ability to pass dual quaternions representing the transformation of the bones must be added. The dual quaternions would be sent as a 2x4 matrices to the shader where the user would then perform the linear blending of the dual quaternions. An efficient algorithm derived from an application of Lagrange’s formula allows for the direct usage of the dual quaternions sans conversion to homogenous transformation matrices.

In order to be compatible with Ogre’s new InstanceManager, several changes must be made to several of the InstanceBatch classes which implement the various instancing techniques. Three types of instancing in the new Ogre InstanceManager have support for skeletal animation: VTF (Vertex Texture Fetch) instancing, Hardware + VTF instancing, and shader-based instancing. Because both VTF and HW + VTF instancing techniques use Vertex Texture Fetch, the classes to support packing either dual quaternions or matrices into textures depending on the skinning type must be changed. As for the shader-based instancing technique, no changes in Ogre should be necessary. For all of the above techniques, new shaders must be written though they would largely be based on existing shaders. Currently the InstanceManager is not integrated with RTSS (Run-Time Shader System), and while integration is a compelling idea, simple provision of raw shader implementations of instancing without RTSS integration will be performed to maintain a focused project scope.

Implementation of this technique should be render system agnostic and is limited only by hardware and shader support. If implemented in all of the appropriate shading languages, it should support any render system that Ogre supports (GL, GL ES, DX9, DX11).

Although it avoids problems associated with linear blend skinning, blending with dual quaternions is marginally slower than linear blend skinning (according to the reference implementation, an extra 7 vertex shader instructions). The two phase skinning that supports scaling and shearing costs an additional 29 vertex shader instructions over linear blend skinning. Dual quaternion skinning occasionally causes flipping artifacts because the skin always goes the shorter way around. Yet, the overall increase in visual quality exceeds the associated performance costs, especially if scale and shear support is not required. The dual quaternion skinning method requires no changes at all to the resource pipeline and minimal effort on the artist side, so it is both easily available to users and widely applicable.

How will this project benefit OGRE users?
This is a method superior to linear blending and can be implemented with relative ease in a shader with proper support in Ogre. If RTSS is used, employment of dual quaternion skinning should be fairly seamless.

Is this project within the core scope of OGRE?
This is well within the scope of Ogre, and generally applicable to any animated model. No special animation methods or re-rigging are required.

This project certainly is of a suitable scope for the time allotted during the summer. In fact, even if half-completed, the results of project would still prove useful, as dual quaternion skinning with RTSS support is helpful in itself without instancing support.

Current State of the Art

Physically-based techniques:
Physically-based animation techniques, while impressive, do not have the run-time performance needed for real-time graphics.

Example-based techniques:
Real-Time Weighted Pose-Space Deformation on the GPU
A Comparison of Linear Skinning Techniques for Character Animation

Recent example-based methods have been developed for an efficient run-time performance comparable to standard hardware skinning. Most example-based methods, however, place an extra burden on the artists. For instance, in the Animation Space method described in “A Comparison of Linear Skinning Techniques for Character Animation,” artists need to produce models in various poses in order to automatically establish the multiple weights used in the algorithm. The WPSD technique described in “Real-Time Weighted Pose-Space Deformation on the GPU,” while appearing quite accurate, also requires such sample poses for weight generation. Due to the required extra steps, the example-based approach is not appropriate for a general-purpose engine such as Ogre.

Geometric Methods:
There several other geometric methods for skinning similar to dual quaternion skinning which also do not require any changes to rigging. Though these methods address some of the issues, they do not remove all of the artifacts and are often not as performant as dual quaternion blending.
For example, Log-Matrix Blending vs. Dual Quaternion Blending and Spherical Blend Skinning vs Dual Quaternion Blending:
geometric-comparison.jpg
Alternative Rigging:
These methods also allow for impressive visual results. However, just as with example-based techniques, the changes required in the resource pipelines render it prohibitive to implement as a general animation method in Ogre.

Existing Implementations

I have gathered some resources to use as references in implementing this technique: Note, while the website of the paper does not contain a full project, it contains both a .c source file and a Cg shader that contain the bulk of the implementation.

The Cg shader contains the following techniques:
  • Basic dual quaternion skinning
  • Basic dual quaternion skinning, using the theoretically perfect per-vertex antipodality handling (more robust, but not as efficient)
  • Optimized version of the dual quaternion skinning that avoids dual quaternion -> matrix conversion by using the formula derived from Lagrange's formula to transform vertices using dual quaternions directly
  • Two-phase skinning, which combines the optimized version of the dual quaternion skinning with scale/shear transformations
The .c source file contains the following functions:
  • Convert from a unit quaternion and a translation vector to a unit dual quaternion
  • Convert a unit dual quaternion to a unit quaternion and a translation vector
  • Convert a dual quaternion with a non-zero non-dual part to a unit quaternion and a translation vector
Schedule

April 25th – May 23rd -
  • Get to know mentor
  • Work on shader programming, quaternion and dual number math
  • Firm handle on integration with Ogre
Deliverable: DualQuaternion class
  • Week 1 (May 23rd) –
    • Begin coding
    • Add support for conversion to and from dual quaternions to Ogre
    Week 2 (May 30th) –
    • Generate dual quaternions from the animations
    • Expose the dual quaternions to shaders via a param_named_auto (world_dual_quaternion_array_2x4)
Deliverable: Extended Skeletal Animation demo (working implementation of dual quaternion skinning in Ogre)
  • Week 3 (June 6th) –
    • I have exams this week and will be unavailable
    Week 4 (June 13th) –
    • Write Cg shader that implements basic dual quaternion skinning.
    Week 5 (June 20th) –
    • Write Cg shader that implements two phase skinning (supports shearing and scaling)
Deliverable: Demo with a comparison between standard skinning and dual quaternion skinning (working RTSS implementation of dual quaternion skinning in Ogre)
  • Week 6 (June 27th) –
    • Begin RTSS work.
    • Refactor the HardwareSkinning class from RTSS into:
      • A virtual parent class HardwareSkinningTechnique
      • A subclass HardwareSkinningLBS that implements the already implemented Linear Blend Skinning
      • Add a new subclass HardwareSkinningDLBS that implements basic Dual Quaternion Linear Blend Skinning in RTSS
      • Add a new subclass HardwareSkinningDBLSTwoPhase that implements two phase skinning in RTSS
    Week 7 (July 4th) –
    • Finish writing the HardwareSkinningDBLS and HardwareSkinningDBLSTwoPhase classes
    Week 8 (July 11th) –
    • Mid Term evaluation
    • For integration with RTSS: Write GLSL, HLSL (and possibly GLSL ES) versions of basic dual quaternion skinning and two phase skinning
Deliverable: Extend previous demo to showcase instancing
  • Week 9 (July 18th) –
    • Begin work integrating Dual Quaternion skinning with instancing
    • Ogre InstanceManager integration - modify OgreInstanceBatchVTF and OgreInstanceBatchHW_VTF to pack dual quaternions into textures
    Week 10 (July 25th) –
    • Begin writing Cg shader implementation for Shader-based, VTF, and HW+VTF instancing
    Week 11 (August 1st) –
    • Finish implementation of instancing
    • Potential RTSS implementation of instancing (since instancing integration is scheduled at the end of the project, if there is additional time, I will attempt an integration with RTSS)
Deliverable: Extensive Doxygen documentation and a tutorial about how to integrate the technique with custom shaders
  • Week 12 (August 7th) –
    • Tests, optimizations
    • Begin writing documentation
    Week 13 (August 14th) –
    • August 15th is the suggested pencils down date
    • Write tutorials to help people integrate Dual Quaternion skinning into their own shaders
End August 22nd

Due to my university’s academic schedule, I will still be in school for the first three weeks of the GSoC. I do not feel that this will impact the progress of the project significantly, however, as I have held a programming job in addition to my undergraduate studies in the past. I will be unavailable the week of exams as noted in the schedule above. To compensate I will certainly make a strong effort in the weeks following weeks to make up for lost time as I do not have any other commitments for this upcoming summer.

Several potential future extensions for this project:
  • OpenGl ES shader support
  • RTSS support for Instancing
  • Add support for the more accurate spherically-blended version of dual quaternion skinning
  • Purely software version of this technique - although it might be slow and it would require changes to the Ogre::Mesh API in order to select the blending type
  • Extend the Ogre skeleton format to support dual quaternions directly - this would reduce some of the run-time conversion costs due to the matrix -> dual quaternion conversion for this technique
Why You're The Person For This Project

I am a 20 year old Computer Engineering student from the United States. I have been programming in various languages since I was nine years old. I have been using C++ for eight years. Recently I have been working to convert a ~30,000 line C++ project to C# as a contractor for a company. I have worked with Ogre since version 0.14 and I’ve done various terrain, lighting, and shadow experiments with Ogre. I’ve also successfully used FFMpeg to play videos on a texture with Ogre. Also I have some open-source experience, I wrote the initial version of the Mac OSX joystick backend for OIS (Open Input System).

Unfortunately, I can’t show the professional work I’ve done, but here is a sample from the OIS work I did. I think this is largely unchanged, although I think there were a few small patches contributed: MacJoyStick.cpp. I also contributed various changes in the MacHIDManager: MacHIDManager.cpp

I have been fairly involved in the Ogre forums since 2005, although I tend to read the forums more than I tend to write in threads. Although recently, I feel that I am coming to a point with my experience that I will be able to contribute more. I also was quite active on the WGE sub-forum of the OIS forums http://www.wreckedgames.com/forum/. Recently I have not been as active online, but I hope to reinvigorate my participation with this project.

Why OGRE?

3D graphics programming has always been one of my favorite activities and I have really enjoyed using Ogre over the past years. As I have learned how to program, I have benefited from the friendly community of fellow Ogre-users and the extensive documentation available. It seems that I end up reading the forums almost daily. It would really be a great accomplishment for me to be able to help out this project that has truly inspired me.

Anything Else

I am aware of the difficult math involved in working on this project, and I admit that I have not fully grasped its entirety. Some of the derivations in the paper are quite tricky. However, I have a fairly solid mathematical background, including multivariable calculus and linear algebra, and I have been researching the mathematics involved in this project. Although the math used in developing this technique is sophisticated, the actual implementation of the technique should be more mathematically straightforward. I have come to have fairly good understanding of the subject matter and I am confident that I will be able to execute this project.

Thank you for reading my proposal. I'm grateful for any comments or guidance you wish to give.
Last edited by mysterycoder on Mon Apr 04, 2011 7:15 am, edited 15 times in total.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Noman
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 714
Joined: Mon Jan 31, 2005 7:21 pm
Location: Israel
x 2
Contact:

Re: [GSoC 2011] Dual Quaternion Skinning

Post by Noman »

First of all, this proposal is very well-written. Any other students that want to see the format of a good application, this is a great starting point.

As for the proposal itself, it is also very nice. The mathematical sophistication of this project is indeed a bit worrying, but it looks like you can work it out.

I'd appreciate it if you took a bit of time to search the net for all available implementations of this type of skinning (even just relevant parts), to try to estimate how many references you'll have in case you get stuck mathematically. You mentioned a CG example in the paper's web page. Does it come with a full project? Is there one available elsewhere?

Also, the timeline is completely linear. Do you think that all tasks are of equal size, or is this just a rough estimate? Also, will you be available 100% during the period? (exams might make you unavailable).
User avatar
tuan kuranes
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 2653
Joined: Wed Sep 24, 2003 8:07 am
Location: Haute Garonne, France
x 4
Contact:

Re: [GSoC 2011] Dual Quaternion Skinning

Post by tuan kuranes »

Nice proposal.

Some remarks:

What about instancing and animation ? not planned ?
Which Rendersystem (GL,GL es, DX9, DX11)?
Which limitations ?
You could add a "current state of the art" would be nice, with links and comparison (http://www.ogre3d.org/forums/viewtopic.php?f=3&t=41255
http://developer.download.nvidia.com/SD ... onSkinning etc.)
Some consideration on further possible enhancements ?
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011] Dual Quaternion Skinning

Post by mysterycoder »

Thanks for the feedback. :)
Noman wrote:I'd appreciate it if you took a bit of time to search the net for all available implementations of this type of skinning (even just relevant parts), to try to estimate how many references you'll have in case you get stuck mathematically. You mentioned a CG example in the paper's web page. Does it come with a full project? Is there one available elsewhere?
I will update my proposal with any implementations that I find.

The paper's website has a cg shader that contains the following techniques:
  • Basic dual quaternion skinning
    Basic dual quaternion skinning, using the theoretically perfect per-vertex antipodality handling. (More robust, but not as efficient)
    Optimized version of the dual quaternion skinning that avoids dual quaternion - matrix conversion by using the formula derived from Lagrange's formula
    Two-phase skinning, which combines the optimized version of the dual quaternion skinning with scale/shear transformations
There is also a .c file on the website which contains several functions that:
  • Convert from a unit quaternion and a translation vector to a unit dual quaternion
    Convert a unit dual quaternion to a unit quaternion and a translation vector
    Convert a dual quaternion with a non-zero non-dual part to a unit quaternion and a translation vector
It doesn't come with a full project per se, but it seems to cover all of the parts that I would possibly run into trouble with.
Noman wrote:Also, the timeline is completely linear. Do you think that all tasks are of equal size, or is this just a rough estimate? Also, will you be available 100% during the period? (exams might make you unavailable).
The timeline is just a rough estimate for now, I will update it soon with more accurate estimations. Realistically I will be unavailable for one week due to exams. Although I don't think this will affect the progress of the project overall, I will be sure indicate it in the updated timeline.
tuan kuranes wrote: What about instancing and animation ? not planned ?

I would like to do a shader that includes both instancing and animation, but I was worried that it might extend the scope of the project a bit too much. If you think it is feasible I would be glad to incorporate it as well into the proposal.
tuan kuranes wrote:Which Rendersystem (GL,GL es, DX9, DX11)?
I plan on supporting GL, DX9, and DX11. I want to first write the initial shaders in CG because I have more experience with CG than HLSL or GLSL, and due to the fact that the example shaders are already written in CG. I'm not familiar with OpenGl ES or the OpenGl ES Shading language, but it seems to be supported by RTSS and if the emulators are good enough to simulate it and there is time left in the project, I'd be happy to do that as well.
tuan kuranes wrote:Which limitations ?
Animation blending with dual quaternions is a bit slower than linear blending. (According the website, an extra 7 vertex shader instructions)
Scale and shearing isn't supported in the basic version of the technique, but is supported via two-phase skinning (According the website, an extra 29 vertex shader instructions)
Sometimes there are flipping artifacts because the skin always goes the shorter way around.
tuan kuranes wrote:You could add a "current state of the art" would be nice, with links and comparison (viewtopic.php?f=3&t=41255
http://developer.download.nvidia.com/SD ... onSkinning etc.)
Some consideration on further possible enhancements ?
Thanks for the links, I will look into doing this.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011] Dual Quaternion Skinning

Post by mysterycoder »

I've updated my proposal with a draft of the current state of the art, information about existing implementations of dual quaternion skinning, an updated schedule (expanded to include instancing), and some potential future project expansions.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Noman
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 714
Joined: Mon Jan 31, 2005 7:21 pm
Location: Israel
x 2
Contact:

Re: [GSoC 2011] Dual Quaternion Skinning

Post by Noman »

Great stuff! The application in its current state is very much submittable as it is.

The one thing I would add is some milestone partitioning to the project - at which points do you have something that is finished and deliverable to the community (in case you don't finish everything you planned)? You used the mid-term evaluation as one, but is that the only thing? We don't want to end up with a bunch of undocumented/untested code if you don't do everything you planned. (You do have such separation, but didn't state it explicitly in your application, which I think is nice, also might trigger some reordering of tasks which usually helps the project progress in a cleaner way)
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011] Dual Quaternion Skinning

Post by mysterycoder »

Thanks for the advice about the milestones, I've now sectioned the schedule with regards to each deliverable. Your right, it certainly did help me clarify things a bit! :D
I've also updated the application with revisions, an additional paragraph about instancing integration, and a paragraph regarding potential downsides.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Noman
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 714
Joined: Mon Jan 31, 2005 7:21 pm
Location: Israel
x 2
Contact:

Re: [GSoC 2011] Dual Quaternion Skinning

Post by Noman »

Nice! Just don't forget to upload your proposal to the google-melange web site (address can be found in the FAQ thread, I believe) before the April 8th deadline. (Its better not to wait until the last minute).

Good luck!
User avatar
Assaf Raman
OGRE Team Member
OGRE Team Member
Posts: 3092
Joined: Tue Apr 11, 2006 3:58 pm
Location: TLV, Israel
x 76

Re: [GSoC 2011] Dual Quaternion Skinning

Post by Assaf Raman »

Yes, go ahead and submit your proposal in the Google dedicated site: http://www.google-melange.com
Time is short - don't wait.
Watch out for my OGRE related tweets here.
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011] Dual Quaternion Skinning

Post by mysterycoder »

Thank you for the heads up, I'll have it up by tonight. :)

Edit: Submitted.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Noman
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 714
Joined: Mon Jan 31, 2005 7:21 pm
Location: Israel
x 2
Contact:

Re: [GSoC 2011] Dual Quaternion Skinning

Post by Noman »

Congratulations! Your project has been accepted to Google Summer of Code 2011, and Mattan Furst will be your mentor.

We'll be setting up a working environment in the coming weeks. In the meantime, could you please update the wiki page of your project with the latest version of your proposal?

http://www.ogre3d.org/tikiwiki/SummerOf ... evelopment
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

I'm really looking forward to doing this project. :D

I'll be sure to update the wiki page with my proposal soon.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
spacegaier
OGRE Team Member
OGRE Team Member
Posts: 4304
Joined: Mon Feb 04, 2008 2:02 pm
Location: Germany
x 135
Contact:

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by spacegaier »

One general note: Please always add important points such as the link to the Ogre fork where you will do your work also to the wiki page, so that those key information are stored at a central place. Thanks!
Ogre Admin [Admin, Dev, PR, Finance, Wiki, etc.] | BasicOgreFramework | AdvancedOgreFramework
Don't know what to do in your spare time? Help the Ogre wiki grow! Or squash a bug...
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

Thanks, certainly noted. I'll make sure that info is there as well as soon as my wiki account gets sorted out. :)

Edit: The issue was quickly resolved, and now the proposal is up!
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
LBDude
Gnome
Posts: 389
Joined: Mon Jul 26, 2010 10:53 pm
x 22

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by LBDude »

This is so cool.
My blog here.
Game twitter here
User avatar
Mattan Furst
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 260
Joined: Tue Jan 01, 2008 11:28 am
Location: Israel
x 32

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by Mattan Furst »

Hi mysterycoder,

Congratulation on having your proposal accepted. It seems like a very worthy and hard subject.

I apologies for the lack of communication. I've been busy moving to a new place.
If you want to contact me directly my e-mail is XXXXXXXXXXXXXXX
or though msn messenger XXXXXXXXXXXX (don't send e-mails to the yahoo account I don't keep track of it).

Update:
I've removed my information from here to protect myself from spam bots.
Last edited by Mattan Furst on Tue Jul 12, 2011 7:56 pm, edited 1 time in total.
it's turtles all the way down
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

LBDude wrote:This is so cool.
I know! It's exciting. :)

Hi Mattan,

It's nice to meet you. No problem for the lack of communication, I've been pretty busy myself anyways.
Perhaps once things start calming down for you, we could set up a time to communicate over msn sometime in the coming weeks?
I look forward to working with you.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Mattan Furst
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 260
Joined: Tue Jan 01, 2008 11:28 am
Location: Israel
x 32

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by Mattan Furst »

Ok,
I think I am finally beginning to understand the math behind these dual quaternions. Please someone correct me if I'm wrong on any of these points:
  • The dual quaternion is used to represent translation and rotation transformations (scale and shear need to be handled separately). The real component of the dual quaternion represents the rotation, while the dual component represents the translation.
  • The skin collapsing issue ("candy wrap" effect) is resolved not because of the individual dual quaternion representation per se, but rather because of mathematical calculations with which quaternions are combined together. In 3d models this applies to vertexes affected by more than one bone.
  • Conversion of 4x4 transformation matrices to dual quaternion can be done by in Ogre by using the Matrix4::decomposition() function. The extracted rotation quaternion will equal the real component of the dual quaternion. The translation vector will equal the i j and k coefficients of the dual component quaternion divided by 2 (The real component of the dual component quaternion will equal zero).
  • After Ogre calculates the matrices an entity's skeleton, it will convert each matrix to a dual quaternion and send this data to the vertex shader. The vertex shader will locate the appropriate quaternion for the given vertex and add them together using the appropriate weights. The final result will be converted back to a 4x4 transformation matrix (to be multiplied by the vertex position).
it's turtles all the way down
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

The math with dual numbers is quite hard to get your head around. :?
I'm not quite there yet with the dual numbers, but I feel as I begin to implement it, some of the finer points will become clear.
From what I know, I think that almost everything you said was correct :), except for two points.
Mattan Furst wrote:Conversion of 4x4 transformation matrices to dual quaternion can be done by in Ogre by using the Matrix4::decomposition() function. The extracted rotation quaternion will equal the real component of the dual quaternion. The translation vector will equal the i j and k coefficients of the dual component quaternion divided by 2 (The real component of the dual component quaternion will equal zero).
The dual component of the quaternion isn't just the components of the translation vector divided by 2. The rotation quaternion also affects the dual component as seen in the .c file provided with the paper:

Code: Select all

// dual part:
dq[1][0] = -0.5*(t[0]*q0[1] + t[1]*q0[2] + t[2]*q0[3]);
dq[1][1] = 0.5*( t[0]*q0[0] + t[1]*q0[3] - t[2]*q0[2]);
dq[1][2] = 0.5*(-t[0]*q0[3] + t[1]*q0[0] + t[2]*q0[1]);
dq[1][3] = 0.5*( t[0]*q0[2] - t[1]*q0[1] + t[2]*q0[0]);
Mattan Furst wrote:After Ogre calculates the matrices an entity's skeleton, it will convert each matrix to a dual quaternion and send this data to the vertex shader. The vertex shader will locate the appropriate quaternion for the given vertex and add them together using the appropriate weights. The final result will be converted back to a 4x4 transformation matrix (to be multiplied by the vertex position).
The non-optimized version of the technique requires a conversion back to a 4x4 transformation matrix. But, they derived a formula that directly applies transformations to the vertex without the conversion to the matrix. The formula is under the "Algorithm 1" heading in the paper and is implemented in the "dqsFast" function in the provided Cg shader.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

I've started work on doing some coding this weekend as Monday, which should be the first day of coding, is quite busy for me.
An initial commit of a DualQuaternion class (based on the Quaternion class in Ogre) and some associated CppUnit tests is in my bitbucket fork: https://bitbucket.org/mysterycoder/ogre ... onskinning.
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Mattan Furst
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 260
Joined: Tue Jan 01, 2008 11:28 am
Location: Israel
x 32

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by Mattan Furst »

@mysterycoder

We haven't had a real chance to talk. It's good to see you already started. I can see from your posts that you are well familiar with Ogre so I wont pester you too much. However:
  • Please do regular commits to the source code, at least one a week.
  • If you have a document with an outline of the changes you wish to do to Ogre code please post it. I believe that the focus for you for the next 2 weeks will be on: DualQuaternion, GpuProgramParams, Entity and AutoParamDataSource. Is this correct?
  • If you have questions please post them on this thread and I will try to answer to the best of my ability. I intend to follow this thread and your commits regularly.
On another note, there is a bug in the hardware skinning of the RTSS which prevents it from working properly on vertexes with more than one bone. I already have a fix for it plus some other improvements / bug fixes. I will check them in as soon as I can. This should be next week. I will post more on this once all changes are checked in.
it's turtles all the way down
User avatar
spacegaier
OGRE Team Member
OGRE Team Member
Posts: 4304
Joined: Mon Feb 04, 2008 2:02 pm
Location: Germany
x 135
Contact:

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by spacegaier »

Mattan Furst wrote:I intend to follow this thread and your commits regularly.
Might be a good idea for you two (Mattan and mysterycoder) to subscribe to that thread (button is at the bottom), so that you receive eMail notifications for each answer here. That could help improving the communication.
Ogre Admin [Admin, Dev, PR, Finance, Wiki, etc.] | BasicOgreFramework | AdvancedOgreFramework
Don't know what to do in your spare time? Help the Ogre wiki grow! Or squash a bug...
User avatar
Mattan Furst
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 260
Joined: Tue Jan 01, 2008 11:28 am
Location: Israel
x 32

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by Mattan Furst »

Thanks, Never noticed that before.
it's turtles all the way down
mysterycoder
Google Summer of Code Student
Google Summer of Code Student
Posts: 169
Joined: Sat Dec 03, 2005 2:04 am
x 6

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by mysterycoder »

@spacegaier
Thanks for the tip. :)

@Mattan Furst
Mattan Furst wrote:Please do regular commits to the source code, at least one a week.
Committing at least once a week should be fine, although I'm expecting to commit every two days or so once I'm out of school.
Mattan Furst wrote:If you have a document with an outline of the changes you wish to do to Ogre code please post it. I believe that the focus for you for the next 2 weeks will be on: DualQuaternion, GpuProgramParams, Entity and AutoParamDataSource. Is this correct?
I don't have a document that outlines the changes that I wish to make to Ogre, however, if you would like I could create one. Your assessment of the classes I'll be modifying is correct as far as I know.
Mattan Furst wrote:If you have questions please post them on this thread and I will try to answer to the best of my ability. I intend to follow this thread and your commits regularly.
In addition to the tip that spacegaier gave, something else that may be helpful is that on bitbucket, I believe there is an option to "follow" a fork, if that might be helpful for you.
Mattan Furst wrote:On another note, there is a bug in the hardware skinning of the RTSS which prevents it from working properly on vertexes with more than one bone. I already have a fix for it plus some other improvements / bug fixes. I will check them in as soon as I can. This should be next week. I will post more on this once all changes are checked in.
Thanks for the heads up about the RTSS bug, it sounds like it should be all sorted by the time I start on RTSS on week 5, but I'll make sure that I update the Ogre code in the fork to the latest before I begin. :)
I'd also be interested learning the details of your patch to help me gain familiarity with that area of RTSS. :D
My Google summer of code 2011 topic: Dual Quaternion Skinning
My Google summer of code thread
My Google summer of code wiki page
User avatar
Mattan Furst
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 260
Joined: Tue Jan 01, 2008 11:28 am
Location: Israel
x 32

Re: [GSoC 2011 - Accepted] Dual Quaternion Skinning

Post by Mattan Furst »

I don't have a document that outlines the changes that I wish to make to Ogre, however, if you would like I could create one. Your assessment of the classes I'll be modifying is correct as far as I know.
No need. I do appreciate the fact that this project is more challenging on a mathematical level than it is on programing. I would suggest doing some sort of general plan document, if only for your own sake, but I don't require it.
thanks for the heads up about the RTSS bug, it sounds like it should be all sorted by the time I start on RTSS on week 5, but I'll make sure that I update the Ogre code in the fork to the latest before I begin.
The bug itself is a dumb bug where I got confused with the order of parameters I entered the shader. The more important change are a series of function that allows you to scan an entity and prepares it to be used in the Hardware skinning without the need to specify things in the material script. But even there the change to the actual sub-render state class is minimal.
it's turtles all the way down
Post Reply