Check that quaternions are correct, and fix them if not

[afritz1]

Last time I tried using quaternions, it was for rotation of stars in the sky, and it looked very incorrect. I added quaternions a few years ago but I don't remember if it was ever a full implementation. I think I implemented just enough for the player camera to work right.

Ideally I would be using quaternions in the renderer for star rotation, but I'm using matrix multiplication as a workaround. Instead of having two functions for obtaining the rotation matrices, I think a single function for obtaining the quaternion would be better.

Places of note:

• Quaternion.h
• Camera3D::pitch()
• SoftwareRenderer::getLatitudeRotation()
• SoftwareRenderer::getTimeOfDayRotation() - daytimePercent is 0 at midnight, 0.5 at noon, and almost 1 at 11:59pm.
• SoftwareRenderer::updateVisibleDistantObjects()

[Digital-Monk]

Looking to see if I can provide any help... Quick question that has nothing to do with quaternions at all, but is there a reason for always accessing members via this->member instead of just member? I can see the desire to clarify that you are modifying object state, but it feels foreign, like a practice brought over from some other language. To me, it increases visual noise without adding clarity. But then, I'm an old programmer, set in my ways, so I'm trying to learn if I've just missed out on new guidelines or industry best practices.

(I have a similar thing with std:: inside .cpp files. Personally, it clogs my brain and I'd rather add using namespace std; near the top. Obviously, never ever ever do that in a .h file, but in a .cpp file, you're only affecting the namespace within that compilation unit.)

Certainly don't want to mess with your code style guidelines, 'coz that makes it much harder to see any useful changes in diffs. Just trying to keep learning.

[Digital-Monk]

The quaternion functions you have implemented match up with the mathematical definitions for those functions. I don't see any errors inside Quaternion.cpp (assuming Double3::cross() works correctly, but I can't imagine anything functioning if that wasn't true...).

I'll look at the usage sites next chance I get.

[afritz1]

For the coding guidelines, I found through practice that using this fit my preferred coding style well. It makes it really easy to narrow down class members with Intellisense and it lets there be no ambiguity with naming without needing to use the icky m_ prefix. Example:

int MyGlobalFunction() { return 1; }

int MyClass::myClassFunction(int localValue)
{
    auto localFunc = []() { return 5 };
    return this->myValue + localValue + localFunc() + MyGlobalFunction();
}

I made this convention up myself, and to me, the four expressions in the return statement each have uniquely identifiable scopes at a glance. myValue is obviously a class member because of this, localValue is obviously a parameter or local variable, localFunc is obviously a lambda because it's called without this, and MyGlobalFunction is obviously a global function because it's upper camel case. I kind of consider all this a post-C++11 convention. I call the m_ prefix icky because it doesn't narrow down naming fast enough with Intellisense. There's always lots of other global garbage that matches m_ too.

That's interesting that the quaternion math looks right. I dunno what to say 😕

[Digital-Monk]

When you say the stars didn't look right, did you have parallax sky active at that time? I know that parallax sky isn't fully implemented, but I've noticed several oddities with it, so that might get confused with quaternion star rotation? I dunno.

Camera seems to work great. Just looked through pitch and it looks good to me (sorry, not super helpful if I can't point at something questionable, but I'll keep looking)

[afritz1]

Using quaternions with stars made them appear completely wrong. It was like the sky was expanding and collapsing on itself along some plane coplanar with the axis of rotation.

[Digital-Monk]

Not sure my brain's up to this exercise tonight, but trying to grind the dust out of the gears... Gonna go see if I can find a commit where the Quaternions were being used for the stars and see if I can spot anything there. Otherwise, I think I have to change all the places that use Matrix4d as rotation to use Quaternion instead, and I know I'm not up to that tonight...

[afritz1]

I don't remember ever committing changes for quaternions with stars, because it was so obviously wrong during initial testing. I think it would be enough to change SoftwareRenderer::getLatitudeRotation() and getTimeOfDayRotation() to use quaternion functions. They are linked in the original post above.

Off the top of my head, I think you use the latitude to make the axis of rotation (tilt the Unit Y vector towards the north pole) then make the axis angle to rotate by? Not sure.

[Digital-Monk]

OK, I've got something compiling, but it's doing the same kind of stretching around the left/right edges as parallax sky does to me, and if I rotate at the right speed, it feels like the stars exist on the walls of a cube, and I can see the corner sliding by. So, yeah, I'm not doing it right either ;) I'll look some more tomorrow. My brain is full.

[Digital-Monk]

GOT IT! Just have to be REALLY conscientious about calling normalized() after every piece-wise calculation. Got a meeting right now, and I want to look at more consistent ways have handling it (considering normalizing the result of every multiplication, because it seems to be VERY sensitive to roundoff issues). More later...

[Digital-Monk]

Yeah, it looks like if we modify Quaternion::operator * so that it always returns a normalized() quaternion, then the stars can be rotated with fairly straightforward quaternion work. But if you don't re-normalize after every multiplication, then the roundoff starts causing the weird lensing effect very quickly (two rotations is definitely enough, and it may happen after only one).

After that, replacing matrix rotations with quaternion transforms is pretty mechanical:

• Replacing Matrix4d and Double4 with Quaternion handles most of the use cases, because a quaternion can be a rotation or a direction, so it can take the place of the rotation matrix or of the direction vector. Nicely, your constructor designs even line up, so Double4(dirvec3, 0) becomes Quaternion(dirvec3, 0) and works correctly.

• Generating rotations is also fairly straightforward. Replace Matrix4d::xRotation(radians) with Quaternion::fromAxisAngle(Double3::UnitX, radians) (and likewise for zRotation/UnitZ, etc).

I can generate a pull request, but it may be just as easy to apply yourself. It would seem that this should work anywhere you're doing rotation matrices...

EDIT: Thinking about why quaternions are more sensitive to rounding errors, it occurs to me that we're using a 4-element quaternion to do the job of a 9-element matrix (16-element, by implementation, but rotation only needs a 3x3). So, each element is having to shoulder the workload of 2.25 "simple" elements. In much the same way that a bit error in a BMP file is imperceptible but a bit error in a JPG file can cause it to explode, this higher information density is more prone to bit-rot as we go through calculations. That's just a gut feeling, and I could be completely off-base...

[afritz1]

It's good to hear you were able to get through it. Next I want to know if it's more efficient to use quaternions for star rotation. I did say this at the start of the issue:

Ideally I would be using quaternions in the renderer for star rotation, but I'm using matrix multiplication as a workaround. Instead of having two functions for obtaining the rotation matrices, I think a single function for obtaining the quaternion would be better.

But actually I think rotation matrices are fine if they are fewer instructions and fewer transcendental function calls.

I don't see how rounding errors would be it when we're using 64-bit floats everywhere. 64-bit floats should be waaaay overkill for just one or two calculations that get projected on-screen.

[Digital-Monk]

Creation of a rotation (whether matrix or quaternion) is going to take a call to sin and a call to cos, regardless. Application of the quaternion does involve a 3x3 matrix-matrix multiplication as well as a few other relatively simple multiplies and additions, so it will be a bit slower than using a 3x3 matrix-vector multiplication, but about the same speed as a 4x4 matrix-vector multiplication (which is what we always do anyway for reasons that are out of scope of this discussion). So performance-wise, quaternion-vs-matrix is roughly a wash so far.

Turning two rotations into one combined rotation is conceptually the same in both cases -- you just multiply the matrices together or multiply the quaternions together. Again, quaternions will be slightly more efficient than 4x4 matrix-matrix multiplication.

On the whole, however, I strongly suspect the performance differences will be small enough to be completely lost in memory access and cache issues...

As far as having a single rotation quaternion/matrix instead of two, that's a matter of architecting your loops to maximize re-use. Now, it does rather seem to me that getLatitudeRotation and getTimeOfDayRotation should not change their results during the course of any single frame of rendering. And that implies that at the beginning of rendering a frame, you could simply do:

Quaternion skyRotation = getLatitudeRotation(lat) * getTimeOfDayRotation(timefrac);

(I may have the multiplication order backwards, but that's easy enough to remedy if things go sideways) Then, for every sky object, it's a single quaternion-vector multiply (technically a quaternion-quaternion multiply, but the second quaternion is just Quaternion(vec, 0))

That could speed things up, especially with high density star fields. But it still may get lost in the raycast-to-voxels cpu load...

[afritz1]

I tried this again just now but even with a lot of experimentation, I can't get the quaternions looking right. Can you do a pull request @Digital-Monk? I would like to see how you're doing the math.

I found it's easier to test stars if I add this at the top of SoftwareRenderer::getSkyGradientRowColor():

return Double3::Zero;