Fastest possible zoom and rotation algos

Guilherme_Campos_Haz · July 26, 2004, 10:56pm

Hi folks,

I’m searching for the fastest possible not-asm code for scale and rotation of a
bitmap (separately).

I already saw the rotozoom, but it is a little complex and big, and the author
states that it is not optimized.

Why i need speed? The target device has 17Mhz.

Many thanks

guich

Patrick_Roberts · July 27, 2004, 4:23am

Assuming you don’t care about quality, (and that you’re not asking about
something already built into an SDL module…I’ve only been playing with
SDL for a couple of days now.)

For scaling, the fastest alg is nearest neighbor. For rotation, it’s 2
skews (one X, one Y, using nearest neighbor).

Assuming you’ll be doing it in fixed-point and not knowing about your
CPU or memory organization, here’s some pseudo-code:

Scale:-----------

incX=width_of_input/width_of_output; /* fixed point /
incY=height_of_input/height_of_output; / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */

for(outY=0;outY<height_of_output;outY++) {
for(outX=0;outX<width_of_output;outX++) {

    inX=truncate_fixed_to_int(inputX);
    inY=truncate_fixed_to_int(inputY);

    pixelOut[outY][outX]=pixelIn[inY][inX];

    inputX+=incX;

}  /* end of X loop */

inputY+=incY;

} /* end of Y loop */

To scale from a different center point, start with inputX and inputY
set to something other than (0,0).

Rotate:

incX=cos_of_angle_shift_in_fixed_pixels(angle); /* fixed point /
incY=sin_of_angle_shift_in_fixed_pixels(angle); / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */
startX=0;
startY=0;

for(outY=0;outY<height_of_output;outY++) {
inputX=startX;
inputY=startY;
for(outX=0;outX<width_of_output;outX++) {

    inX=truncate_fixed_to_int(inputX);
    inY=truncate_fixed_to_int(inputY);

    pixelOut[outY][outX]=pixelIn[inY][inX];

    inputX+=incX;
    inputY+=incY;

}  /* end of X loop */
 startX+=incX;
 startY+=incY;

} /* end of Y loop */

To do both at the same time, you can combine the source look-ups. Also,
with the rotate, the numbers can be negative. To rotate around a
different location, set startX/Y.

Keep in mind both pseduo-code snippets above don’t have any clipping.
You’ll probably need that for at least the rotation.

Hope that helps…
-Pat

Guilherme Campos Hazan wrote:

Hi folks,

I’m searching for the fastest possible not-asm code for scale and rotation of a
bitmap (separately).

I already saw the rotozoom, but it is a little complex and big, and the author
states that it is not optimized.

Why i need speed? The target device has 17Mhz.

Many thanks
guich
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

Donny_Viszneki · July 27, 2004, 12:11pm

If you like image quality and speed, and your system has enough memory,
you could prerender several rotations. Could you be more specific about
your target hardware?On Jul 27, 2004, at 12:23 AM, Patrick Roberts wrote:

Assuming you don’t care about quality, (and that you’re not asking
about something already built into an SDL module…I’ve only been
playing with SDL for a couple of days now.)

For scaling, the fastest alg is nearest neighbor. For rotation, it’s
2 skews (one X, one Y, using nearest neighbor).

Assuming you’ll be doing it in fixed-point and not knowing about your
CPU or memory organization, here’s some pseudo-code:

Scale:

incX=width_of_input/width_of_output; /* fixed point /
incY=height_of_input/height_of_output; / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */

for(outY=0;outY<height_of_output;outY++) {
for(outX=0;outX<width_of_output;outX++) {
   inX=truncate_fixed_to_int(inputX);
   inY=truncate_fixed_to_int(inputY);

   pixelOut[outY][outX]=pixelIn[inY][inX];

   inputX+=incX;
} /* end of X loop */

inputY+=incY;

} /* end of Y loop */

To scale from a different center point, start with inputX and inputY
set to something other than (0,0).

Rotate:

incX=cos_of_angle_shift_in_fixed_pixels(angle); /* fixed point /
incY=sin_of_angle_shift_in_fixed_pixels(angle); / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */
startX=0;
startY=0;

for(outY=0;outY<height_of_output;outY++) {
inputX=startX;
inputY=startY;
for(outX=0;outX<width_of_output;outX++) {
   inX=truncate_fixed_to_int(inputX);
   inY=truncate_fixed_to_int(inputY);

   pixelOut[outY][outX]=pixelIn[inY][inX];

   inputX+=incX;
   inputY+=incY;
} /* end of X loop /
startX+=incX;
startY+=incY;
} / end of Y loop */

To do both at the same time, you can combine the source look-ups.
Also, with the rotate, the numbers can be negative. To rotate around
a different location, set startX/Y.

Keep in mind both pseduo-code snippets above don’t have any
clipping. You’ll probably need that for at least the rotation.

Hope that helps…
-Pat

Guilherme Campos Hazan wrote:

Hi folks,
I’m searching for the fastest possible not-asm code for scale and
rotation of a bitmap (separately).
I already saw the rotozoom, but it is a little complex and big, and
the author states that it is not optimized.
Why i need speed? The target device has 17Mhz.
Many thanks
guich

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

Donny Viszneki

Guilherme_Campos_Haz · July 27, 2004, 5:49pm

Hi,

If you like image quality and speed, and your system has enough memory,
you could prerender several rotations. Could you be more specific about
your target hardware?

Yes, Palm OS from 2.0 to 5.0.

But i’m expecting a direct link to an already-made routine: i don’t want to
reinvent the wheel.

thx

guich

atrix2 · July 27, 2004, 6:04pm

well if your looking for fast rotation you might tell the user to turn the
handset 20 degrees counter clockwise

of course speed varies from user to user (;

(sorry couldnt resist)> ----- Original Message -----

From: guich@superwaba.com.br (Guilherme Campos Hazan)
To:
Sent: Tuesday, July 27, 2004 10:49 AM
Subject: [SDL] Re: Fastest possible zoom and rotation algos

Hi,

If you like image quality and speed, and your system has enough memory,
you could prerender several rotations. Could you be more specific about
your target hardware?

Yes, Palm OS from 2.0 to 5.0.

But i’m expecting a direct link to an already-made routine: i don’t want
to
reinvent the wheel.

thx

guich

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

Stephane_Marchesin · July 27, 2004, 6:08pm

Guilherme Campos Hazan wrote:

Hi,

If you like image quality and speed, and your system has enough memory,
you could prerender several rotations. Could you be more specific about
your target hardware?

Yes, Palm OS from 2.0 to 5.0.

But i’m expecting a direct link to an already-made routine: i don’t want to
reinvent the wheel.

Since that the palm is 68k powered, I don’t think it’ll be hard to find
an optimized assembly sprite rotation for this architecture that you
could adapt/use.
Back in the glorious amiga/atari times, rotozoomers were the basis of
all the demo programming

Stephane

Donny_Viszneki · July 27, 2004, 6:39pm

well if your looking for fast rotation you might tell the user to turn
the
handset 20 degrees counter clockwise

of course speed varies from user to user (;

(sorry couldnt resist)

Does anybody remember those old mechanical handheld arcade games with
moving parts beneath the glass surface? Man those things were so
awesome!On Jul 27, 2004, at 2:04 PM, Alan Wolfe wrote:

devel_at_integra-sc · August 4, 2004, 9:07am

Hi,
your mail it’s very interesting. Thanks.
Do you know about a well optimized code for MMX or SSE or 3dnow to perfome rotation and scaling?
Thanks again.

Il Mon, 26 Jul 2004 21:23:26 -0700
Patrick Roberts scrisse:>

Assuming you don’t care about quality, (and that you’re not asking about
something already built into an SDL module…I’ve only been playing with
SDL for a couple of days now.)

For scaling, the fastest alg is nearest neighbor. For rotation, it’s 2
skews (one X, one Y, using nearest neighbor).

Assuming you’ll be doing it in fixed-point and not knowing about your
CPU or memory organization, here’s some pseudo-code:

Scale:

incX=width_of_input/width_of_output; /* fixed point /
incY=height_of_input/height_of_output; / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */

for(outY=0;outY<height_of_output;outY++) {
for(outX=0;outX<width_of_output;outX++) {
    inX=truncate_fixed_to_int(inputX);
    inY=truncate_fixed_to_int(inputY);

    pixelOut[outY][outX]=pixelIn[inY][inX];

    inputX+=incX;

}  /* end of X loop */

inputY+=incY;
} /* end of Y loop */

To scale from a different center point, start with inputX and inputY
set to something other than (0,0).

Rotate:

incX=cos_of_angle_shift_in_fixed_pixels(angle); /* fixed point /
incY=sin_of_angle_shift_in_fixed_pixels(angle); / fixed point /
inputX=0; / fixed point /
inputY=0; / fixed point */
startX=0;
startY=0;

for(outY=0;outY<height_of_output;outY++) {
inputX=startX;
inputY=startY;
for(outX=0;outX<width_of_output;outX++) {
    inX=truncate_fixed_to_int(inputX);
    inY=truncate_fixed_to_int(inputY);

    pixelOut[outY][outX]=pixelIn[inY][inX];

    inputX+=incX;
    inputY+=incY;

}  /* end of X loop */
 startX+=incX;
 startY+=incY;
} /* end of Y loop */

To do both at the same time, you can combine the source look-ups. Also,
with the rotate, the numbers can be negative. To rotate around a
different location, set startX/Y.

Keep in mind both pseduo-code snippets above don’t have any clipping.
You’ll probably need that for at least the rotation.

Hope that helps…
-Pat

Guilherme Campos Hazan wrote:
Hi folks,

I’m searching for the fastest possible not-asm code for scale and rotation of a
bitmap (separately).

I already saw the rotozoom, but it is a little complex and big, and the author
states that it is not optimized.

Why i need speed? The target device has 17Mhz.

Many thanks
guich
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl