Quaternions – Intuitive way to start understanding them.

There are a lot of materials out there talking about quaternions, and most of you are already familiar with them, but I thought I will add a small piece from myself, and explain how I do look at them.

So, what they are ? I like to describe them as :

4 dimensional numbers describing 3d rotation in space.

There is some history how they were invented by William Hamilton and what else they are being used for, but for now I want to limit this post just to absolute minimum to understand what they do in your game.

Let’s look at the official formula describing quaternion :

a + bi + cj + dk

a,b,c,d are real numbers – these are the numbers you are most likely well familiar with.

i,j,k are imaginary numbers ( a little bit unfortunate naming ), to ease the pain of understanding them, think about them as a next category of numbers. Similar to negative numbers, fractions etc. Another group of numbers we can use. In case of a quaternion these 3 are referred as fundamental quaternion units.

There are really exciting properties behind Mr Hamilton discovery :

i^2 = j^2 = k^2 = ijk = -1

and I would highly encourage you to dig in a little bit more into the math behind it, to get a full grasp on what is going on under the surface…

For now though, since you know a little bit of theory, how do you create a quaternion knowing the rotation in 3d space you want to achieve ?

To create a quaternion you will need to two variables, an angle (in radians) describing the rotation and a vector describing axis it is rotated along. Then you can fill it with the following formula : X,Y,Z,W

Angle in Radian = Angle in Degree / 360 * PI * 2;

X,Y,Z = AxisInfo * sin ( theta / 2)

W = cos ( theta / 2)

That will define a rule where X^2 + Y^2 + Z^2 + W^2 = 1

Quaternion length is 1.

Multiplying two quaternions will result in one quaternion with the length of 1.

Interpolation :

/–t–\

A      P               B
*—-^———-*

Linear interpolation : p = A +  t * (B-A)

Applying the same to the quaternion will change the magnitude of the quaternion, therefore we do want to use Slerp :

/–t–\

A      P               B
*—-^———-*

To start SLERP interpolation, we need to find out what quaternion allows us to rotate from A to B, so B = X * A where X is an unknown quaternion we need to figure out. Having :

B = X * A

we can try multiply both sides by inverted quaternion A will give us :

B*invertedA = X

At this point we could do t * (B*invertedA) but that will result in a quaternion having incorrect magnitude (remember the rule from above). So instead multiplying the whole quaternion by t, we can look into how the quaternion is created, and recreate it with interpolated angle value it takes.

Based on the definition previously mentioned, it would be :

X,Y,Z = X.AxisInfo * sin ( t * theta / 2)

W = cos (t * theta / 2)

newRotation = (X,Y,Z,W)

That will result in a quaternion describing the rotation from A to B by t, so to finalize it we have to do newRotation * A, and that gives us P.

 

Dithering – Unity

Inspired by a post about Uncharted 4 development, I decided to write a short post about dither alghoritm and one of its uses in game development, speficically to render opaque object as semi transparent.

What is Dither ? Dither per wikipedia :

Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images.

For our purposes we need to go step further and look at Ordered Dithering, which in opposite to standard dithering alghoritm (random) has pre-determined threshold map.

 

Ordered dithering is an image dithering algorithm. It is commonly used by programs that need to provide continuous image of higher colors on a display of less color depth.

In this example, I am going to use Bayer Matrix as a threshold map :

Screen Shot 2017-10-01 at 2.23.29 PM.png

For purpose of this post, I did a small excercise and similary to Ming-Lun, wrote a small alghoritm generating power of 2 bayer matrices and visualized results in Unity.

With threshold map ready, time to simulate transparency by rendering opaque object using fragment shader which is discarding pixels based on current opacity level.

By using DitheringValue function :

float DitheringValue(int cordX, int cordY) {
int x = cordX % _ArraySide;
int y = cordY % _ArraySide;
float result = _Array[(x + y * _ArraySide)] / _ArrayLength;
return result;
}

we wrap current pixels coordinates to be within bayer matrix size and do the look up to pull precalculated threshold value. Then we divide it by the length of the array giving us a value between 0 and 1.

With that value ready, we do want to determine if a pixel should be discarded or not. We can use discard function available in HLSL, but that would require from us to introduce not necessary if statement. Instead we can use clip which will discard every pixel if value provided is going to be less than 0;

clip(DitheringValue(i.uv.y * _Resolution, i.uv.x * _Resolution) – _Transparency);

_Transparency is a value defining the opacity level of the material.

The final results looks like this :

coolcaringfrilledlizard-size_restricted

It shows object going from 0 opacity to 1 and back to 0.

Image below shows two planes in a front of a cube. Top Left (green) plane is using standard semi-transparent material set to 0.5f opacity, Bottom Right (blue) plane is using opaque material with dithering alghoritm set to 0.5f opacity.

Screen Shot 2017-09-30 at 12.22.37 AM

As you can see results are not the same. There are several issues visible at the first glance :

  • Repeating tiling effect
  • Colors doesn’t mix as in the green plane case

These issues can be addressed by improving the threshold map generating alghoritm (i.e. by using Robert A. Ulichney’s void and cluster method). I will try to show how these can improve dithering in part 2, and in mean time, if you are interested, code for this experiment is available here :

Dithering on GitHub

Thanks to Ming-Lun (Uncharted 4 Dithering) for the work over Uncharted 4 and a post about dithering which inspired me to do a quick experiment on my own. For more resources I encourage you to have a look at Libcaca study: the science behind colour ASCII art. With a little bit more time, I will prepare Part 2 in which I plan to describe pros and const of using dithering in more detail as well as improved alghoritm to generate better threshold map.

Thanks !

Next Part :

  • Performance Considerations
  • Optimization (Avoiding Tile Artifefacts)

 

Update [ 04.11.2017 ]

While playing recently released Super Mario Odyssey, I’ve noticed that similar technique was used to render transparent object getting close to the camera. Thought it would be a great example to share a short gif as an example of using it in a game.