Working Quaternions for stars and moons

[Digital-Monk]

Star and Moon rotations handled by Quaternions instead of matrices. I do see some edge stretching of the starfield as I rotate, but I see that with the Matrix code as well, so I think it is related to the HFoV. (I'm used to keeping HFoV fairly narrow, but I know action gamers like it wider, and that results in some fisheye distortions around the edges)

Quaternion products now normalize automatically. This appears to be critical for proper behavior. I do wonder, since we need to normalize Quaternions this frequently even with double precision, if we could get by with single precision in the Quaternions and rely on normalization to keep things sane... If so, that would double the amount of work per opcode that the SSE optimizations could do...

This is my first pull request, and it includes some small changes that are local to my setup. Sorry about that, but I couldn't see a way to block those (compilation options, .gitignore settings, etc).

Hopefully this works for you as well.

[afritz1]

Oh I see. I had been trying to multiply the two quaternions together into one sky rotation, and that wasn't working. I guess there isn't a way to do that safely?

I'm wondering about this pattern:

quaternionA * (quaternionB * quaternionC).normalized();

It's not really normalizing the whole thing, just B and C, which seems like it shouldn't work.

[Digital-Monk]

It's not really normalizing the whole thing, just B and C, which seems like it shouldn't work.

I dunno if I messed something up before pushing... My intent was to put the normalized() inside Quaternion::operator *, and then you don't need those other calls to normalized() anywhere else because every multiplication normalizes its own result. But I may have goofed up the operator * or I may have missed some of the places where I did the .normalized() out at the call. Sorry, this isn't my main dev machine, and I could easily have missed some details...

You should be able to multiply the two rotation quaternions together, as long as the result is normalized (which it would be by operator *). That should actually be a good optimization.

[Allofich]

Sorry about that, but I couldn't see a way to block those (compilation options, .gitignore settings, etc).

If you are using the Git Bash command line, you can reset files you accidentally modified and added to your commit like this (if you are using the GitHub GUI or some other way, I don't know how):

git checkout (last commit before you changed those files) (path to file)

Looking at your fork it looks like the last commit before any of yours is 03493a2, so

git checkout 03493a2 .gitignore

and

git checkout 03493a2 CMakeLists.txt

should work (these two files are in the root folder of the project so just the file name should be OK). Then do

git commit --amend

and you should be able to re-do the commit with those two files no longer modified. Then force push to update your branch.

Edit: Actually, in this case looks like those two files were modified, and were the only modifications at all, in the first commit, so just removing that commit should also work.

[afritz1]

I would like to leave the Quaternion initializer list as it was, because there is no gain to putting primitive types in there. The initializer list is only for keeping a non-primitive type's default constructor from running. In the case of primitive types (int, double), their default constructor is empty, and it is this project's convention to put them in the body of the constructor.

The moon position calculation should also be left alone since that is a value from the original game.

[afritz1]

Let me know when you're done with changes. I would like to make one commit with a few minor things.

[Digital-Monk]

Sorry for Git clumsiness. I didn't want to risk trying to partially revert my first commit, so I added commits to put collateral things back the way I found them. The only intentional changes are in SoftwareRenderer.h/.cpp and Quaternion.h/.cpp. And I apologize for my old habits of leaving commented dead code as reference in a couple of places... I came late to the revision control party.

Rather than wading through my commit mess one at a time, you'll probably be happier just looking at the final differences... They're not much...

I don't have anything further to add, really.

I played around a little bit with memoizing latitude and daytime quaternions, and switching Quaternion to use single-precision internally. Neither gave me any noticeable speed improvement -- but neither caused any problems, either, so at some point it might be worth seeing if you actually need double precision for this work -- very few game engines do, as long as things stay normalized, which you're already doing. Just changing Quaternion's insides while leaving the public interface double precision didn't help, but if values could stay in single precision and be used that way throughout the renderer, I would expect a noticeable improvement in SSE performance. But that's a separate issue entirely...

[afritz1]

I am planning on using 32-bit floats eventually. I just started out with doubles everywhere to prevent the possibility of bugs being caused by lack of precision.

The important parts in the renderer (namely, the shaders) don't really have compiler-vectorizable code yet, so I wouldn't expect the generated code to be that much different between floats and doubles.

[afritz1]

Testing this branch out locally, it looks like the star rotation math isn't quite right. What is it looking like on your computer? At noon, all the stars are squishing to the east (+Z).

[afritz1]

I rebased it after adding a new RendererUtils namespace. I also recommend using a new branch other than master for any new pull requests as it makes these kinds of things a little safer.

[Digital-Monk]

I'll check that tonight. What's the easiest way to make time zoom forward? I don't remember ever seeing anything like that, but maybe I just didn't wait long enough.

[afritz1]

Hold R to fast-forward time.

[Digital-Monk]

To quote Joe Kenda: "Well, my, my, my..."

Broken the same way here. Looks cool, but yeah, no bueno... I'll continue poking.

[Digital-Monk]

Ah... Looked deeper into quaternions, thinking maybe composition of rotation quaternions was something other than just multiplication. Dead end there, but then looking at how to use quaternions to rotate 3-vectors, I see that it's not as simple as I had hoped.

https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation#Performance_comparisons

Then go down a bit further to "Uses", where three methods of rotation vectors are given. The second points out that, where I thought that I could hack it as a quaternion multiplication along the lines of Vnew = Q * {V,0}, the real solution is Vnew = Q * V * inverse(Q). We don't want to actually calculate it that was as it is inefficient, but they give a more efficient formula there. Experiments in progress...

[Digital-Monk]

Argh. That didn't seem to change anything.

So, back to wondering about "product". I'm not sure what kind of product Quaternion::operator* is doing (sorry, I know I checked it before, but I've slept, and I don't remember the name...), but to compose quaternions, we want the Hamilton Product:

https://en.wikipedia.org/wiki/Quaternion#Hamilton_product

The last statement in that piece states that the Hamilton product of two rotation quaternions is a rotation quaternion representing doing both rotations (one after the other, so order is still important, as always)

Yet more experimentation!

[Digital-Monk]

Argh. OK, I've been messing up a lot of stuff tonight, but I finally got a foothold on a correct solution...

You can represent a direction in a quaternion by using it (must be normalized) as the vector portion and w==0. Then, to rotate, you conjugate the direction quaternion with the rotation quaternion. So, if r is the rotation quaternion and d is the direction vector:

dNew = r * d * inv(r)

As long as r is a rotation quaternion (ie, is normalized), then inv(r) is just -x,-y,-z,w (ie, invert x, y, and z, leave w alone).

That's not the most efficient way to calculate that rotation, but it's the first one that has made the stars rotate sanely. I tried the "more efficient" formulation above, and it did some weird squashing stuff...

So, I at least have a point where I can do time of day rotations through quaternions and it works. But right now I'm still having an issue when I try to compose time-of-day with latitude rotations. Experiments continue, but likelihood of a patch tonight is very very low.

[afritz1]

Just making a note that it's not crucial that quaternions even get used. It was just a knee-jerk reaction when I was first writing the star rotation code. I'd be completely fine leaving the matrix multiplications as they are. However, it is interesting to hear you working through quaternions, as I am still pretty mystified by them.

[Digital-Monk]

Now my OCD has locked onto it... I've been wanting to understand quaternions for years anyway. I'll try not to flood you with so much "in progress" stuff though.

[afritz1]

I've changed my mind on this and am going to keep things the way they are. Thanks for looking into it though.