Going round in (almost) circles

TAD

Introduction

This article describes a very simple and very, very old method of rotating a 2d (x,y) co-ordinate around an origin by a certain angle. This method was used back in the days of 8-bit computers which had NO multiplication or division instructions.

Common 2d-rotation

You should all have this formula etched into your skulls by now.

                x' = x * cos(a) - y * sin(a)    <--- step 1
                y' = x * sin(a) + y * cos(a)    <--- step 2
                x = x'
                y = y'

where,
                a = angle to rotate through
                (x,y) = old co-ordinate 2d values to rotate
                (x',y') = new rotated 2d values

NOTEYou should note the BOTH steps use the old x and y values, and the result is stored in two NEW variables (namely x' and y'). If you try updating (x,y) directly in step 1 then it will fail. You need a minimum of 1 temporary variable.

                old_x = x
                x = x * cos(a) - y * sin(a)
                y = old_x * sin(a) + y * sin(a)

Fast 90-degree rotation

Using the above 2d rotation formula you can replace those nasty cos(a) and sin(a) with constant values for a 90 degree rotation.

                cs = cos(90) = 0
                sn = sin(90) = 1

                x' = (x * cs) - (y * sn)
                y' = (x * sn) + (y * cs)

which is,
                x' = (x * 0) - (y * 1)
                y' = (x * 1) + (y * 0)

which gives:
                x' = - (y * 1)
                y' = (x * 1)

and is:
                x' = - y
                y' = x

In Code this can be done in just two instructions which can be very useful when you want to quickly draw a border or to preform some 90 degree rotation.

        (eax) = x
        (edx) = y

                XCHG    EAX, EDX
                NEG     EAX

Of course you could replace cs and sn with some other constants and yield 180 degree or 270 degree rotation using nothing more than XCHG and NEG instructions. If you want to rotate by a non-multiple of 90, then you need to use some multiplication.

Constant Rotation

As you have probably already figured out, we can rotate through any constant angle by pre-calculating the cos(a) and sin(a) values then inserting them into the 2d rotation.

e.g.
        sn = sin(30') = 0.5
        cs = cos(30') = 0.86602540378...

                x' = x * cs - y * sn
                y' = x * sn + y * cs
using constants:
                x' = x * 0.86602540378 - y * 0.5
                y' = x * 0.5 + y * 0.86602540378

Division, are you crazy?

And now Ladies and Gentlemen what you have been waiting for, using division to replace the multiplications like on those 8-bit computers many moons ago.

Again, we can replace the sin(a) and cos(a) values with constants. This time we choose a 1 degree rotation.

        sn = sin(1') = 0.01745240643
        cs = cos(1') = 0.99984769515

                x' = x * 0.99984769515 - y * 0.01745240643
                y' = x * 0.01745240643 + y * 0.99984769515
                x = x'
                y = y'

We convert the sn and cs values into 1/sn and 1/cs values because we will be performing division instead of multiplication.

        r_sn = 1/sin(1') = 57.2986884986
        r_cs = 1/cos(1') = 1.00015232804

                x' = x / r_cs - y / r_sn
                y' = x / r_sn + y / r_cs
expanded:
                x' = x / 1.00015232804 - y / 57.2986884986
                y' = x / 57.2986884986 + y / 1.00015232804

And now the naughty bit. We round those numbers up or down to something more 'cpu-friendly'. ;)

        a_sn = approx. 1/sin(1') = 57.2986884986 ---> 64
        a_cs = approx. 1/cos(1') = 1.00015232804 --->  1

                x' = x / a_cs - y / a_sn
                y' = x / a_sn + y / a_cs
expanded:
                x' = x / 1 - y / 64
                y' = x / 64 + y / 1

As you're probably already noticed, we can remove the divide-by-1 in each step to give this more pleasing method.

                x' = x - y / 64
                y' = x / 64 + y
Mr. Shifty:
                x' = x - (y SHR 6)
                y' = (x SHR 6) + y
Same:
                x' = x - (y SHR 6)
                y' = y + (x SHR 6)

In 80x86 using 1.15.16 fixed-point it looks like this...

        (eax) = x SHL 65536
        (edx) = y SHL 65536

                mov     ebx, eax        ; old_x = x
                mov     ecx, edx        ; old_y = y
                sar     ebx, 6          ; old_x / 64
                sar     ecx, 6          ; old_y / 64
                sub     eax, ecx        ; x' = x - (old_y / 64)
                add     edx, ebx        ; y' = y + (old_x / 64)

Go Timmy!!!

Now, there are a few problems with that division (shift) method. Firstly it will spiral outwards over a long period of time (remember we have messed with those important sin and cos values). Also if you do try smaller values for the shift-right counts (for example shr 4) then the amount of error is even worse. And of course you need to store and handle fixed-point or floating-point maths for it to work.

I doubt if this method will be used outside a size-optimization compo, but you never know. If you want to draw dodgy-looking spirals then see above. ;)

Have fun.

TAD