Programming question: image rotation

[Munch]

Hi guys,

I did a search but didn't spot anything on this topic. Probably because it's confusing and very difficult (I think it is anyway). Nevertheless it's a critical problem for my work: how do you rotate an image by an arbitrary angle (i.e. not a multiple of 90 degrees)?

In a lot of flash games it seems to be a common thing to have an image rotate 'freely', but I just can't figure out how it works. How do you map a pixel to a location that doesn't necessarily correspond to a nice coordinate point?

If anyone in the know can elaborate with an explanation or even pseudocode, that would be awesome!

Thanks

PS: coding in java or c

 

[warpus]

just find a library that has a 'rotate image' function

you do not really want to code something like that from scratch..
well, you could.. but there's libraries out there, so unless you need the exercise..

 

[GVBN]

Dunno about C or Java, in Python it's pygame.transform.rotate. Quick Google search gives this

 

[Genocidicbunny]

In java you can do AffineTransform.

 

[mdwh]

If you really need to do it by hand yourself, you should find info by googling something like: rotate bitmap (e.g., I found http://www.leunen.com/cbuilder/rotbmp.html ).

One way to do it is basically to calculate the inverse rotation transform to map from the destination pixel to the source pixel, that way you don't have the problem of leaving holes. A better way might be to have some anti-aliasing, by sampling multiple source pixels and using a weighted average, where the destination pixel doesn't map to integer coordinates in the source image.

I'm sure there must be some libraries that do this, but I don't know any off hand. If you only need it for rendering, then DirectX or OpenGL will do it for you, complete with anti-aliasing and hardware acceleration (although that might be overkill, depending on your needs).

In java you can do AffineTransform.

Well you could use that for the transformation itself, but that's the easy part - would it help with the various problems associated with transforming an image?

 

[Munch]

Unfortunately I do need to know how the algorithm works, and build a method from scratch. I'm hoping that 2D arbitrary rotation will be easy enough (as it seems to be everywhere e.g. flash games), so that I can adapt it for 3D rotation. Ultimately I need to write code that can rotate very large 3D grids so yeah, I'm trying to learn it from the ground up.

If you really need to do it by hand yourself, you should find info by googling something like: rotate bitmap (e.g., I found http://www.leunen.com/cbuilder/rotbmp.html ).

One way to do it is basically to calculate the inverse rotation transform to map from the destination pixel to the source pixel, that way you don't have the problem of leaving holes. A better way might be to have some anti-aliasing, by sampling multiple source pixels and using a weighted average, where the destination pixel doesn't map to integer coordinates in the source image.

Thanks. I've been googling relentlessly and found this page which includes some brief stuff about anti-aliasing. I think I'll have to do AA, even if it is slower.

 

[mdwh]

Unfortunately I do need to know how the algorithm works, and build a method from scratch. I'm hoping that 2D arbitrary rotation will be easy enough (as it seems to be everywhere e.g. flash games), so that I can adapt it for 3D rotation. Ultimately I need to write code that can rotate very large 3D grids so yeah, I'm trying to learn it from the ground up.

3D should be able to be done the same way, just that your transformation will be different.

Another way (possibly faster, but harder to implement) to approach this is to treat it as a special case of software 3D rendering. Here you work out how to draw the transformed rectangle exactly, and the original pixel coordinates are calculated by interpolating values (the idea is that interpolating coordinates is quicker than performing a rotation/transformation for every single pixel). There should be articles out there somewhere on the algorithm...

Do you just need this for rendering, or do you need to access/save the pixel data?

 

[mdwh]

Just to add to this - even if you need to do 3D rotation, perhaps there might be some library out there that would do this (as long as it can apply a general linear transformation to an image, that should be what you want)? Or is there some other reason why you need to do it by hand?

 

[Ultraworld]

They use linear algebra for this. A pixel is a vector v which is multiplied by the transformation matrix A

so you get v'= Av, where v' is the new rotated pixel.

The transformation matrix looks like

| cos t    -sin t|
| sin t     cos t|

t is the angle

in 3D this gets more complicated but stilll doable

 

[Chieftess]

I think I remember something like this from 15 years ago.... but it was either in Pascal or Assembler. (I'm guessing the later)

I think the best approach would be to look at each row of pixels as a line. Draw that line from point A to point B, then for each row, you would offset the y by however many rows you're on.

i.e., this is your line:

***#*###***#*###*

It's going from let's say, 0,0,16,0 (that's startX, startY, endX, endY). Now, you want to rotate that to 0,0,16,1 (maybe it's a 1% rotation). Let's assume that the point of rotation is at 0,0.

***#*###*
__________**#*###*

Excluding the underline (only for formatting), this line is now rotated.

So...

***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*

Becomes

***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
__________**#*###*


Now, how they take a huge 256x256 image, and rotate it so smoothly at 5,000 rpm (maybe adding animation for good measure) is beyond me. (They probably use assembly programming)

 

[Munch]

Thanks everyone for your input, I think I'll use this part of the forum a lot more!

Another way (possibly faster, but harder to implement) to approach this is to treat it as a special case of software 3D rendering... There should be articles out there somewhere on the algorithm...

Do you just need this for rendering, or do you need to access/save the pixel data?

I'm not sure I understand what you mean, but I will look it up. If you have a link that would be even more useful. It sounds like the kind of thing I need anyway! Yes, I need to be able to save the voxel data.

Just to add to this - even if you need to do 3D rotation, perhaps there might be some library out there that would do this (as long as it can apply a general linear transformation to an image, that should be what you want)? Or is there some other reason why you need to do it by hand?

Without going into too much detail I am trying to write a program to find and create an optimal chemically meaningful 3D alignment between small molecules; it's the next part of my research project and I've been putting it off for a long time because rotation has been a serious headache for me. Initially I though the actual rotation would simply work like Ultraworld says below, using simple trigonometry...

They use linear algebra for this. A pixel is a vector v which is multiplied by the transformation matrix A

so you get v'= Av, where v' is the new rotated pixel.

The transformation matrix looks like

| cos t    -sin t|
| sin t     cos t|

t is the angle

in 3D this gets more complicated but stilll doable

... but the problem with this is that the values of cos and sin t are not integer values, and so don't correlate with pixel (voxel) locations.

I've read about two 2D methods that I think I will try: "rotation by three shears", and "rotation by area mapping". The former is a quick method because it only performs shears (of course), but the result is an image with 'jagged edges'. The latter is more like the kind of thing I want, with an 'anti-aliasing' feel. I think this might be similar to the software rendering mentioned above but maybe I'm wrong.

I think I remember something like this from 15 years ago.... but it was either in Pascal or Assembler. (I'm guessing the later)

I think the best approach would be to look at each row of pixels as a line. Draw that line from point A to point B, then for each row, you would offset the y by however many rows you're on.

i.e., this is your line:

***#*###***#*###*

It's going from let's say, 0,0,16,0 (that's startX, startY, endX, endY). Now, you want to rotate that to 0,0,16,1 (maybe it's a 1% rotation). Let's assume that the point of rotation is at 0,0.

***#*###*
__________**#*###*

Excluding the underline (only for formatting), this line is now rotated.

So...

***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*

Becomes

***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
***#*###***#*###*
__________**#*###*


Now, how they take a huge 256x256 image, and rotate it so smoothly at 5,000 rpm (maybe adding animation for good measure) is beyond me. (They probably use assembly programming)

This is similar to the rapid "rotation by three shears" I have read about. The last image you drew is basically a small vertical shear; if this is followed by a small horizontal shear (and for large angles a third, correcting shear) then you get something like:

_____#____
___####___
__######__
_########_
#########_
_#########
_########_
__######__
___####___
____#_____

Which is a rotated square image but with jagged edges. At this point I don't know whether I am looking for speed or accuracy in my method, as I don't know quite how I'm going to determine what an optimum chemical alignment is using grid values. Nevertheless, I do need to code a rotation method from scratch!

 

[mdwh]

I'm not sure I understand what you mean, but I will look it up. If you have a link that would be even more useful. It sounds like the kind of thing I need anyway! Yes, I need to be able to save the voxel data.

Ah, forget the 3D software rendering method - I thought you still wanted to project it onto a 2D screen, rather than doing rotations in 3D space.

It should still be possible with a 3D version of the first method I said:

One way to do it is basically to calculate the inverse rotation transform to map from the destination pixel to the source pixel, that way you don't have the problem of leaving holes. A better way might be to have some anti-aliasing, by sampling multiple source pixels and using a weighted average, where the destination pixel doesn't map to integer coordinates in the source image.

As also described at http://www.leunen.com/cbuilder/rotbmp.html , for example.

... but the problem with this is that the values of cos and sin t are not integer values, and so don't correlate with pixel (voxel) locations.

The key point is that rather than transforming your source pixel locations to a destination, you do it in reverse: for each pixel in your destination, do the inverse transformation to find the location in the source.

As you say, in general this won't be an integer. For a simple version, you'll still get something okay just by rounding. For a more complex version, you can sample adjacent values in the source data, and interpolate between them (basically doing anti-aliasing).

For 3D, you just have a 3D set of "pixels" instead of a 2D set.

There might be quicker methods however.

PS - as great as this forum is, there might be ones with more programmers on (one that might be helpful is http://gamedev.net - although your problem isn't specifically games, it obviously crosses over with 3D graphics and 3D maths).