 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 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 #define TIMES 256

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

Pokitto::Core game;

int sine;
int cosine;

void setup(){
game.begin();
game.display.width = 110; // half size
game.display.height = 88;
game.setFrameRate(60);
game.display.setColorDepth(4);
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;
}

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?