Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (686) Games in Android Showcase (198) games submitted by our members Games in WIP (758) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Show Posts Pages: [1]
1  Game Development / Performance Tuning / Fastest AABB collision response on: 2016-04-28 02:40:50
Let's say I have a flat 2D world of AABBs, what's the fastest way to respond to collisions in terms of computation?

Right now I build a large AABB (The black outline) by expanding the moving AABB (Red box) through adding the motion to the min/max points.

I then check what collides with that large box (The green boxes). Finally I slide the box as far as I can in each direction, one direction at a time.

Here's some example code regarding the slide:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41 `// CollisionData holds all the collisions inside of the black outline in the image// motionY is the desired offset to the entity's y position.motionPositiveMax = motionY;motionNegativeMin = motionY;for (int i = 0; i < CollisionData.size; i++) {    AxisAlignedBB collision = CollisionData.collisions[i];    // Check collision in the X axis    if (tmaxX > collision.minX && tminX < collision.maxX) {        motionPositiveMax = Math.min(motionPositiveMax, collision.minY - tmaxY);        motionNegativeMin = Math.max(motionNegativeMin, collision.maxY - tminY);    }}// Flag if motionY is positiveif (posY) {    motionNegativeMin = motionPositiveMax;}// Slide the entity's bounding box in the y axisentity.minY += motionNegativeMin;entity.maxY += motionNegativeMin;// motionX is the desired offset to the entity's x position.motionPositiveMax = motionX;motionNegativeMin = motionX;for (int i = 0; i < CollisionData.size; i++) {    AxisAlignedBB collision = CollisionData.collisions[i];    // Check collision in the Y axis    if (entity.maxY > collision.minY && entity.minY < collision.maxY) {        motionPositiveMax = Math.min(motionPositiveMax, collision.minX - tmaxX);        motionNegativeMin = Math.max(motionNegativeMin, collision.maxX - tminX);    }}// Flag if motionX is positiveif (posX) {    motionNegativeMin = motionPositiveMax;}// Slide the entity's bounding box in the x axisentity.minX += motionNegativeMin;entity.maxX += motionNegativeMin;`

For those using Swept AABB Collision http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084, this is basically the "slide" collision response, except this does significantly less work.

This method I'm using for 3D collision and it's working well. It makes a number of assumptions, such as the collisions are calculated frequently and aren't moving exceptionally fast because it's more of a best guess on when the resulting position is rather than the correct position. Worst case, such as with fast moving projectiles, ray tracing can be used instead.

I'm curious if anyone has a faster method.
 2 Game Development / Newbie & Debugging Questions / Re: What is the granularity of branching? on: 2016-04-12 15:51:23 If I chained expressions using &, then would  (a < b & c > d) be a single branch?
 3 Game Development / Newbie & Debugging Questions / What is the granularity of branching? on: 2016-04-12 15:28:51 This is a pretty dumb question, and googling gave me conflicting answers.In a if statement, say if(a < b && c > d), would this be considered 1 or 2 branches in java? I'm mainly confused on if the statement is considered a branch, or if each compare expression are branches. I understand only one gets evaluated at a time leading me to believe there are 2 branches, but I would like to be reassured by someone.
 4 Discussions / Miscellaneous Topics / Re: What I did today on: 2015-11-15 17:42:01 Managed to get openJDK to build on windows 10 and removed array bounds checks from generating to see what'll happen.There's a lot of LUT math going on server side and if I can end up with a annotation to skip bounds checks on specific arrays that can't otherwise be eliminated then I'll be pretty happy.
5  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-14 22:33:13
@theagentd / BurntPizza: use my FastFloor impl instead of (int)Math.floor(...).

 1  2  3  4  5  6 `// valid input range: -BIG_ENOUGH .. INFINITY-ishprivate static final int BIG_ENOUGH_INT = 65536; // whatever makes senseprivate static final float BIG_ENOUGH_FLOAT = BIG_ENOUGH_INT;public static int fastFloor(float x) {   return (int)(x + BIG_ENOUGH_FLOAT) - BIG_ENOUGH_INT;}`
You trade input range for accuracy.

Not a single branch, nor cache trashing lookup table

Casual reminder to make the type of
 1 `BIG_ENOUGH_FLOAT`
to double otherwise there are rounding errors.
For example, the fastFloor function returns 100 for 99.999F when using just floats.
 6 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-08-02 22:50:04 @RivenYeah, it was actually really slow to use the switch statement. I however have a different approach I think I'll try.Given these benchmarks are often unrealistic because often the array can fit in cache, why not just allocate the array offheap, get the base address / size of each element, then just use dead reckoning to pull the value. If anything it should be faster as it avoids bounds checks, Unsafe should get compiled down by the jit, and it doesn't have to load the array.
 7 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-31 04:35:15 Quote from: Roquen on 2015-07-30 13:57:54Table-lookup are almost always slow (as in much worse than using the default) in real use cases.  Especially as table sizes get large.Then we must implement the.. final solution [Sarcasm].We use a simple loop to generate the corresponding switch statement with the thousands of elements and paste it into a static method. You'll avoid bounds checking and the caching problem if it's compiled to a tableswitch. Have fun loading that monster of text in your ide though.I'll try it in the morning and see what we get, even though it sounds extremely silly. I will use icecore's method with the table set to 1000 elements.
 8 Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-07-27 22:13:02 Quote from: Riven on 2015-07-27 12:26:57Because I'm always suspicious of benchmarks written by *gasp* others... I rolled my own. There was just no way that my LUT code was 'about as fast' as some of the competition Lo and behold, the results are completely different After adding Icecore's I accidentally used your method for the test, resulting in his being just as fast as yours  ; didn't catch it until this morning. I even updated the benchmark code with the mistake in it but I guess no one caught it either. On a sidenote, I am looking into better ways to test a range of results in JMH without increasing the test time by an order of magnitude, but the results have been pretty consistent regardless.
 9 Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-07-27 02:45:56 Updated to include Icecore's version
 10 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-26 23:18:31 @klaus If you're looking for the same accuracy, Icecore's is very nice as denoted by the main post. I have the accuracy set to 100000 which warrants a max error of 0.0001 . It also performs the best.
11  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-07-26 23:04:44
 1  2  3  4 `     // Accuracy    public static void main(String[] args) {        int range = 90;`

I think range must be bigger like 9000;
For any unnatural values, who knows when function can return critical error)

Well, devmaster's critically errors past 180, but it's also only designed to function between -180 and 180. I'll up it to 180 and also provide a second one with up to 9000.
 12 Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-07-26 22:31:35 Quote from: KaiHH on 2015-07-26 16:30:01True. I tried now everything to prevent constant folding, and as I said earier on the other thread, devmaster's sine is about 2x faster than Java's. It doesn't get any better. Of course, it will be better if you do something like this: sine(1.3f) but not Math.sin(1.3f), because the code for Math.sin() cannot be constant-folded and inlined.But in the end the 2x faster is not worth the dramatic loss in precision for me.EDIT: You must also make sure that the jit is not completely eliminating the invocation of any custom sine function altogether, when being invoked in a loop. It did that for me when I just had a loop over some many million invocations and the jit completely erased the call to sine(), because it neither changed global program state nor was the result of that call being used anywhere else. That resulted in the same runtime no matter how many loop invocations there were.So I changed that invocation to increment an accumulator variable with the invocation result. And those changes then gave me 2x faster for devmaster compared to Java's Math.sin().There's a lot you have to take into account to prevent JIT and CPU magic. I've seen a number of benchmarks on this site that didn't take into consideration these problems, skewing results. It pushed me to make an account and post the atan2 comparison so that there would be some solid data on the popular function.For the original post, JMH is preventing dead code and loop optimization, the multiple values help prevent branch prediction, and the use of public variables as parameters prevents the JIT from caching the results. The lookup tables can still be sitting in the cache however, but that's pretty hard to avoid.
 13 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-26 22:04:00 Quote from: klaus on 2015-07-26 21:50:45@mooman219: Thanks for the comparison! Could you maybe add the atan2 implementation from the Apache FastMath library? http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/FastMath.html#atan2(double,%20double)It would be really interesting how this performs to the algorithms here. I'll include it in the benchmark if you would like. Results so far have it ~400 ns/op, I'll update the main post shortly.Edit: Main post is updated. It is about 1.58x faster than the default while maintaining all the accuracy. I'm assuming they had a contract to fulfill in terms of accuracy that prevented the heavy optimization that we're doing in this thread.
 14 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-26 20:07:28 I ran the benchmark with the addition of Icecore's atan2. I'll be updating the main post shortly. It appears to be in first place by a large margin.Also, I updated the accuracy measure to actually have somewhat relevant data (As opposed to me just randomly testing a couple values).
 15 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 23:28:10 Very importantMy benchmarks were flawed and the JIT was doing magic, I updated with more realistic versions. The JIT precomputed and cached the results because the parameter wasn't changing. The corrected benchmarks references a public variable instead, preventing the JIT from being able to cache the result.Riven's is the fastest, kappa is the runner up.
16  Game Development / Shared Code / Extremely Fast sine/cosine on: 2015-07-25 22:32:13
Hey all,

This is a breakout topic from the atan2 one where we started listing a number of alternate sin/cos implementations. To compare them, I setup a simple JMH benchmark and accuracy test. Criticisms and new sin/cos submissions are appreciated.

Recommended implementation with lookup table: Riven's
Recommended implementation without lookup table: FastCosSin.java posted by kappa

Warning, some of these only function within a margin such as Fast's implementation, which is intended for values between -3PI and 3PI.

Relevant data

 1  2  3  4  5  6  7  8  9  10  11  12 `     Current results:     math_default_sin   : Average Error 0.00000 / Largest Error 0.00000 - Performance 207.574 ns/op     math_devmaster_sin : Average Error 0.00050 / Largest Error 0.00109 - Performance 232.644 ns/op     math_fast_sin      : Average Error 0.02996 / Largest Error 0.05601 - Performance   8.812 ns/op     math_icecore_sin   : Average Error 0.00036 / Largest Error 0.00112 - Performance 126.611 ns/op     math_riven_sin     : Average Error 0.00060 / Largest Error 0.00224 - Performance   7.054 ns/op             math_default_cos   : Average Error 0.00000 / Largest Error 0.00000 - Performance 206.086 ns/op     math_devmaster_cos : Average Error 0.00050 / Largest Error 0.00109 - Performance 231.762 ns/op     math_fast_cos      : Average Error 0.02996 / Largest Error 0.05601 - Performance  11.096 ns/op     math_icecore_cos   : Average Error 0.00036 / Largest Error 0.00112 - Performance 126.019 ns/op     math_riven_cos     : Average Error 0.00060 / Largest Error 0.00224 - Performance   7.306 ns/op`

The raw data is provided for anyone to interpret for yourselves. The links to the original sources are provided in the comments.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258 `public class SIN {    // Example values used in the tests:    //   15 deg = 0.2617993878 rad    //   105 deg = 1.8325957146 rad    //   285 deg= 4.9741883682 rad    public float valueFloatA = 0.2617993878f;    public float valueFloatB = 1.8325957146f;    public float valueFloatC = 4.9741883682f;    public double valueDoubleA = 0.2617993878;    public double valueDoubleB = 1.8325957146;    public double valueDoubleC = 4.9741883682;    ///////////////////////////////////////    // Default sin    ///////////////////////////////////////    @Benchmark    public double math_default_sin() {        return Math.sin(valueDoubleA) + Math.sin(valueDoubleB) + Math.sin(valueDoubleC);    }    @Benchmark    public double math_default_cos() {        return Math.cos(valueDoubleA) + Math.cos(valueDoubleB) + Math.cos(valueDoubleC);    }    ///////////////////////////////////////    // FastCosSin.java posted by kappa  ( http://www.java-gaming.org/topics/extremely-fast-atan2/36467/msg/346117/view.html#msg346117 )    ///////////////////////////////////////    public static final class Fast {        private static final float PI = 3.1415927f;        private static final float MINUS_PI = -PI;        private static final float DOUBLE_PI = PI * 2f;        private static final float PI_2 = PI / 2f;        private static final float CONST_1 = 4f / PI;        private static final float CONST_2 = 4f / (PI * PI);        public static final float sin(float x) {            if (x < MINUS_PI) {                x += DOUBLE_PI;            } else if (x > PI) {                x -= DOUBLE_PI;            }            return (x < 0f) ? (CONST_1 * x + CONST_2 * x * x)                    : (CONST_1 * x - CONST_2 * x * x);        }        public static final float cos(float x) {            if (x < MINUS_PI) {                x += DOUBLE_PI;            } else if (x > PI) {                x -= DOUBLE_PI;            }            x += PI_2;            if (x > PI) {                x -= DOUBLE_PI;            }            return (x < 0f) ? (CONST_1 * x + CONST_2 * x * x)                    : (CONST_1 * x - CONST_2 * x * x);        }    }    @Benchmark    public double math_fast_sin() {        return Fast.sin(valueFloatA) + Fast.sin(valueFloatB) + Fast.sin(valueFloatC);    }    @Benchmark    public double math_fast_cos() {        return Fast.cos(valueFloatA) + Fast.cos(valueFloatB) + Fast.cos(valueFloatC);    }    ///////////////////////////////////////    // Devmaster's sine/cosine ( http://forum.devmaster.net/t/fast-and-accurate-sine-cosine/9648 )    ///////////////////////////////////////    public static final class Devmaster {        public static final float PI = 3.1415927f;        public static final float PI_2 = PI / 2f;        public static final float DOUBLE_PI = PI * 2f;        public static final float B = 4 / PI;        public static final float C = -4 / (PI * PI);        public static final float P = 0.225f;        public static final float sin(float x) {            float x1 = x % PI;            float x2 = x % DOUBLE_PI;            if (x > 0) {                float y = x1 * (B + C * x1);                y = (y > 0) ? (y = P * (y * y - y) + y)                        : (y = P * (-y * y - y) + y);                float xp = x2 - DOUBLE_PI;                if (!(xp < 0 && xp < -PI)) {                    y = -y;                }                return y;            } else {                float y = x1 * (B - C * x1);                y = (y > 0) ? (y = P * (y * y - y) + y)                        : (y = P * (-y * y - y) + y);                float xp = x2 + DOUBLE_PI;                if (xp > 0 && xp < PI) {                    y = -y;                }                return y;            }        }        public static final float cos(float x) {            float x0 = x + PI_2;            float x1 = x0 % PI;            float x2 = x0 % DOUBLE_PI;            if (x0 > 0) {                float y = x1 * (B + C * x1);                y = (y > 0) ? (y = P * (y * y - y) + y)                        : (y = P * (-y * y - y) + y);                float xp = x2 - DOUBLE_PI;                if (!(xp < 0 && xp < -PI)) {                    y = -y;                }                return y;            } else {                float y = x1 * (B - C * x1);                y = (y > 0) ? (y = P * (y * y - y) + y)                        : (y = P * (-y * y - y) + y);                float xp = x2 + DOUBLE_PI;                if (xp > 0 && xp < PI) {                    y = -y;                }                return y;            }        }    }    @Benchmark    public double math_devmaster_sin() {        return Devmaster.sin(valueFloatA) + Devmaster.sin(valueFloatB) + Devmaster.sin(valueFloatC);    }    @Benchmark    public double math_devmaster_cos() {        return Devmaster.cos(valueFloatA) + Devmaster.cos(valueFloatB) + Devmaster.cos(valueFloatC);    }    ///////////////////////////////////////    // Riven's sine/cosine ( http://www.java-gaming.org/topics/fast-math-sin-cos-lookup-tables/24191/view.html )    ///////////////////////////////////////    public static final class Riven {        private static final int SIN_BITS, SIN_MASK, SIN_COUNT;        private static final float radFull, radToIndex;        private static final float degFull, degToIndex;        private static final float[] sin, cos;        static {            SIN_BITS = 12;            SIN_MASK = ~(-1 << SIN_BITS);            SIN_COUNT = SIN_MASK + 1;            radFull = (float) (Math.PI * 2.0);            degFull = (float) (360.0);            radToIndex = SIN_COUNT / radFull;            degToIndex = SIN_COUNT / degFull;            sin = new float[SIN_COUNT];            cos = new float[SIN_COUNT];            for (int i = 0; i < SIN_COUNT; i++) {                sin[i] = (float) Math.sin((i + 0.5f) / SIN_COUNT * radFull);                cos[i] = (float) Math.cos((i + 0.5f) / SIN_COUNT * radFull);            }            // Four cardinal directions (credits: Nate)            for (int i = 0; i < 360; i += 90) {                sin[(int) (i * degToIndex) & SIN_MASK] = (float) Math.sin(i * Math.PI / 180.0);                cos[(int) (i * degToIndex) & SIN_MASK] = (float) Math.cos(i * Math.PI / 180.0);            }        }        public static final float sin(float rad) {            return sin[(int) (rad * radToIndex) & SIN_MASK];        }        public static final float cos(float rad) {            return cos[(int) (rad * radToIndex) & SIN_MASK];        }    }    @Benchmark    public double math_riven_sin() {        return Riven.sin(valueFloatA) + Riven.sin(valueFloatB) + Riven.sin(valueFloatC);    }    @Benchmark    public double math_riven_cos() {        return Riven.cos(valueFloatA) + Riven.cos(valueFloatB) + Riven.cos(valueFloatC);    }    ///////////////////////////////////////    // Icecore's sine/cosine ( http://www.java-gaming.org/topics/extremely-fast-sine-cosine/36469/msg/346190/view.html#msg346190 )    ///////////////////////////////////////    public static final class Icecore {        private static final int Size_SC_Ac = 5000;        private static final int Size_SC_Ar = Size_SC_Ac + 1;        private static final float Sin[] = new float[Size_SC_Ar];        private static final float Cos[] = new float[Size_SC_Ar];        private static final float Pi = (float) Math.PI;        private static final float Pi_D = Pi * 2;        private static final float Pi_SC_D = Pi_D / Size_SC_Ac;        static {            for (int i = 0; i < Size_SC_Ar; i++) {                double d = i * Pi_SC_D;                Sin[i] = (float) Math.sin(d);                Cos[i] = (float) Math.cos(d);            }        }        public static final float sin(float r) {            float rp = r % Pi_D;            if (rp < 0) {                rp += Pi_D;            }            return Sin[(int) (rp / Pi_SC_D)];        }        public static final float cos(float r) {            float rp = r % Pi_D;            if (rp < 0) {                rp += Pi_D;            }            return Cos[(int) (rp / Pi_SC_D)];        }    }    @Benchmark    public double math_icecore_sin() {        return Icecore.sin(valueFloatA) + Icecore.sin(valueFloatB) + Icecore.sin(valueFloatC);    }    @Benchmark    public double math_icecore_cos() {        return Icecore.cos(valueFloatA) + Icecore.cos(valueFloatB) + Icecore.cos(valueFloatC);    }}`

Accuracy

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 `    ///////////////////////////////////////    // Accuracy    ///////////////////////////////////////    public static void main(String[] args) {        int range = 180;        double[] totalCos = new double[5];        double[] totalSin = new double[5];        double[] largestErrorCos = new double[5];        double[] largestErrorSin = new double[5];        float conversion = (float) (Math.PI / 180.0f);        int count = 0;        for (int x = -range; x <= range; x++) {            float value = conversion * x;            double result;            // Cos            result = Math.abs(Math.cos(value) - Math.cos(value));            totalCos[0] += result;            largestErrorCos[0] = result > largestErrorSin[0] ? result : largestErrorCos[0];            result = Math.abs(Math.cos(value) - Devmaster.cos(value));            totalCos[1] += result;            largestErrorCos[1] = result > largestErrorCos[1] ? result : largestErrorCos[1];            result = Math.abs(Math.cos(value) - Fast.cos(value));            totalCos[2] += result;            largestErrorCos[2] = result > largestErrorCos[2] ? result : largestErrorCos[2];            result = Math.abs(Math.cos(value) - Riven.cos(value));            totalCos[3] += result;            largestErrorCos[3] = result > largestErrorCos[3] ? result : largestErrorCos[3];            result = Math.abs(Math.cos(value) - Icecore.cos(value));            totalCos[4] += result;            largestErrorCos[4] = result > largestErrorCos[4] ? result : largestErrorCos[4];            // Sin            result = Math.abs(Math.sin(value) - Math.sin(value));            totalSin[0] += result;            largestErrorSin[0] = result > largestErrorSin[0] ? result : largestErrorSin[0];            result = Math.abs(Math.sin(value) - Devmaster.sin(value));            totalSin[1] += result;            largestErrorSin[1] = result > largestErrorSin[1] ? result : largestErrorSin[1];            result = Math.abs(Math.sin(value) - Fast.sin(value));            totalSin[2] += result;            largestErrorSin[2] = result > largestErrorSin[2] ? result : largestErrorSin[2];            result = Math.abs(Math.sin(value) - Riven.sin(value));            totalSin[3] += result;            largestErrorSin[3] = result > largestErrorSin[3] ? result : largestErrorSin[3];            result = Math.abs(Math.sin(value) - Icecore.sin(value));            totalSin[4] += result;            largestErrorSin[4] = result > largestErrorSin[4] ? result : largestErrorSin[4];            count++;        }        System.out.println(String.format("A lower average means higher accuracy. Results over %,d samples.", count));        // Cos        System.out.println(String.format("math_default_cos   : Average Error %.5f / Largest Error %.5f", totalCos[0] / count, largestErrorCos[0]));        System.out.println(String.format("math_devmaster_cos : Average Error %.5f / Largest Error %.5f", totalCos[1] / count, largestErrorCos[1]));        System.out.println(String.format("math_fast_cos      : Average Error %.5f / Largest Error %.5f", totalCos[2] / count, largestErrorCos[2]));        System.out.println(String.format("math_icecore_cos   : Average Error %.5f / Largest Error %.5f", totalCos[4] / count, largestErrorCos[4]));        System.out.println(String.format("math_riven_cos     : Average Error %.5f / Largest Error %.5f", totalCos[3] / count, largestErrorCos[3]));        // Sin        System.out.println(String.format("math_default_sin   : Average Error %.5f / Largest Error %.5f", totalSin[0] / count, largestErrorSin[0]));        System.out.println(String.format("math_devmaster_sin : Average Error %.5f / Largest Error %.5f", totalSin[1] / count, largestErrorSin[1]));        System.out.println(String.format("math_fast_sin      : Average Error %.5f / Largest Error %.5f", totalSin[2] / count, largestErrorSin[2]));        System.out.println(String.format("math_icecore_sin   : Average Error %.5f / Largest Error %.5f", totalSin[4] / count, largestErrorSin[4]));        System.out.println(String.format("math_riven_sin     : Average Error %.5f / Largest Error %.5f", totalSin[3] / count, largestErrorSin[3]));        /*         Range of 180         A lower average means higher accuracy. Results over 361 samples.         math_default_cos   : Average Error 0.00000 / Largest Error 0.00000         math_devmaster_cos : Average Error 0.00050 / Largest Error 0.00109         math_fast_cos      : Average Error 0.02996 / Largest Error 0.05601         math_icecore_cos   : Average Error 0.00036 / Largest Error 0.00112         math_riven_cos     : Average Error 0.00060 / Largest Error 0.00224                 math_default_sin   : Average Error 0.00000 / Largest Error 0.00000         math_devmaster_sin : Average Error 0.00050 / Largest Error 0.00109         math_fast_sin      : Average Error 0.02996 / Largest Error 0.05601         math_icecore_sin   : Average Error 0.00036 / Largest Error 0.00112         math_riven_sin     : Average Error 0.00060 / Largest Error 0.00224                 Range of 10000         A lower average means higher accuracy. Results over 20,001 samples.         math_default_cos   : Average Error 0.00000 / Largest Error 0.00000         math_devmaster_cos : Average Error 0.00051 / Largest Error 0.00110         math_fast_cos      : Average Error 3385.79416 / Largest Error 11047.17010 !!! Test goes outside of intended range         math_icecore_cos   : Average Error 0.00040 / Largest Error 0.00126         math_riven_cos     : Average Error 0.00061 / Largest Error 0.00230                 math_default_sin   : Average Error 0.00000 / Largest Error 0.00000         math_devmaster_sin : Average Error 0.00050 / Largest Error 0.00110         math_fast_sin      : Average Error 3583.72491 / Largest Error 11257.58258 !!! Test goes outside of intended range         math_icecore_sin   : Average Error 0.00039 / Largest Error 0.00126         math_riven_sin     : Average Error 0.00061 / Largest Error 0.00230         */    }`

Benchmark results

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290  291  292  293  294  295  296  297  298  299  300  301  302  303  304  305  306  307  308  309  310  311  312  313 `# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_default_cos# Run progress: 0.00% complete, ETA 00:01:40# Fork: 1 of 1# Warmup Iteration   1: 210.988 ns/op# Warmup Iteration   2: 205.902 ns/op# Warmup Iteration   3: 207.415 ns/op# Warmup Iteration   4: 207.827 ns/op# Warmup Iteration   5: 204.809 ns/opIteration   1: 204.567 ns/opIteration   2: 204.636 ns/opIteration   3: 209.536 ns/opIteration   4: 206.779 ns/opIteration   5: 204.910 ns/opResult "math_default_cos":  206.086 ñ(99.9%) 8.208 ns/op [Average]  (min, avg, max) = (204.567, 206.086, 209.536), stdev = 2.132  CI (99.9%): [197.878, 214.293] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_default_sin# Run progress: 10.00% complete, ETA 00:01:33# Fork: 1 of 1# Warmup Iteration   1: 207.585 ns/op# Warmup Iteration   2: 206.643 ns/op# Warmup Iteration   3: 212.465 ns/op# Warmup Iteration   4: 209.597 ns/op# Warmup Iteration   5: 207.192 ns/opIteration   1: 206.839 ns/opIteration   2: 206.776 ns/opIteration   3: 209.633 ns/opIteration   4: 206.813 ns/opIteration   5: 207.809 ns/opResult "math_default_sin":  207.574 ñ(99.9%) 4.736 ns/op [Average]  (min, avg, max) = (206.776, 207.574, 209.633), stdev = 1.230  CI (99.9%): [202.838, 212.310] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_devmaster_cos# Run progress: 20.00% complete, ETA 00:01:23# Fork: 1 of 1# Warmup Iteration   1: 231.947 ns/op# Warmup Iteration   2: 232.759 ns/op# Warmup Iteration   3: 233.528 ns/op# Warmup Iteration   4: 232.575 ns/op# Warmup Iteration   5: 230.663 ns/opIteration   1: 231.842 ns/opIteration   2: 232.178 ns/opIteration   3: 233.663 ns/opIteration   4: 230.563 ns/opIteration   5: 230.563 ns/opResult "math_devmaster_cos":  231.762 ñ(99.9%) 4.972 ns/op [Average]  (min, avg, max) = (230.563, 231.762, 233.663), stdev = 1.291  CI (99.9%): [226.790, 236.734] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_devmaster_sin# Run progress: 30.00% complete, ETA 00:01:12# Fork: 1 of 1# Warmup Iteration   1: 230.069 ns/op# Warmup Iteration   2: 229.269 ns/op# Warmup Iteration   3: 234.922 ns/op# Warmup Iteration   4: 230.136 ns/op# Warmup Iteration   5: 232.788 ns/opIteration   1: 230.068 ns/opIteration   2: 230.098 ns/opIteration   3: 235.049 ns/opIteration   4: 237.674 ns/opIteration   5: 230.333 ns/opResult "math_devmaster_sin":  232.644 ñ(99.9%) 13.552 ns/op [Average]  (min, avg, max) = (230.068, 232.644, 237.674), stdev = 3.519  CI (99.9%): [219.093, 246.196] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_fast_cos# Run progress: 40.00% complete, ETA 00:01:02# Fork: 1 of 1# Warmup Iteration   1: 11.612 ns/op# Warmup Iteration   2: 11.429 ns/op# Warmup Iteration   3: 11.423 ns/op# Warmup Iteration   4: 10.993 ns/op# Warmup Iteration   5: 11.219 ns/opIteration   1: 10.976 ns/opIteration   2: 10.966 ns/opIteration   3: 11.295 ns/opIteration   4: 11.272 ns/opIteration   5: 10.972 ns/opResult "math_fast_cos":  11.096 ñ(99.9%) 0.658 ns/op [Average]  (min, avg, max) = (10.966, 11.096, 11.295), stdev = 0.171  CI (99.9%): [10.438, 11.755] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_fast_sin# Run progress: 50.00% complete, ETA 00:00:51# Fork: 1 of 1# Warmup Iteration   1: 9.646 ns/op# Warmup Iteration   2: 9.421 ns/op# Warmup Iteration   3: 8.971 ns/op# Warmup Iteration   4: 8.905 ns/op# Warmup Iteration   5: 8.778 ns/opIteration   1: 8.794 ns/opIteration   2: 8.839 ns/opIteration   3: 9.057 ns/opIteration   4: 8.685 ns/opIteration   5: 8.686 ns/opResult "math_fast_sin":  8.812 ñ(99.9%) 0.587 ns/op [Average]  (min, avg, max) = (8.685, 8.812, 9.057), stdev = 0.153  CI (99.9%): [8.225, 9.399] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_icecore_cos# Run progress: 60.00% complete, ETA 00:00:41# Fork: 1 of 1# Warmup Iteration   1: 126.369 ns/op# Warmup Iteration   2: 124.888 ns/op# Warmup Iteration   3: 127.466 ns/op# Warmup Iteration   4: 125.693 ns/op# Warmup Iteration   5: 126.229 ns/opIteration   1: 125.641 ns/opIteration   2: 125.819 ns/opIteration   3: 127.509 ns/opIteration   4: 125.537 ns/opIteration   5: 125.587 ns/opResult "math_icecore_cos":  126.019 ñ(99.9%) 3.234 ns/op [Average]  (min, avg, max) = (125.537, 126.019, 127.509), stdev = 0.840  CI (99.9%): [122.785, 129.253] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_icecore_sin# Run progress: 70.00% complete, ETA 00:00:31# Fork: 1 of 1# Warmup Iteration   1: 126.271 ns/op# Warmup Iteration   2: 124.888 ns/op# Warmup Iteration   3: 127.539 ns/op# Warmup Iteration   4: 125.718 ns/op# Warmup Iteration   5: 125.784 ns/opIteration   1: 125.551 ns/opIteration   2: 126.679 ns/opIteration   3: 127.568 ns/opIteration   4: 127.394 ns/opIteration   5: 125.862 ns/opResult "math_icecore_sin":  126.611 ñ(99.9%) 3.454 ns/op [Average]  (min, avg, max) = (125.551, 126.611, 127.568), stdev = 0.897  CI (99.9%): [123.157, 130.065] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_riven_cos# Run progress: 80.00% complete, ETA 00:00:20# Fork: 1 of 1# Warmup Iteration   1: 7.710 ns/op# Warmup Iteration   2: 7.779 ns/op# Warmup Iteration   3: 7.438 ns/op# Warmup Iteration   4: 7.180 ns/op# Warmup Iteration   5: 7.324 ns/opIteration   1: 7.320 ns/opIteration   2: 7.315 ns/opIteration   3: 7.411 ns/opIteration   4: 7.172 ns/opIteration   5: 7.314 ns/opResult "math_riven_cos":  7.306 ñ(99.9%) 0.330 ns/op [Average]  (min, avg, max) = (7.172, 7.306, 7.411), stdev = 0.086  CI (99.9%): [6.976, 7.636] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.SIN.math_riven_sin# Run progress: 90.00% complete, ETA 00:00:10# Fork: 1 of 1# Warmup Iteration   1: 7.652 ns/op# Warmup Iteration   2: 7.808 ns/op# Warmup Iteration   3: 7.112 ns/op# Warmup Iteration   4: 7.011 ns/op# Warmup Iteration   5: 7.024 ns/opIteration   1: 7.121 ns/opIteration   2: 7.016 ns/opIteration   3: 7.112 ns/opIteration   4: 7.000 ns/opIteration   5: 7.021 ns/opResult "math_riven_sin":  7.054 ñ(99.9%) 0.223 ns/op [Average]  (min, avg, max) = (7.000, 7.054, 7.121), stdev = 0.058  CI (99.9%): [6.831, 7.276] (assumes normal distribution)# Run complete. Total time: 00:01:43Benchmark               Mode  Cnt    Score    Error  UnitsSIN.math_default_cos    avgt    5  206.086 ñ  8.208  ns/opSIN.math_default_sin    avgt    5  207.574 ñ  4.736  ns/opSIN.math_devmaster_cos  avgt    5  231.762 ñ  4.972  ns/opSIN.math_devmaster_sin  avgt    5  232.644 ñ 13.552  ns/opSIN.math_fast_cos       avgt    5   11.096 ñ  0.658  ns/opSIN.math_fast_sin       avgt    5    8.812 ñ  0.587  ns/opSIN.math_icecore_cos    avgt    5  126.019 ñ  3.234  ns/opSIN.math_icecore_sin    avgt    5  126.611 ñ  3.454  ns/opSIN.math_riven_cos      avgt    5    7.306 ñ  0.330  ns/opSIN.math_riven_sin      avgt    5    7.054 ñ  0.223  ns/op`

Keep in mind these are micro benchmarks and not indicative of real world performance; the JMH can only do so much to make sure the JIT doesn't interfere. There may be a fair amount of branch prediction and caching that's going on. For example, the lookup table in Riven's implementation might just be sitting in a cpu cache.
 17 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 22:13:24 I'll put together a benchmark for sin/cos real quick with the two versions you guys posted and then break out into a new topic for sin/cos specifically probably.As with the original post, I'll post the benchmark code, the accuracy through some random tests, and the performance report.Edit: Removed the benchmark code because it would be troublesome to keep it updated in two places. I moved it to http://www.java-gaming.org/topics/extremely-fast-sine-cosine/36469/view.html
 18 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 20:54:08 This post is turning into a repository for atan2 implementations haha.Kappa's version was added and it's very fast as well, testing only about 10% slower than the dsp version, which at ~3ns is pretty negligible.
 19 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 20:42:00 I'll add that into the JMH and update the results. Should be a couple of minutes to run.Edit: Kappa's version was added to the benchmark.
 20 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 20:31:33 That sounds great KaiHH! Do you think you could post a comparison with Riven's in there too? That one is also quite fast too and I would like to see how dsp's version holds up.
 21 Game Development / Shared Code / Re: Extremely Fast atan2 on: 2015-07-25 19:47:18 Yeah, that's pretty unreasonable error, so I have updated the original post with a more accurate version. The faster version was within ~0.07 radians. The new version I just added is within ~0.01 radians which should be acceptable in most cases. The benchmark/error/results have been updated to reflect this new addition. Given it's just a couple of more multiplications, there doesn't seem to be a performance difference between the accurate and faster version when using JMH. I suspect the minor difference would only matter on embedded devices meant for digital signal processing (What the original C implementation was targeting).
22  Game Development / Shared Code / Extremely Fast atan2 on: 2015-07-25 16:38:45
Hello,

I've just been looking around for a faster way to do Math.atan2(y,x) and I came across a number of methods. To compare them, I setup a simple JMH benchmark and accuracy test. Criticisms and new atan2 submissions are appreciated.

Recommended implementation with lookup table: Icecore's
Recommended implementation without lookup table: Kappa's

Relevant data

 1  2  3  4  5  6  7  8 `     Current results:     apache_atan2   : Average Error 0.00000 / Largest Error 0.00000 - Performance 367.945 ns/op     default_atan2  : Average Error 0.00000 / Largest Error 0.00000 - Performance 579.170 ns/op     DSP.atan2_acc  : Average Error 0.00344 / Largest Error 1.57079 - Performance  64.812 ns/op     DSP.atan2_fast : Average Error 0.04318 / Largest Error 1.57080 - Performance  51.691 ns/op     Icecore.atan2  : Average Error 0.00004 / Largest Error 0.00010 - Performance  27.291 ns/op     Kappa.atan2    : Average Error 0.00231 / Largest Error 0.00488 - Performance  38.766 ns/op     Riven.atan2    : Average Error 0.00288 / Largest Error 0.00787 - Performance  36.640 ns/op`

I posted the raw data below for anyone to interpret for yourselves. The links to the original sources are provided in the comments.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220  221  222  223  224  225  226  227  228  229  230  231  232  233  234  235  236  237  238  239  240  241  242  243  244  245  246  247  248  249  250  251  252  253  254  255  256  257  258  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287 `public class ATAN2 {    // Values declared above to avoid the JIT from inlining    public static int nTen = -10;    public static int nFour = -4;    public static int nTwo = -2;    public static int nOne = -1;    public static int pOne = 1;    public static int pThree = 3;    public static int pFour = 4;    public static int pNine = 9;    ///////////////////////////////////////    // Default atan2    ///////////////////////////////////////    @Benchmark    public double math_default() {        return Math.atan2(pThree, pFour) + Math.atan2(nTwo, pOne) + Math.atan2(nFour, nOne) + Math.atan2(pNine, nTen);    }    ///////////////////////////////////////    // Riven's atan2 ( http://www.java-gaming.org/index.php?topic=14647.0 )    ///////////////////////////////////////    public static final class Riven {        private static final int ATAN2_BITS = 7;        private static final int ATAN2_BITS2 = ATAN2_BITS << 1;        private static final int ATAN2_MASK = ~(-1 << ATAN2_BITS2);        private static final int ATAN2_COUNT = ATAN2_MASK + 1;        private static final int ATAN2_DIM = (int) Math.sqrt(ATAN2_COUNT);        private static final float INV_ATAN2_DIM_MINUS_1 = 1.0f / (ATAN2_DIM - 1);        private static final float[] atan2 = new float[ATAN2_COUNT];        static {            for (int i = 0; i < ATAN2_DIM; i++) {                for (int j = 0; j < ATAN2_DIM; j++) {                    float x0 = (float) i / ATAN2_DIM;                    float y0 = (float) j / ATAN2_DIM;                    atan2[j * ATAN2_DIM + i] = (float) Math.atan2(y0, x0);                }            }        }        public static final float atan2(float y, float x) {            float add, mul;            if (x < 0.0f) {                if (y < 0.0f) {                    x = -x;                    y = -y;                    mul = 1.0f;                } else {                    x = -x;                    mul = -1.0f;                }                add = -3.141592653f;            } else {                if (y < 0.0f) {                    y = -y;                    mul = -1.0f;                } else {                    mul = 1.0f;                }                add = 0.0f;            }            float invDiv = 1.0f / (((x < y) ? y : x) * INV_ATAN2_DIM_MINUS_1);            int xi = (int) (x * invDiv);            int yi = (int) (y * invDiv);            return (atan2[yi * ATAN2_DIM + xi] + add) * mul;        }    }    @Benchmark    public double math_riven() {        return Riven.atan2(pThree, pFour) + Riven.atan2(nTwo, pOne) + Riven.atan2(nFour, nOne) + Riven.atan2(pNine, nTen);    }    ///////////////////////////////////////    // DSP's atan2 ( http://dspguru.com/dsp/tricks/fixed-point-atan2-with-self-normalization )    ///////////////////////////////////////    public static final class DSP {        private static final double coeff_1 = Math.PI / 4;        private static final double coeff_2 = coeff_1 * 3;        public static final double atan2_fast(double y, double x) {            double r;            if (y < 0) {                y = -y;                if (x > 0) {                    r = (x - y) / (x + y);                    return -(coeff_1 - coeff_1 * r);                } else {                    r = (x + y) / (y - x);                    return -(coeff_2 - coeff_1 * r);                }            } else {                if (y == 0) {                    y = 1.0E-25;                }                if (x > 0) {                    r = (x - y) / (x + y);                    return coeff_1 - coeff_1 * r;                } else {                    r = (x + y) / (y - x);                    return coeff_2 - coeff_1 * r;                }            }        }        public static final double atan2_accurate(double y, double x) {            double r;            if (y < 0) {                y = -y;                if (x > 0) {                    r = (x - y) / (x + y);                    return -(0.1963 * r * r * r - 0.9817 * r + coeff_1);                } else {                    r = (x + y) / (y - x);                    return -(0.1963 * r * r * r - 0.9817 * r + coeff_2);                }            } else {                if (y == 0) {                    y = 1.0E-25;                }                if (x > 0) {                    r = (x - y) / (x + y);                    return 0.1963 * r * r * r - 0.9817 * r + coeff_1;                } else {                    r = (x + y) / (y - x);                    return 0.1963 * r * r * r - 0.9817 * r + coeff_2;                }            }        }    }    @Benchmark    public double math_dsp_fast() {        return DSP.atan2_fast(pThree, pFour) + DSP.atan2_fast(nTwo, pOne) + DSP.atan2_fast(nFour, nOne) + DSP.atan2_fast(pNine, nTen);    }    @Benchmark    public double math_dsp_accurate() {        return DSP.atan2_accurate(pThree, pFour) + DSP.atan2_accurate(nTwo, pOne) + DSP.atan2_accurate(nFour, nOne) + DSP.atan2_accurate(pNine, nTen);    }    ///////////////////////////////////////    // kappa's atan2 ( http://www.java-gaming.org/topics/extremely-fast-atan2/36467/msg/346112/view.html#msg346112 )    ///////////////////////////////////////    public static final class Kappa {        static final float PI = 3.1415927f;        static final float PI_2 = PI / 2f;        static final float MINUS_PI_2 = -PI_2;        public static final float atan2(float y, float x) {            if (x == 0.0f) {                if (y > 0.0f) {                    return PI_2;                }                if (y == 0.0f) {                    return 0.0f;                }                return MINUS_PI_2;            }            final float atan;            final float z = y / x;            if (Math.abs(z) < 1.0f) {                atan = z / (1.0f + 0.28f * z * z);                if (x < 0.0f) {                    return (y < 0.0f) ? atan - PI : atan + PI;                }                return atan;            } else {                atan = PI_2 - z / (z * z + 0.28f);                return (y < 0.0f) ? atan - PI : atan;            }        }    }    @Benchmark    public double math_kappa() {        return Kappa.atan2(pThree, pFour) + Kappa.atan2(nTwo, pOne) + Kappa.atan2(nFour, nOne) + Kappa.atan2(pNine, nTen);    }    ///////////////////////////////////////    // Icecore's atan2 ( http://www.java-gaming.org/topics/extremely-fast-atan2/36467/msg/346145/view.html#msg346145 )    ///////////////////////////////////////    public static final class Icecore {        private static final int Size_Ac = 100000;        private static final int Size_Ar = Size_Ac + 1;        private static final float Pi = (float) Math.PI;        private static final float Pi_H = Pi / 2;        private static final float Atan2[] = new float[Size_Ar];        private static final float Atan2_PM[] = new float[Size_Ar];        private static final float Atan2_MP[] = new float[Size_Ar];        private static final float Atan2_MM[] = new float[Size_Ar];        private static final float Atan2_R[] = new float[Size_Ar];        private static final float Atan2_RPM[] = new float[Size_Ar];        private static final float Atan2_RMP[] = new float[Size_Ar];        private static final float Atan2_RMM[] = new float[Size_Ar];        static {            for (int i = 0; i <= Size_Ac; i++) {                double d = (double) i / Size_Ac;                double x = 1;                double y = x * d;                float v = (float) Math.atan2(y, x);                Atan2[i] = v;                Atan2_PM[i] = Pi - v;                Atan2_MP[i] = -v;                Atan2_MM[i] = -Pi + v;                Atan2_R[i] = Pi_H - v;                Atan2_RPM[i] = Pi_H + v;                Atan2_RMP[i] = -Pi_H + v;                Atan2_RMM[i] = -Pi_H - v;            }        }        public static final float atan2(float y, float x) {            if (y < 0) {                if (x < 0) {                    //(y < x) because == (-y > -x)                    if (y < x) {                        return Atan2_RMM[(int) (x / y * Size_Ac)];                    } else {                        return Atan2_MM[(int) (y / x * Size_Ac)];                    }                } else {                    y = -y;                    if (y > x) {                        return Atan2_RMP[(int) (x / y * Size_Ac)];                    } else {                        return Atan2_MP[(int) (y / x * Size_Ac)];                    }                }            } else {                if (x < 0) {                    x = -x;                    if (y > x) {                        return Atan2_RPM[(int) (x / y * Size_Ac)];                    } else {                        return Atan2_PM[(int) (y / x * Size_Ac)];                    }                } else {                    if (y > x) {                        return Atan2_R[(int) (x / y * Size_Ac)];                    } else {                        return Atan2[(int) (y / x * Size_Ac)];                    }                }            }        }    }    @Benchmark    public double math_icecore() {        return Icecore.atan2(pThree, pFour) + Icecore.atan2(nTwo, pOne) + Icecore.atan2(nFour, nOne) + Icecore.atan2(pNine, nTen);    }    ///////////////////////////////////////    // Apache's FastMath.atan2 ( http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/FastMath.html )    ///////////////////////////////////////    @Benchmark    public double math_apache() {        return FastMath.atan2(pThree, pFour) + FastMath.atan2(nTwo, pOne) + FastMath.atan2(nFour, nOne) + FastMath.atan2(pNine, nTen);    }}`

Accuracy

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64 `    ///////////////////////////////////////    // Accuracy    ///////////////////////////////////////    public static void main(String[] args) {        int range = 1500;        double[] total = new double[7];        double[] largestError = new double[7];        int count = 0;        for (int y = -range; y <= range; y++) {            for (int x = -range; x <= range; x++) {                double result;                result = Math.abs(Math.atan2(y, x) - Math.atan2(y, x));                total[0] += result;                largestError[0] = result > largestError[0] ? result : largestError[0];                result = Math.abs(Math.atan2(y, x) - DSP.atan2_accurate(y, x));                total[1] += result;                largestError[1] = result > largestError[1] ? result : largestError[1];                result = Math.abs(Math.atan2(y, x) - DSP.atan2_fast(y, x));                total[2] += result;                largestError[2] = result > largestError[2] ? result : largestError[2];                result = Math.abs(Math.atan2(y, x) - Icecore.atan2(y, x));                total[3] += result;                largestError[3] = result > largestError[3] ? result : largestError[3];                result = Math.abs(Math.atan2(y, x) - Kappa.atan2(y, x));                total[4] += result;                largestError[4] = result > largestError[4] ? result : largestError[4];                result = Math.abs(Math.atan2(y, x) - Riven.atan2(y, x));                total[5] += result;                largestError[5] = result > largestError[5] ? result : largestError[5];                result = Math.abs(Math.atan2(y, x) - FastMath.atan2(y, x));                total[6] += result;                largestError[6] = result > largestError[6] ? result : largestError[6];                count++;            }        }        System.out.println(String.format("A lower average means higher accuracy. Results over %,d samples.", count));        System.out.println(String.format("apache_atan2   : Average Error %.5f / Largest Error %.5f", total[6] / count, largestError[6]));        System.out.println(String.format("default_atan2  : Average Error %.5f / Largest Error %.5f", total[0] / count, largestError[0]));        System.out.println(String.format("DSP.atan2_acc  : Average Error %.5f / Largest Error %.5f", total[1] / count, largestError[1]));        System.out.println(String.format("DSP.atan2_fast : Average Error %.5f / Largest Error %.5f", total[2] / count, largestError[2]));        System.out.println(String.format("Icecore.atan2  : Average Error %.5f / Largest Error %.5f", total[3] / count, largestError[3]));        System.out.println(String.format("Kappa.atan2    : Average Error %.5f / Largest Error %.5f", total[4] / count, largestError[4]));        System.out.println(String.format("Riven.atan2    : Average Error %.5f / Largest Error %.5f", total[5] / count, largestError[5]));        /*         A lower average means higher accuracy. Results over 9,006,001 samples.         apache_atan2   : Average Error 0.00000 / Largest Error 0.00000         default_atan2  : Average Error 0.00000 / Largest Error 0.00000         DSP.atan2_acc  : Average Error 0.00344 / Largest Error 1.57079         DSP.atan2_fast : Average Error 0.04318 / Largest Error 1.57080         Icecore.atan2  : Average Error 0.00000 / Largest Error 0.00001         Kappa.atan2    : Average Error 0.00231 / Largest Error 0.00488         Riven.atan2    : Average Error 0.00288 / Largest Error 0.00787         */    }`

Benchmark results

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  201  202  203  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  219  220 `# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_apache# Run progress: 0.00% complete, ETA 00:01:10# Fork: 1 of 1# Warmup Iteration   1: 374.275 ns/op# Warmup Iteration   2: 372.820 ns/op# Warmup Iteration   3: 369.142 ns/op# Warmup Iteration   4: 368.814 ns/op# Warmup Iteration   5: 367.294 ns/opIteration   1: 366.987 ns/opIteration   2: 371.812 ns/opIteration   3: 366.907 ns/opIteration   4: 366.877 ns/opIteration   5: 367.142 ns/opResult "math_apache":  367.945 ñ(99.9%) 8.334 ns/op [Average]  (min, avg, max) = (366.877, 367.945, 371.812), stdev = 2.164  CI (99.9%): [359.611, 376.279] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_default# Run progress: 14.29% complete, ETA 00:01:02# Fork: 1 of 1# Warmup Iteration   1: 590.515 ns/op# Warmup Iteration   2: 585.678 ns/op# Warmup Iteration   3: 578.451 ns/op# Warmup Iteration   4: 577.610 ns/op# Warmup Iteration   5: 578.103 ns/opIteration   1: 577.544 ns/opIteration   2: 585.795 ns/opIteration   3: 577.450 ns/opIteration   4: 577.399 ns/opIteration   5: 577.663 ns/opResult "math_default":  579.170 ñ(99.9%) 14.266 ns/op [Average]  (min, avg, max) = (577.399, 579.170, 585.795), stdev = 3.705  CI (99.9%): [564.904, 593.437] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_dsp_accurate# Run progress: 28.57% complete, ETA 00:00:51# Fork: 1 of 1# Warmup Iteration   1: 66.682 ns/op# Warmup Iteration   2: 65.408 ns/op# Warmup Iteration   3: 64.661 ns/op# Warmup Iteration   4: 64.637 ns/op# Warmup Iteration   5: 64.707 ns/opIteration   1: 64.645 ns/opIteration   2: 65.505 ns/opIteration   3: 64.629 ns/opIteration   4: 64.631 ns/opIteration   5: 64.652 ns/opResult "math_dsp_accurate":  64.812 ñ(99.9%) 1.492 ns/op [Average]  (min, avg, max) = (64.629, 64.812, 65.505), stdev = 0.387  CI (99.9%): [63.320, 66.304] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_dsp_fast# Run progress: 42.86% complete, ETA 00:00:41# Fork: 1 of 1# Warmup Iteration   1: 52.145 ns/op# Warmup Iteration   2: 51.808 ns/op# Warmup Iteration   3: 51.245 ns/op# Warmup Iteration   4: 51.228 ns/op# Warmup Iteration   5: 51.298 ns/opIteration   1: 51.269 ns/opIteration   2: 52.402 ns/opIteration   3: 51.282 ns/opIteration   4: 51.425 ns/opIteration   5: 52.078 ns/opResult "math_dsp_fast":  51.691 ñ(99.9%) 1.993 ns/op [Average]  (min, avg, max) = (51.269, 51.691, 52.402), stdev = 0.518  CI (99.9%): [49.698, 53.684] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_icecore# Run progress: 57.14% complete, ETA 00:00:31# Fork: 1 of 1# Warmup Iteration   1: 44.693 ns/op# Warmup Iteration   2: 28.011 ns/op# Warmup Iteration   3: 27.220 ns/op# Warmup Iteration   4: 27.225 ns/op# Warmup Iteration   5: 27.249 ns/opIteration   1: 27.204 ns/opIteration   2: 27.599 ns/opIteration   3: 27.220 ns/opIteration   4: 27.212 ns/opIteration   5: 27.221 ns/opResult "math_icecore":  27.291 ñ(99.9%) 0.663 ns/op [Average]  (min, avg, max) = (27.204, 27.291, 27.599), stdev = 0.172  CI (99.9%): [26.628, 27.955] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_kappa# Run progress: 71.43% complete, ETA 00:00:20# Fork: 1 of 1# Warmup Iteration   1: 40.813 ns/op# Warmup Iteration   2: 40.480 ns/op# Warmup Iteration   3: 38.620 ns/op# Warmup Iteration   4: 38.945 ns/op# Warmup Iteration   5: 38.653 ns/opIteration   1: 38.622 ns/opIteration   2: 39.381 ns/opIteration   3: 38.611 ns/opIteration   4: 38.615 ns/opIteration   5: 38.600 ns/opResult "math_kappa":  38.766 ñ(99.9%) 1.325 ns/op [Average]  (min, avg, max) = (38.600, 38.766, 39.381), stdev = 0.344  CI (99.9%): [37.441, 40.090] (assumes normal distribution)# JMH 1.9.3 (released 73 days ago)# VM invoker: C:\Program Files\Java\jdk1.8.0_45\jre\bin\java.exe# VM options: # Warmup: 5 iterations, 1 s each# Measurement: 5 iterations, 1 s each# Timeout: 10 min per iteration# Threads: 1 thread, will synchronize iterations# Benchmark mode: Average time, time/op# Benchmark: com.gmail.mooman219.benchmark_test.ATAN2.math_riven# Run progress: 85.71% complete, ETA 00:00:10# Fork: 1 of 1# Warmup Iteration   1: 45.780 ns/op# Warmup Iteration   2: 40.609 ns/op# Warmup Iteration   3: 36.467 ns/op# Warmup Iteration   4: 36.467 ns/op# Warmup Iteration   5: 36.502 ns/opIteration   1: 36.458 ns/opIteration   2: 37.000 ns/opIteration   3: 36.473 ns/opIteration   4: 36.435 ns/opIteration   5: 36.836 ns/opResult "math_riven":  36.640 ñ(99.9%) 1.002 ns/op [Average]  (min, avg, max) = (36.435, 36.640, 37.000), stdev = 0.260  CI (99.9%): [35.638, 37.643] (assumes normal distribution)# Run complete. Total time: 00:01:12Benchmark                Mode  Cnt    Score    Error  UnitsATAN2.math_apache        avgt    5  367.945 ñ  8.334  ns/opATAN2.math_default       avgt    5  579.170 ñ 14.266  ns/opATAN2.math_dsp_accurate  avgt    5   64.812 ñ  1.492  ns/opATAN2.math_dsp_fast      avgt    5   51.691 ñ  1.993  ns/opATAN2.math_icecore       avgt    5   27.291 ñ  0.663  ns/opATAN2.math_kappa         avgt    5   38.766 ñ  1.325  ns/opATAN2.math_riven         avgt    5   36.640 ñ  1.002  ns/op`

Keep in mind these are micro benchmarks and not indicative of real world performance; the JMH can only do so much to make sure the JIT doesn't interfere. There may be a fair amount of branch prediction and caching that's going on. For example, the lookup table in Riven's atan2 implementation might just be sitting in a cpu cache.
 23 Game Development / Newbie & Debugging Questions / Re: 2D Overlay lwjgl on: 2012-06-06 22:44:05 I did what you told me to do.It works great, and is simple. Thank you very much for your help !!!!!
 24 Game Development / Newbie & Debugging Questions / (Solved) 2D Overlay lwjgl on: 2012-06-06 22:21:24 How would I overlay an object on the screen so that when I use glVertex2i(x, y);, it is in relation to the screen and not the translation.Right now I am using glTranslatef to move the screen around, so when I decided to attempt to make a gui that overlays over the screen, I realized that the gui would also be translated. Of which I do not want.
 Pages: [1]
 roseslayer (510 views) 2016-08-06 11:43:29 roseslayer (468 views) 2016-08-06 09:43:11 xTheGamerCodes (542 views) 2016-08-04 15:40:59 xTheGamerCodes (537 views) 2016-08-04 15:40:24 orrenravid (882 views) 2016-07-16 03:57:23 theagentd (960 views) 2016-07-11 14:28:54 Hydroque (1056 views) 2016-07-06 05:56:57 Hydroque (1038 views) 2016-07-03 08:52:54 GrandCastle (852 views) 2016-07-01 09:13:47 GrandCastle (644 views) 2016-07-01 09:09:45
 Archive 47x Ecumene 24x Spasi 24x theagentd 23x orange451 15x gouessej 14x DarkCart 14x EgonOlsen 13x h.pernpeintner 12x ags1 12x admin 10x Riven 10x philjord 9x TheMeatMan 8x Brynn 8x thechrisizeful 7x
 Rendering resourcesby Roquen2016-08-08 05:55:21Rendering resourcesby Roquen2016-08-08 05:52:42Rendering resourcesby Roquen2016-08-08 05:50:38Rendering resourcesby Roquen2016-08-08 05:49:53Rendering resourcesby Roquen2016-08-08 05:32:39Making a Dynamic Plugin Systemby Hydroque2016-06-25 00:13:25Java Data structures2016-06-13 21:22:09Java Data structures2016-06-13 21:20:42
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org