# Need a good quality bitmap rotation algorithm for Android

I am creating a kaleidoscopic effect on an android tablet. I am using the code below to rotate a slice of an image, but as you can see in the image when rotating a bitmap 60 degrees it distorts it quite a lot (red rectangles) – it is smudging the image! I have set dither and anti-alias flags but it does not help much. I think it is just not a very sophisticated bitmap rotation algorithm.

canvas.save();
canvas.rotate(angle, screenW/2, screenH/2);
canvas.drawBitmap(picSlice, screenW/2, screenH/2, pOutput);
canvas.restore();


So I wonder if you can help me find a better way to rotate a bitmap. It does not have to be fast, because I intend to use a high quality rotation only when I want to save the screen to the SD card - I would redraw the screen in memory before saving.

Do you know any comprehensible or replicable algorithm for bitmap rotation that I could programme or use as a library? Or any other suggestion?

EDIT: The answers below made me think if Android OS had bilinear or bicubic interpolation option and after some search I found that it does have its own version of it called FilterBitmap. After applying it to my paint

pOutput.setFilterBitmap(true);


I get much better result

I have seen term "rotation by shearing" mentioned in several times. I have not tried it myself but it doesn't look impossible to implement

http://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/rotation_by_shearing.html

http://www.codeproject.com/KB/graphics/rotatebyshear.aspx

• Thank you for this, learing about rotation issues helped me find android's own bitmap interpolation. – Lumis Apr 25 '11 at 9:55

Instead of applying a better rotation algorithm you could improve the image quality by using multisampling instead. That is you make everything say four times bigger, then reduce the final result back down to the required size by averaging pixels.

This will obviously increase your memory requirements, but it should be simple to implement, and it works with transforms other than rotation. You should also be able to get the graphics hardware to do it for you.

I don't know if this will help anyone, but I use this algorithm to pre-rotate all my sprites while I'm loading my resources. In essence I create one sprite, and then the code caches the rotated versions of the sprites for use in the game.

You could also use this to rotate your larger bitmap, but I don't know if this will give you better results or not. It's easy enough to use however, so give it a try.

private Bitmap rotate(Bitmap src, int Degrees) {
double width = src.getWidth();
double height = src.getHeight();

double sine = MathEx.sind(Degrees);
double cosine = MathEx.cosd(Degrees);

double px1 = width * cosine;
double px2 = width * cosine - height * sine;
double px3 = -height * sine;
double py1 = height * cosine;
double py2 = height * cosine + width * sine;
double py3 = width * sine;

int minx = (int) Math.min(0, Math.min(px1, Math.min(px2, px3)));
int miny = (int) Math.min(0, Math.min(py1, Math.min(py2, py3)));
int maxx = (int) Math.max(px1, Math.max(px2, px3));
int maxy = (int) Math.max(py1, Math.max(py2, py3));

int dw = Math.abs(maxx) - minx;
int dh = Math.abs(maxy) - miny;

int w = 2;
int h = 2;
while (w < dw)
w *= 2;

while (h < dh)
h *= 2;

int xoff = 0;
int yoff = 0;

if (w > dw)
xoff = (int)((w - dw) / 2.0F + 0.5F);
if (h > dh)
yoff = (int)((h - dh) / 2.0F + 0.5F);

Bitmap map = Bitmap.createBitmap(w, h, Config.ARGB_8888);
map.eraseColor(0x00000000);

for (int x = 0; x < dw; x++) {
for (int y = 0; y < dh; y++) {
int sx = (int) ((x + minx) * cosine + (y + miny) * sine);
int sy = (int) ((y + miny) * cosine - (x + minx) * sine);

if (sx < 0 || sx >= width || sy < 0 || sy >= height)
continue;

map.setPixel(x + xoff, y + yoff, src.getPixel(sx, sy));
}
}

return map;
}


This looks similar to when you have a vector model and you rotate it, and rotate the result, and rotate the result, etc. Eventually the model will be noticeably distorted due to rounding. The solution is have a read-only source and always transform from that. Not sure how that applies to your android kaleidoscope effect (it looks great to me), but I hope that's helpful.

• I am of course using the same image 'picSlice' which I draw 6 times, it is canvas that rotates. As you can see 90' angles work fine but not 60'. Yes it looks good, bacause I am using a pretty fractal image for the effect ;) – Lumis Apr 24 '11 at 23:12
• Yes, so you're drawing the image at 0', rotating the canvas 60', and repeating that 6 times? So the first image you drew is rotated 5 times? If that's right, that image will be more distorted than the others. 90' rotation is lossless because you're essentially just swapping x and y of each pixel. If you can (I don't know the Android's API - I have an Android, but haven't started developing for it yet), you need to draw the image at 0', then at 60', then at 120', and so on. Have you tried specifying the rotation using createBitmap instead of doing it to the canvas? – Lee Kowalkowski Apr 26 '11 at 14:54
• I don't think cavas is really rotating. The only thing rotated is the matrix of the bitmap at the moment of drawing. You can see that all distorsions are the same in the first image. createBitmap would do the same thing - translate matrix. I am using canvas rotate because it is fast it can do 60fps. I have found a solution which is in the edit of my question. The trick is in interpolation. Anyway, thanks for your comments. – Lumis Apr 26 '11 at 17:24
• In which case applying the matrix on the canvas itself would be exactly the same thing (except more efficient as new bitmaps are not required). Glad you found your solution! – Lee Kowalkowski Apr 26 '11 at 19:20
• Hi you can see the result, I have just published the app as Kaleido-Magic on Android market. market.android.com/… – Lumis May 29 '11 at 9:26