Short Description

Dual quaternion skinning is a method of skinning that addresses commonly associated problems with linear blend skinning. By using an approximate blending method, dual quaternion skinning is able to achieve comparable speeds to linear blend skinning, while still retaining the increase in visual quality. This project will cause Ogre to support dual quaternion skinning seamlessly for the user, including InstanceManager support.

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:

|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 R3, where SO(3) is the set of all rotations in three space, and R3 is a vector in three space. A transformation in SE(3) would be composed of a matrix:

|R v|
|0 1|


where R is a rotation matrix in SO(3) and v is a vector in R3.

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

Where wi are the various weights associated with each transformation and qi 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
An XNA implementation of Dual Quaternion Skinning
Dual Quaternion Skinning implementation for Maya
Sample from Nvidia - Skinning with Dual Quaternions
Some implementation notes

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)
Integrate Cg shaders from reference implementation for basic dual quaternion skinning and two phase skinning (supports shearing and scaling)
Write GLSL and HLSL versions of basic dual quaternion skinning and two phase skinning shaders

Deliverable: Demo with a comparison between standard skinning and dual quaternion skinning (working RTSS implementation of dual quaternion skinning in Ogre)

Week 5 (June 20th)
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 6 (June 27th)
Finish writing the HardwareSkinningDBLS and HardwareSkinningDBLSTwoPhase classes
Week 7 (July 4th)
For integration with RTSS: Adapt existing Cg, GLSL, and HLSL shaders (and possibly GLSL ES) to work with RTSS
Write demo that highlights the differences between dual quaternion skinning and linear blend skinning
General code cleanup and optimization before moving on to instancing support

Deliverable: Extend previous demo to showcase instancing

Week 8 (July 11th)
Mid Term evaluation - having the comparison demo is essential
Begin work integrating Dual Quaternion skinning with instancing
Ogre InstanceManager integration - modify OgreInstanceBatchVTF and OgreInstanceBatchHW_VTF to pack dual quaternions into textures
Week 9 (July 18th)
Begin writing Cg, GLSL, and HLSL shader implementation for Shader-based, VTF, and HW+VTF instancing
Week 10 (July 25th)
Finish implementation of instancing
Week 11 (August 1st)
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)
Potential OpenGl ES implementation is considered as well

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 and 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 have done various terrain, lighting, and shadow experiments with Ogre. I’ve also successfully used FFMpeg to play videos on a texture with Ogre. In addition, I have open-source experience in that I wrote the initial version of the Mac OSX joystick backend for OIS (Object-Oriented Input System).

Due to the nature of the job, I cannot show you an example of the professional work I that I have done; however, I have provided samples from the OIS work I have done in the past. I believe these to be largely unchanged, although I believe there were a few small patches contributed: MacJoyStick.cpp. I also contributed various changes in the MacHIDManager: MacHIDManager.cpp

I have been involved in the Ogre forums since 2005. I am more apt to read the forums than I am to write in threads, although I am reaching to the point in my experience with this program that I feel I can contribute more of my knowledge. I also was quite active on the WGE sub-forum of the OIS forums http://www.wreckedgames.com/forum/. I have not been as active online lately due to the labors of my University studying; however, through this project I hope to reinvigorate my participation.

Why OGRE?

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

Anything Else

I am aware of the advanced mathematics that are involved in this project, and I admit that I have not fully grasped to implications of some of the constructs in their entirety. To be straightforward, I found a few of the derivations in the paper to be quite tricky. However, I have a solid mathematical background, including multivariable calculus and linear algebra, and I have been researching the mathematics involved in this project. Although the mathematics used in developing this technique are sophisticated, the actual implementation of the technique should be more mathematically straightforward. I have developed a good understanding of the subject matter and I am confident that I have the potential to successfully execute this project.