how 2 speed up rotozoomer

[fir]

rotozumer is a routine that displays bitmap
on screen (which is also a bitmap so this is like
copying bitmap onto bitmap) but the input bitmap
(you may call it 'sprite') will be rotated by given angle and scaled by given zoom

the method is just to iterate on spirite all pixels, totate them (this is multiply by rotated base vectors that
sescribes rotation and zoom) and set this roteted zoomed pixels to screen (yet if zoom is like 2.0 the sampling of the input should be not by +1 step but more like +0.5 to not make holes in output)

my unoptymised and not much edited for names etc function for this is that

inline void Rotate2d(float* x, float* y, float angle)
{
float xt = (*x) * cos(angle*degree360) - (*y) * sin(angle*degree360);
float yt = (*x) * sin(angle*degree360) + (*y) * cos(angle*degree360);

*x = xt;
*y = yt;
}


void DrawSprite2(float pos_x,
float pos_y,
char* file,
int sprite_bitmap_pos_x,
int sprite_bitmap_pos_y,
int sprite_bitmap_end_x,
int sprite_bitmap_end_y,
float angle = 0 ,
float zoom = 1,
int sprite_centre_bitmap_x = -1,
int sprite_centre_bitmap_y = -1

)

{

if(sprite_centre_bitmap_x<0 || sprite_centre_bitmap_y<0)
{
sprite_centre_bitmap_x = (sprite_bitmap_pos_x + sprite_bitmap_end_x)/2;
sprite_centre_bitmap_y = (sprite_bitmap_pos_y + sprite_bitmap_end_y)/2;

}


float sprite_width = sprite_bitmap_end_x - sprite_bitmap_pos_x + 1 ;
float sprite_height = sprite_bitmap_end_y - sprite_bitmap_pos_y + 1;



float Ax = sprite_bitmap_pos_x - sprite_centre_bitmap_x ;
float Ay = sprite_bitmap_pos_y - sprite_centre_bitmap_y ;
float Bx = sprite_bitmap_end_x - sprite_centre_bitmap_x ;
float By = sprite_bitmap_pos_y - sprite_centre_bitmap_y ;
float Cx = sprite_bitmap_end_x - sprite_centre_bitmap_x ;
float Cy = sprite_bitmap_end_y - sprite_centre_bitmap_y ;
float Dx = sprite_bitmap_pos_x - sprite_centre_bitmap_x ;
float Dy = sprite_bitmap_end_y - sprite_centre_bitmap_y ;

Rotate2d(&Ax,&Ay, angle);
Rotate2d(&Bx,&By, angle);
// Rotate2d(&Cx,&Cy, angle);
Rotate2d(&Dx,&Dy, angle);


float dxdx = (Bx-Ax)/sprite_width;
float dydx = (By-Ay)/sprite_width;

float dxdy = (Dx-Ax)/sprite_height;
float dydy = (Dy-Ay)/sprite_height;

float x, y;


for(float j=sprite_bitmap_pos_y-sprite_centre_bitmap_y; j<sprite_bitmap_end_y-sprite_centre_bitmap_y; j+=.7/zoom)
{
for(float i=sprite_bitmap_pos_x-sprite_centre_bitmap_x; i<sprite_bitmap_end_x-sprite_centre_bitmap_x; i+=.7/zoom)
{
unsigned color = sprites_buf_[sprite_centre_bitmap_y + int(j)][sprite_centre_bitmap_x + int(i)];

x = 0*sprite_centre_bitmap_x + i * dxdx*zoom + j*dxdy*zoom;
y = 0*sprite_centre_bitmap_y + i * dydx*zoom + j*dydy*zoom;

if(color==0) {} else SetPixelSafe(pos_x + x, pos_y + y, color);


}
}


}


the problem is clipping, if sprite is rotated positioned and zoomed often quite large parts and a lot of pixels destinate out the screen - and here in that routine i clib them all per pixel (in "SetPixelSafe")

this is much wastefull, and optimistation of this routine is very important as sprites, esp big sprites or sprites that are zoomed to be big may take real lot of time on cpu
(rotozuming big screen size or overscreen sprites sadly may take like 40 ms which is deadly slow (where small ones may take like 1 ms which is ok)

so how to speed it up?
(id someone want to see how it runs i may ulpoad te win32 exe showing how it worx)

[Öö Tiib]

On Sunday, 1 October 2017 11:22:36 UTC+3, fir wrote:
>
> the problem is clipping, if sprite is rotated positioned and zoomed
> often quite large parts and a lot of pixels destinate out the
> screen - and here in that routine i clib them all per pixel
> (in "SetPixelSafe")

I trust that with such problem your concept is backwards.
It does not loop over destination view and find out what point of what
original bitmap should there be. Instead it does something else.

[Christian Gollwitzer]

Am 01.10.17 um 10:22 schrieb fir:

> rotozumer is a routine that displays bitmap
> on screen (which is also a bitmap so this is like
> copying bitmap onto bitmap) but the input bitmap
> (you may call it 'sprite') will be rotated by given angle and scaled by given zoom
>
> the method is just to iterate on spirite all pixels, totate them (this is multiply by rotated base vectors that
> sescribes rotation and zoom) and set this roteted zoomed pixels to screen

This is the worst possible method to do it concerning quality.

> if(color==0) {} else SetPixelSafe(pos_x + x, pos_y + y, color);

...and this is probably your speed issue, if this SetPixel function
calls out into the WIN-API. You are calling a drawing function for every
single pixel - extremely slow due to overhead. Instead, you should
rotate the image in a buffer, and then call a function which blits the
whole buffer to the screen.

> so how to speed it up?
> (id someone want to see how it runs i may ulpoad te win32 exe showing how it worx)

A classic method of image rotation with good quality is Paeth rotation,
which consists of three shear deformations along the coordinate axes.
For best overall performance, you shouldn't use the Win-API for drawing,
but instead OpenGL. There you can directly specify a transformatino
matrix, and the computation will be offloaded to the GPU.

Christian

[fir]

setpixels write to ram but they do clipping on per pixel level which means 4 ifs must be executed for every pixel that pass to screen (and 1 to 4 for each one that not pass) which is propbably deadly to efficiency

thats why i need big scale clipping

now i think i need to do cliping on perscanline level
becouse this just takes sprite scanlines and draws them skewed to screen, i probably need just to clip this shewed line to screen

this line is inner loop of this

for(float j=sprite_bitmap_pos_y-sprite_centre_bitmap_y; j<=sprite_bitmap_end_y-sprite_centre_bitmap_y; j+=.7/zoom)
{
for(float i=sprite_bitmap_pos_x-sprite_centre_bitmap_x; i<=sprite_bitmap_end_x-sprite_centre_bitmap_x; i+=.7/zoom)

{
unsigned color = sprites_buf_[sprite_centre_bitmap_y + int(j)][sprite_centre_bitmap_x + int(i)];

x = pos_x + i * dxdx + j*dxdy;
y = pos_y + i * dydx + j*dydy;

if(color==0) {} else SetPixelSafe(x, y, color);


}
}

question is how to do it exactly.. i even gos somewhere some cliping routine but must find it

btw check how ir runs (i mean this unoptimised version)

minddetonator.htw.pl/rotozoomer.zip

(win32 app no malware)

[fir]

also see side question ,
normally i could samble input sprite just
doin

for(y)
for(x) { }

but if sprite is rotated esp by 45 degrees it make hols in output as width become sqrt(2)*width long
- which is 1.414.. thats why i need to sample in more density thats why i multiply pessimisticaly sampling coordinates * .7 but for less angles i dont need to multiply by .7 just by 1.0

does someone know the exact equation for this factor releted to angle at which i rotate sprite, (it my just gove length of rotated line in pixels (i mean line roted by some angle is shorter in pixels (if i said longer i made mistake) its geometrically the same long but in covered pixels its shorter as pixels are squares)

whats thet equation

float len = foo(angle);
?

[Öö Tiib]

On Sunday, 1 October 2017 14:18:04 UTC+3, fir wrote:
>
> also see side question ,
> normally i could samble input sprite just
> doin
>
> for(y)
> for(x) { }
>
> but if sprite is rotated esp by 45 degrees it make hols in output as width become sqrt(2)*width long
> - which is 1.414.. thats why i need to sample in more density thats why i multiply pessimisticaly sampling coordinates * .7 but for less angles i dont need to multiply by .7 just by 1.0

That would also go away if you would iterate over destination coordinates
and find what point there should be instead of iterating over source
coordinates.

[fir]

i think iterating over source is better, i just need do proper cliping

ps i revrited the loop slightly

for(float j=bot_wing; j<=top_wing; j+=.7/zoom)
{
for(float i=left_wing; i<=right_wing; i+=.7/zoom)

{
unsigned color = sprites_buf_[sprite_centre_bitmap_y + int(j)][sprite_centre_bitmap_x + int(i)];

x = pos_x + i * dxdx + j*dxdy;
y = pos_y + i * dydx + j*dydy;

if(color==0) {} else SetPixelSafe(x, y, color);


}
}

those loops just iterate over input sprite but coordinates are reshifted to give 0,0 in point that was chosen as sprite centre

for example if sprite is 200x 200 and centre is in 50 50 it will be

for(float j=-50; j<=150; j+=.7/zoom)
for(float i=-50; i<=150; i+=.7/zoom)

i need to do cliping but it seems also i would needto reverse transform this cliping points on input sprite points

[fir]

i must think a bit...


clipping i would just do like that

for(float j=bot_wing; j<=top_wing; j+=.7/zoom)
{

px = pos_x + left_wing * dxdx + j*dxdy;
py = pos_y + left_wing * dydx + j*dydy;

qx = pos_x + right_wing * dxdx + j*dxdy;
qy = pos_y + right_wing * dydx + j*dydy;

if!(ClipLineToScreen(&px,&py,&qx,&qy)) continue;

for(float i=left_wing; i<=right_wing; i+=.7/zoom)
{
unsigned color = sprites_buf_[sprite_centre_bitmap_y + int(j)][sprite_centre_bitmap_x + int(i)];

x = pos_x + i * dxdx + j*dxdy;
y = pos_y + i * dydx + j*dydy;

if(color==0) {} else SetPixelSafe(x, y, color);


}
}

assuming that i will wrote good cliping line routine (i had some but remember it was problematic )

but how thetn to reberse those clipped points to inner for coordinates? (just count distances rescale by this distorting factor and subb add to edges? (sounds weird)

[fir]

W dniu niedziela, 1 października 2017 13:48:43 UTC+2 użytkownik fir napisał:
>
px = pos_x + left_wing * dxdx + j*dxdy;
py = pos_y + left_wing * dydx + j*dydy;

qx = pos_x + right_wing * dxdx + j*dxdy;
qy = pos_y + right_wing * dydx + j*dydy;

if!(ClipLineToScreen(&px,&py,&qx,&qy)) continue;

or maybe i just do here inversed rotation (rotate by -angle again but how exactly, first -pos then -rotation or first -rotation and then -pos? (yet zomm comes)

do this moatric rotation is orthogonal is there a trick for easy reversing?

[fir]

my wild gues it could be (without zoom, assumng zoom is 1.0 for simplicity)

px = pos_x + left_wing * dxdx + j*dxdy;
py = pos_y + left_wing * dydx + j*dydy;

qx = pos_x + right_wing * dxdx + j*dxdy;
qy = pos_y + right_wing * dydx + j*dydy;

if!(ClipLineToScreen(&px,&py,&qx,&qy)) continue;

lwx = (px-pos_x) * dxdx + (py-pos_y)*dxdy*(-1);
// lwy = (px-pos_x) * dydx*(-1) + (py-pos_y)*dydy;


rwx = pos_x + (qx-pos_x) * dxdx + (qy-pos_y)*dxdy*(-1);
// rwy = pos_y + (qx-pos_x) * dydx*(-1) + (qy-pos_y)*dydy;

but im not sure and my head started to hurt

[Christian Gollwitzer]

Am 01.10.17 um 13:37 schrieb fir:

> W dniu niedziela, 1 października 2017 13:26:50 UTC+2 użytkownik Öö Tiib napisał:
>> That would also go away if you would iterate over destination coordinates
>> and find what point there should be instead of iterating over source
>> coordinates.
>
> i think iterating over source is better, i just need do proper cliping
>

No, it's not, and you have been told the reason multiple times. Why do
you try to sharpen a wooden knife instead of using a sharp blade?


Christian

[fir]

anyway something like that seem reasonable and maybe when i rest i will test it

[fir]

i dont think yu understand it - if you understand tell me why its not better?

in this reversed way i would need to count area for which it should reach for pixels, which seem unnatural to me, here i got the area naturalely
also if i skip onj transparency color i dont need to do transformation on such transparent pixels in reversed method i would need to do transformation only to see that pixel is transparent

[Christian Gollwitzer]

Am 01.10.17 um 14:19 schrieb fir:

> W dniu niedziela, 1 października 2017 14:13:35 UTC+2 użytkownik Christian Gollwitzer napisał:
>> Am 01.10.17 um 13:37 schrieb fir:
>>> W dniu niedziela, 1 października 2017 13:26:50 UTC+2 użytkownik Öö Tiib napisał:
>>>> That would also go away if you would iterate over destination coordinates
>>>> and find what point there should be instead of iterating over source
>>>> coordinates.
>>>
>>> i think iterating over source is better, i just need do proper cliping
>>>
>> No, it's not, and you have been told the reason multiple times. Why do
>> you try to sharpen a wooden knife instead of using a sharp blade?
>>
>
> i dont think yu understand it - if you understand tell me why its not better?

Because when you iterate over the destination pixels, you will ensure
that you hit every pixel only once. The source will come from
non-integer locations, which is "easily" dealt with interpolation. The
simplest solution is trilinear interpolation which weighs all four
pixels surrounding the non-integer location that you hit. More
sophisticated interpolation schemes exist (look up bicubic or Lanczos
filtering). Without filtering your turned image will look very ugly.

Iterating over the destination pixels will also be faster due to the
architecture of current computers. It is faster if you write a block of
memory in a single continuous row, while reading from scattered
locations (so called "gather" operation) than to do it the other way
round ("scatter" operation)

Finally, to deal with transparency, you only need to enhance your blend
operation. If you use Paeth's algorithm or any other, where the pixels
outside of the source image are set to fully transparent, you will most
likely get the expected result.

Christian

[fir]

what you say is opinion and not the proof
(becouse other factiors also come to play, other than mentioned)

(hovever im not sayin there is no sense in it, this filtering my have some point,

as to read from sequential write to skewed beats write to sequential read from skewed im not sure - maybe..)

anyway you should note i dont want the
best quality algorithm, i can think on more fast one (and in raw wersion im not sure if this reversed is faster) im searchng for easier to write and run..
and esp as i got what i got i want now only slightly to improve what i got and that is on question
(at later stage i could try both and compare now easiest seem to just run this one)

[fir]

hell it dont work, it meens i would need to start detailed long debug sesion (esp as my line clipping routine is probably wrong)

[fir]

i once tested line cliping algorithms and it made problem as line defined on ints and one defined on floats canbe somewhat incompatible

other problem was that if i clipped int-based line to also int based clipped line
the result of clipping was uncompatiblle with a part drawed by bresenham b-couse bressenham remembers fractional parts when entering slipped area and starting new integer line in the edge points (line that not remembered those fraction parts at start end end) was giving a bit different line than oryginal

i would even rethink how to define both integer and float coordinates of pixels,
should 0. 0. point point center of top left pixel ot its tol left corner? this decisian has serious consequences (even probably influences the speed of some routines slightly)

[fir]

some notes

if i chose 0. 0. at the centre of the pixel i got some like unsymetry which is weird, on the other hand int coordinates of pixels give identical unsymetry,
there would be unsymetry but
conversion form int coordinates to float will be more natural

consequences are hhovever even more serious (think on drawing adjacent rectangles when 0. 0. is in ppixel corners or centres, to draw lines center-pixel coordinates are beter but to write
adjacent shapes seems worse

yet other complication is if to use c natural cast in such graphics it probably works just wrong in both scenarios (i would need to rethink it a bit hovever)

in short writing some routines only on int coordinates alllows me to not make this float decision but when i need
to do cliping etc or more care on details i just need to taks this float coordinate decision

im closer to establish 0. 0. point in the centre of first pixel it is becouse
othervise i would need to think wierdly on integer coordinetes (in integer coordinates i just think on centres of the pixels) or having two uncompatible
sets and that would be very confusing
(when for example set_pixel(1,1) would work other than set_pixel(1., 1.))
(in such way here one couls say integer rulez floats not floats rulez integers)

yet still i would need to be careful on
default float to int casts (which afair
just eat one column and one row as they
both cast .9 .9 and -.9 -.9 to 0 0

where according to convention .9 .9 could yeild to 1 1 and -.9 -.9 to -1 -1
first pixel spans -.5 to .5 im not sure
what to do with edges (probably will need to treat it always with special atention? :C) and dont even know what c expression realizes such cast, just round(x) ?

[fir]

anyway it seems that only after that consideration i could think how to design clip_line function, .. it must be float coz as i said integer clipline just dont work

if i rest maybe i will write some notes on this (it is somewhat boring work but sadly it must be somewhat done)

[fir]

i got totally lame clip line function
(its old i see how bad names i use thise times)


int ClipLineToArea(int* xi, int* yi, int* xi_, int* yi_, int left, int up, int right, int down)
{
int x = *xi;
int y = *yi;
int x_ = *xi_;
int y_ = *yi_;



// int up = 0 ;
// int down = frame_size_y - 1;
//
// int left = 0 ;
// int right = frame_size_x - 1;



if(x==x_) //pionowa linia
{

if(x>=left && x<=right)
{

if(y<y_)
{
if(y< up && y_>=up) y=up;
if(y<=down && y_> down) y_=down;
}

if(y_<y)
{
if(y_< up && y>=up) y_=up;
if(y_<=down && y> down) y=down;
}

// ERROR_("clip pionowa");

(*xi) = x;
(*yi) = y;
(*xi_) = x_;
(*yi_) = y_;

return 1;
}
else
{
// ERROR_("pionowa linia poza zakresem");
return 0;
}



}

if(y==y_) ///pozioma
{

if(y>=up && y<=down)
{

if(x<x_)
{
if(x<left && x_>=left) x=left;
if(x<=right && x_>right) x_=right;

}

if(x_<x)
{
if(x_<left && x>=left) x_=up;
if(x_<=right && x>right) x=right;

}

//ERROR_("clip pozioma");

(*xi) = x;
(*yi) = y;
(*xi_) = x_;
(*yi_) = y_;

return 1;

}
else
{
// ERROR_("p0zioma linia poza zakresem");
return 0;
}

}

// return;



/*
float x = *xi;
float y = *yi;
float x_ = *xi_;
float y_ = *yi_;

float up = 0 ;
float down = CLIENT_Y - 1;

float left = 0 ;
float right = CLIENT_X - 1;
*/

float DYdoDX = float(y_ - y) / float( x_ - x);
float DXdoDY = float(x_ - x) / float( y_ - y);

float a = 0.5 ;


if(y < y_)
{
if(y<up && y_>=up)
{
x = x + (((up-y-a)*DXdoDY));

y = up;
}

if(y<=down && y_>down)
{
x_ = x_ + (((down-y_+a)*DXdoDY));

y_ = down;
}

}
else if(y_ < y)
{
if(y_<up && y>=up)
{
x_ = x_ + (((up-y_-a)*DXdoDY));

y_ = up;
}

if(y_<=down && y>down)
{
x = x + (((down-y+a)*DXdoDY));

y = down;

}

}


//clip to bottom

// clip left

if(x < x_)
{
if(x<left && x_>=left)
{
y = y + (((left-x-a)*DYdoDX));

x = left;
}

if(x<=right && x_>right)
{ // 33 499 - 0
y_ = y_ + (((right-x_+a)*DYdoDX));

x_ = right;
}

}
else if(x_ < x)
{
if(x_<left && x>=left)
{
y_ = y_ + (((left-x_-a)*DYdoDX));

x_ = left;
}

if(x_<=right && x>right)
{
y = y + (((right-x+a)*DYdoDX));

x = right;
}

}
if(x<left) return 0;
if(x>right) return 0;
if(y<up) return 0;
if(y>down) return 0;

if(x_<left) return 0;
if(x_>right) return 0;
if(y_<up) return 0;
if(y_>down) return 0;


*xi = x;
*yi = y;
*xi_ = x_;
*yi_ = y_;

return 1;
}

and im not even sure it this works ok,
with some tests on random generated lines it seems to work ok hovever - hovever it has those errors i said i mean clip+bresenham has slight different pixel positioning that bressenhams clipped on pixels

this above is also not quite efficient i think hovever when measured and compered to drawline routines that make clip on sperate pixels it speed up things, how much depends mostly obviously on the area of offscreen pixels, sometomes it speeds things from 4 to 3 and sometimes from 40 to 10

must say that form some reasons such clipline routines are distaster for me to vrite, hovever i later should revrite it nicer and improve it (as i said im still not sure if this generally works well or not quite)