Image Rotate


#1

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

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


#3

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


#4

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;
}

#5

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…


#6

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.


#7

2^TIMES.

repo updated.


#8

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.


#9

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


#10

Nice demo in Twitter!

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


#11

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


#12

Yes, that and also aliasing


#13

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.


#14

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


#15

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.


#16

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


#17

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).


#18

Is it usable in some way now?


#19

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


#20

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