Handmade Hero»Forums»Code
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
Edited by Ginger Bill on
I know a lot of people want to know about quaternions: what they are and how to use them. A while ago, I made a few videos on quaternions as part of my Dunjun series.



------

On a side note, I don't particularly like how Dunjun went. I had to stop due to work and lack of time but I also would have preferred if had just done the entire thing in C from the start. I got caught up in thinking I had to programming in a OOP-style so people would "understand". I also experimented in trying to fix C++'s OOP implementation but failed as it was flawed from the start.

I think I will start another series in the next month though. I was thinking of making short/mini series. I was thinking of doing: retro-style game programming such as raycasters, and mode-7/wolfenstein-3d style rendering; advanced memory management techniques (custom allocators, Registers/L1/L2/etc.). Something that will only take 2-4 (20 minute) videos at the most.
Gonçalo Santos
5 posts
Studying Electrical and Computers Engineering @FEUP
Quaternions
I think I will start another series in the next month though.
Yeah! I watched some videos from the Dunjun series, and from time to time I went to your twitter to see if there were any news about the project, but I am really glad that you are going to start a new small project that, from what I understand, will be in C or C-like C++ (never really liked OOP so that's great news!).

Good luck!
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
Edited by Ginger Bill on
I will most definitely use C. I've been thinking why do I even use C++ lately.

I use the following C++ features:
  • Function Overloading
  • Default Parameters
  • Operator Overloading (only for math libraries)
  • 1
    const&
    
    as an indication of immutability for functions (I don't use non-const references).
  • Namespaces as why to manage modules
  • No need to
    1
    typedef struct
    
  • Struct initialization anywhere
  • Move semantics in some places only for compiler optimizations
  • Templates only for
    1
    Array<T>
    
    and
    1
    Hash_Table<T>
    
  • RAII only for use with my
    1
    defer
    
    macro: my article

These are all useful and make my life easier but they are not necessary and I actually make the language too complex. C++ has a lot more than this and half it is dreadful. May of the features I use, I can easily implement them metaprogramming style and/or macros.
511 posts
Quaternions
There are a few thing that you should at least cover if you are talking about quaternions to use in games.

First how to create one from a rotation described by 2 vectors that isn't QuatFromAxisAngle(Normalized(Cross(v1, v2)), Acos(dot(v1, v2)));

Instead you can do Normalize(QuatFromWAndVector(1 + dot(v1, v2), cross(v1, v2)))

This works out because QuatFromWAndVector(dot(v1, v2), cross(v1, v2)) is the quaternion of the double angle so if you NLerp(DoubleQuat, Quat(1,0,0,0), 0.5) you get the quaternion you want without having to call any trig functions.

With Slerp you can optimize the acos based formula based on NLerp(q1, q2, 0.5) == SLerp(q1, q2, 0.5) and the constant velocity of slerp to bisect the slerp range and only slerp on half of it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
quat SLerp(quat q1, quat q2, r32 t)
{
    quat Result;
    if(Dot(q1, q2) > 0.95)
    {
        Result = NLerp(q1, q2, t);
    }
    else if(t < 0.5)
    {
        Result = SLerp(q1, NLerp(q1, q2, 0.5), t*2);
    }
    else
    {
        Result = SLerp(NLerp(q1, q2, 0.5), q2, t*2 - 1);
    }
    return(Result);
}


If you turn this into the iterative form you can change the stopping criteria:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
quat SLerp(quat q1, quat q2, r32 t)
{
    for(u32 Step = 0;
        Step < 5;
        ++Step)
    {
        quat Mid = NLerp(q1, q2, 0.5);
        if(t < 0.5)
        {
            q2 = Mid;
            t = t*2;
        }
        else
        {
            q1 = Mid;
            t = t*2 - 1;
        }
    }
    quat Result = NLerp(q1, q2, t);

    return(Result);
}


and voilà; a function that used to take an acos and 2 sins and a normalize is changed to a function that takes a tune-able amount of normalizes. The step limit 5 that I picked is the limit to where Cos(PI/(1<<n)) becomes larger than 0.95. The branch can be optimized with a conditional mov and changing t*(1<<5) into an int you can do bit checks with.

As an added bonus unlike the acos based formula this version does not become unstable when q1 is nearly equal to q2. Only when q1 is nearly equal to -q2 but you can't do anything about that.
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
I did not cover this as these videos were originally part of my Dunjun and series and just videos on Quaternions.

Your `SLerp` is a very good approximation and the error compared to the real spherical lerp would be extremely minute.

Another way of doing `slerp` is just use `nlerp` and change how `t` varies. Rather than it be linear interpolation (a + b*t), you can use a Hermite interpolation to approximate this deviation from the true spherical interpolation.

e.g.

(assuming t := [0, 1])

t' = -2 t^3 + 3 t^2 (3rd order Hermite interpolation polynomial)

t' = 6 t^5 - 15 t^4 + 10 t^3 (5th order Hermite interpolation polynomial)


You can refine this further by going to higher orders to get better approximations but after the 5th order, you probably won't notice a difference.

Hermite polynomials have a close relation ship to spherical harmonics so this is why it can be used. Quaternions can be used to even derive the spherical harmonics much like the complex number can be used to derive the Fourier series. A friend and I discovered this a while ago and it's pretty cool/fun to do if you want to try it (it had been discovered well before but we didn't know).
511 posts
Quaternions
It's just some things that I would like to see.

I was debating also mentioning that you don't need a normalized quaternion to generate the matrix if you divide each xx, yy, ... term by LengthSquared. But I've learned that invSqrt is less expensive as a fdiv. I wouldn't be surprised if the reciprocal finding was defined in terms of invSqrt: 1/r = Square(invSqrt(r));

I'm a bit too much of a purist to trust the approximation of the Hermite polynomials. Especially when I know that how much the t should deviate from the input depends on the angle between the quaternions.
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
Edited by Ginger Bill on
It really depends on what you want. This is why quaternions in games a funny subject. I have a physics background I've used them explain the spin transition of particles quite easily but in physics, you never need to worry about interpolating a quaternion. Matrices are still favoured in physics because of their analytical properties but I still love my quaternions.

Quaternions to me are just the Spin(3) group which are isomorphic to the SU(2) group (Pauli matrices which imaginary components (Even Cl_3,0(R)) pretty much and only norm-quaternions). This is why norm-quaternions always have that angle/2 part as the SU(2) group double-covers the SO(3) group.

When it comes to quaternions and computers, it's approximation everywhere. Slerp may not be problem on modern computers as they are that damn fast. It's really a question of how accurate you want it and the Hermite approximation is pretty good even with arbitrary quaternions.
popcorn
70 posts
Quaternions
There are a lot of series to follow! Since this one is in C++ and 3D, I will follow and watch it, although, handmade hero itself is keeping me a bit busy and is very tiresome to go through so, I'm not sure if I'm going to follow and code (doing the same for Handmade Quake as well). I really want to though and I might later.
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
I would only recommend watching the later videos are the blackboard only videos. I do not like what I have done in the series and also, I cannot continue with the series at the moment. I really wish I did the entire series in plain C but oh well.
popcorn
70 posts
Quaternions
Edited by popcorn on
It's fine, I think. Anyways, Are you still making these videos?
Ginger Bill
222 posts / 3 projects
I am ginger thus have no soul.
Quaternions
Sadly no. I am planning a new series to teach programming in C for total beginners. Also I have a few mini series planned such as ray tracing and memory management techniques.
popcorn
70 posts
Quaternions
oh I mean are you still going to the Dunjun series? I have watch some of it already and is kind of learning c++11 and opengl (concept) in the process.