acos 0.99+ values are out by several degrees

[jdtec01]

Hi,

Acos input values between ~0.99 - 1.0 lead to some fairly imprecise output values, off by up to 5 degrees.

eg.

input=0.9941521, expected=0.1082002,  real=0.06253052, diff=0.04566966, :: degrees diff:2.616679
input=0.9961014, expected=0.0883307,  real=0,          diff=0.0883307,  :: degrees diff:5.060977
input=0.9980507, expected=0.06244908, real=0,          diff=0.06244908, :: degrees diff:3.578069

I found this whilst implementing a quaternion angle diff function which had some nasty snapping in these values leading to it being 2-5 degrees off floating point math acos.

I'm not sure what to suggest to improve it. I was considering generating a larger LUT table, however, I'd probably need to change some of the precision bit stuff.

I thought I'd raise it incase you also see this as an issue?

Thanks for putting this project up on github.

[RomanZhu]

Yeah, that is expected for such a small LUT

In the past of this library, I had LUT entry for each single FP value, but that resulted in a ~30-60kb LUT file (for each function)
I thought to get it back, as I also saw some small issues when I was implementing transformation logic

I will think about whenever it's possible to have both approaches

[RomanZhu]

There is one thing you can do to reduce the deviation:

idk why last 3 entries were 0, but with that change, issue is only on the last case

Will take a deeper look into LUT generation for Acos later today

[jdtec01]

Thanks for the suggestion! Adding those extra values appears to reduce the problem a fair bit, say by ~50%. It's less noticeable in my application now.

I slowed down what I was doing and saw that a 2-3(?) deg snap still happens as shown in the video I've included. The red arrow is fixed point and the magenta arrow is floating point. They are both trying to rotate towards the green line.

acos_snap_c.mp4

It's tricky. You have ample precision in parts of the table where the curve delta is small, but then at the extremes of the acos graph you have a larger value delta. Ideally you'd have some sort of 'flexi' LUT which accommodated that (but still had only 512 values). It might be that the easiest thing is to simply increase the LUT size slightly though. I'm not sure, what do you think? Have you used it much in a real application yet?

[jdtec01]

Regarding the last 3 entries being zero, I did spot this in Data.cs:

//Special handling for value of 1, as graph is not symmetric
            AcosLut.Add(AcosLut[ACOS_VALUE_COUNT - 1]);
            AcosLut.Add(AcosLut[ACOS_VALUE_COUNT - 1]);

I guess that accounts for the zero values? I confess I don't understand what this is for yet.

[RomanZhu]

The problem with LUTs which have non-uniform deltas is querying becomes a fair bit more expensive
I've done 2D physics & transformations, but it doesn't use Acos/Asin (which I assume is also affected by that issue)

Soon I will also dive into 3D, so will face this issue too

I think I will make a branch which will use full LUT (so no lerping will be needed) on a weekend
Quick info: each LUT will have a weight of ~2mb ;D

[jdtec01]

Cool, maybe this is the best approach. I wonder if it's worth trying a compromise size between the two extremes later, but probably best to have correctness first and then if it is a performance issue you could always come back to it.

I see that FixedMath.net has ~2mb lut for some of these functions so it's probably not terrible, even though that lib is less performance orientated.

I'll be using it for lots of 3d rotations so I'll probably do some profiling at some point.

[Vincenz099]

Ideally your whole LUT fits in CPU memory, at least L3, otherwise any physics will be dead slow. 2MB won't really fit realistically next to all the other LUTS.

[jdtec01]

Yes @Vincenz099 it's a good point. Are any difficulties thrown up by a compromise solution between the current ~2kb(?) and the full 2Mb. Maybe 8-16kb is sufficient to avoid these sort of snapping issues I've observed in visualisations.

[Vincenz099]

I remember we had similar problems with other Luts, like sin cos tan where the near to zero and near to 1 are very inacurate, one could introduce an extra lut for the lower range, it's what the solution was before.. you could even add like 16 values just for the sub 0.99 or whatever. experiment with that.

[Vincenz099]

The problem is simply this, for trigonometry Luts you are sampling on a constant interval, but the variance between input values is not constant. Forgive my paint skills but lets say you have a value range like this, and you sample constantly, because you linear interpolate between two samples you loose a lot in the beginning and the end as you see.
https://i.imgur.com/8w47XfY.png

[RomanZhu]

Ye, that was the most apparent on SQRT lut

[RomanZhu]

Pushed the LUT for the positive side of Asin, which is used for the negative side, and for Acos

Chech HugeAsinAcos branch
It has an accuracy of 0.0001

[RomanZhu]

I also tried to increase the LUT size from 512 elements to 4k elements, but the distance between the last entry and pre-last was still too big

So I have LUT entry for each FP value right now in the 0-1 range

[jdtec01]

Hi,

I've been running tests to try and understand the original problem (shown in the video above) more. Although acos was inaccurate, I don't think it was the sole cause of my rotation jitter.

So far I think the thing that was causing the most precision loss was conversions from 4x4 matrices to quaternions and back.

I was getting a quaternion rotation from a transform 4x4 matrix, modifying the quaternion, then applying it back to the transform matrix, and repeating that each frame. Instead of this I switched to storing a separate quaternion rotation and only manipulating that. The 4x4 matrix is effectively only a by-product of the quaternion rotation now (quaternion is applied to the matrix but I don't read from the matrix when changing rotation).

This isn't a complete answer but I am guessing that going between matrices & quaternions repeatedly involved a fair few trig functions which may have contributed to the precision loss, but I'm not sure.

The jitter is eliminated by avoid these extra conversions. My only lesson learned so far is to bare in mind these sort of things happen in fixed point!