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|
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|
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.
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:
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: 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:
- An XNA implementation of Dual Quaternion Skinning
Dual Quaternion Skinning implementation for Maya
Sample from Nvidia - Skinning with Dual Quaternions
Some implementation notes
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
- 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
April 25th – May 23rd -
- Get to know mentor
- Work on shader programming, quaternion and dual number math
- Firm handle on integration with Ogre
- Week 1 (May 23rd) –
- Begin coding
- Add support for conversion to and from dual quaternions to Ogre
- Generate dual quaternions from the animations
- Expose the dual quaternions to shaders via a param_named_auto (world_dual_quaternion_array_2x4)
- Week 3 (June 6th) –
- I have exams this week and will be unavailable
- Write Cg shader that implements basic dual quaternion skinning.
- Write Cg shader that implements two phase skinning (supports shearing and scaling)
- 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
- Finish writing the HardwareSkinningDBLS and HardwareSkinningDBLSTwoPhase classes
- Mid Term evaluation
- For integration with RTSS: Write GLSL, HLSL (and possibly GLSL ES) versions of basic dual quaternion skinning and two phase skinning
- 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
- Begin writing Cg shader implementation for Shader-based, VTF, and HW+VTF instancing
- 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)
- Week 12 (August 7th) –
- Tests, optimizations
- Begin writing documentation
- August 15th is the suggested pencils down date
- Write tutorials to help people integrate Dual Quaternion skinning into their own shaders
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
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.