Rotating 2D Arrays/Pixels w/o FP or Trig - Can It Be Done?

[elusiveshame]

Hey everyone, I'm trying to figure out how to rotate a grid of pixels, but I'm have a tough time. For simplicity sake, let's assume the pixels are in an 2 dimensional array, and each index is in a multiple of 8 (0-7, 0-15, etc).

Now comes the fun parts:
1.) I can't use floating point numbers/precision
2.) I can't use trig functions (no sine or cosine)
3.) I have no clue where to begin

The first 2 restrictions comes from the processor (m68k, these operations aren't supported natively, and I think being 7.5mhz, trig functions would be painfully slow).

Is this possible using just integers? The language is a dialect of BASIC.

Thanks!

 

[.Scott]

Hey everyone, I'm trying to figure out how to rotate a grid of pixels, but I'm have a tough time. For simplicity sake, let's assume the pixels are in an 2 dimensional array, and each index is in a multiple of 8 (0-7, 0-15, etc).

Now comes the fun parts:
1.) I can't use floating point numbers/precision
2.) I can't use trig functions (no sine or cosine)
3.) I have no clue where to begin

The first 2 restrictions comes from the processor (m68k, these operations aren't supported natively, and I think being 7.5mhz, trig functions would be painfully slow).

Is this possible using just integers? The language is a dialect of BASIC.

Thanks!

So each array dimension (not index) is a multiple of 8. For example, an 8x16 array.

You haven't quite supplied enough information to fully attack the problem.
But let's just say you want to rotate a coordinate (3,6) by an angle (40 degrees) around the origin (0,0).
Since you can't use floating point, we will use fixed point. And since you can't do trig, we will use a table lookup.
For 8 bits of precision, cos(40) is 196; that is 196/256. Sine will be 165.
So: (3,6)*(196,165) = (3*196-6*165,3*165+6*196) = (588-990,495+1176) = (-402,1671)
Restoring to integer (if that's what you want): (-402,1671)/256 (with rounding) = -2,7

 

[elusiveshame]

Yes, you're right, each dimension size is in multiples of 8. Basically the rotations won't happen on anything smaller than 8x8, or larger than 32x32, and the rotation point will always be the center of the square.

I figured I would have to use a lookup table, but I'm having a hard time visualizing what the grid is supposed to look like.

I'm also pretty horrible with trig functions, so that definitely hurts my ability to figure this out. Where did the cos(40), and the rest of the numbers you used, come from?

If I remember right, the 40 is the angle of rotation, but from there I'm lost.

 

[.Scott]

1st: If you include a quote in the reply to my post, I will get a little red flag alerting me to your response. ... and I can get back to you quicker.

I was just giving an example of 40 degrees as the rotation angle.
You aren't being clear on your question, so I'm filling in as best I can.

This is really more analytical geometry than it is trig.
I rotated about (0,0), but you wanted to rotate about the center.

So let's say that you have a 16x16 grid with the corner points at 0,0, 0,15, 15,0, and 15,15 and you want to rotate it through an angle R.
Let's walk through it:

First, to rotate a vector about (0,0), you need:
$X_{new} = cos(R)X_{old} - sin(R)Y_{old}$
and
$Y_{new} = cos(R)Y_{old} + sin(R)X_{old}$

Or, if you already know what $X_{new},Y_{new}$ is, but you need to know where it came from, then you would use these equations:
$X_{old} = cos(R)X_{new} + sin(R)Y_{new}$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new}$

But you want to rotate about the center of the square, at coordinates 7.5, 7.5. So we would use this:
$X_{old}-7.5 = cos(R)(X_{new}-7.5) + sin(R)(Y_{new}-7.5)$
$Y_{old}-7.5 = cos(R)(Y_{new}-7.5) - sin(R)(X_{new}-7.5)$
or
$X_{old} = cos(R)X_{new} + sin(R)Y_{new} + 7.5 - 7.5cos(R) - 7.5sin(R)$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new} + 7.5 -7.5cos(R) + 7.5sin(R)$
or
$X_{old} = cos(R)X_{new} + sin(R)Y_{new} + 7.5(1-cos(R)-sin(R))$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new} + 7.5(1-cos(R)+sin(R))$

Then, by table lookup, you would find the sin and cosine of the angle of rotation. In my example, I used 40 degrees, but any rotation angle can be selected.
As I described before, these would be fixed point values with enough places to the right on the binary point to produce the precision you needed.
C = sine-table-lookup(90°-R)
S = sine-table-lookup(R)

Then compute those two offset values (keeping fixed point arithmetic):
$X_o = 7.5(1-C-S)$
$Y_o = 7.5(1-C+S)$

Now loop through all pixels in your destination pixel array $X_{new}=0 to 15$ and $X_{new}=0 to 15$
For each of those 256 coordinate pairs compute the location where the pixel value will come from:
$X_{old} = C\times X_{new} + S\times Y_{new} + X_o$
$Y_{old} = C\times Y_{new} - S\times X_{new} + Y_o$

Finally, copy the pixel data:
If $0\le X_{old}\le 15$ and $0\le Y_{old}\le 15$ then:
$Image_{new}[X_{new},Y_{new}]=Image_{old}[X_{old},Y_{old}]$
else:
$Image_{new}[X_{new},Y_{new}]=$background_color

 

[elusiveshame]

1st: If you include a quote in the reply to my post, I will get a little red flag alerting me to your response. ... and I can get back to you quicker.

I was on a cell phone, which is already a pain to post on :P

You aren't being clear on your question.

I apologize, I really thought it was pretty straight forward.

This is really more analytical geometry than it is trig.
I rotated about (0,0), but you wanted to rotate about the center.

So let's say that you have a 16x16 grid with the corner points at 0,0, 0,15, 15,0, and 15,15 and you want to rotate it through an angle R.
Let's walk through it:

First, to rotate a vector about (0,0), you need:
$X_{new} = cos(R)X_{old} - sin(R)Y_{old}$
and
$Y_{new} = cos(R)Y_{old} + sin(R)X_{old}$

Or, if you already know what $X_{new},Y_{new}$ is, but you need to know where it came from, then you would use these equations:
$X_{old} = cos(R)X_{new} + sin(R)Y_{new}$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new}$

But you want to rotate about the center of the square, at coordinates 7.5, 7.5. So we would use this:
$X_{old}-7.5 = cos(R)(X_{new}-7.5) + sin(R)(Y_{new}-7.5)$
$Y_{old}-7.5 = cos(R)(Y_{new}-7.5) - sin(R)(X_{new}-7.5)$
or
$X_{old} = cos(R)X_{new} + sin(R)Y_{new} + 7.5 - 7.5cos(R) - 7.5sin(R)$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new} + 7.5 -7.5cos(R) + 7.5sin(R)$
or
$X_{old} = cos(R)X_{new} + sin(R)Y_{new} + 7.5(1-cos(R)-sin(R))$
$Y_{old} = cos(R)Y_{new} - sin(R)X_{new} + 7.5(1-cos(R)+sin(R))$

Then, by table lookup, you would find the sin and cosine of the angle of rotation. In my example, I used 40 degrees, but any rotation angle can be selected.
As I described before, these would be fixed point values with enough places to the right on the binary point to produce the precision you needed.
C = sine-table-lookup(90°-R)
S = sine-table-lookup(R)

Then compute those two offset values (keeping fixed point arithmetic):
$X_o = 7.5(1-C-S)$
$Y_o = 7.5(1-C+S)$

Now loop through all pixels in your destination pixel array $X_{new}=0 to 15$ and $X_{new}=0 to 15$
For each of those 256 coordinate pairs compute the location where the pixel value will come from:
$X_{old} = C\times X_{new} + S\times Y_{new} + X_o$
$Y_{old} = C\times Y_{new} - S\times X_{new} + Y_o$

Finally, copy the pixel data:
If $0\le X_{old}\le 15$ and $0\le Y_{old}\le 15$ then:
$Image_{new}[X_{new},Y_{new}]=Image_{old}[X_{old},Y_{old}]$
else:
$Image_{new}[X_{new},Y_{new}]=$background_color

I understand about half of this lol. It's probably simple confusion, but here's how I'm understanding this:

The corner points - got it, just like a typical grid.
R = angle = Radians, right? or is that normal vernacular and its up to me to decide if I want to use radians or degrees? (see, simple questions! haha)

$X_{old}$ and $Y_{old}$ would be the x and y values from my control loops (assuming I'm using FOR...NEXT loops, that is)

C = SineTable(90°-R), the 90° is because that's the phase in comparison from a cosine to a sine Wave

I'm assuming the SineTable() is an array in this example and each degree is the index of the array (or a data label and that would be the offset)

Then from there, fill the frame array with the new data.

There are some issues with the starting point used. I guess I should've said I can only use integers/whole numbers, so 7.5 would end up as 7 instead. Would that mean I'd have to use a group of blocks for the starting point? I've attached an image to help explain what I mean (the red . Or would the answer to that be "then you can't rotate from the exact center, so you'll have to choose the closest point that matches your image"?

Also, what happens when the pixel location is out of bounds? Would that pixel data be lost forever? (I suppose the easy solution is to never draw close to the border/edges)

Thanks!

 

[.Scott]

Based on your responses, it sounds as though I understood the problem correctly.
Xold and Yold are indices into the original (unrotated) image.
Xnew and Ynew are indeces into the new (rotated) image.
So you are looping through Xnew,Ynew and generating Xold and Yold from them.

At the time you are using the 7.5, you are using fixed point arithmetic. So you can multiply by 15 then divide by 2.
Also, you need to convert the fixed point to integer before you use it as an index. So when you calculate Xold and Yold, you will need to do that conversion.

The R stood for "rotation angle".

Set up the table to whatever resolution you want. If you use degrees, then you will need 91 entries for one quadrant of sine. From there you can get the other quadrants and cosine.

Here's an example:
R=30°.
From a table lookup: S=128, C=222 (ie, 128/256 and 222/256)
X0=7.5*(1-C-S)=7.5*(256-222-128)=7.5(-94)=-705
Y0=7.5*(1-C+S)=7.5*(256-222+128)=7.5(162)=1215
Xold= (222Xnew+128Ynew-705) / 256 rounded
Yold= (222Ynew-128Xnew+1215) / 256 rounded

So for any Xnew,Ynew in the rotated image, we can find an Xold,Yold from the original image.
We would loop through all Xnew,Ynew to build the new (rotated) image.
For example:
Xnew,Ynew=(5,8)
Xold= (222(5)+128(8)-705) / 256 = 1429/256 = 6
Yold= (222(8)-128(5)+1215) / 256 = 3631/256 = 14
So, set ImageNew[5,8] = ImageOld[6,14]

 

[Filip Larsen]

Be aware that mapping one (old) source pixel to one (new) destination pixel to make arbitrary rotation or scaling of a raster image will in general produce low quality results as many of the old pixels are effectively never used, and that is even if you scale the image down so that the rotated corners of the source "fit inside" the destination. The information those unused pixels contains is, as you put it, lost forever so if you rotate or scale two or more times in a sequence the resulting image will quickly become completely uncorrelated with the original source raster. For small rasters, like for instance icons, the loss of information when transforming is even worse as they often contain geometric lines or are crafted with sub-sampling techniques to allow them to be perceived in a specific way by human vision and such effects are hard to maintain during arbitrary image transformations.

So, depending on the nature of the source images and the reason you need them rotated, you should not be surprised if you find that simple remapping of pixels will not be adequate.

 

[elusiveshame]

Thanks everyone. I'm going to write up the code and give everything a shot. If I have any more questions, I'll be sure to ask :)

 

[.Scott]

Be aware that mapping one (old) source pixel to one (new) destination pixel to make arbitrary rotation or scaling of a raster image will in general produce low quality results as many of the old pixels are effectively never used, and that is even if you scale the image down so that the rotated corners of the source "fit inside" the destination.

Of course, part of the issue here is giving Elusive bite sized algorithm pieces. But once he gets this working, he can experiment with doing something better than just rounding.

The information those unused pixels contains is, as you put it, lost forever so if you rotate or scale two or more times in a sequence the resulting image will quickly become completely uncorrelated with the original source raster.

That would be a bad idea no matter what form of pixel interpolation and sharpening you used. In all cases, you should only rotate from the original image.

 

[chiro]

Hey elusiveshame.

In addition (and building on) Filip Larsens advice, I'd consider using a combination of blending in the sub texel/pixel (a texel is a texture element while a pixel is a picture element) so that you can smooth the pixels out so that they map to a single axis aligned pixel that best represents what is being displayed.

When you rotate a normal axis aligned set of pixels they won't line up unless you have multiples of 90 degrees.

To fix this you will need to blend the surrounding pixels in some way by factoring in how the newly rotated pixels "cover" the axis aligned blocks that pixels represent.

I would look at interpolation in combination with techniques of blending by the amount of surface area a pixel has (newly rotated one) with respect to what is viewed.

If you don't do this it will look really weird and "un-natural" and the blending of the above should help retain it's information better after a rotation.

 

[elusiveshame]

Chiro - I agree with everything you're saying, but there's a few limitations I have to work with. Being only 7 MHz, the processor is already slow, so figuring out a fast method to load the pixels into video memory is a challenge on its own :)

The other limitation is there's only 15 colors per palette, so using any form of anti aliasing and alpha blending are out of the question for this project.

I need to devise a method to load pixel data into the video display processor at a fast enough fill (fortunately you can load 2 pixels at once, so for an 8x8 tile, it'll take 32 writes). If I can't manage to get it fast enough to rotate on the fly, I'll have to use some memory as a buffer and generate all the frames before the screen is viewable.

 

[chiro]

Can you perform area tests of a rotated pixel relative to an axis aligned one?

What you could try is to see if you can store the proportions of the surface area of a rotated pixel to some axis aligned one and use those proportions to blend.

See if you can derive a formula to take a pixel at some offset and find the contribution it has in the neighboring cells (so you assume a 3x3 tile for each pixel and each tile has a component of contribution to the final pixel).

You can use that to do the blending function and if it ends up being low in memory or low in computation cycles then it can be used for that purpose.

You can write some code to simulate the process for different angular measures and output it or if you have floating point routines you can find the area by forming a triangle and using the ratio of the areas that way.

 

[Baluncore]

An interesting challenge.
How many different angles might you need to rotate through, what resolution 90°, 45°, 30°, 15°, 1° ?
How is that angle specified, as a ratio, 2π * integer / 2ⁿ, or better as a unit vector pair = a + jb