Image Rotate

I have gave rotating an image a try on Pokitto. Currently it is very slow, so shouldn’t be used for any real time effects, it was just a test really.


If anyone can think of a way to speed it up, that would be good :stuck_out_tongue:

It uses 8bit image data in 110x88 16colour mode. the 8bit image data just makes the math a little easier as you don’t have to think about splitting the bytes.

2 Likes

Yes, use fixed point numbers instead of floats and use a sine table.

Welp, I know what my first job is going to be as soon as I’ve got some time to spare.

1 Like

OK, the lookup table helpd a lot, but I’m having a little trouble with the fixed point thing. From my understanding it should be as simple as multiplying everything by a number, usually something bitshiftable to speed it up, then dividing the end result by the same number… I appear to be doing it wrong :frowning:

#define TIMES 256

#include "Pokitto.h"
#include "gfx.h"

Pokitto::Core game;

int sine[360];
int cosine[360];

void setup(){
    game.begin();
    game.display.width = 110; // half size
    game.display.height = 88;
    game.setFrameRate(60);
    game.display.setColorDepth(4);
    game.display.load565Palette(sprite_pal);
    game.display.bgcolor = 0;
    game.display.invisiblecolor = -16;
}

int main(){
    setup();
    float angle=0;
    for(int t=0; t<360; t++){
        sine[t]=sin(angle)*TIMES;
        cosine[t]=cos(angle)*TIMES;
        angle+=(0.0174533); // radians
    }

    int ang=0;
    while (game.isRunning()) {

        int SIN = sine[ang];
        int COS = cosine[ang];
        int ux,uy;

        for(int y=0; y<88; y++){
            for(int x=0; x<110; x++){

                int x1 = (x-55)*TIMES;
                int y1 = (y-44)*TIMES;

//                ux=(x-55) * COS - (y-44) * SIN;
//                uy=(x-55) * SIN + (y-44) * COS;
                ux = (x1 * COS - y1 * SIN) / TIMES;
                uy = (x1 * SIN + y1 * COS) / TIMES;

                if(ux>-55 && ux <55 && uy >-44 && uy <44){
                    char col = rawData[(ux+55)+112*(87-(uy+44))];
                    game.display.drawPixel(x,y,col);
                }
            }
        }

        if(ang++>=360) ang=0;
        game.display.update();
  }
    return 1;
}

if you multiply 2 fixed point numbers, the result must be divided by 2*TIMES.

As you said bit shifting is much faster than multiply or divide, unless the compiler is smart enough to optimize it…

I’d recommend reading this as an intro.

And then for resources for operation implementation there’s this, this, this and this. (I find #3 to be the easiest/best, but it doesn’t cover everything.)

And if those don’t help, why not peek at a fully working implementation (which I swear I’ll port to be usable for Pokitto as soon as I unburden myself of other projects).

If any of this seems complicated at any point, that’s because it is.
(I hate maths, but it’s a necessary evil.)


Also try to avoid adding floats in a loop if you can multiply instead, floating points accumulate errors when added in a loop.

2^TIMES.

repo updated.

For multiplication specifically (from #3):

This one is a bit more involved, but quite easy.

r = x * y

However, x and y don’t need to have the same format. The result will have a format containing the sum of both integer part’s bits and fractional part’s bits in x and y. For example if x is of the format 4.3 (4 bits for integer and 3 for fractional) and y is of the format 5.7, then the result will be of the format 9.10 (9 bits for integer part and 10 for fractional part).

Now we gotta think logically – if we, for example, have two numbers x and y in 8.8 format, then multiplying them will yield a 16.16 result. So, if we want a 8.8 result, we need to shift it right 8 bits. For the integer part, just ignore the upper bits, or do the same as if it overflowed (since you had a 16.16 format and now you want 8.8). Here’s an example:

// multiply fixed point number x with y, both are 8.8 format
// we want the result to be of 8.8 format too, so we need to shift right by 8
r = (x * y) >> 8

Meaning

ux = (x1 * COS - y1 * SIN) / TIMES;
uy = (x1 * SIN + y1 * COS) / TIMES;

Becomes:

ux = (((x1 * TIMES) * COS) / TIMES - ((y1 * TIMES) * SIN) / TIMES);
uy = (((x1 * TIMES) * SIN) / TIMES - ((y1 * TIMES) * COS) / TIMES);

Which can be simplified to:

ux = (((x1 * TIMES) * COS) - ((y1 * TIMES) * SIN)) / TIMES;
uy = (((x1 * TIMES) * SIN) - ((y1 * TIMES) * COS)) / TIMES;

Then to turn into an integer you’d divide by TIMES again, giving

ux = ((((x1 * TIMES) * COS) - ((y1 * TIMES) * SIN)) / TIMES) / TIMES;
uy = ((((x1 * TIMES) * SIN) - ((y1 * TIMES) * COS)) / TIMES) / TIMES;

Which can be turned into:

ux = (((x1 * TIMES) * COS) - ((y1 * TIMES) * SIN)) / (TIMES * TIMES);
uy = (((x1 * TIMES) * SIN) - ((y1 * TIMES) * COS)) / (TIMES * TIMES);

Make sure the compiler is turning the multiplication and division into bitshifts though.

1 Like

Right, divide by TIMESTIMES, not 2TIMES

Edit: that is, if you want normal integer. If you want the result to be a FP number, just divide by TIMES, as in example by @Pharap

1 Like

Nice demo in Twitter!

Some of the artefacts in rotation might be due that the FP number is truncated to int, not rounded.

1 Like

also the low resolution of both the screen mode and original image? It’s only 110x88.

Yes, that and also aliasing

To have rounded values for ux and uy you just have to add (TIMES2/2) before dividing the whole sum by TIMES2. That should be comparable to adding 0.5 to a float.

The main speedup that can be done is to not calculate the transform for each pixel.

What you do is you calculate the u and v texture vectors once before the drawing loop and then simply accumulate the vectors inside the loop

3 Likes

The code isn’t very pretty and it breaks modern ideals like RAII, but I must admit I’m amazed I never realised that was possible.

I just noticed that there is now Pokitto\POKITTO_LIB\FixMath\ in the PokittoLib repo. That also includes lookup tables for e.g. Sine.

2 Likes

It’s just a copy of the FixMath library. I haven’t implemented it in a meaningful way. Feel free to work with that if you want.

EDIT: there are many ways of doing fixed point maths. There can be more than 1 library to do the same thing. There will be more than 1 library for SD card functions also (I plan on adding SDFat so that we get video streaming from SD also).

1 Like

Is it usable in some way now?

yea just start using it. i think its a plug n play library

Any example is welcome. I can’t include it. Probably missing some path reference?