Integer Trigonometry

Adding a live GPS feed to a map means, besides near-second updates, the requirement to display a location marker with the current heading. The Window Mobile GPSID provides the current heading in the GPS_POSITION structure as the fHeading value, representing the angle in degrees between the current heading and true North (zero degrees). So how do you go about drawing a compass like the one in the picture?

The drawing is composed of two simple triangles: red for North and blue for South. The drawing is performed by using the Polygon GDI function that takes a list of points describing a closed shape and draws it using the selected pen and brush. Nothing new here. The interesting challenge is how to draw the image in the different angles without a big performance hit (translated: how to implement fast trigonometry functions).

Current Windows Mobile devices are not guaranteed to have an FPU unit that will do all the floating point math for you. If you use the Compact Framework, you are sure that all floating point calculations are performed in a software emulated FPU, so they are much slower than what they could be when performed with a real FPU. When using native code, you have the advantage of using the FPU if one is available, but the code will fall back to the emulator if the FPU is missing.

My approach here was to skip any floating point processing at all. There are two reasons for this:

1. Drawing a map on a Windos Mobile device is a resource-intensive operation, especially if you are updating it frequently and you want to spend the least amount of time drawing any decorations on top of it. So a fast implementation is required.
2. This object requires very simple transformations (rotation plus offset) and the required accuracy of the final result is not very high. In fact, it is somewhat low considering the relatively small resolution of WM device screens. The bottom line is that you can live with a bit of error when drawing your compass (this is not rocket science).
   

So how do you calculate a rotation transformation? Please refer to a good book on the subject (I'm using this lovely book as a reference: Essential Mathematics for Games and Interactive Applications) and you will see that it all boils down to these two simple equations (transforms a point through a counter-clockwise rotation around the origin):

• x' = x cos(a) - y sin(a)
• y' = x sin(a) + y cos(a)

Where (x, y) are the original point coordinates, (x', y') are the transformed point coordinates and a is the rotation angle. The first thing you need to do is to "draw" your compass by defining the vertexes assuming that the center of your coordinate system is in the center of the image. In this case, I used the following points:

• (0, 32) - North
• (-7, 0) - West
• (0, -32) - South
• (8, 0) - East

The reason why I'm not using (7, 0) for East is simple: the final image looks much better on a discrete screen if it has an odd width. If you look at the sample project you will see that I split the compass into two distinct triangles in order to draw them with different pens and brushes.

Now the interesting bit is how I implemented the sin and cos functions: through a table lookup. Assuming that you can live with an error of one degree when specifying the angle, all you need is a precomputed list of the sin values between 0 and 90 degrees. Using basic trigonometry you can derive all sin and cos values from the first quadrant sin values. If you look at the code, you will see that the precomputed sin values are scaled by 10,000. When calculating x sin(a) the code uses the precomputed value and divides the result by 10,000 to get the approximate result (you can use a higher scale for a higher resolution calculation, but that might not be required for this purpose). You can see the implementation of these functions in the FastTrig.h and FastTrig.cpp files in the sample.

Before we can draw our compass on the screen, we must take care of two important issues:

1. The original compass coordinates are centered around the origin, so we must transform them further to make it fully visible on the screen;
2. The screen coordinates of a Windows Mobile device are a bit different: while x grows to the right as we expect, y grows down and not up.
   

This means that beside the rotation we must apply a translation and a "mirror" transformation. In the sample code, I translate by adding the x and y offsets corresponding to the middle of the screen and then the y coordinate is flipped by subtracting it from the window height. Enough of this talk, here's the sample project: GpsCompass.zip.

On a future post I will update this code so that it uses a double buffer painting method to eliminate flickering and connect the compass direction to the GPS heading.