Optimisation of Fixed Point Trigonometic Approximations

[Thanduel]

The algorithm currently used in the atan2_aprox has a very large error term for its performance.

To improve it I suggest the use of a CORDIC algorithm. A CORDIC algorithm calculates the angle by working out, through a binary search of precomputed values, what angle rotation would reduce the original angle to zero. All the numerical operations are done in power of 2 operations.

This should at least double the performance for a slightly smaller error (3.576deg vs 4.5deg) term or give slightly faster performance for a sub 0.5 deg error term.

The algorithm currently used in the SIN and COS approximation is very accurate but very slow. I propose to improve this with a CORDIC algorithm as well. For slightly worse accuracy the performance would be about double.

[Thanduel]

I am currently working on a patch for this and will submit it soon.

[sanderd17]

Note that our code also has a second atan and atan2 implementation in JS. It's used by the JS scripts (as the native spidermonkey function wasn't platform consistent and caused OOS problems). That algorithm works with a simple taylor polynome, so it's likely it can be done better too. You can find it in binaries/data/mods/public/globalscripts/Math.js.

If your algorithm turns out to be better, it can be used there too. I don't know how much performance advantage it will give though, as I don't think the atan function is used very often in the JS scripts. But while you're doing all the research on the algorithms, it should be a simple language translation exercise.

[Thanduel]

I will take a look, the same algorithm can be applied to sin and cos approximations of angles calculation of the hypotenuse as well as things like calculating a sqrt or log. It is, however, unclear whether or not it would provide a performance improvement in all of those circumstances.

In my benchmarks averaged over 500000 samples the cordic algorithm improves the performance of the atan2 function by a factor of about 2 for an error term of 3.576deg.

[sanderd17]

Well, be sure to include some benchmarks on real-world examples (not on special cases, unless they happen a lot in the code), as well how you did those benchmarks (so we can repeat them). It would help us decide weather it's better or not.

I don't think we're too concerned about precision (most angle stuff is for visual things), the biggest concern is that it has to be cross-platform.

[Thanduel]

The fixed point trigonometric functions are used in the game logic for example the atan2 approximation is used to determine what direction a unit is facing. The reason for using the fixed point library in 0AD is to prevent OOS errors. The precision of this routine is 100% the accuracy of the routine is bounded by an error of +- 3.57deg for 5 iterations which is the way it is currently in the patch.

I've attached the patch I will attach main of the benchmarking program in a moment. I looked at the javascript maths functions but I'll need to chat with someone more experienced with javascript to know what the best way to implement this algorithm is and how to benchmark it.

I have made the constructor from specified value public in order to be able to construct a table of angles at compile time. I don't think it will create the table at compile time if I use the static FromInt method but I may be wrong.

[sanderd17]

Can you make your patch from the svn root directory? That makes it show up nicer in trac.

If you want to chat, be sure to drop by on #0ad-dev on Quakenet.

To check performance of JS code, you can use the spidermonkey stand-alone interpreter (usually the "js" command on Linux). Use +(new Date) to get the current time in milliseconds, so you can get the time difference.

In javascript, you can't access the internal value of the number.

But anyway, if you don't want to do the JS optimisations, the C++ optimisations will be welcome anyway (if they're as good as promised ;)

[Thanduel]

Sure its actually the first patch file I've ever made so I wasn't sure what the procedure was. I just realised I need to fix that patch file as well to put the types back to the 0ad standard i64 u64 etc.

[Thanduel]

patch for fixed.h and fixed.cpp with cordic version of atan2_approx

[Thanduel]

patch to replace current sincos_approx with cordic sincos approx

[Thanduel]

benchmarking project for both atan2 and sincos approximations