Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspxThese days most people represent angles using degrees or radians, but many old-skool game programmers preferred a binary integer format where a full circle is 65536. To convert: short ToBinary( float degrees)
{
return ( short )(degrees * 65536 / 360enTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#10200069Thu, 25 Aug 2011 01:04:15 GMT91d46819-8472-40ad-a661-2c78acb4018c:10200069Ken Clement<p>Shawn,</p>
<p>I agree with your analysis of Cardin's comments. I have done more than a little simulation software that dealt calculations involving changing angles. Using the scaled binary angle approach (BAMs/BRADs) greatly simplified my code and eliminated boundary conditions that were always a plague.</p>
<p>Additionally, they forgave a multitude of sins.</p>
<p>Not only did I no longer have to worry about normalizing my angles with every computation, I no longer had to worry about HOW to normalize them. The two most common normalization ranges are [0,360) and [-180,+180). Either can be realized without any computation at all. The first is realized by interpreting the stored integer as an unsigned integer with no sign bit. The second is realized by interpreting the stored integer as a twos-complement signed integer with the traditional sign bit being the high order bit. Conversion to degrees/radians/grads is a simple matter of scaling the integer appropriately (as signed or unsigned depending on the normalization range). This was done in the user-interface subsystem.</p>
<p>The biggest gain though was with trigonometric functions. Transcendental functions can eat your lunch in high-fidelity, real-time simulation systems. The trig functions of BAMS can be computed by dividing the integer into three zones. The high order 2 or 3 bits tell you what quadrant or octant the angle is in (permitting the trig computation to make use of that function's symmetry; the middle set of bits can be used for a table lookup; while the low-order bits can be used for interpolation. I suppose these days a specialized ASIC or FGPA could be assembled that did the computation is silicon. The bottom line is that the trig functions were blazeingly fast, the models built using them had no discontinuities in them, and the user-interface was simple and effective.</p>
<p>The modulo arithmetic of binary integers is also rather easily grapsed.</p>
<p>All in all I find this to be a useful technique for the roaming programmer (or indeed ANY programmer) to have in his bag of techniques.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10200069" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9955286Fri, 29 Jan 2010 12:59:58 GMT91d46819-8472-40ad-a661-2c78acb4018c:9955286Baqueta<p>Hmm, interesting point Shawn. I do development mostly for mobile devices, so that's not a tradeoff I've considered before!</p>
<p>My original statement is probably best replaced with something along these lines:</p>
<p>"If you're that concerned about speed, try writing a test app to compare the different approaches."</p>
<p>:¬)</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9955286" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9954142Wed, 27 Jan 2010 16:07:18 GMT91d46819-8472-40ad-a661-2c78acb4018c:9954142Shawn Hargreaves - MSFT<p>> If you're that concerned about speed, precompute!</p>
<p>Beware: in these days of fast CPUs with relatively slow memory, lookup tables are no longer necessarily a speeed boost over just recomputing values whenever you need them.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9954142" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9954003Wed, 27 Jan 2010 10:49:13 GMT91d46819-8472-40ad-a661-2c78acb4018c:9954003Baqueta<p>@Erzengel: If you're that concerned about speed, precompute!</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9954003" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9953172Mon, 25 Jan 2010 20:24:43 GMT91d46819-8472-40ad-a661-2c78acb4018c:9953172tyboyes<p>Looking back, I think dealing with angles and having to re-learn trigonometry was one of the areas that took most of my time when making relspace. The more examples/explanations the better! :)</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9953172" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9952735Mon, 25 Jan 2010 02:09:35 GMT91d46819-8472-40ad-a661-2c78acb4018c:9952735Erzengel<p>Now if only there was a "short BinaryMath.Sin(short Angle)" that didn't involve converting it to a double then back again... But then, doesn't the FPU have a sin instruction that would be faster than trying to compute it on the CPU for an integer?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9952735" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9951267Thu, 21 Jan 2010 05:10:12 GMT91d46819-8472-40ad-a661-2c78acb4018c:9951267Sly<p>This may come down to a performance issue as well. If the angle remained within the normalised range most of the time, the cost of two false if statements might have some effect if this code was called a lot every frame. Using the implicit wrapping of an unsigned short would eliminate that cost.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9951267" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9944160Tue, 05 Jan 2010 20:44:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:9944160Shawn Hargreaves - MSFT<p>> Given a choice between a really smart one-liner code, and an explicit overflow check, I think it's best to code a few more lines.</p>
<p>Such decisions can be a subtle judgment call.</p>
<p>On the one hand, it's certainly not a good idea to rely on cryptic one liners that depend on non obvious side effects.</p>
<p>But on the other hand, it's also not a good idea to write more code than is strictly necessary to solve the problem at hand! The more code you have to write, the more risk you will make a mistake or forget to include something important.</p>
<p>If someone was doing computations with floating point numbers, and every time they stored a result, they were adding a floor() call, I would say that was silly: if they wanted the result to always be an integer, they could simplify their code and reduce the chance of error by just doing the computations directly with an integer data type.</p>
<p>So I guess the question here is whether the modulo nature of integer overflow is an obscure implementation detail that is liable to confuse the reader, or a fundamental characteristic of the data type which the reader can be expected to intuitively understand?</p>
<p>I suspect this mostly comes down to how familiar you (and of course anyone else expected to work on the code in question) are with binary number representations, bit twiddling, etc.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9944160" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9944141Tue, 05 Jan 2010 20:14:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:9944141Terry<p>Have been following your blog for a while. Thought I'd say hello and give my appreciation!</p>
<p>It was only the day before yesterday that was I reading through Doom's source code and came across the curious BAMS (Binary Angle Measurement System), so it's a great coincidence (or scary?) that you mention it :)</p>
<p>I had been using a similar method up until now for breaking a circle up into a custom number of "arcs" for some old school ray casting.</p>
<p>Thanks again! Great posts as always.</p>
<p>Best regards,</p>
<p>Terry</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9944141" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9943936Tue, 05 Jan 2010 15:02:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:9943936Kainsin<p>It goes back to your optimization article. I tend to optimize for readability and maintainability rather than speed (especially since I'm writing a turn-based game where most of the time I'm waiting for user input).</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9943936" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9943836Tue, 05 Jan 2010 10:22:02 GMT91d46819-8472-40ad-a661-2c78acb4018c:9943836Epsicode<p>Aw, you just gave me some Allegro nostalgia :)</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9943836" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9943752Tue, 05 Jan 2010 06:08:07 GMT91d46819-8472-40ad-a661-2c78acb4018c:9943752Greg D<p>I actually think that in this case, the really smart one-liner may be more readable and less error-prone. The bounds checking due to wrapping around at 360 degrees is really a corner-case for most types of functions that accept an angle as an input, and this approach eliminates it.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9943752" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9943674Tue, 05 Jan 2010 00:53:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:9943674Cardin<p>Given a choice between a really smart one-liner code, and an explicit overflow check, I think it's best to code a few more lines.</p>
<p>It's more readable. Readable = easier to optimize, less room for bugs.</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9943674" width="1" height="1">re: Angles, integers, and modulo arithmetichttp://blogs.msdn.com/b/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx#9943668Tue, 05 Jan 2010 00:42:15 GMT91d46819-8472-40ad-a661-2c78acb4018c:9943668Brian L.<p>Great post Shawn. I can think of a *very* popular engine that even today, still uses this method of angle representation for many of its rotations.</p>
<p>The other major win with this method of angle representation is the inherent compression, which is a huge win when it comes to sending rotational data over the network.</p>
<p>The rotation a quaternion or 3x3 matrix represents can instead be represented this way and only use 6 bytes (yaw, pitch, roll) instead of 16 bytes for a quat (4 floats) or 36 bytes for a 3x3 matrix (9 floats).</p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=9943668" width="1" height="1">