Archived

This topic is now archived and is closed to further replies.

Ruval

Modified line algorithm for bitmap rotation

Recommended Posts

Hi, I''m currently working on upgrading my existing 2D engine to handle stuff like rotated sprites, scaling etc... My rotation function works like this: 1. Clear destination surface, size of the source diagonal in each direction to rotate the bitmap into. 2. Calculate coordinates of source rectangle aroud the origin 3. Build a combined 2D rotation/translation matrix to rotate the points about the origin the translate then to the centre of the surface. 4. Multiply 3 corners by the matrix, do subtractions for the 4th 5. Calculate endpoints of each row using Bresenhams line algorithm 6. Draw each source row between endpoints, again using Bresenhams The problem is that since Bresenhams plots one pixel for each step along the major axis, in the worst case it will plot half the number of pixels needed to display a row of the image, leading to a funky but unwanted roto-zooming effect. So what I was wondering is... does anyone know of a fast (but still fairly pretty) way of drawing the rotated image rows? Thanks Jim

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I was going to do something similar, but never got round to implementing it. Forgive me if the following makes no snse, I''m a newbie:

To solve the problem of one row in the rotated rectangle having a differnet number of pixels than one row in the source rectangle, I was thinking of using an adapted version of Bresenham''s algorithm to englarge each line. Rather than using it to increase y every few times x is increased, use it to calculate when you should advance along the source row and when you should advance along the destination row. You''d then need another copy of the algorithm within this to actually draw the rotated row.

Would that work?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
draw destination row,
like everybody in 2d and 3d does

Share this post


Link to post
Share on other sites
Well I got something that works, using linear interpolation
with fixed point numbers so its all still integer.
Like texture coordinates, kind of.

I also have to draw an pixel every time the minor axis is changed otherwise there''ll be gaps.

Thanks anyway.

Share this post


Link to post
Share on other sites
Just rotate all the pixels. The angle is constant for the entire rotation so the sin() and cos() is constant. As you process a row you are just adding one to x and y is remaining constant. So you can replace the multiplications with addition. Integers will create an unacceptable rounding error, but fixed point should do fine. Basically just shift the sin(), cos() and x/y values to the left 16 places. Since you are adding the implied decimal place has to be in the same place. You can round to the nearest interger by adding 2^15 and shifting the value right 16 places. It is just like adding 1.1 to 1.1 by shifting the decimal right one place, adding 11 to 11 to get 22 and shifting the decimal left one place to get 2.2 except it is a binary decimal point. You will get a 30% overplot, i.e. mapping two pixels to the same destination, in the worst case, but eliminating it will most likely cost you everything you might save.

If the image doesn''t look good then you can first try averaging the overplots. If it still doesn''t look good then you are going to have to reverse direction and interpolate the color. A pixel in the destination actually maps to a location between two columns and two rows in the source in most cases. You have to do a weighted average of the four pixels at the upper left, upper right, lower left and lower right of where it actually mapped to. You can assign each of the rows and columns a weight based upon how far between them the actual point is. Then you take the four pixels, multiply each by their row and column weight and then sum them. Needless to say this adds a great deal more work though perhaps not as much as you might think once optimized. So unless there is really a serious problem with the rotated sprite then I doubt it is worth it.

Share this post


Link to post
Share on other sites