Rotating arrays/pixels

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

 

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:
[itex]X_{new} = cos(R)X_{old} - sin(R)Y_{old}[/itex]
and
[itex]Y_{new} = cos(R)Y_{old} + sin(R)X_{old}[/itex]

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

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

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):
[itex]X_o = 7.5(1-C-S)[/itex]
[itex]Y_o = 7.5(1-C+S)[/itex]

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

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

 

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]

 

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.

 

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.

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.

 

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.

 

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.

 

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